欢迎大家加QQ群:623375442,可以方便群里面交流。

100309. Find the XOR of Numbers Which Appear Twice

给你一个数组 nums ,数组中的数字 要么 出现一次,要么 出现两次。

请你返回数组中所有出现两次数字的按位 XOR 值,如果没有数字出现过两次,返回 0 。

测试样例:

输入:nums = [1,2,1,3]

输出:1

解释:nums 中唯一出现过两次的数字是 1 。

解答:用一个HashSet记录一下曾经出现过的数字。第二次出现,就取一下XOR。

class Solution {
    public int duplicateNumbersXOR(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int res = 0;
        for (int n : nums) {
            if (set.contains(n)) {
                res ^= n;
            } else {
                set.add(n);
            }
        }
        return res;
    }
}

100303. Find Occurrences of an Element in an Array

给你一个整数数组 nums ,一个整数数组 queries 和一个整数 x 。

对于每个查询 queries[i] ,你需要找到 nums 中第 queries[i] 个 x 的位置,并返回它的下标。如果数组中 x 的出现次数少于 queries[i] ,该查询的答案为 -1 。

请你返回一个整数数组 answer ,包含所有查询的答案。

测试样例:

输入:nums = [1,3,1,7], queries = [1,3,2,4], x = 1

输出:[0,-1,2,-1]

解释:

  • 第 1 个查询,第一个 1 出现在下标 0 处。
  • 第 2 个查询,nums 中只有两个 1 ,所以答案为 -1 。
  • 第 3 个查询,第二个 1 出现在下标 2 处。
  • 第 4 个查询,nums 中只有两个 1 ,所以答案为 -1 。

解答:暴力记录一下所有x出现的位置,然后queries的时候搜索一下。

class Solution {
    public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == x) {
                list.add(i);
            }
        }
        int[] res = new int[queries.length];
        for (int i = 0; i < res.length; ++i) {
            int q = queries[i];
            if (q <= list.size()) {
                res[i] = list.get(q - 1);
            } else {
                res[i] = -1;
            }
        }
        return res;
    }
}

100313. Find the Number of Distinct Colors Among the Balls

给你一个整数 limit 和一个大小为 n x 2 的二维数组 queries 。

总共有 limit + 1 个球,每个球的编号为 [0, limit] 中一个 互不相同 的数字。一开始,所有球都没有颜色。queries 中每次操作的格式为 [x, y] ,你需要将球 x 染上颜色 y 。每次操作之后,你需要求出所有球中 不同 颜色的数目。

请你返回一个长度为 n 的数组 result ,其中 result[i] 是第 i 次操作以后不同颜色的数目。

注意 ,没有染色的球不算作一种颜色。

测试样例:

输入:limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]

输出:[1,2,2,3]

解释:

  • 操作 0 后,球 1 颜色为 4 。
  • 操作 1 后,球 1 颜色为 4 ,球 2 颜色为 5 。
  • 操作 2 后,球 1 颜色为 3 ,球 2 颜色为 5 。
  • 操作 3 后,球 1 颜色为 3 ,球 2 颜色为 5 ,球 3 颜色为 4 。

解答:两个HashMap记录一下球的颜色标记情况和各种颜色的计数器。

class Solution {
    public int minimumSubstringsInPartition(String s) {
        int[] dp = new int[s.length() + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < s.length(); ++i) {
            int[] count = new int[26];
            for (int j = i; j >= 0; --j) {
                count[s.charAt(j) - 'a'] += 1;
                if (dp[j] != Integer.MAX_VALUE && isValid(count)) {
                    dp[i + 1] = Math.min(dp[j] + 1, dp[i + 1]);
                }
            }
        }
        return dp[s.length()];
    }

    private boolean isValid(int[] count) {
        int last = -1;
        for (int n : count) {
            if (n != 0) {
                if (last == -1) {
                    last = n;
                } else if (last != n) {
                    return false;
                }
            }
        }
        return true;
    }
}

100314. Block Placement Queries

有一条无限长的数轴,原点在 0 处,沿着 x 轴 正 方向无限延伸。

