欢迎大家加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;
}
}