《剑指offer》第二版

03. 数组中重复的数字

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        visited = set()
        for num in nums:
            if num in visited:
                return num
            visited.add(num)

04. 二维数组中的查找

站在右上角看

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        m, n = len(matrix), len(matrix[0])

        i, j = 0, n - 1

        while 0 <= i < m and 0 <= j < n:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1
            elif matrix[i][j] < target:
                i += 1
        
        return False

二分法的话可以对每一行二分，但是还不如按照二叉搜索树来找。

05. 替换空格

class Solution:
    def replaceSpace(self, s: str) -> str:
        words = s.split(' ')
        return '%20'.join(words)

06. 从尾到头打印链表

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        nums = []
        cur = head
        while cur:
            nums.append(cur.val)
            cur = cur.next
        
        return nums[::-1]

07. 重建二叉树（🎂）

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def recur(root, left, right):
            '''
            root: 先序遍历中的根节点坐标
            left: 中序遍历中左子树的左边界
            right: 中序遍历中右子树的右边界
            '''
            if left > right: return
            # 建立根节点
            node = TreeNode(preorder[root])
            i = dic[preorder[root]]  # 找到根节点在中序遍历中的位置
            node.left = recur(root + 1, left, i-1) # 重建左子树
            node.right = recur(i - left + root + 1, i+1, right) # 重建右子树
            return node


        dic = {
   }
        for i, num in enumerate(inorder):
            dic[num] = i
        
        return recur(0, 0, len(inorder) - 1)

剑指 Offer 09. 用两个栈实现队列

class CQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def appendTail(self, value: int) -> None:
        self.stack1.append(value)

    def deleteHead(self) -> int:
        if self.stack2:
            return self.stack2.pop()
        
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        
        if self.stack2:
            return self.stack2.pop()
        return -1

class CQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def appendTail(self, value: int) -> None:
        self.stack1.append(value)

    def deleteHead(self) -> int:
        if self.stack2:
            return self.stack2.pop()
        if not self.stack1: return -1
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        
        return self.stack2.pop()

10- I. 斐波那契数列（🎂 自己实现LRU）

class Solution:
    def fib(self, n: int) -> int:
        # 迭代
        if n < 2: return n
        a, b = 0, 1

        for _ in range(n-1):
            c = int((a + b) % (1e9+7))
            a = b
            b = c
        
        return c

class Solution:
    def fib(self, n: int) -> int:
        # 强行递归，会超时
        if n < 2: return n
        return (self.fib(n-1) + self.fib(n-2)) % (1e9+7)

class Solution:
    @lru_cache
    def fib(self, n: int) -> int:
        # 强行递归，会超时
        if n < 2: return n
        return int((self.fib(n-1) + self.fib(n-2)) % (1e9+7))

自己实现LRU_Cache

import collections

class LRU_Cache:
    def __init__(self, func):
        self.func = func
        self.cache = {
   }
    def __call__(self, *args):
        if args in self.cache:
            return self.cache[args]
        else:
            self.cache[args] = self.func(*args)
            return self.cache[args]


def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

print(fib(10))

10- II. 青蛙跳台阶问题

class Solution:
    def numWays(self, n: int) -> int:
        if n == 0: return 1
        if n <= 2: return n
        a, b = 1, 1

        for _ in range(n-1):
            c = int((a + b) % (1e9 + 7))
            a = b
            b = c
        
        return c

11. 旋转数组的最小数字（🎂）

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        # 二分法
        n = len(numbers)
        l, r = 0, n - 1

        while l < r:
            mid = l + (r - l) // 2
            # 后半段是无序, 最小值肯定在前半段
            if numbers[mid] < numbers[r]:
                r = mid
            # 后半段是有序的，但是不能确定最小值一定在后半段
            elif numbers[mid] > numbers[r]:
                l = mid + 1
            else:
                r -= 1
        
        return numbers[l]

12. 矩阵中的路径（🎂）

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if k >= len(word): return True
            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
                return False
            if not board[i][j]: return False
            board[i][j] = ''

            up = dfs(i-1, j, k+1)
            down = dfs(i+1, j, k+1)
            left = dfs(i, j-1, k+1)
            right = dfs(i, j+1, k+1)
            board[i][j] = word[k]   # 取消操作
            return up or down or left or right
        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    res = dfs(i, j, 0)
                    if res: return True
        
        return False

14- I. 剪绳子

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 拆成2，3就行了
        # 因为2只能拆成1+1，而1x1=1<2
        # 3只能拆成2+1或者1+1+1，乘积都小于3，而4就开始不一样了
        if n == 2: return 1
        if n == 3: return 2

        three_nums = n // 3
        left = n % 3

        if left == 1:
            three_nums -= 1
            left += 3
        elif left == 0:
            left = 1
        return 3 ** three_nums * left

14- II. 剪绳子 II

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 本题不可以先拆再直接算，因为中间有些值可能过大，需要取模
        if n == 2: return 1
        if n == 3: return 2

        res = 1
        while n > 0:
            if 2 <= n <= 4:
                break
            n = n - 3
            res = int((res * 3) % (1e9+7))
        
        return int((res * n) % (1e9+7))

15. 二进制中1的个数

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += n & 1
            n = n >> 1
        
        return res

16. 数值的整数次方（🎂 快速幂）

递归，但是递归会出现超出最大递归深度。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0: return 1