Leetcode 2564. Substring XOR Queries

[Woodyiiiiiii]

这道题非常简单，但我竟然没答出来。。

两个知识点：

1. a ^ b = c，有a ^ c = b 或者 b ^ c = a
2. 整数的二进制表示长度最大是31

正解是先预处理一遍字符串，找到所有可以形成的整数的最早出现范围，用哈希存储。第二个知识点给上次遍历map的题目一样。

第一点我很快就知道了，问题是第二点，我一直没想到，所以卡在了如何优化查询这上面。一开始还试图用滑动窗口来做。所以这次有教训：

1. 三思而后行，快速尝试
2. 如果一个方法错了，尽快转到另一个方法

class Solution {
    public int[][] substringXorQueries(String s, int[][] queries) {
        int n = queries.length;
        int[][] ans = new int[n][2];
        for (int i = 0; i < n; i++) {
            ans[i][0] = -1;
            ans[i][1] = -1;
        }
        int[] queriesCopy = new int[n];
        for (int i = 0; i < n; i++) {
            queriesCopy[i] = queries[i][0] ^ queries[i][1];
        }
        Map<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '1') {
                int cur = 1;
                if (!map.containsKey(1)) {
                    map.put(1, new int[]{i, i});
                }
                for (int j = i + 1; j - i + 1 < 32 && j < s.length(); ++j) {
                    cur = (cur << 1) + s.charAt(j) - '0';
                    if (!map.containsKey(cur)) {
                        map.put(cur, new int[]{i, j});
                    }
                }
            } else {
                if (!map.containsKey(0)) {
                    map.put(0, new int[]{i, i});
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            int[] range = map.get(queriesCopy[i]);
            if (range != null) {
                ans[i][0] = range[0];
                ans[i][1] = range[1];
            }
        }
        return ans;
    }
}

---

• 2564. Substring XOR Queries