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_bound
                int 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_bound
                l = 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;
        }
    }