2682. 找出转圈游戏输家

  • 模拟

  • Python

     1class Solution:
 2    def circularGameLosers(self, n: int, k: int) -> List[int]:
 3        n_set = set()
 4        start = 1
 5        i = 1
 6        while start not in n_set:
 7            n_set.add(start)
 8            start = (start + i * k) % n
 9            if start == 0:
10                start = n
11            i += 1
12
13        return [i for i in range(1, n+1) if i not in n_set]

  • Golang

     1func circularGameLosers(n int, k int) []int {
 2	nMap := make(map[int]bool)
 3	start := 1
 4	i := 1
 5
 6	for !nMap[start] {
 7		nMap[start] = true
 8		start = (start + i*k) % n
 9		if start == 0 {
10			start = n
11		}
12		i++
13	}
14
15	ans := make([]int, 0)
16
17	for i := 1; i <= n; i++ {
18		if _, ok := nMap[i]; !ok {
19			ans = append(ans, i)
20		}
21	}
22
23	return ans
24}

2683. 相邻值的按位异或

  • 位运算

    根据派生规则可知。如果derived由原始二进制数组派生得来的话，derived的所有值异或值应为：

    xor = original[0] ⊕ original[1] ⊕ original[1] ... ⊕ original[n] ⊕ original[0]

    由异或运算性质可知：

    xor = 0

  • Python

    1class Solution:
2    def doesValidArrayExist(self, derived: List[int]) -> bool:
3        ans = 0
4        for num in derived:
5            ans ^= num
6
7        return ans == 0

  • Golang

    1func doesValidArrayExist(derived []int) bool {
2	ans := 0
3	for _, n := range derived {
4		ans ^= n
5	}
6
7	return ans == 0
8}

2684. 矩阵中移动的最大次数

  • BFS

  • Python

     1class Solution:
 2    def maxMoves(self, grid: List[List[int]]) -> int:
 3        direct = ((0, 1), (-1, 1), (1, 1))
 4        m, n = len(grid), len(grid[0])
 5
 6        def bfs(q):
 7            step = -1
 8            while q:
 9                size = len(q)
10                tmp = set()
11                for i in range(size):
12                    xi, xj = q[i]
13
14                    for yi, yj in direct:
15                        if 0 <= xi+yi < m and 0 <= xj+yj < n and grid[xi+yi][xj+yj] > grid[xi][xj]:
16                            tmp.add((xi+yi, xj+yj))
17                q = list(tmp)
18                step += 1
19
20            return step
21
22        ans = 0
23        for i in range(m):
24            ans = max(ans, bfs([(i, 0)]))
25            if ans == n-1:
26                break
27
28        return ans

  • Golang

     1func maxMoves(grid [][]int) int {
 2	m, n := len(grid), len(grid[0])
 3
 4	direct := [][2]int{% raw %}{{0, 1}, {1, 1}, {-1, 1}}{% endraw %}
 5
 6	bfs := func(q [][2]int) int {
 7		step := -1
 8		vis := make(map[[2]int]bool)
 9		for len(q) > 0 {
10			size := len(q)
11			for i := 0; i < size; i++ {
12
13				for _, d := range direct {
14					xi, xj := d[0]+q[0][0], d[1]+q[0][1]
15					if xi >= 0 && xi < m && xj >= 0 && xj < n && grid[xi][xj] > grid[q[0][0]][q[0][1]] && !vis[[2]int{xi, xj}] {
16						q = append(q, [2]int{xi, xj})
17						vis[[2]int{xi, xj}] = true
18					}
19				}
20				q = q[1:]
21			}
22			step++
23
24		}
25		return step
26	}
27
28	ans := 0
29	for i := 0; i < m; i++ {
30		ans = max(ans, bfs([][2]int{{i, 0}}))
31
32		if ans == n -1{
33			break
34		}
35	}
36
37	return ans
38}
39
40func max(a, b int) int {
41	if a > b {
42		return a
43	}
44	return b
45}

2685. 统计完全连通分量的数量

  • 图 DFS

  • Python

     1class Solution:
 2    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
 3        self.v = 0
 4        self.e = 0
 5
 6        # 建图
 7        g = [[] for _ in range(n)]
 8        for x, y in edges:
 9            g[x].append(y)
10            g[y].append(x)
11
12        vis = [False] * n
13
14        def dfs(x):
15            self.v += 1
16            self.e += len(g[x])
17            vis[x] = True
18
19            for y in g[x]:
20                if not vis[y]:
21                    dfs(y)
22
23        ans = 0
24        for i, r in enumerate(vis):
25            if not r:
26                self.e = 0
27                self.v = 0
28                dfs(i)
29                ans += self.e == self.v * (self.v - 1)
30
31        return ans

  • Golang

     1func countCompleteComponents(n int, edges [][]int) int {
 2	ans := 0
 3	vis := make([]bool, n)
 4	e, v := 0, 0
 5	g := make([][]int, n)
 6
 7	for _, p := range edges {
 8		g[p[0]] = append(g[p[0]], p[1])
 9		g[p[1]] = append(g[p[1]], p[0])
10	}
11
12	var dfs func(x int)
13	dfs = func(x int) {
14		vis[x] = true
15		v++
16		e += len(g[x])
17
18		for _, y := range g[x] {
19			if !vis[y] {
20				dfs(y)
21			}
22		}
23	}
24
25	for i, r := range vis {
26		e, v = 0, 0
27		if !r {
28			dfs(i)
29			if e == v*(v-1) {
30				ans++
31			}
32		}
33	}
34
35	return ans
36}