6354. 找出數(shù)組的串聯(lián)值

題意

將數(shù)組首尾元素接在一起，就是串聯(lián)值。
串聯(lián)之后刪除，如果只剩下一個(gè)元素，加上這個(gè)元素即可

雙指針，從首和尾向中間移動(dòng)即可

code

**注意：**用 long
沒看題目用了 int wa了一發(fā)

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. 統(tǒng)計(jì)公平數(shù)對(duì)的數(shù)目

題意

給定 lower 和 upper 找到 數(shù)組中 兩個(gè)不同的數(shù)字，如果滿足 lower <= nums[i] + nums[j] <= upper 就是一組公平數(shù)對(duì)。
求公平數(shù)對(duì)的個(gè)數(shù)

我們枚舉每個(gè) nums[i] 將 lower <= nums[i] + nums[j] <= upper 變形為：lower - nums[i] <= nums[j] <= upper - nums[i]
所以我們二分找到 第一個(gè)大于 upper - nums[i] 的位置，和 第一個(gè) 大于等于 lower- nums[i] 的位置前者減去后者即可得到差。
對(duì)應(yīng)的 c++中的函數(shù)就是 uppper_bound 和 lower_bound，Java中么有這倆函數(shù)，我們自己寫一個(gè)
并且，我們求的是數(shù)對(duì)，有重復(fù)的，為防止重復(fù)，我們只搜索下標(biāo)為 i 的數(shù)的 左邊的數(shù)，也避免了 i 被統(tǒng)計(jì)進(jìn)去的情況

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 等號(hào)兩邊同時(shí) ^ first 得到 val = first ^ second
所以我們只要找 queries數(shù)組中的 first 和 second 異或值時(shí)候存在于 s 中

因?yàn)?異或并不會(huì)增加二進(jìn)制位數(shù)，0 <= firsti, secondi <= 109，小于 2^30 - 1，最多就 31 位，所以枚舉的時(shí)候只需要枚舉字符串的連續(xù) 30 個(gè)即可

s 是 1e4 時(shí)間復(fù)雜度最多就 1e4 * 30 = 3e5 足夠的
后面枚舉queries是 1e5
時(shí)間復(fù)雜度 = 4e5

用 map 預(yù)處理，存儲(chǔ) s 的二進(jìn)制子串出現(xiàn)過的 十進(jìn)制數(shù)字，以及對(duì)應(yīng)的 邊界 ，要求存儲(chǔ)長度最小的子串

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++) { // 計(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;}}