345 LeetCode周赛

2682. 找出转圈游戏输家

• 模拟

• Python

  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

  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++ &#123;
          if _, ok := nMap[i]; !ok &#123;
              ans = append(ans, i)
          &#125;
      &#125;
  
      return ans
  &#125;

2683. 相邻值的按位异或

• 位运算

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

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

  由异或运算性质可知：

  xor = 0

• Python

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

• Golang

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

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

• BFS

• Python

  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

  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++ &#123;
  
                  for _, d := range direct &#123;
                      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&#123;xi, xj&#125;] &#123;
                          q = append(q, [2]int&#123;xi, xj&#125;)
                          vis[[2]int&#123;xi, xj&#125;] = true
                      &#125;
                  &#125;
                  q = q[1:]
              &#125;
              step++
  
          &#125;
          return step
      &#125;
  
      ans := 0
      for i := 0; i < m; i++ &#123;
          ans = max(ans, bfs([][2]int&#123;&#123;i, 0&#125;&#125;))
  
          if ans == n -1&#123;
              break
          &#125;
      &#125;
  
      return ans
  &#125;
  
  func max(a, b int) int &#123;
      if a > b &#123;
          return a
      &#125;
      return b
  &#125;

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

• 图 DFS

• Python

  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

  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
  }