锐客网

  1. 首页 > 睿知 > it技术 > >

leetcode刷题|LeetCode 第63场双周赛复盘

leetcode算法PythonLeetCode刷题

LeetCode 第63场双周赛复盘 背景 2022秋招以0 offer基本结束，没有收到很满意的offer，基本上大厂全挂。对自己这样一个结果并不满意，为了能在春招上收获到满意的offer，于是决定继续参加周赛，提高自己的算法能力。
结果 前面二道过了，第二题wa了9次。全球排名4603 / 9524，全国排名1499/2828，妥妥的中位数。下次的目标是进前50%
复盘 第一题[简单贪心]：
传送门
题目描述： 一个房间里有 n 个座位和 n 名学生，房间用一个数轴表示。给你一个长度为 n 的数组 seats ，其中 seats[i] 是第 i 个座位的位置。同时给你一个长度为 n 的数组 students ，其中 students[j] 是第 j 位学生的位置。
你可以执行以下操作任意次：

  • 增加或者减少第 i 位学生的位置，每次变化量为 1 （也就是将第 i 位学生从位置 x 移动到 x + 1 或者 x - 1）
请你返回使所有学生都有座位坐的 最少移动次数 ，并确保没有两位学生的座位相同。
请注意，初始时有可能有多个座位或者多位学生在 同一 位置。
示例1 ：
输入：seats = [3,1,5], students = [2,7,4]
输出：4
解释：学生移动方式如下：
  • 第一位学生从位置 2 移动到位置 1 ，移动 1 次。
  • 第二位学生从位置 7 移动到位置 5 ，移动 2 次。
  • 第三位学生从位置 4 移动到位置 3 ，移动 1 次。
    总共 1 + 2 + 1 = 4 次移动。
