8.1 最小区间

原题地址.
变相的用滑动窗口法求解，统计每个数字出现在输入的哪几个数组里面，然后利用双指针滑动窗口寻找最小的左右边界，使得全部数组都有这些元素。

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        n = len(nums)
        indices = collections.defaultdict(list)
        xMin, xMax = 10**9, -10**9
        for i, vec in enumerate(nums):
            for x in vec:
                indices[x].append(i)
            xMin = min(xMin, *vec)
            xMax = max(xMax, *vec)

        freq = [0] * n
        inside = 0
        left, right = xMin, xMin - 1
        bestLeft, bestRight = xMin, xMax

        while right < xMax:
            right += 1
            if right in indices:
                #新加入统计右边界元素出现的list
                for x in indices[right]:
                    freq[x] += 1
                    #首次出现计数
                    if freq[x] == 1:
                        inside += 1
                while inside == n:
                    if right - left < bestRight - bestLeft:
                        bestLeft, bestRight = left, right
                    if left in indices:
                        for x in indices[left]:
                            freq[x] -= 1
                            #减到0推出窗口
                            if freq[x] == 0:
                                inside -= 1
                    left += 1

        return [bestLeft, bestRight]

8.2 二叉树展开为链表

原题地址.
递归处理，每次把左子树交换到右子树，把原来的右子树摘出来挂到左子树的最右儿子上，再处理下一层树。

class Solution:
    def flatten(self, root: TreeNode) -> None:
        if not root:
            return
        temp = root.right
        root.right = root.left
        root.left = None
        curr = root
        while curr.right:
            curr = curr.right
        curr.right = temp
        if root.right:
            self.flatten(root.right)
        return

8.3字符串相加

原题地址.
模拟实际加法，从右到左相加进位。

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        res = ""
        i, j, carry = len(num1) - 1, len(num2) - 1, 0
        while i >= 0 or j >= 0 or carry:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0
            tmp = n1 + n2 + carry
            carry = tmp // 10
            res = str(tmp % 10) + res
            i, j = i - 1, j - 1
        return res

8.4 课程表

原题地址.
先统计好每个课程的依赖关系，再依次消去没有以来的课程，看最后剩余与否。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegrees = [0 for _ in range(numCourses)]
        adjacency = [[] for _ in range(numCourses)]
        queue = []
        # 统计每个课程的出入度信息
        for cur, pre in prerequisites:
            indegrees[cur] += 1
            adjacency[pre].append(cur)

		#队列初始
        for i in range(len(indegrees)):
            if not indegrees[i]: queue.append(i)
        
        while queue:
            pre = queue.pop()
            numCourses -= 1
            #消去课程时，处理对应的依赖
            for cur in adjacency[pre]:
                indegrees[cur] -= 1
                if not indegrees[cur]: queue.append(cur)
        return not numCourses

8.5 打家劫舍Ⅲ

原题地址.
采用递归求解

class Solution:
    
    def dp(self , cur : TreeNode) -> List[int] :  
        #返回数组[不打劫当前根节点的最大收益，打劫根节点的最大收益]
        if not cur :
            return [0,0]
        l = self.dp(cur.left)
        r = self.dp(cur.right)
        #注意返回值的第一项，不打劫cur的话，l和r的选择就是自由的，可以选择俩者最大值
        return [max(l)+max(r),cur.val+l[0]+r[0]]
        
    def rob(self, root: TreeNode) -> int:
        return max(self.dp(root))

8.6 回文对

原题地址.
利用hash表减少枚举操作，使得快速查找有无对应字符串。

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:

        def findWord(s: str, left: int, right: int) -> int:
            return indices.get(s[left:right+1], -1)
        
        def isPalindrome(s: str, left: int, right: int) -> bool:
            return (sub := s[left:right+1]) == sub[::-1]
        
        n = len(words)
        #字符串倒序和index构成的hash表
        indices = {word[::-1]: i for i, word in enumerate(words)}
        
        ret = list()
        for i, word in enumerate(words):
            m = len(word)
            for j in range(m + 1):
                #后面是回文，寻找前半段是否存在
                if isPalindrome(word, j, m - 1):
                    leftId = findWord(word, 0, j - 1)
                    if leftId != -1 and leftId != i:
                        ret.append([i, leftId])
                #前半段回文，搜索后半段是否存在
                if j and isPalindrome(word, 0, j - 1):
                    rightId = findWord(word, j, m - 1)
                    if rightId != -1 and rightId != i:
                        ret.append([rightId, i])

        return ret

8.7 相同的树

原题地址.
利用递归思想，逐节点判断。

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

