LeetCode 周赛笔记 —— 2022年8月 第一周

LeetCode 周赛笔记 —— 2022年8月 第一周

文章目录

​​84双周赛​​

​​2363.合并相似物品​​​​6142. 统计坏数对的数目​​​​6174.任务调度器II​​​​6144.将数组排序的最少替换次数​​

​​305周赛​​

​​2637.算数三元组的数目​​​​2368.受限条件下可到达节点的数目​​​​2369.检查数组是否存在有效划分​​​​2370.最长理想子序列​​

​​总结​​

84双周赛

2363.合并相似物品

签到题，使用简单的哈希表进行合并即可，注意最后需要排序。

/**** 9ms**/class Solution { public List> mergeSimilarItems(int[][] items1, int[][] items2) { Map map = new HashMap<>(); for (int[] i : items1) map.put(i[0], i[1]); for (int[] i : items2) map.put(i[0], map.getOrDefault(i[0], 0) + i[1]); List keyList = new ArrayList<>(map.keySet()); Collections.sort(keyList); List> ans = new ArrayList<>(); for (int key : keyList) ans.add(Arrays.asList(key, map.get(key))); return ans; }}

当然，也可以直接使用TreeMap，会自动根据key进行排序

/*** 11ms**/class Solution { public List> mergeSimilarItems(int[][] items1, int[][] items2) { Map map = new TreeMap<>(); for (int[] i : items1) map.put(i[0], i[1]); for (int[] i : items2) map.put(i[0], map.getOrDefault(i[0], 0) + i[1]); List> ans = new ArrayList<>(); for (int key : map.keySet()) ans.add(Arrays.asList(key, map.get(key))); return ans; }}

周赛当晚我是手写了排序

