6430. Find the Losers of the Circular Game
n 个朋友在玩游戏。这些朋友坐成一个圈，按 顺时针方向 从 1 到 n 编号。从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i + 1) 个朋友的位置（1 <= i < n），而从第 n 个朋友的位置开始顺时针移动 1 步会回到第 1 个朋友的位置。
游戏规则如下：
第 1 个朋友接球。
- 接着，第 1 个朋友将球传给距离他顺时针方向 k 步的朋友。
- 然后，接球的朋友应该把球传给距离他顺时针方向 2 * k 步的朋友。
- 接着，接球的朋友应该把球传给距离他顺时针方向 3 * k 步的朋友，以此类推。
换句话说，在第 i 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 i * k 步的朋友。
当某个朋友第 2 次接到球时，游戏结束。
在整场游戏中没有接到过球的朋友是 输家 。
给你参与游戏的朋友数量 n 和一个整数 k ，请按升序排列返回包含所有输家编号的数组 answer 作为答案。
测试样例：
输入：n = 5, k = 2
输出：[4,5]
解释：
以下为游戏进行情况：
- 第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 2 步的玩家 —— 第 3 个朋友。
- 第 3 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 2 个朋友。
- 第 2 个朋友将球传给距离他顺时针方向 6 步的玩家 —— 第 3 个朋友。
- 第 3 个朋友接到两次球，游戏结束。
解答：提示有：1 <= k <= n <= 50。这个范围实在是太小了，直接按照要求暴力运算就行了
class Solution {
public int[] circularGameLosers(int n, int k) {
boolean[] isVisit = new boolean[n];
int cur = 0, add = 0, step = 1;
while (!isVisit[cur]) {
isVisit[cur] = true;
++add;
cur = (cur + step * k) % n;
++step;
}
int[] res = new int[n - add];
int p = 0;
for (int i = 0; i < n; ++i) {
if (!isVisit[i]) {
res[p++] = i + 1;
}
}
return res;
}
}6431. Neighboring Bitwise XOR
下标从 0 开始、长度为 n 的数组 derived 是由同样长度为 n 的原始 二进制数组 original 通过计算相邻值的 按位异或（⊕）派生而来。
特别地，对于范围 [0, n - 1] 内的每个下标 i ：
- 如果 i = n - 1 ，那么 derived[i] = original[i] ⊕ original[0]
- 否则 derived[i] = original[i] ⊕ original[i + 1]
给你一个数组 derived ，请判断是否存在一个能够派生得到 derived 的 有效原始二进制数组 original 。
如果存在满足要求的原始二进制数组，返回 true ；否则，返回 false 。
- 二进制数组是仅由 0 和 1 组成的数组。
测试样例：
输入：derived = [1,1,0]
输出：true
解释：
能够派生得到 [1,1,0] 的有效原始二进制数组是 [0,1,0]
解答：这题需要用到异或特性: A ⊕ A = 0。按照题意所有元素都会出现2次，所以对derived数组全部异或一下，结果应该为0
class Solution {
public boolean doesValidArrayExist(int[] derived) {
int res = 0;
for (int d : derived) {
res ^= d;
}
return res == 0;
}
}6433. Maximum Number of Moves in a Grid
给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。
你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：
- 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。
测试样例
输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：
可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。
解答：这道题目是一道动态规划题目。如果某一个位置(i,j)，它的前驱节点(i-1,j-1), (i,j-1), (i+1,j-1)可达，且某一个前驱节点小于当前单元格，那么当前单元格也可达。加之按照列的视角观看，列只会单调递增。所以一列一列动态规划的计算一下，就能知道多少列可达，即最大的自动次数。
class Solution {
private static final int[][] moves = {{-1,-1},{0,-1},{1,-1}};
public int maxMoves(int[][] grid) {
int m = grid.length, n = grid[0].length;
int res = 0;
boolean[] last = new boolean[m];
Arrays.fill(last, true);
for (int i = 1; i < n; ++i) {
boolean[] next = new boolean[m];
boolean isAdd = false;
for (int j = 0; j < m; ++j) {
for (int[] mv : moves) {
int xb = j + mv[0], yb = i + mv[1];
if (xb >= 0 && xb < m && yb >= 0 && yb < n && grid[xb][yb] < grid[j][i] && last[xb]) {
next[j] = true;
isAdd = true;
}
}
}
if (isAdd) {
++res;
last = next;
} else {
break;
}
}
return res;
}
}6432. Count the Number of Complete Components
给你一个整数 n 。现有一个包含 n 个顶点的 无向 图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条 无向 边。
返回图中 完全连通分量 的数量。
如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为 连通分量 。
如果连通分量中每对节点之间都存在一条边，则称其为 完全连通分量 。
测试样例
输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
输出：3
解释：
所有分量都是完全连通分量。
解答：这道题目可以先利用并查集寻找出所有联通分量。由于条件：1 <= n <= 50，范围也是非常小。对每个联通分量暴力运算任意2定点是否有边就行了
class Solution {
private class DSU{
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}
public int countCompleteComponents(int n, int[][] edges) {
DSU uf = new DSU(n);
HashSet<Integer> edgeSet = new HashSet<>();
for (int[] e : edges) {
uf.union(e[0], e[1]);
edgeSet.add(e[0] * 100 + e[1]);
edgeSet.add(e[1] * 100 + e[0]);
}
List<Integer>[] connected = new List[n];
for (int i = 0; i < n; ++i) {
int p = uf.find(i);
if (connected[p] == null) {
connected[p] = new ArrayList<>();
}
connected[p].add(i);
}
int res = 0;
for (int i = 0; i < n; ++i) {
if (connected[i] != null) {
boolean isFull = true;
out:
for (int l = 0; l < connected[i].size(); ++l) {
for (int r = l + 1; r < connected[i].size(); ++r) {
if (!edgeSet.contains(connected[i].get(l) * 100 + connected[i].get(r))) {
isFull = false;
break out;
}
}
}
if (isFull) {
++res;
}
}
}
return res;
}
}着实究极手速场了。