8.8 恢复二叉搜索树

原题地址.
利用二叉搜索树的中序遍历是递增序列这一特点，找到不符合条件的两个节点值交换。

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        firstNode = None
        secondNode = None
        pre = TreeNode(float("-inf"))

        stack = []
        p = root
        #迭代的中序遍历
        while p or stack:
            while p:
                stack.append(p)
                p = p.left
            p = stack.pop()
            
            #第一次出现非升序，是交换完过大的节点
            if not firstNode and pre.val > p.val:
                    firstNode = pre
            #第二次，是交换完过小的节点
            if firstNode and pre.val > p.val:
                secondNode = p
            pre = p
            p = p.right
        firstNode.val, secondNode.val = secondNode.val, firstNode.val

8.9 复原ip地址

原题地址.
dfs搜索

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        SEG_COUNT = 4
        ans = list()
        segments = [0] * SEG_COUNT
        
        def dfs(segId: int, segStart: int):
            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if segId == SEG_COUNT:
                if segStart == len(s):
                    ipAddr = ".".join(str(seg) for seg in segments)
                    ans.append(ipAddr)
                return
            
            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
            if segStart == len(s):
                return

            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if s[segStart] == "0":
                segments[segId] = 0
                dfs(segId + 1, segStart + 1)
            
            # 一般情况，枚举每一种可能性并递归
            addr = 0
            for segEnd in range(segStart, len(s)):
                addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
                if 0 < addr <= 255:
                    segments[segId] = addr
                    dfs(segId + 1, segEnd + 1)
                else:
                    break
        

        dfs(0, 0)
        return ans

8.10 计数二进制字串

只需要统计连续的0和1的长度，那么相邻的符合条件字符串就是两者最小长度。

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        n = len(s)
        pre = 0
        cur = 1
        res = 0
        for i in range(1,n):
            if s[i] == s[i-1]:
                cur += 1
            else:
                res += min(pre,cur)
                pre = cur
                cur = 1
        return res + min(pre,cur)

8.11 被围绕的区域

原题地址.
考虑没有被围住的O,肯定有一条连接到边缘的路径，既可以由边缘dfs访问到。

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:
            return
        
        n, m = len(board), len(board[0])

        def dfs(x, y):
            if not 0 <= x < n or not 0 <= y < m or board[x][y] != 'O':
                return
            
            board[x][y] = "A"
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)
        #由区域边缘联通的节点是没有被围住的。所以会dfs访问到，设标记为A
        for i in range(n):
            dfs(i, 0)
            dfs(i, m - 1)
        
        for i in range(m - 1):
            dfs(0, i)
            dfs(n - 1, i)
        
        for i in range(n):
            for j in range(m):
                if board[i][j] == "A":
                    board[i][j] = "O"
                elif board[i][j] == "O":
                    board[i][j] = "X"

8.12克隆图

原题地址.
用图的dfs遍历方法，遍历图完成复制。

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        #以访问记录表
        self.visited = {}
        #dfs递归函数
        def dfs(node):
            if not node:
                return node
            if node in self.visited:
                return self.visited[node]
            #深拷贝
            clone_node = Node(node.val, [])
            self.visited[node] = clone_node
            #递归构建相邻节点
            if node.neighbors:
                clone_node.neighbors = [dfs(n) for n in node.neighbors]
            return clone_node
        return dfs(node)

8.13字符串相乘

原题地址.
模拟分步的乘法操作，把多项结果相加求和。

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        
        ans = "0"
        m, n = len(num1), len(num2)
        for i in range(n - 1, -1, -1):
            add = 0
            y = int(num2[i])
            curr = ["0"] * (n - i - 1)
            #单独一项
            for j in range(m - 1, -1, -1):
                product = int(num1[j]) * y + add
                curr.append(str(product % 10))
                add = product // 10
            #最高位进位
            if add > 0:
                curr.append(str(add))
            curr = "".join(curr[::-1])
            ans = self.addStrings(ans, curr)
        
        return ans
    #字符串加法
    def addStrings(self, num1: str, num2: str) -> str:
        i, j = len(num1) - 1, len(num2) - 1
        add = 0
        ans = list()
        while i >= 0 or j >= 0 or add != 0:
            x = int(num1[i]) if i >= 0 else 0
            y = int(num2[j]) if j >= 0 else 0
            result = x + y + add
            ans.append(str(result % 10))
            add = result // 10
            i -= 1
            j -= 1
        return "".join(ans[::-1])

8.14 有效的括号

原题地址.
使用栈结构，判断括号能否对应起来。

