6-周赛332总结

过了Q1和Q2，Q2知道用二分但是边界处理的不是很好，迷迷糊糊过的（手动再移动了下返回值…）

Q3知道将子字符串的值取出来，将最短位置放在哈希表中，然后异或在哈希表中找值。但是我这个猪头脑袋直接将值用Integer.parseInt(s)取值，然后右移取余，移了大半天，很蠢就是了…然后就没有时间做第四题了

继续努力继续努力

下文为自己的题解总结，参考其他题解写成，取其精华，做以笔记，如有描述不清楚或者错误麻烦指正，不胜感激，不喜勿喷！

找出数组的串联值【LC2562】

给你一个下标从 0 开始的整数数组 nums 。

现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。

• 例如，15 和 49 的串联是 1549 。

nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：

• 如果 nums 中存在不止一个数字，分别选中 nums 中的第一个元素和最后一个元素，将二者串联得到的值加到 nums 的 串联值 上，然后从 nums 中删除第一个和最后一个元素。
• 如果仅存在一个元素，则将该元素的值加到 nums 的串联值上，然后删除这个元素。

返回执行完所有操作后 nums 的串联值。

• 思路：使用双指针匹配数组中的元素，并将元素进行串联，累加至结果中，直至数组中没有元素剩余

  • 如果前后指针指向同个元素，直接将值累加至结果
  • 如果前后指针指向两个元素$nums1,nums2$，那么串联值为$num1\ast nums2的位数+nums2$

• 实现

  class Solution {public long findTheArrayConcVal(int[] nums) {int l = 0, r = nums.length - 1;long res = 0L;while (l <= r){if (l == r){res += nums[l];break;}else{int n = getN(nums[r]);res += Math.pow(10, n) * nums[l] + nums[r];l++;r--;}}return res;}public int getN(int num){int n = 0;while (num != 0){num /= 10;n++;}return n;}
  }
  

  • 复杂度
    • 时间复杂度：$O(n)$
    • 空间复杂度：$O(1)$

统计公平数对的数目【LC2563】

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

• 0 <= i < j < n，且
• lower <= nums[i] + nums[j] <= upper

• 思路：二分查找

  将数组按顺序排序后，枚举每一个nums[i],那么在$nums[0,i)$范围内，使用二分查找另一个数小于$lower-nums[i]$或者小于等于$upper-nums[i]$的个数，记为left和right，那么符合条件的公平数对为$right-left$

  • 可以转换为使用二分查找另一个数大于等于$lower-nums[i]$或者大于$upper-nums[i]$的第一个数的下标
  • 可以转换为使用二分查找另一个数大于等于$lower-nums[i]$或者大于等于$upper-nums[i]+1$的第一个数的下标

