LeetCode_单周赛_332

6354. 找出数组的串联值

题意

将数组首尾元素接在一起，就是串联值。
串联之后删除，如果只剩下一个元素，加上这个元素即可

双指针，从首和尾向中间移动即可

code

**注意：**用 long
没看题目用了 int wa了一发

class Solution {public long findTheArrayConcVal(int[] nums) {int n = nums.length;int l = 0, r = n - 1;long ans = 0;while (l < r) {String s = "";s += nums[l++];s += nums[r--];ans += Integer.parseInt(s);}if (l == r) ans += nums[l];return ans;}
}

6355. 统计公平数对的数目

题意

给定 lower 和 upper 找到 数组中 两个不同的数字，如果满足 lower <= nums[i] + nums[j] <= upper 就是一组公平数对。
求公平数对的个数

我们枚举每个 nums[i] 将 lower <= nums[i] + nums[j] <= upper 变形为：lower - nums[i] <= nums[j] <= upper - nums[i]
所以我们二分找到 第一个大于 upper - nums[i] 的位置，和 第一个 大于等于 lower- nums[i] 的位置前者减去后者即可得到差。
对应的 c++中的函数就是 uppper_bound 和 lower_bound，Java中么有这俩函数，我们自己写一个
并且，我们求的是数对，有重复的，为防止重复，我们只搜索下标为 i 的数的 左边的数，也避免了 i 被统计进去的情况

code

class Solution {public long countFairPairs(int[] nums, int lower, int upper) {long ans = 0;int n = nums.length;Arrays.sort(nums);// lower <= nums[i] + nums[j] <= upper// 枚举 nums[i] 找 j// lower - nums[i] <= nums[j] <= upper - nums[i]for (int i = 0; i < n; i++) { int a = i, b = i;// upper_boundint l = 0, r = i - 1;while (l < r) {int mid = l + r >> 1;if (nums[mid] > upper - nums[i]) r = mid;else l = mid + 1;}if (nums[l] > upper - nums[i]) a = l;// a = l;// if (nums[a] <= upper - nums[i]) a = i;// lower_boundl = 0; r = i - 1;while (l < r) {int mid = l + r >> 1;if (nums[mid] >= lower - nums[i]) r = mid;else l = mid + 1;}if (nums[l] >= lower - nums[i]) b = l;// b = l;// if (nums[b] < lower - nums[i]) b = i;ans += a - b;}return ans;}}

6356. 子字符串异或查询

题意

要满足 val ^ firsti == secondi 等号两边同时 ^ first 得到 val = first ^ second
所以我们只要找 queries数组中的 first 和 second 异或值时候存在于 s 中

因为 异或并不会增加二进制位数，0 <= firsti, secondi <= 109，小于 2^30 - 1，最多就 31 位，所以枚举的时候只需要枚举字符串的连续 30 个即可

s 是 1e4 时间复杂度最多就 1e4 * 30 = 3e5 足够的
后面枚举queries是 1e5
时间复杂度 = 4e5

用 map 预处理，存储 s 的二进制子串出现过的 十进制数字，以及对应的 边界 ，要求存储长度最小的子串

code

class Solution {public int[][] substringXorQueries(String s, int[][] queries) {HashMap<Integer, int[]> mp = new HashMap<>();int n = s.length();char[] c = s.toCharArray();for (int i = 0; i < n; i++) {int x = 0;for (int j = i; j < i + 30 && j < n; j++) { // 计算子串x = (x << 1) | (c[j] - '0');if (!mp.containsKey(x)  || (j - i < mp.get(x)[1] - mp.get(x)[0])) {mp.put(x, new int[]{i, j});}}}ArrayList<int[]> a = new ArrayList<>();for (var pr : queries) {int t = pr[0] ^ pr[1];if (mp.getOrDefault(t, null) != null)a.add(new int[]{mp.get(t)[0], mp.get(t)[1]});else a.add(new int[]{-1, -1});}int len = a.size();int[][] ans = new int[len][2];for (int i = 0; i < len; i++) {ans[i] = a.get(i);}return ans;}}