class Solution:
    def isValid(self, s: str) -> bool:
        mapping = {')':'(',']':'[','}':'{'}
        stack = []
        for x in s:
            if x not in mapping.keys():
                stack.append(x)
            else:
                if not stack:
                    return False
                if stack.pop() != mapping[x]:
                    return False
        if stack:
            return False
        return True

8.15 移除盒子

原题地址.
采用动态规划，难点在于转移方程，因为子问题的约减和一般的不同。

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        n = len(boxes)
        #初始化
        dp = [[[0]*n for _ in range(n)] for _ in range(n)]
        #i,j为数组边界，k为与i代表元相等的元素个数
        def dfs(boxes,i,j,k,dp):
            if i > j:
                return 0
            if dp[i][j][k] > 0:
                return dp[i][j][k]
            while i < j and boxes[i] == boxes[i+1]:
                i += 1
                k += 1
            #左部分消去
            res = (k+1)*(k+1) + dfs(boxes,i+1,j,0,dp)
            #子问题求解
            for m in range(i+1,j+1):
                if boxes[m] == boxes[i]:
                    res = max(res,dfs(boxes,i+1,m-1,0,dp)+dfs(boxes,m,j,k+1,dp))
            dp[i][j][k] = res
            return res
        
        return dfs(boxes,0,n-1,0,dp)

8.16 图像渲染

原题地址.
常规的深度或者广度遍历即可。

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        def dfs(x,y):
            if image[x][y] == currColor:
                image[x][y] = newColor
            for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:
                        dfs(mx, my)
            
        n, m = len(image), len(image[0])
        currColor = image[sr][sc]
        if currColor != newColor:
            dfs(sr, sc)
        return image

8.17平衡二叉树

原题地址.
递归搜索，利用剪枝优化。

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.isBalancedHelper(root)[0]

    def isBalancedHelper(self,root):
        if not root:
            return True, -1
        
        #两段提前终止返回
        leftIsBalanced, leftHeight = self.isBalancedHelper(root.left)
        if not leftIsBalanced:
            return False,0
        rightIsBalanced, rightHeight = self.isBalancedHelper(root.right)
        if not rightIsBalanced:
            return False, 0

        return abs(leftHeight-rightHeight) <= 1,1+max(leftHeight,rightHeight)

8.18有序链表转换二叉搜索树

原题地址.
和从数组重建差不多，就是右边界的确定需要调整一下。

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
    	#需要确定右边界
        def getMedian(left: ListNode, right: ListNode) -> ListNode:
            fast = slow = left
            while fast != right and fast.next != right:
                fast = fast.next.next
                slow = slow.next
            return slow
        
        def buildTree(left: ListNode, right: ListNode) -> TreeNode:
            if left == right:
                return None
            mid = getMedian(left, right)
            root = TreeNode(mid.val)
            root.left = buildTree(left, mid)
            root.right = buildTree(mid.next, right)
            return root
        
        return buildTree(head, None)

8.19回文子串

原题地址.
暴力中心扩展

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        out = 0
        #遍历中心位置
        for i in range(2*n -1):
            l = i//2
            r = l + i%2
            #扩展
            while l >= 0 and r < n and s[l] == s[r]:
                out += 1
                l -= 1
                r += 1
        return out

8.20 扫雷游戏

原题地址.
模拟运行，分情况处理。

# DFS
class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        # 定义 8 个方位
        dx = [-1, -1, -1, 0, 1, 1, 1, 0] 
        dy = [-1, 0, 1, 1, 1, 0, -1, -1]

        m = len(board)
        n = len(board[0])

        def in_board(x, y):
            """判断坐标是否在限定边界内
            """
            return 0 <= x < m and 0 <= y < n

        def dfs(x, y):
            count = 0
            # 先判断相邻(8 个方位)的方块是否含有***
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]
                # 如果相邻方块都在限定范围内，且含有***，统计***数
                if in_board(nx, ny) and board[nx][ny] == 'M':
                    count += 1
            if count > 0:
                # 含有***，修改当前点为数字对应***数，返回
                board[x][y] = str(count)
                return
            # 如果相邻方块不含***，修改为 'B'
            # 并向相邻位置扩散搜索
            board[x][y] = 'B'
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]
                if in_board(nx, ny) and board[nx][ny] == 'E':
                    dfs(nx, ny)

        x, y = click

        # 如果当前点击的是未挖出的***，那么将其修改为 'X'，返回
        if board[x][y] == 'M':
            board[x][y] = 'X'
        else:
            # 当点击的是未挖出的方块，分情况讨论
            dfs(x, y)

        return board

8.21 二叉树的最小深度

原题地址.
递归的搜索，但是需要注意有一个儿子为空的状况。