• 实现

  注意：二分查找指定范围内第一个大于等于target的数的下标，左闭右闭

  class Solution {public long countFairPairs(int[] nums, int lower, int upper) {long res = 0L;Arrays.sort(nums);int n = nums.length;for (int i = 1; i < n; i++){int left = binarySearch(nums, lower - nums[i], i - 1);// 第一个大于等于 lower - nums[i] 的下标int right = binarySearch(nums, upper - nums[i] + 1, i - 1);// 第一个大于等于high nums[i]的下标[0, i - 1] res += right - left;}return res;       }// 返回第一个大于等于target的下标public int binarySearch(int[] nums, int target, int r){int l = 0;// 左闭右闭while (l <= r){int mid = (l + r) >>> 1;if (nums[mid] < target){l = mid + 1;}else{r = mid - 1;}}return l;}
  }
  

  • 复杂度
    • 时间复杂度：$O(nlogn)$
    • 空间复杂度：$O(1)$

子字符串异或查询【LC2564】

给你一个 二进制字符串 s 和一个整数数组 queries ，其中 queries[i] = [firsti, secondi] 。

对于第 i 个查询，找到 s 的 最短子字符串 ，它对应的 十进制值 val 与 firsti 按位异或 得到 secondi ，换言之，val ^ firsti == secondi 。

第 i 个查询的答案是子字符串 [lefti, righti] 的两个端点（下标从 0 开始），如果不存在这样的子字符串，则答案为 [-1, -1] 。如果有多个答案，请你选择 lefti 最小的一个。

请你返回一个数组 ans ，其中 ans[i] = [lefti, righti] 是第 i 个查询的答案。

子字符串 是一个字符串中一段连续非空的字符序列。

• 思路：

  • 首先进行预处理，将二进制字符串所有子字符串对应的十进制整数值存储在哈希表中，哈希表记录该值对应的最短子字符串的起始位置和终止位置
  • 然后遍历循环数组查找结果：根据异或性质，当哈希表中存在值为val = firsti ^ secondi 时，对于第$i$个查询可以找到答案，答案即为哈希表的key值

• 实现

  注意：由于 数值大小$10^9<2^{30}$，因此，我们可以只需要计算 s 中所有长度不超过 30的子字符串即可

  class Solution {public int[][] substringXorQueries(String s, int[][] queries) {char[] chars = s.toCharArray();int n = s.length();int m = queries.length;int[][] res = new int[m][2];Map<Integer, int[]> map = new HashMap<>();for (int i = 0; i < m; i++){Arrays.fill(res[i], -1);}        for (int l = 0; l < n; l++){int num = 0;for (int r = l; r < Math.min(l + 30, n); r++){num = (num << 1) + chars[r] - '0';if (!map.containsKey(num) || map.get(num)[1] - map.get(num)[0]  > r - l){map.put(num, new int[]{l, r});}}}for (int i = 0; i < m; i++){int target = (queries[i][0] ^ queries[i][1]);if (map.containsKey(target)){res[i] = map.get(target);}}return res;}
  }

  • 复杂度
    • 时间复杂度：$O(nlogU+q)$，其中 $n$ 为 s 的长度，$U=max(queries)$，$q$ 为 queries 的长度。
    • 空间复杂度：$O(nlogU)$

最少得分子序列【LC2565】

给你两个字符串 s 和 t 。

你可以从字符串 t 中删除任意数目的字符。

如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：

• 令 left 为删除字符中的最小下标。
• 令 right 为删除字符中的最大下标。

字符串的得分为 right - left + 1 。

请你返回使 t 成为 s 子序列的最小得分。

一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "***a\***b***c\***d***e\***" 的子序列，但是 "aec" 不是）。

• 思路：

  • 删除$[left,right]$之间的字符，不会影响最终结果，因为删除不影响得分，并且更能让剩余字符成为s的子串，因此可以视为删除子串【没想到】
  • 删除后，t中剩余的字符为t$[:,left),(right,:]$。假设s的一个前缀字符串$s[0,i]$可以匹配该前缀字符串，s的一个后缀字符串$s[i+1,:]$可以匹配该后缀字符串，那么表明t中剩余的字符是s的子序列，得分为$right-left+1$
  • 反而言之，我们可以枚举$i$，求得$s[0,i]$能够匹配t的最长前缀字符串的结束位置下标l，以及$s[i+1,:]$能够匹配t的最长后缀字符串的开始位置r，那么此时需要删除的位置即为$[l+1,r-1]$，得分为$r-l-1$，取最小值返回节课

• 实现

  • 预处理后缀数组suff[i]：s的一个后缀字符串$s[i,:]$可以匹配t的最长后缀字符串的开始位置
  • 预处理前缀数组pre[i+1]：s的一个前缀字符串$s[0,i]$可以匹配t的最长前缀字符串的结束位置

  class Solution {public int minimumScore(String s, String t) {int n = s.length(), m = t.length();int[] pre = new int[n + 1];int[] suf = new int[n + 1];suf[n] = m;for (int i = n - 1, j = m - 1; i >= 0; i--){if (j >= 0 && s.charAt(i) == t.charAt(j)) j--;suf[i] = j + 1;}int res = suf[0];if (suf[0] == 0) return res;// t是s的子序列pre[0] = -1;for (int i = 1; i <= n; i++){if (s.charAt(i - 1) == t.charAt(pre[i - 1] + 1)){pre[i] = pre[i - 1] + 1;}else{pre[i] = pre[i - 1];}res = Math.min(res, suf[i] - pre[i] - 1);}return res;}
  }
  

  • 复杂度
    • 时间复杂度：$O(n)$
    • 空间复杂度：$O(n)$

• 优化：前缀数组可以用变量代替

  class Solution {public int minimumScore(String s, String t) {int n = s.length(), m = t.length();int[] suf = new int[n + 1];suf[n] = m;for (int i = n - 1, j = m - 1; i >= 0; i--){if (j >= 0 && s.charAt(i) == t.charAt(j)) j--;suf[i] = j + 1;}int res = suf[0];if (suf[0] == 0) return res;// t是s的子序列int pre = -1;for (int i = 1; i <= n; i++){if (s.charAt(i - 1) == t.charAt(pre + 1)){pre += + 1;}res = Math.min(res, suf[i] - pre - 1);}return res;}
  }