题目解答： 翻译翻译就是，给这些懒得多走路的学生找位置坐，使得他们走的路是最少的。
当时竞赛的解答： 我的想法非常朴素，是给每个懒学生找离他们最近的位子坐。
主要是靠经验，因为周赛一般来说第一题都很简单，通常就是贪心题。比较常见的贪心做法就是先排序。
class Solution { public int minMovesToSeat(int[] seats, int[] students) { Arrays.sort(seats); Arrays.sort(students); int n = seats.length; int res = 0; for(int i=0; i

贪心题的证明[想要提高必须要吃的苦] 证明上述的贪心做法是正确的,别看写的多，其实就是去绝对值
  • n=1时，只能有去做那个位置
  • n=2时，设两个座位位置分别是a,b，满足a
    • 方案一，按照大小关系一一对应，即cost1=|a-c|+|b-d|
    • 方案二，不按照方案一，那么选择的代价cost2=|a-d|+|b-c|;
    要证明方案一的代价要比方案二的代价小，即cost1 要求绝对值，就得判断大小关系，题设有a 情况一：a∣ a ? c ∣ + ∣ b ? d ∣ ? ( ∣ a ? d ∣ + ∣ b ? c ∣ ) = c ? a + d ? b ? ( d ? a + c ? b ) |a-c|+|b-d|-(|a-d|+|b-c|)=c-a+d-b-(d-a+c-b) ∣a?c∣+∣b?d∣?(∣a?d∣+∣b?c∣)=c?a+d?b?(d?a+c?b)
    = c ? a + d ? b ? d + a ? b ? c = 0 =c-a+d-b-d+a-b-c=0 =c?a+d?b?d+a?b?c=0
    情况二：c
∣ a ? c ∣ + ∣ b ? d ∣ ? ( ∣ a ? d ∣ + ∣ b ? c ∣ ) = 0 |a-c|+|b-d|-(|a-d|+|b-c|)=0 ∣a?c∣+∣b?d∣?(∣a?d∣+∣b?c∣)=0
? 情况三：a∣ a ? c ∣ + ∣ b ? d ∣ ? ( ∣ a ? d ∣ + ∣ b ? c ∣ ) = 2 ( c ? b ) < 0 |a-c|+|b-d|-(|a-d|+|b-c|)=2(c-b)<0 ∣a?c∣+∣b?d∣?(∣a?d∣+∣b?c∣)=2(c?b)<0
? 情况四：c∣ a ? c ∣ + ∣ b ? d ∣ ? ( ∣ a ? d ∣ + ∣ b ? c ∣ ) = 2 ( c ? d ) < 0 |a-c|+|b-d|-(|a-d|+|b-c|)=2(c-d)<0 ∣a?c∣+∣b?d∣?(∣a?d∣+∣b?c∣)=2(c?d)<0
? 情况五：a∣ a ? c ∣ + ∣ b ? d ∣ ? ( ∣ a ? d ∣ + ∣ b ? c ∣ ) = c ? a + b ? d ? ( d ? a + b ? c ) = 2 ( c ? d ) < 0 |a-c|+|b-d|-(|a-d|+|b-c|)=c-a+b-d-(d-a+b-c)=2(c-d)<0 ∣a?c∣+∣b?d∣?(∣a?d∣+∣b?c∣)=c?a+b?d?(d?a+b?c)=2(c?d)<0
  • n>2时，用数学归纳法证明
第二题Alice和Bob
传送门
题目描述 总共有 n 个颜色片段排成一列，每个颜色片段要么是 ‘A’ 要么是 ‘B’ 。给你一个长度为 n 的字符串 colors ，其中 colors[i] 表示第 i 个颜色片段的颜色。
Alice 和 Bob 在玩一个游戏，他们 轮流 从这个字符串中删除颜色。Alice 先手 。
如果一个颜色片段为 ‘A’ 且 相邻两个颜色 都是颜色 ‘A’ ，那么 Alice 可以删除该颜色片段。Alice 不可以 删除任何颜色 ‘B’ 片段。
如果一个颜色片段为 ‘B’ 且 相邻两个颜色 都是颜色 ‘B’ ，那么 Bob 可以删除该颜色片段。Bob 不可以 删除任何颜色 ‘A’ 片段。
Alice 和 Bob 不能 从字符串两端删除颜色片段。
如果其中一人无法继续操作，则该玩家 输 掉游戏且另一玩家 获胜 。
假设 Alice 和 Bob 都采用最优策略，如果 Alice 获胜，请返回 true，否则 Bob 获胜，返回 false。
示例 1：
输入：colors = “AAABABB”
输出：true
解释：
AAABABB -> AABABB
Alice 先操作。
她删除从左数第二个 ‘A’ ，这也是唯一一个相邻颜色片段都是 ‘A’ 的 ‘A’ 。
现在轮到 Bob 操作。
Bob 无法执行任何操作，因为没有相邻位置都是 ‘B’ 的颜色片段 ‘B’ 。
因此，Alice 获胜，返回 true 。
题目解答 就是找出两个人可以操作的次数，因为alice先开始，所以如果alice的操作次数大于bob的操作次数+1的话，那么alice就赢了
wa了9次，才想出的，可以看出写出的代码也很烂。看别人的代码也有用字符串写的
class Solution { public boolean winnerOfGame(String colors) { int n = colors.length(); int prevA = -1; int cnt1 = 0; int cnt2 = 0; int lenA = 0; int prevB = -1; int lenB = 0; for(int i=0; i=3){ cnt2+=lenB-2; } lenB=0; lenA = Math.max(lenA,i-prevA); //统计当前连续的A }else{ prevA = i; if(lenA>=3){ cnt1+=lenA-2; //如果A的连续断了就将这一段可以操作的次数加上去 } lenA = 0; lenB = Math.max(lenB,i-prevB); } } //统计末尾的情况 if(lenA>=3){ cnt1+=lenA-2; } if(lenB>=3){ cnt2+=lenB-2; } if(cnt1>=cnt2+1){ return true; }else{ return false; } } }

字符串分割写法
参考链接
public static boolean winnerOfGame(String colors) { String A[] = colors.split("B"); //比如"AAABABB"，划分出来的就是[AAA,A] String B[] = colors.split("A"); //划分出来的就是[ , , ,B,BB] int cnt1 = 0, cnt2 = 0; for (String str : A) { if (str.length() > 2) { cnt1 += (str.length() - 2); //只有大于三才能操作 } } for (String str : B) { if (str.length() > 2) { cnt2 += (str.length() - 2); } } if (cnt1 == 0) return false; if (cnt1 <= cnt2) return false; else return true; }

第三题[无向图的最短路径]
传送门
题目描述： 给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示服务器 ui 和 vi 之间有一条信息线路，在 一秒 内它们之间可以传输 任意 数目的信息。再给你一个长度为 n 且下标从 0 开始的整数数组 patience 。
题目保证所有服务器都是 相通 的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。
编号为 0 的服务器是 主 服务器，其他服务器为 数据 服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按 最优 线路传输，也就是说每个信息都会以 最少时间 到达主服务器。主服务器会处理 所有 新到达的信息并 立即 按照每条信息来时的路线 反方向 发送回复信息。
在 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，每 一秒最 开始 时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：
如果还没收到任何回复信息，那么该服务器会周期性 重发 信息。数据服务器 i 每 patience[i] 秒都会重发一条信息，也就是说，数据服务器 i 在上一次发送信息给主服务器后的 patience[i] 秒 后 会重发一条信息给主服务器。
否则，该数据服务器 不会重发 信息。
当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲 状态。
【leetcode刷题|LeetCode 第63场双周赛复盘】请返回计算机网络变为 空闲 状态的 最早秒数 。
题目解答： 图这一块还是老样子，老是做不出来
下面是参考借鉴的大佬思路
T i T_i Ti?表示 i i i号服务器完成所有传输需要的最短时间, d i s t i dist_i disti?表示 i i i号服务器与0号服务器（也叫主服务器）的距离， p a t i e n c e i patience_i patiencei?表示 i i i号服务器对应的重发等待时间
从i号服务器发送到主服务器，再从主服务器传回给i号服务器
T i = 2 ? d i s t i + [ ( 2 ? d i s t i ? 1 ) / p a t i e n c e i ] ? p a t i e n c e i T_i=2*dist_i+[(2*dist_i-1)/patience_i]*patience_i Ti?=2?disti?+[(2?disti??1)/patiencei?]?patiencei?
public int networkBecomesIdle(int[][] edges, int[] patience) { int n = patience.length; int res = 0; //建图 HashMap> adj = new HashMap<>(); for(int[] e:edges){ int x = e[0], y = e[1]; adj.putIfAbsent(x,new ArrayList<>()); adj.putIfAbsent(y,new ArrayList<>()); //无向图建两次 adj.get(x).add(y); adj.get(y).add(x); } //bfs求最短路径 int INF = (int)1e9; int[] dmin = new int[n]; Arrays.fill(dmin,INF); Queue q = new LinkedList<>(); q.offer(0); dmin[0] = 0; while (!q.isEmpty()){ int x = q.poll(); if (x!=0){ int time = dmin[x]; int cur_cost = 2*time+(2*time-1)/patience[x]*patience[x]; res = Math.max(res,cur_cost); } for (int y : adj.getOrDefault(x, new ArrayList<>())) { if(dmin[x]+1

这个代码完全可以总结出求最小路径的模版
//建图 HashMap> adj = new HashMap<>(); for(int[] e:edges){ int x = e[0], y = e[1]; adj.putIfAbsent(x,new ArrayList<>()); adj.putIfAbsent(y,new ArrayList<>()); //无向图建两次 adj.get(x).add(y); adj.get(y).add(x); } //bfs求最短路径 int INF = (int)1e9; int[] dmin = new int[n]; Arrays.fill(dmin,INF); Queue q = new LinkedList<>(); q.offer(0); dmin[0] = 0; while (!q.isEmpty()){ int x = q.poll(); if (x!=0){ int time = dmin[x]; } for (int y : adj.getOrDefault(x, new ArrayList<>())) { if(dmin[x]+1

第四题
传送门
题目描述： 给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k ，请你返回第 k （从 1 开始编号）小的 nums1[i] * nums2[j] 的乘积，其中 0 <= i < nums1.length 且 0 <= j < nums2.length 。
示例1:
输入：nums1 = [2,5], nums2 = [3,4], k = 2
输出：8
解释：第 2 小的乘积计算如下：
  • nums1[0] * nums2[0] = 2 * 3 = 6
  • nums1[0] * nums2[1] = 2 * 4 = 8
    第 2 小的乘积为 8 。
数据范围：
1 <= nums1.length, nums2.length <= 5 * 10^4
-10^5 <= nums1[i], nums2[j] <= 10^5
1 <= k <= nums1.length * nums2.length
nums1 和 nums2 都是从小到大排好序的。
题目解答： 从数据范围上去看，O(n^2)的算法肯定是过不了的
于是思考时间复杂度低的算法，二分
二分中套二分
public class Solution { int[] A; int[] B; long k; public void mswap(int[] a,int[] b){ int[] c = a; a = b; b = c; } public long kthSmallestProduct(int[] nums1, int[] nums2, long k) { A=nums1; B=nums2; this.k=k; long l = (long)(-1e10); long r = (long)(1e10); //二分找一个数mid 使得小于mid的数正好有k个 while (l>1; if (check(mid)){ r=mid; }else { l=mid+1; } } return l; }private boolean check(long uplimit) { long res = 0; if (A.length > B.length) { mswap(A, B); } //A代表的是长度小的数组 //B代表的是长度大的数组 int n1 = A.length; //两个数组都是从小到大排的 int n2 = B.length; for (int x : A) {//对A数组中的每一个数分奇偶来判断 if (x < 0)//如果这个数是负数，那么它乘以B数组里最大的数就是最小的 { //----如果最小的都大了，就过0 if ((long)x * B[n2 - 1] > uplimit) { continue; } else { //----二分最左 int l = 0; int r = n2 - 1; while (l < r) { int mid = l + r >> 1; if ((long)x * B[mid] <= uplimit) r = mid; else l = mid + 1; } //由于x是负数，x乘以l的右边的数都小于uplimit， res += (n2 - l); } } else if (x > 0) { //----如果最小的都大了，就过 if ((long)x * B[0] > uplimit) { continue; } else { //----二分最右 int l = 0; int r = n2 - 1; while (l < r) { int mid = l + r + 1 >> 1; if ((long)x * B[mid] <= uplimit) l = mid; else r = mid - 1; } //由于x是负数，x乘以l的左边的数都小于uplimit， res += (l + 1); } } else { if (uplimit >= 0) { res += n2; } }} return res >= k ? true : false; } }

    推荐阅读


    上一篇：《Java入门100练》|【第26天】给定 n 个元素的升序数组nums，求实现一个函数在nums中寻找target的下标 | 初识二分查找

    下一篇：leetcode周赛记录|第一次打leetcode周赛复盘——第286场周赛