class Solution:
    def minDepth(self, root):
        if not root:
            return 0
        l = self.minDepth(root.left)
        r = self.minDepth(root.right)
        #有且只有一个儿子是空，需要再另外一个路径搜索。
        if not all([l,r]) and any([l,r]):
            return max(l,r) + 1
        else:
            return min(l,r) + 1

8.22 24点游戏

原题地址.
模拟真实操作，运用回溯法处理。

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        TARGET = 24
        EPSILON = 1e-6
        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3

        def solve(nums: List[float]) -> bool:
            if not nums:
                return False
            if len(nums) == 1:
                return abs(nums[0] - TARGET) < EPSILON
            for i, x in enumerate(nums):
                for j, y in enumerate(nums):
                    if i != j:
                        newNums = list()
                        for k, z in enumerate(nums):
                            if k != i and k != j:
                                newNums.append(z)
                        for k in range(4):
                            if k < 2 and i > j:
                                continue
                            if k == ADD:
                                newNums.append(x + y)
                            elif k == MULTIPLY:
                                newNums.append(x * y)
                            elif k == SUBTRACT:
                                newNums.append(x - y)
                            elif k == DIVIDE:
                                if abs(y) < EPSILON:
                                    continue
                                newNums.append(x / y)
                            if solve(newNums):
                                return True
                            newNums.pop()
            return False

        return solve(nums)

8.23 数字范围按位与

原题地址.
找到边界数字的公共前缀即可。

class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        shift = 0   
        # 找到公共前缀
        while m != n:
            m = m >> 1
            n = n >> 1
            shift += 1
        return m << shift

8.24 重复的子字符串

原题地址.
枚举所有可能的长度进行判断。

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for i in range(1, n // 2 + 1):
            if n % i == 0:
                if all(s[j] == s[j - i] for j in range(i, n)):
                    return True
        return False

8.25 递增子序列

原题地址.
采用遍历，不断往现有答案后面增加元素，注意set添加元素用能用list，要改用tuple

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        pres = {(nums[0], )}
        for i in nums[1:]:
            pres.update({j+(i, ) for j in pres if j[-1] <= i})
            pres.add((i, ))
        return list([list(i) for i in pres if len(i) > 1])

8.26电话号码的字母组合

原题地址.
模拟遍历即可。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone = {'2': ['a', 'b', 'c'],
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']}
        if not digits:
            return []
        out = ['']
        for c in digits:
            temp = []
            for short in out:
                for x in phone[c]:
                    temp.append(short+x)
            out = temp
        return out

8.27 重新安排行程

题目条件假设了一定存在，dfs一边搜索一边删除用过的边即可。

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        #转变为图结构存储
        vec = collections.defaultdict(list)
        for depart, arrive in tickets:
            vec[depart].append(arrive)
        for key in vec:
            heapq.heapify(vec[key])
        #dfs搜索
        def dfs(curr: str):
            while vec[curr]:
                tmp = heapq.heappop(vec[curr])
                dfs(tmp)
            stack.append(curr)
        

        stack = list()
        dfs("JFK")
        return stack[::-1]

8.28 机器人能否返回原点

原题地址.
简单计数即可。

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        steps = [0,0]
        for c in moves:
            if c == 'U':
                steps[0] += 1
            elif c == 'D':
                steps[0] -= 1
            elif c == 'L':
                steps[1] += 1            
            elif c == 'R':
                steps[1] -= 1
        return not(steps[0] or steps[1])

8.29 最短回文串

原题地址.
借助字符串匹配，找到s前缀最长的回文子串，剩下部分的逆序就是要求的附加字串。

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        fail = [-1] * n
        #next数组计算
        for i in range(1, n):
            j = fail[i - 1]
            while j != -1 and s[j + 1] != s[i]:
                j = fail[j]
            if s[j + 1] == s[i]:
                fail[i] = j + 1
        
        best = -1
        for i in range(n - 1, -1, -1):
            while best != -1 and s[best + 1] != s[i]:
                best = fail[best]
            if s[best + 1] == s[i]:
                best += 1

        add = ("" if best == n - 1 else s[best+1:])
        return add[::-1] + s

8.30 反转字符串中的单词

原题地址.
再转每个单词再反转整个字符串，

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(s.split(' ')[::-1])[::-1]

8.31 钥匙和房间

当成图结构来进行遍历处理

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(i):
            nonlocal num
            vis.add(i)
            num += 1
            for nxt in rooms[i]:
                if nxt not in vis:
                    dfs(nxt)

        n = len(rooms)
        num = 0
        vis = set()
        dfs(0)
        return num == n