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;
        }
    }

標籤：其他

上一篇：分布式專題 - Dubbo + Zookeeper

下一篇：ChatGPT留給知乎、小紅書的時間不多了