【LeetCode】1905 and 67（DFS解决岛屿问题4 and 二进制求和运算）

有关岛屿系列问题的求解流程可以参考【LeetCode】200 and 258（DFS解决岛屿问题）。本文继续从实例出发，熟悉⼆维矩阵的 DFS 代码框架的使用。

解决：DFS
该题对比之前文章岛屿相关问题，重点在于体会终止条件的判断，以及bool变量在回溯中的传递过程。

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m, n = len(grid1), len(grid1[0])
        res = 0
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1 and self.dfs(i, j, grid1, grid2):
                    res += 1
        return res
    def dfs(self, row, col, grid1, grid2):
        m, n = len(grid1), len(grid1[0])
        if row < 0 or row >= m or col < 0 or col >= n:
            return True
        if grid2[row][col] == 0:
            return True
        else:
            if grid1[row][col] != grid2[row][col]:
                return False
        grid2[row][col] = 0
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        result = True
        for i, j in directions:
            if not self.dfs(row+i, col+j, grid1, grid2):
                result = False
        return result

解法：模拟
我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。
值得注意的是我们要先根据较短的字符串进行计算，随后再处理较长字符串剩下的部分，整个过程维护digit变量存储进位信息。
该题求解过程我们没有反转字符串，而是利用python中倒序索引，可以借此体会一下与前序索引的不同之处。

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        result = []
        digit = 0
        if len(a) > len(b):
            a, b = b, a
        
        for i in range(-1, -1*len(a)-1, -1):
            value = int(b[i]) + int(a[i]) + digit
            digit = value // 2
            result = [str(value % 2)] + result
        for i in range(-1*len(a)-1, -1*len(b)-1, -1):
            value = int(b[i]) + digit
            digit = value // 2
            result = [str(value % 2)] + result
        if digit == 1:
            result = ['1'] + result
        return "".join(result)