给你一个二维数组 queries ,它包含两种操作:

  • 操作类型 1 :queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候,位置 x 处 没有 任何障碍物。
  • 操作类型 2 :queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块,这个物块需要 完全 放置在范围 [0, x] 内。如果物块与任何障碍物有重合,那么这个物块 不能 被放置,但物块可以与障碍物刚好接触。注意,你只是进行查询,并 不是 真的放置这个物块。每个查询都是相互独立的。

请你返回一个 boolean 数组results ,如果第 i 个操作类型 2 的操作你可以放置物块,那么 results[i] 为 true ,否则为 false 。

测试样例:

输入:queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]

输出:[false,true,true]

解释:查询 0 ,在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。

解答:虽然粗心WA了好几次,但是说实话,这题没有8分难度。主要难点是给一个x之后,需要知道[0,x]这个区间内,最大的没有障碍物的长度。这道题目分为2步。第一步先把所有涉及到的障碍物位置记录一下,并按照障碍物升序的排序情况,记录一下它们出现的位置。

第二步就是遍历整个queries。如果发生type1,就更新障碍物数组。否则就动态查询最大区间。因为牵涉到动态查询区间值,比较容易想到SegmentTree。

class Solution {
    class SegmentWithMap {
        HashMap<Integer, Integer> map;
        List<Integer> distinctList;
        int[] tree;
        int n;

        public SegmentWithMap(int[][] queries) {
            sortBlock(queries);
            if (distinctList != null && distinctList.size() > 0) {
                n = distinctList.size();
                tree = new int[n * 2];
                buildTree();
            }
        }

        private void sortBlock(int[][] queries) {
            List<Integer> list = new ArrayList<>();
            for (int[] q : queries) {
                if (q[0] == 1) {
                    list.add(q[1]);
                }
            }
            Collections.sort(list);
            distinctList = list;
            map = new HashMap<>();
            // 按照障碍物升序排序的情况,记录障碍物实际位置和升序队列offset的对应关系。
            for (int i = 0; i < list.size(); ++i) {
                map.put(list.get(i), i);
            }
        }

        private void buildTree() {
            for (int i = n, j = 0;  i < 2 * n; i++,  j++)
                tree[i] = 0;
            for (int i = n - 1; i > 0; --i)
                tree[i] = Math.max(tree[i * 2], tree[i * 2 + 1]);
        }

        public void update(int pos, int val) {
            pos = getOffset(pos) + n;
            tree[pos] = val;
            while (pos > 0) {
                int left = pos;
                int right = pos;
                if (pos % 2 == 0) {
                    right = pos + 1;
                } else {
                    left = pos - 1;
                }
                tree[pos / 2] = Math.max(tree[left], tree[right]);
                pos /= 2;
            }
        }

        public int maxRange(int r) {
            int l = n;
            r = getOffset(r) + n;
            int sum = 0;
            while (l <= r) {
                if ((l % 2) == 1) {
                    sum = Math.max(sum, tree[l]);
                    l++;
                }
                if ((r % 2) == 0) {
                    sum = Math.max(sum, tree[r]);
                    r--;
                }
                l /= 2;
                r /= 2;
            }
            return sum;
        }

        public int getOffset(int num) {
            return map.get(num);
        }
    }

    public List<Boolean> getResults(int[][] queries) {
        SegmentWithMap data = new SegmentWithMap(queries);
        TreeSet<Integer> blockPosSet = new TreeSet<>();

        List<Boolean> res = new ArrayList<>();
        for (int[] q : queries) {
            if (q[0] == 1) {
                int pos = q[1];
                blockPosSet.add(pos);
                // 刷新障碍物数组
                // 更新当前位置的最大距离
                Integer lower = blockPosSet.lower(pos);
                if (lower != null) {
                    data.update(pos, pos - lower);
                } else {
                    data.update(pos, pos);
                }

                // 如果存在更高位置的障碍物,还得减少一下它的最大距离
                Integer higher = blockPosSet.higher(pos);
                if (higher != null) {
                    data.update(higher, higher - pos);
                }
            } else {
                // 动态查询
                Integer floor = blockPosSet.floor(q[1]);
                if (floor == null) {
                    res.add(q[1] >= q[2]);
                } else if (q[1] - floor >= q[2]) {
                    res.add(true);
                } else if (data.maxRange(floor) >= q[2]) {
                    res.add(true);
                } else {
                    res.add(false);
                }
            }
        }
        return res;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *