刷题记录 | 岛屿问题 + 幂集运算

岛屿数量

题目描述：

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

Python 代码如下：

class Solution:
    # 方向数组，表示了相对于当前位置的4个方向的横纵坐标的偏移量
    directions = [(-1,0),(0,-1),(1,0),(0,1)]

    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid) # 有多少行
        if m == 0:
            return 0
        n = len(grid[0]) # 有多少列
        marked = [[False for _ in range(n)] for _ in range(m)]
        count = 0
        # 从第1行、第1格，对每一个格子进行一次DFS操作
        for i in range(m):
            for j in range(n):
                # 只要是陆地，且没有被访问过，就可以使用DFS发现与之相连的陆地，并进行标记
                if not marked[i][j] and grid[i][j] == '1':
                    # count 可以理解为连通分量，可以在深度优先遍历完成以后再计数
                    count += 1
                    self.__dfs(grid, i, j, m, n, marked)
        return count

    def __dfs(self, grid, i,j, m, n, marked):
        marked[i][j] = True
        for direction in self.directions:
            new_i = i + direction[0]
            new_j = j + direction[1]
            if 0 <= new_i < m and 0 <= new_j < n and not marked[new_i][new_j] and grid[new_i][new_j] == '1':
                self.__dfs(grid, new_i, new_j, m, n, marked)

x 的 n 次幂

用迭代的思路。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            ans = 1.0
            # 贡献的初始值为 x
            x_contribute = x
            # 在对 N 进行二进制拆分的同时计算答案
            while N > 0:
                if N % 2 == 1:
                    # 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                    ans *= x_contribute
                # 将贡献不断地平方
                x_contribute *= x_contribute
                # 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
                N //= 2
            return ans
        
        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)