Onehr7

2682. 找出转圈游戏输家#

• 模拟

• Python

  Copy

  class Solution:
      def circularGameLosers(self, n: int, k: int) -> List[int]:
          n_set = set()
          start = 1
          i = 1
          while start not in n_set:
              n_set.add(start)
              start = (start + i * k) % n
              if start == 0:
                  start = n
              i += 1
  
          return [i for i in range(1, n+1) if i not in n_set]
  

• Golang

  Copy

  func circularGameLosers(n int, k int) []int {
  	nMap := make(map[int]bool)
  	start := 1
  	i := 1
  
  	for !nMap[start] {
  		nMap[start] = true
  		start = (start + i*k) % n
  		if start == 0 {
  			start = n
  		}
  		i++
  	}
  
  	ans := make([]int, 0)
  
  	for i := 1; i <= n; i++ {
  		if _, ok := nMap[i]; !ok {
  			ans = append(ans, i)
  		}
  	}
  
  	return ans
  }
  

2683. 相邻值的按位异或#

• 位运算

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

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

  由异或运算性质可知：

  xor = 0

• Python

  Copy

  class Solution:
      def doesValidArrayExist(self, derived: List[int]) -> bool:
          ans = 0
          for num in derived:
              ans ^= num
              
          return ans == 0
  

• Golang

  Copy

  func doesValidArrayExist(derived []int) bool {
  	ans := 0
  	for _, n := range derived {
  		ans ^= n
  	}
  
  	return ans == 0
  }
  

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

• BFS

• Python

  Copy

  class Solution:
      def maxMoves(self, grid: List[List[int]]) -> int:
          direct = ((0, 1), (-1, 1), (1, 1))
          m, n = len(grid), len(grid[0])
  
          def bfs(q):
              step = -1
              while q:
                  size = len(q)
                  tmp = set()
                  for i in range(size):
                      xi, xj = q[i]
  
                      for yi, yj in direct:
                          if 0 <= xi+yi < m and 0 <= xj+yj < n and grid[xi+yi][xj+yj] > grid[xi][xj]:
                              tmp.add((xi+yi, xj+yj))
                  q = list(tmp)
                  step += 1
  
              return step
  
          ans = 0
          for i in range(m):
              ans = max(ans, bfs([(i, 0)]))
              if ans == n-1:
                  break
  
          return ans
  

• Golang

  Copy

  func maxMoves(grid [][]int) int {
  	m, n := len(grid), len(grid[0])
  
  	direct := [][2]int{{0, 1}, {1, 1}, {-1, 1}}
  
  	bfs := func(q [][2]int) int {
  		step := -1
  		vis := make(map[[2]int]bool)
  		for len(q) > 0 {
  			size := len(q)
  			for i := 0; i < size; i++ {
  
  				for _, d := range direct {
  					xi, xj := d[0]+q[0][0], d[1]+q[0][1]
  					if xi >= 0 && xi < m && xj >= 0 && xj < n && grid[xi][xj] > grid[q[0][0]][q[0][1]] && !vis[[2]int{xi, xj}] {
  						q = append(q, [2]int{xi, xj})
  						vis[[2]int{xi, xj}] = true
  					}
  				}
  				q = q[1:]
  			}
  			step++
  
  		}
  		return step
  	}
  
  	ans := 0
  	for i := 0; i < m; i++ {
  		ans = max(ans, bfs([][2]int{{i, 0}}))
  
  		if ans == n -1{
  			break
  		}
  	}
  
  	return ans
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

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

• 图 DFS

• Python

  Copy

  class Solution:
      def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
          self.v = 0
          self.e = 0
  
          # 建图
          g = [[] for _ in range(n)]
          for x, y in edges:
              g[x].append(y)
              g[y].append(x)
  
          vis = [False] * n
  
          def dfs(x):
              self.v += 1
              self.e += len(g[x])
              vis[x] = True
  
              for y in g[x]:
                  if not vis[y]:
                      dfs(y)
  
          ans = 0
          for i, r in enumerate(vis):
              if not r:
                  self.e = 0
                  self.v = 0
                  dfs(i)
                  ans += self.e == self.v * (self.v - 1)
  
          return ans
  

• Golang

  Copy

  func countCompleteComponents(n int, edges [][]int) int {
  	ans := 0
  	vis := make([]bool, n)
  	e, v := 0, 0
  	g := make([][]int, n)
  
  	for _, p := range edges {
  		g[p[0]] = append(g[p[0]], p[1])
  		g[p[1]] = append(g[p[1]], p[0])
  	}
  
  	var dfs func(x int)
  	dfs = func(x int) {
  		vis[x] = true
  		v++
  		e += len(g[x])
  
  		for _, y := range g[x] {
  			if !vis[y] {
  				dfs(y)
  			}
  		}
  	}
  
  	for i, r := range vis {
  		e, v = 0, 0
  		if !r {
  			dfs(i)
  			if e == v*(v-1) {
  				ans++
  			}
  		}
  	}
  
  	return ans
  }