精选留言(4)

• 
  陈志恒

  2019-09-28

  如果问题能够抽象为两两关系，那么可以尝试使用并查集解决
  
  抽象为并查集解决的步骤：
  1.并查集初始化
  2.元素合并union（建立两两之间的一对一联系）
  3.查找find

  展开

  

   1
• 
  Hc_Zzz

  2019-08-05

  朋友圈那題如果有union-find做的話：
  ```
  class Solution:
      def findCircleNum(self, M: List[List[int]]) -> int:
          if not M:
              return
          row, col = len(M), len(M[0])
          self.count = len(M)
          friends = [i for i in range(row)]
          # find
          def find(x):
              if friends[x] != x:
                  return find(friends[x])
              return friends[x]
          # unio
          def union(x, y):
              xroot, yroot = find(x), find(y)
              if xroot == yroot:
                  return
              friends[xroot] = yroot
              self.count -= 1
  
          for i in range(row):
              for j in range(col):
                  # handle only half the chart
                  if i < j and M[i][j] == 1:
                      union(i, j)
          return self.count
  
  ```
  
  

  展开

  

   1
• 
  Sun0010

  2019-10-23

  func numIslands(_ g: [[Character]]) -> Int {
          
          var grid = g
          var count = 0
          
          if grid.count == 0 {
              return 0
          }
      
          
          let Rows = grid.count
          let Cols = grid.first?.count ?? 0
          
          
          for i in 0..<Rows {
              for j in 0..<Cols {
                  if grid[i][j] == "1" {
                      count += 1
                      renderOneToZero(&grid,Rows: Rows,Cols: Cols,i: i,j: j)
                  }
              }
          }
          
          return count
      }
      
      func renderOneToZero(_ grid: inout [[Character]], Rows:Int,Cols:Int, i:Int, j:Int) {
          
          if i >= Rows || j >= Cols || i < 0 || j < 0 {
              return
          }
          
          if grid[i][j] == "1" {
              grid[i][j] = "0"
              //把 上 左 下 右
              //左
              renderOneToZero(&grid, Rows: Rows, Cols: Cols, i: i, j: j-1)
              //右
              renderOneToZero(&grid, Rows: Rows, Cols: Cols, i: i , j: j + 1)
              //上
              renderOneToZero(&grid, Rows: Rows, Cols: Cols, i: i - 1 , j: j)
              //下面
              renderOneToZero(&grid, Rows: Rows, Cols: Cols, i: i + 1 , j: j)
          }
      }

  展开

  

  
• 
  原

  2019-06-28

  朋友圈问题不能转化成求岛屿个数问题，比如三个人的朋友圈，AC互相认识，B只认识自己，输入如下所示：
  [[1, 0, 1],
   [0, 1, 0],
   [1, 0, 1]]
  这要统计岛屿岂不是有5个？！
  

   1

  