抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

53 | 面试题:岛屿的个数

200. 岛屿数量

解法一:染色 FloodFill

写一个循环,遍历所有的节点,是1(陆地)的话,将count++,同时节点和附近节点都变成0(染色),依次递归。

实现方式:

  1. DFS:对任意一个为1的节点,上下左右递归扩散,将周围的1改为0。
  2. BFS:将 queue 放去队列,相邻的节点也放入 queue,把 queue 中的元素都变成0.

Kotlin 版( DFS ):
代码中有很多可优化的地方,如:可使用 String 替换 Pair、精简重复的定义等,这里是为了方便理解。

可解释的地方:

  1. dx,dy 用于动态变换坐标
  2. isValid用于判断是否越界以及忽略为‘0’的元素和访问过的元素
class Solution {
    lateinit var grid: Array<CharArray>
    val visited = HashSet<Pair<Int, Int>>()
    val dx = intArrayOf(-1, 1, 0, 0)
    val dy = intArrayOf(0, 0, -1, 1)

    fun numIslands(grid: Array<CharArray>): Int {
        if (grid.isNullOrEmpty()) return 0
        if (grid[0].isEmpty()) return 0
        val maxX = grid.size
        val maxY = grid[0].size
        this.grid = grid

        var sum = 0
        for (i in 0 until maxX) {
            for (j in 0 until maxY) {
                sum += floodfill_DFS(i, j)
            }
        }
        return sum
    }

    private fun floodfill_DFS(x: Int, y: Int): Int {
        return when {
            isValid(x, y) -> {
                visited.add(Pair(x, y))
                for (k in 0 until 4) {
                    floodfill_DFS(x + dx[k], y + dy[k])
                }
                1
            }
            else -> {
                0
            }
        }
    }

    private fun isValid(x: Int, y: Int): Boolean {
        val maxX = grid.size
        val maxY = grid[0].size
        if (x < 0 || x >= maxX || y < 0 || y >= maxY) return false
        if (grid[x][y] == '0' || Pair(x, y) in visited) return false
        return true
    }

}

Kotlin(BFS)版:这里就只贴 BFS 代码块了,其余部分除调用 floodfill_DFS 改为 floodfill_BFS 外并无不同。

private fun floodfill_BFS(x: Int, y: Int): Int {
if (!isValid(x, y)) {
return 0
} else {
val element = Pair(x, y)
visited.add(element)
val queue = ArrayDeque<Pair<Int, Int>>()
queue.add(element)

while (queue.isNotEmpty()) {
val (curX, curY) = queue.pollFirst()
for (k in 0 until 4) {
val newX = curX + dx[k]
val newY = curY + dy[k]
if (isValid(newX, newY)) {
val pair = Pair(newX, newY)
visited.add(pair)
queue.add(pair)
}
}
}
return 1
}

}

解法二:并查集

  1. 把每个为1的元素,将其 parent 赋值为它自己。遍历所有的节点,相邻则合并。
  2. 遍历查询有多少个 root 即可,此处可合并至上一步中。

Kotlin 版:rank 是一个高度数组,是一种按秩合并的加速手段

class Solution {

    fun numIslands(grid: Array<CharArray>): Int {
        if (grid.isNullOrEmpty()) return 0
        if (grid[0].isEmpty()) return 0

        val m = grid.size
        val n = grid[0].size

        val direction = arrayOf(Pair(0, 1), Pair(0, -1), Pair(-1, 0), Pair(1, 0))

        val uf = UnionFind(grid)

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid[i][j] == '0') continue
                direction.forEach { (dx, dy) ->
                    val ni = i + dx
                    val nj = j + dy
                    if (ni >= 0 && nj >= 0 && ni < m && nj < n && grid[ni][nj] == '1') {
                        //坐标合法,合并
                        //i * n + j 之前的节点 二维转一维
                        //ni * n + nj 不同方向的新节点 二维转一维
                        uf.union(i * n + j, ni * n + nj)
                    }
                }
            }
        }
        return uf.count
    }

    class UnionFind(grid: Array<CharArray>) {

        val m = grid.size
        val n = grid[0].size
        var count = 0
        val parent = IntArray(m * n) { -1 }
        val rank = IntArray(m * n) { 0 }

        init {
            for (i in 0 until m)
                for (j in 0 until n ){
                    if (grid[i][j]=='1'){
                        parent[i*n +j]=i*n +j
                        count++
                    }
                }
        }

        fun findRoot(i: Int): Int {
            if (parent[i]!=i){
                parent[i]=findRoot(parent[i])
            }
            return parent[i]
        }

        fun union(p: Int, q: Int) {
            val rootP = findRoot(p)
            val rootQ = findRoot(q)

            if (rootP!=rootQ){
                when {
                    rank[rootP]>rank[rootQ] -> {
                        parent[rootQ]=rootP
                    }
                    rank[rootP]>rank[rootQ] -> {
                        parent[rootP]=rootQ
                    }
                    else -> {
                        parent[rootQ]=rootP
                        rank[rootP]++
                    }
                }
                count--
            }
        }

    }

}

0条评论

发表评论