/*** 3ms**/class Solution { public List> mergeSimilarItems(int[][] items1, int[][] items2) { quickSort(items1, 0, items1.length - 1); quickSort(items2, 0, items2.length - 1); List> ans = new ArrayList<>(); int n1 = items1.length, n2 = items2.length; int i = 0, j = 0; while (i < n1 && j < n2) { if (items1[i][0] < items2[j][0]) { ans.add(Arrays.asList(items1[i][0], items1[i][1])); i++; } else if (items1[i][0] > items2[j][0]) { ans.add(Arrays.asList(items2[j][0], items2[j][1])); j++; } else { ans.add(Arrays.asList(items1[i][0], items1[i][1] + items2[j][1])); i++; j++; } } while (i < n1) { ans.add(Arrays.asList(items1[i][0], items1[i][1])); i++; } while (j < n2) { ans.add(Arrays.asList(items2[j][0], items2[j][1])); j++; } return ans; } private void quickSort(int[][] arr, int l, int r) { if (l >= r) return; int x = arr[l + r >>1][0]; int i = l - 1, j = r + 1; while (i < j) { do i++; while (arr[i][0] < x); do j--; while (arr[j][0] > x); if (i < j) { int[] t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } quickSort(arr, l, j); quickSort(arr, j + 1, r); }}

6142. 统计坏数对的数目

给定一个数组，若​​i < j​​​并且​​nums[j] - nums[i] != j - i​​​，则称​​(i, j)​​为一个坏数对，求坏数对的数目。

将上面的式子进行一下变形，将等号两边进行一下交换，得到 ​​nums[j] - j != nums[i] - i ​​​。则对于每个位置​​i​​​，我们可以求出一个数常数​​c(i) = nums[i] - i​​​，若对每个位置，求出的常数​​c​​​都是一样的，则整个数组的坏数对数目为​​0​​​。比如数组​​[1,2,3,4,5]​​​。每个位置的​​c(i) = 1​​​。容易得出结论，对于那些​​c​​​相等的位置​​i​​，这些位置之间全都不是坏数对。或者说，对于坏数对​​(i,j)​​​ 一定有​​c(i) != c(j)​​​。那么我们可以遍历一次，对每个位置求出其​​c(i)​​，进而算出坏数对的数目。

/*** 48ms**/class Solution { public long countBadPairs(int[] nums) { Map map = new HashMap<>(); int n = nums.length; // 进行统计计数 for (int i = 0; i < n; i++) { int c = nums[i] - i; map.put(c, map.getOrDefault(c, 0) + 1); } // 采用累加法计算 long ans = 0; long remainNum = n; for (int key : map.keySet()) { ans += (remainNum - map.get(key)) * map.get(key); remainNum -= map.get(key); } return ans; }}

也可以采用排除法，先算出所有数对的总数，然后依次减去不是坏数对的数量

/*** 39ms**/class Solution { public long countBadPairs(int[] nums) { Map map = new HashMap<>(); long n = nums.length; long total = n * (n - 1) / 2; // 全部数对的数量 // 进行统计计数 for (int i = 0; i < n; i++) { // 这个数与前面的数是否能形成好数对 int c = nums[i] - i; total -= map.getOrDefault(c, 0); map.put(c, map.getOrDefault(c, 0) + 1); } return total; }}

周赛当晚这道题没做出来。/(ㄒoㄒ)/，一直没想到将等式左右两边进行交换，一直在想用归并排序求逆序对的方法= =。

6174.任务调度器II

简单模拟即可，用一个Map保存某一类型前一次出现的天数即可。

/*** 39ms**/class Solution { public long taskSchedulerII(int[] tasks, int space) { long curDay = 0; // 最近一次完成的任务类型以及天数 Map map = new HashMap<>(); for (int i = 0; i < tasks.length; i++) { curDay++; if (!map.containsKey(tasks[i])) { // 第一次出现该任务 map.put(tasks[i], curDay); } else { // 出现重复类型的任务, 获取上一次做这个类型工作的日期 long doneDay = map.get(tasks[i]); long delta = curDay - doneDay - 1; if (delta >= space) map.put(tasks[i], curDay); // 间隔时间够了, 直接做 else { // 需要休息 curDay += space - delta; // 休息完后做这件事 map.put(tasks[i], curDay); } } } return curDay; }}

6144.将数组排序的最少替换次数

拆数，且要保持非递减，问最少进行操作的次数。拆数会使数变小，而要保持非递减，要尽可能让右侧的数更大（贪心的思路），所以我们从最右边开始遍历，每当遇到一个递减的两个数，比如​​[a,9,5]​​​，那么要将左侧更大的那个数进行拆数，这就要拆​​9​​​这个数，假设拆为2个数，即​​9 = x + y​​​，那么变成​​[a,x,y,5]​​​，那么要保证 ​​y <= 5​​​，同时要保证​​x <= y​​​，且要​​x​​​尽可能的大，​​x​​​尽可能的大，才能保证更左侧的数拆数的可能性，尽可能地小。那么容易知道将​​9​​​拆成​​4,5​​就能满足。

更一般的，假设是​​[16,5]​​​, 则最好的拆法是：​​[4,4,4,4,5]​​

对​​[17,5]​​​，最好的拆法是​​[4,4,4,5,5]​​​，对​​[18,5]​​​，最好的拆法是​​[4,4,5,5,5]​​​，对​​[19,5]​​​，最好的拆法是​​[4,5,5,5,5]​​​，对​​[20,5]​​​，是​​[5,5,5,5,5]​​

能够观察出规律。假设​​[x, y]​​​，​​x > y​​​，那么需要对​​x​​​进行拆数。当​​x​​​恰好是​​y​​​的倍数，则将​​x​​​拆成数个​​y​​​即可，操作次数为​​x / y - 1​​​，比如上面的​​[20,5]​​​；若​​y​​​不能整除​​x​​​，设​​c = x / y​​​，那么最好的拆法，最左侧的数为​​x / (c + 1)​​​，需要的操作次数为​​c​​。

/*** 3ms**/class Solution { public long minimumReplacement(int[] nums) { long ans = 0; int n = nums.length; int right = nums[n - 1]; for (int i = n - 2; i >= 0; i--) { if (nums[i] <= right) { right = nums[i]; continue; } if (nums[i] % right == 0) ans += nums[i] / right - 1; else { int c = nums[i] / right; ans += c; right = nums[i] / (c + 1); } } return ans; }}

战绩：

305周赛

2637.算数三元组的数目

根据题目，严格递增， 容易想到用双指针（其实直接暴力也可以），然后同样，将题目中的等式进行移项操作。得到​​2 * nums[j] = nums[i] + nums[k]​​​，那么固定​​j​​​，用双指针移动​​i​​​和​​k​​即可。

/*** 3ms**/class Solution { public int arithmeticTriplets(int[] nums, int diff) { int n = nums.length; int ans = 0; for (int j = 1; j < n - 1; j++) { int i = 0, k = n - 1; while (i < j && j < k) { if (nums[i] + nums[k] == 2 * nums[j]) { if (nums[j] - nums[i] == diff) ans++; i++; k--; } else if (nums[i] + nums[k] < 2 * nums[j]) { i++; } else { k--; } } } return ans; }}

2368.受限条件下可到达节点的数目

一道简单的图的遍历问题，直接用DFS或者BFS即可。

关于图的表示：邻接表，邻接矩阵。此题是稀疏图，故用邻接表表示即可。

邻接表的实现，可以用数组模拟链表，也可以用内置的数据结构

/*** 数组实现邻接表 + DFS* 13ms**/class Solution { int[] h; int[] e; int[] ne; int idx = 0; boolean[] ban; public int reachableNodes(int n, int[][] edges, int[] restricted) { h = new int[n]; e = new int[2 * n]; ne = new int[2 * n]; Arrays.fill(h, -1); // 建图 for (int[] e : edges) { // 无向图, 连2条边 add(e[0], e[1]); add(e[1], e[0]); } ban = new boolean[n]; for (int r : restricted) ban[r] = true; return dfs(0); } private int dfs(int node) { if (ban[node]) return 0; int ans = 1; ban[node] = true; for (int i = h[node]; i != -1; i = ne[i]) { int son = e[i]; ans += dfs(son); } return ans; } private void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; }}

/*** map实现邻接表 + BFS* 101ms**/class Solution { public int reachableNodes(int n, int[][] edges, int[] restricted) { // map 实现邻接表 Map> adjTable = new HashMap<>(); for (int[] e : edges) { int a = e[0], b = e[1]; if (!adjTable.containsKey(a)) adjTable.put(a, new ArrayList<>()); if (!adjTable.containsKey(b)) adjTable.put(b, new ArrayList<>()); adjTable.get(a).add(b); adjTable.get(b).add(a); } boolean[] st = new boolean[n]; for (int r : restricted) st[r] = true; Queue queue = new LinkedList<>(); queue.offer(0); st[0] = true; int ans = 1; while(!queue.isEmpty()) { int x = queue.poll(); for (int t : adjTable.get(x)) { if (st[t]) continue; st[t] = true; queue.offer(t); ans++; } } return ans; }}

/*** List数组实现邻接表 + BFS* 48ms**/class Solution { public int reachableNodes(int n, int[][] edges, int[] restricted) { List[] adjTable = new List[n]; for (int[] e : edges) { int a = e[0], b = e[1]; if (adjTable[a] == null) adjTable[a] = new ArrayList<>(); if (adjTable[b] == null) adjTable[b] = new ArrayList<>(); adjTable[a].add(b); adjTable[b].add(a); } boolean[] ban = new boolean[n]; for (int r : restricted) ban[r] = true; Queue queue = new LinkedList<>(); int ans = 1; ban[0] = true; queue.offer(0); while (!queue.isEmpty()) { int x = queue.poll(); for (int b : adjTable[x]) { if (ban[b]) continue; ans++; ban[b] = true; queue.offer(b); } } return ans; }}

2369.检查数组是否存在有效划分

记忆化递归

用函数 ​​canDivide(l, r)​​​ 来表示区间​​[l, r]​​​是否能够有效划分。 每2个连续数字，每3个连续数字，构成一个划分的最小单位。我们先求出每个最小单位的结果。 对于区间​​​[l,r]​​​, 存储时，我们将其序列化为一个整数 ​​l * BASE + r​​​, 类似于将二维坐标拉成一维数字。用这样一个整数来表示这个区间。 那么我们先遍历一次数组，预处理出所有大小为2和3的区间。随后进行DFS深搜，并为了减少重复计算，加入记忆化。

这是周赛当时的做法，但是提交后只通过了110/112个测试样例，还剩2个没通过。很可惜，当时应该想到，这种情况一般是数据太大溢出导致的。后来今天复盘时，发现把代码中的​​int​​​换成​​long​​​就能提交通过了。（换成​​int[][] dp​​ 进行状态存储会报超出内存限制）

/*** 230ms**/class Solution { long BASE = 1_000_00; // 数字最大为 1e6 Set valid = new HashSet<>(); Set invalid = new HashSet<>(); public boolean validPartition(int[] nums) { int n = nums.length; // 预处理 for (int i = 0; i < n; i++) { if (i + 1 < n) { if (nums[i] == nums[i + 1]) valid.add(i * BASE + i + 1); else invalid.add(i * BASE + i + 1); } if (i + 2 < n) { if (nums[i] == nums[i + 1] && nums[i] == nums[i + 2]) valid.add(i * BASE + i + 2); else if (nums[i + 1] - nums[i] == 1 && nums[i + 2] - nums[i + 1] == 1) valid.add(i * BASE + i + 2); else invalid.add(i * BASE + i + 2); } } // 把所有有效的最小区间全部拿出来了 return canDivide(nums, 0, n - 1); } private boolean canDivide(int[] nums, int l, int r) { if (l > r) return true; // 不需要分了, 自然就能分了 if (l == r) return false; // 不能分 if (valid.contains(l * BASE + r)) return true; // 已经计算完成, 能分 if (invalid.contains(l * BASE + r)) return false; // 已经计算完成, 不能分 // 未计算完成, 则进行计算 boolean two = valid.contains(l * BASE + l + 1) && canDivide(nums, l + 2, r); boolean three = valid.contains(l * BASE + l + 2) && canDivide(nums, l + 3, r); if (two || three) { valid.add(l * BASE + r); } else { invalid.add(l * BASE + r); } return two || three; }}

其实这道题可以用标准的线性动态规划来做

设​​f[i]​​​表示从​​[0, i]​​​是否能进行有效划分，​​f[i] = true​​​表示可划分，​​false​​表示不可划分。

状态转移，​​f[i]​​可以由下面几个式子做或运算转移过来。

​​f[i - 2] && nums[i] = nums[i - 1]​​

​​f[i - 3] && nums[i] = num[i - 1] = nums[i - 2]​​

​​f[i - 3] && nums[i] = nums[i - 1] + 1 = nums[i - 2] + 2​​

/*** 6ms**/class Solution { public boolean validPartition(int[] nums) { int n = nums.length; boolean[] f = new boolean[n]; if (nums[1] == nums[0]) f[1] = true; for (int i = 2; i < n; i++) { if (nums[i] == nums[i - 1] && f[i - 2]) f[i] = true; if (i == 2 || (i >= 3 && f[i - 3])) { if (nums[i] == nums[i - 1] && nums[i] == nums[i - 2]) f[i] = true; if (nums[i] == nums[i - 1] + 1 && nums[i - 1] == nums[i - 2] + 1) f[i] = true; } } return f[n - 1]; }}

2370.最长理想子序列

给定一个由小写字母组成的字符串​​s​​​和一个整数​​k​​​，若满足如下2个条件，则将字符串​​t​​视为理想字符串

​​t​​​是​​s​​的一个子序列​​t​​中每两个相邻字母的绝对差值​​<=k​​

求最长的理想字符串的长度。

这道题很容易想到要用动态规划来做，因为与字符串相关的类似的题目，也都用DP的思路。比如求最长上升子序列等经典题目。

我们用​​f[i]​​​表示，只从​​[0, i]​​的区间中选，选出的最长的理想子序列的长度。

周赛当时，我也是这个思路，代码如下

class Solution { public int longestIdealString(String s, int k) { int n = s.length(); int[][] f = new int[n][2]; // 只从前n个位置中出现的子序列中, 最长的且不相邻不超过k的 // f[i] 只在前i个位置中出现的, 最长的且不超过k的 // 最后一个位置i是否被纳入其中 // 是, 否 f[0][0] = 0; f[0][1] = 1; for (int i = 1; i < n; i++) { f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]); f[i][1] = 1; for (int j = i - 1; j >= 0; j--) { int gap = Math.abs(s.charAt(i) - s.charAt(j)); if (gap <= k) { f[i][1] = Math.max(f[i][1], f[j][1] + 1); } } } return Math.max(f[n - 1][0], f[n - 1][1]); }}

正解：

类似的思路，不过我们开二维数组，第二个维度表示最后一个位置的字符。

即状态数组开为​​f[n][26]​​​，比如​​f[5][0]​​​，表示在​​[0,5]​​​中选，得出的以​​a​​为最后一个字符的，最长理想字符串，的最大长度。

我们枚举每个位置，进行状态转移的计算，对于每个位置，我们可以有两种操作

取这个位置的字符作为子序列的末尾不取这个字符

对于不取这个位置的字符，那么对所有的26个字母​​c​​​，有​​f[i][c] = f[i - 1][c]​​

若取这个位置的字符，那么我们需要枚举前一个位置的字符，只在前一个字符和当前字符相差​​<=k​​时，进行状态转移。

/*** 79ms**/class Solution { public int longestIdealString(String s, int k) { int n = s.length(); int[][] f = new int[n][26]; f[0][s.charAt(0) - 'a'] = 1; for (int i = 1; i < n; i++) { // 不取当前位置的字符作为子序列的最后一个字符时 for (int j = 0; j < 26; j++) f[i][j] = f[i - 1][j]; // 取当前字符 int c = s.charAt(i) - 'a'; for (int j = c - k; j <= c + k; j++) { // 前一个字符的有效区间 [c-k, c+k] // 注意可能越界 if (j >= 0 && j < 26) f[i][c] = Math.max(f[i][c], f[i - 1][j] + 1); } } int ans = 0; for (int i = 0; i < 26; i++) ans = Math.max(ans, f[n - 1][i]); return ans; }}

由于状态转换，只依赖于上一层，则可以优化为一维数组

/*** 25ms**/class Solution { public int longestIdealString(String s, int k) { int n = s.length(); int[] f = new int[26]; f[s.charAt(0) - 'a'] = 1; for (int i = 1; i < n; i++) { // 不取当前位置的字符作为子序列的最后一个字符时 // 取当前字符 int c = s.charAt(i) - 'a'; int x = 0; for (int j = c - k; j <= c + k; j++) { // 前一个字符的有效区间 [c-k, c+k] // 注意可能越界 if (j >= 0 && j < 26) x = Math.max(x, f[j]); } f[c] = ++x; } int ans = 0; for (int i = 0; i < 26; i++) ans = Math.max(ans, f[i]); return ans; }}

战绩：

总结

这周两场周赛，都只做出2/4道 题目。

其中，周六晚上的比赛：

第2题坏数对没有观察出规律，没想到对等式进行移项变换，思路上一直卡在使用归并排序求逆序对上面，这是题目见得太少。第4题，基本思路正确（贪心），代码实现上有点问题，每次拆数，都尽可能保证，新的最右侧的数最大，这个想法是没错的，但是我拆数的策略错了，我的策略并不能保证拆后新的最右侧的数最大。比如固定右侧为​​b​​，举例子​​[a,b]​​。当晚我的拆数策略是：若​​a​​是​​b​​的倍数，则直接拆成若干个​​b​​，这个没什么好说的；当​​ 2b > a > b​​，则拆的数为​​a / 2​​，这也是没问题的；对于​​a > 2b​​，我的策略就错了，我当时想的是，每次从​​a​​中减去一个​​b​​，直到剩余的数​​a'​​，满足​​2b > a' > b​​，然后取拆的数为​​a' / 2​​。这是不正确的。比如​​[16, 5]​​，若按我的拆法，则结果是​​[6,5,5,5]​​，最后将​​6 / 2​​，得到​​[3,3,5,5,5]​​，这样拆完后最左侧的数并不能保证最大。实际应该这样拆，先求​​16 / 5 = 3 ... 1​​，则我们最终会把​​16​​拆成4个数，因为拆的数不能大于​​5​​，所以最多等于​​5​​。而要使得最左侧的数最大，那么最好的分配方式就是，依次分配。比如把16个数，依次分配到4个槽，那能恰好分为​​[4,4,4,4]​​，这样就能让最左侧的数最大了。同理，若​​[17,5]​​，按我原先的拆法，结果是​​[7,5,5,5]​​，则​​[3,4,5,5,5]​​也是不对的。实际应该是​​17 / 5 = 3 ... 2​​。我们同样要把17分配到4个槽，可以这样想，4个槽，右侧的更大，则我们从右往左，依次循环填入1。填到最后就是​​[4,4,4,4]​​，此时还剩​​1​​，再填到最右侧，形成​​[4,4,4,5]​​。所以，最左侧的数的计算方法应该是，先求​​c = a / b​​，然后最左侧的数为​​a / (c + 1)​​。其实当​​c > 2​​时，拆后最左侧的数等于​​b - 1​​，为了兼容​​c == 2​​时的情况，按照​​a / (c + 1)​​来进行计算

周日早上的比赛

第3题，虽然当晚我的方法有点笨拙（记忆化DFS），但是代码是没问题的，提交后110/112，只有2个用例没通过。但是我没有意识到是用例的数据太大导致可能溢出。第二天才发现这个问题，把当晚的代码拿出来，把其中的​​int​​​改为​​long​​，提交就通过了，虽然耗时很长。这是很可惜的一个点，本来周日早上的比赛可以A掉3题的。第4题，有思路，思路是正确的，但是时间复杂度很高，会超时。后面也没有想到能如何优化。DP的关键在于状态转移，状态转移一般也是枚举最后一个位置的可能情况，我想到了需要依赖前一个子序列的最后一个位置的字符，但是没想到第二维度可以直接枚举全部的26个字母。可惜！

总的来说，这周的两场周赛都不难，我见的题目太少，有些思路，解法想不到。所以还是要多多参加周赛，多多刷题。下周继续！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。