剑指Offer(Python版本)

面试题03. 数组中重复的数字

# 法一
# 使用Counter统计，找到重复即可
from collections import Counter
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        c = Counter(nums)
        return c.most_common()[0][0]
# 法二
# 哈希法 时间O(n)空间O(n)，如果字典中有记录，那么直接返回
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        repeat_dict = {}
        for num in nums:
            if num not in repeat_dict:
                repeat_dict[num] = 1
            else:
                return num
# 法三，评论区获得
# 原地哈希 时间O（n）空间O（1）
class Solution:
    def findRepeatNumber(self, nums) -> int:
        for i in range(len(nums)):
            while i != nums[i]:
                if nums[i] == nums[nums[i]]:
                    return nums[i]
                temp = nums[i]
                nums[i], nums[temp] = nums[temp], nums[i]
            #   注意这里不要写成nums[i], nums[nums[i]] = nums[nums[i]], nums[i] Python这么写会有问题

面试题04. 二维数组中的查找

# 从右上角开始走，小于目标值行加1，大于目标值列减一，注意边界
class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        column = len(matrix[0])-1
        row = 0
        rows = len(matrix) # 包括只有一行的特殊情况
        if target > matrix[rows-1][column]: # 如果比矩阵最大值还大，那么直接返回
            return False
        if target < matrix[0][0]:  # 如果比矩阵最小值还小，直接返回
            return False
        while(row < rows and column >= 0):
            if target == matrix[row][column]:  # 找到了~
                return True
            elif target > matrix[row][column]:  # 目标值更大，那么往下走
                row += 1
            elif target < matrix[row][column]:  # 目标值更小，那么往左走
                column -=1
        return False  # 没找到，返回False

面试题06. 从尾到头打印链表

# 法一
# 递归-时间换空间，不占用额外空间
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if not head:
            return []
        return self.reversePrint(head.next) + [head.val]
# 法二
# 使用额外空间，空间换时间
class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        res = []
        while head:
            res.append(head.val)
            head=head.next
        return res[::-1]

面试题07. 重建二叉树

需注意边界idx

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(inorder) == 0:
            return None
        
        # 根节点，前序遍历第一个就是根
        root = TreeNode(preorder[0])
        # 获取根节点在 inorder 中的索引
        idx = inorder.index(preorder[0])
        # 左子树，边界条件，除去根节点
        root.left = self.buildTree(preorder[1:idx+1], inorder[:idx])
        # 右子树，边界条件，除去根节点
        root.right = self.buildTree(preorder[idx+1:], inorder[idx+1:])
        return root

面试题09. 用两个栈实现队列

class CQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def appendTail(self, value: int) -> None:
        self.stack1.insert(0, value)
        return None
    def deleteHead(self) -> int:
        if not self.stack1:
            return -1
        return self.stack1.pop()
        


# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

面试题10- I. 斐波那契数列

from functools import lru_cache
class Solution:
    @lru_cache(None) # 评论获得，不然递归超过最大深度
    def fib(self, n: int) -> int:
        if n<2:
            return n
        return (self.fib(n-1)+self.fib(n-2))%1000000007
# 动态规划
class Solution:
    def fib(self, n: int) -> int:
        dp={}
        dp[0] = 0  # 初始条件
        dp[1] = 1  # 初始条件
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return int(dp[n]%(1000000007))

面试题10- II. 青蛙跳台阶问题

dp[0]=1
dp[1]=1

面试题11. 旋转数组的最小数字

# 二分法
# 比较右侧值
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        left = 0
        right = len(numbers)-1
        while left<right:
            mid = (left+right)//2
            if numbers[mid]>numbers[right]:
                left = mid+1
            elif numbers[mid]<numbers[right]:
                right = mid  # 注意left和right
            else : right -= 1  # 相等的情况
        return numbers[left]  # 注意return

面试题12- 矩阵中的路径

# DFS+回溯，参考LeetCode题解
class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        def dfs(i, j, k):
            if not 0<=i<len(board) or not 0<=j<len(board[0]) or board[i][j]!=word[k]: return False  # i、j超界,并且字符不相等
            if len(word)-1 == k: return True  # 比较到了最后一个字符
            tmp, board[i][j] = board[i][j], '/'  # 走过的路径用'/'标记
            res = dfs(i-1, j, k+1) or dfs(i+1,j, k+1) or dfs(i, j-1, k+1) or dfs(i, j+1, k+1)  # 分别往左、右、上、下走
            board[i][j] = tmp  # 还原状态
            return res
        for i in range(len(board)):  # 所有格子都走
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True
        return False  # 不存在路径

面试题13. 机器人的运动范围

  • DFS, numsum为数位和，往右下方向走
  • 最差情况 时间O（MN），遍历所有
  • 最差情况，空间O（MN）矩阵存储单元格所有索引
  • DFS
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def numsum(x):
            s=0
            while x:
                s+=x%10
                x=x//10
            return s
        def dfs(i,j,si,sj):
            if not 0<=i<m or not 0<=j<n or si+sj>k or (i,j) in visited: return 0
            visited.add((i,j))
            return 1+dfs(i+1,j,si+numsum(si),sj)+dfs(i,j+1,si,sj+numsum(sj))
        visited=set()
        return dfs(0,0,0,0)
  • BFS，时空如上
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        queue, visited,  = [(0, 0, 0, 0)], set()
        while queue:
            i, j, si, sj = queue.pop(0)
            if not 0 <= i < m or not 0 <= j < n or k < si + sj or (i, j) in visited: continue
            visited.add((i,j))
            queue.append((i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj))
            queue.append((i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8))
        return len(visited)

面试题14- I. 剪绳子

from collections import defaultdict
class Solution:
    def cuttingRope(self, n: int) -> int:
        dp=defaultdict(int)
        dp[1]=1
        dp[2]=1
        for i in range(3, n+1):
            for j in range(i):
                dp[i] = max(dp[i], (i-j)*j, j*dp[i-j])
        return dp[n]
    # dp[i]维持原状态不剪
    # j*(i-j)从j剪一刀后不剪
    # j*dp[i-j]从j剪一刀后再剪

动态规划优化，原地 时间O（N）空间O（1），LeetCode题解中获得。

  • 我们发现任何大于 3 的数都可以拆分为数字 1，2，3 的和，且它们对 3 的余数总是 0，1，2，因此我们可以仅用 dp[0]，dp[1]，dp[2] 表示所有大于 3 的值，这样空间复杂度可降到 O(1)。
class Solution:
    def cuttingRope(self, n):
        dp = [0, 1, 1]

        for i in range(3, n + 1):
            dp[i % 3] = max(max(dp[(i - 1) % 3], i - 1),
                    2 * max(dp[(i - 2) % 3], i - 2),
                    3 * max(dp[(i - 3) % 3], i - 3))
        return dp[n % 3]

面试题16. 数值的整数次方

# 法一
# 递归形式
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1

        if n < 0:  # 把负指数转为正，同时x取倒数
            return 1 / self.myPow(x, -n)

        # 如果是奇数
        if n & 1:
            return x * self.myPow(x, n - 1)
        return self.myPow(x * x, n >> 1)
# 法二
# 非递归

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            # 负数变成正数
            n = -n

        res = 1
        while n:
            if n & 1:  # 如果n为奇数
                res *= x
            x *= x
            n >>= 1
        return res

面试题18. 删除链表的节点

# 假头 用了额外空间
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        prior = ListNode(-1)
        prior.next = head
        p = prior
        while head:
            if head.val == val:
                prior.next = prior.next.next
            head = head.next
            prior = prior.next
        return p.next
# 双指针 不用额外空间 时间O（N）
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head.val == val: return head.next  # 判断链表头
        pre, cur = head, head.next  # 双指针
        while cur and cur.val != val:
            pre, cur = cur, cur.next
        pre.next = cur.next 
        return head

面试题21. 调整数组顺序使奇数位于偶数前面

# 评论区的一行大法
return sorted(nums,key=lambda x:1-x%2)

面试题22. 链表中倒数第k个节点

# 双指针 快指针先跑k，然后一起跑，慢指针就到k了
class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        fast = head
        for i in range(k): # 快指针跑到k
            fast = fast.next
        while fast:  # 快、慢指针一起跑
            head = head.next
            fast = fast.next
        return head

面试题24. 反转链表

# 法一，常规做法
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head: return None
        
        new = ListNode(head.val) # 处理结尾多出的NULL
        cur = head.next
        
        while cur:
            temp = cur.next
            cur.next = new
            new = cur
            cur = temp
        return new
# 法二
# 先存为List，然后重新构造链表
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        res = []
        p = new = ListNode(None)
        while head:  # 值存入List
            res.append(head.val)
            head = head.next
        while res:  # 重新构造链表，反向
            new.next = ListNode(res.pop())
            new = new.next
        return p.next

面试题25. 合并两个排序的链表

# 递归
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    if not l1:  # l1为空，直接把l2拼接在后
        return l2
    if not l2:  # l2为空，直接把l1拼接在后
        return l1
    pre = None  # 新链表
    if l1.val < l2.val:  # 谁小把谁拼接在后
        pre = l1
        pre.next = self.mergeTwoLists(l1.next, l2)
    else:
        pre = l2
        pre.next = self.mergeTwoLists(l1, l2.next)
    return pre

面试题26. 树的子结构

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not A or not B:  # 题目中说空树不是子结构
            return False
        if A.val != B.val:  # 如过值不相等，那么A移动比较
            return self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)
        else:  # 值相等，开始判断子结构
            return self.helper(A,B)
    def helper(self, a, b):  # 判断子结构
        if not b:  # a分支节点可以大于等于b，但一定不能小于
            return True
        if not a:  # 如果a为空，b不为空，那么不是子结构，所以一定要先判断b
            return False
        if a.val != b.val:  # 如果值不等也不是子结构
            return False
        return self.helper(a.left, b.left) and self.helper(a.right, b.right)  #左和左比较，右和右比较

面试题27. 二叉树的镜像

# 法一
# 递归
class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return None
        root.left, root.right = self.mirrorTree(root.right), self.mirrorTree(root.left)
        return root
# 法二
# 迭代-涉及到树的都差不多写法
class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return []
        stack = [root]
        while stack:
            nextStack = []
            while stack:
                node = stack.pop(0)
                node.left, node.right = node.right, node.left
                if node.left: nextStack.append(node.left)
                if node.right: nextStack.append(node.right)
            stack = nextStack
        return root

面试题28. 对称的二叉树

# 递归
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:return True  # 空树
        return self.helper(root, root)
    def helper(self, root1, root2):
        if not root1 and not root2:  # 左树为空，右树为空
            return True
        if not root1 and root2:  # 左树为空，右树非空，不对称
            return False
        if root1 and not root2:  # 左树非空，右树为空，不对称
            return False
        if root1.val != root2.val:  # 值不等，也不对称
            return False
        return self.helper(root1.left, root2.right) and self.helper(root1.right, root2.left)

面试题29. 顺时针打印矩阵

  • 将矩阵第一行的元素添加到res列表里，删除第一行（也就是matrix中的第一个列表），然后逆时针旋转（这里通过转置+倒序实现），新的matrix的第一行即为接下来要打印的元素。
# LeetCode题解思路，矩阵逆时针旋转
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)  # 弹出最前列表
            matrix = list(zip(*matrix))[::-1]
        return res

面试题30. 包含min函数的栈

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minStack = []
    def push(self, x: int) -> None:
        self.stack.append(x)  # 正常栈，正常压入
        if not self.minStack: self.minStack.append(x)  # 如果辅助栈为空，不比较直接压入
        else: 
            if x > self.minStack[-1]:  # 压入元素和栈顶元素比较，如果压入元素大，那么复制栈顶元素，如果压入元素小，将小元素压入
                self.minStack.append(self.minStack[-1])
            else: self.minStack.append(x)
        
    def pop(self) -> None:  # 两个栈同时弹出
        self.stack.pop()
        self.minStack.pop()
    def top(self) -> int:
        return self.stack[-1]
    def min(self) -> int:
        return self.minStack[-1]

面试题31. 栈的压入、弹出序列

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        j = 0
        for x in pushed:
            stack.append(x)
            while stack and j<len(popped) and stack[-1] == popped[j]:
                stack.pop()
                j+=1
        return not stack

面试题33. 二叉搜索树的后序遍历序列

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if not postorder: return True
        def helper(nums):
            if len(nums) <= 1: return True
            root = nums[-1]
            for i in range(len(nums)):
                if nums[i] > root: break # 取得比根节点大的i值
            for j in range(i, len(nums)-1):# 除去根节点
                if nums[j] < root: return False
            return helper(nums[:i]) and helper(nums[i:-1]) # -1为除去根节点
        return helper(postorder)

面试题34. 二叉树中和为某一值的路径

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import copy
class Solution:
    def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:
        res = []
        temp = []
        def helper(root,sum_):
            if not root: return
            if not root.left and not root.right: # #判断是否为叶节点
                temp.append(root.val)
                if sum(temp) == sum_: # # 满足条件,则添加到最终结果中
                    res.append(copy.deepcopy(temp)) # 此处为深拷贝，不然temp的操作会影响res
                temp.pop()
                return 
            temp.append(root.val) # 进栈
            helper(root.left, sum_)
            helper(root.right, sum_)
            temp.pop() # 出栈
        helper(root, sum_)
        return res

面试题36. 二叉搜索树与双向链表

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root: return 
        def change_ptr(root, node): # 改造中序遍历
            if not root: return node
            node = change_ptr(root.left, node)
            node.right = root
            root.left = node
            node = root
            node = change_ptr(root.right, node)
            return node
        visual_head = Node(0) # 假结点，用于调用函数
        tail = change_ptr(root,visual_head)
        head = visual_head.right
        head.left = tail
        tail.right = head
        return head

面试题38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例: 输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]

class Solution:
    def permutation(self, s: str) -> List[str]:
        c, res = list(s), []
        def dfs(x):
            if x == len(c) - 1:
                res.append(''.join(c)) # 添加排列方案
                return
            dic = set()
            for i in range(x, len(c)):
                if c[i] in dic: continue # 重复，因此剪枝
                dic.add(c[i])
                c[i], c[x] = c[x], c[i] # 交换，固定此位为 c[i] 
                dfs(x + 1) # 开启固定第 x + 1 位字符
                c[i], c[x] = c[x], c[i] # 恢复交换
        dfs(0)
        return res

面试题39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2

  • 法一：需要的数字出现次数多于一半 那么排序后必定在中间, 时间O(nlogn)，空间O(1)
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums = sorted(nums)
        return nums[len(nums)//2]
  • 法二：字典统计：略
  • 法三：摩尔投票法 时间O(n)，空间O(1)
    • 也可以理解成混战极限一换一，不同的两者一旦遇见就同归于尽，最后活下来的值都是相同的，即要求的结果
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        vote = 0
        for num in nums:
            if vote == 0: x=num  # 注意这里没有else,保证vote=1
            if x==num:
                vote+=1 
            else:
                vote-=1
        return x

面试题41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例 1：

输入： ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]] 输出：[null,null,null,1.50000,null,2.00000] 示例 2：

输入： ["MedianFinder","addNum","findMedian","addNum","findMedian"] [[],[2],[],[3],[]] 输出：[null,null,2.00000,null,2.50000]

  • 常规做法，因为排序时间nlogn 空间n
class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.store = []

    def addNum(self, num: int) -> None:
        self.store.append(num)

    def findMedian(self) -> float:
        self.store.sort()
        n = len(self.store)
        if n & 1 == 1: # n 是奇数
            return self.store[n // 2]
        else:
            return (self.store[n // 2 - 1] + self.store[n // 2]) / 2
  • 用堆，Python只有小顶堆，值取负来模拟大顶堆
class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        # 初始化大顶堆和小顶堆
        self.max_heap = []
        self.min_heap = []

    def addNum(self, num: int) -> None:
        if len(self.max_heap) == len(self.min_heap):# 先加到大顶堆，再把大堆顶元素加到小顶堆
            heapq.heappush(self.min_heap, -heapq.heappushpop(self.max_heap, -num))
        else:  # 先加到小顶堆，再把小堆顶元素加到大顶堆
            heapq.heappush(self.max_heap, -heapq.heappushpop(self.min_heap, num))

    def findMedian(self) -> float:
        if len(self.min_heap) == len(self.max_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2
        else:
            return self.min_heap[0]

面试题42. 连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

动态规划解析：
状态定义： 设动态规划列表 dp ，dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。

为何定义最大和 dp[i] 中必须包含元素 nums[i] ：保证 dp[i] 递推到 dp[i+1] 的正确性；如果不包含 nums[i] ，递推时则不满足题目的 连续子数组 要求。
转移方程： 若 dp[i−1]≤0 ，说明dp[i−1] 对 dp[i] 产生负贡献，即 dp[i-1] + nums[i] 还不如 nums[i]本身大。

当 dp[i - 1] > 0 时：执行 dp[i] = dp[i-1] + nums[i] ；
当 dp[i − 1] ≤ 0 时：执行 dp[i] = nums[i] ；
初始状态： dp[0] = nums[0]，即以 nums[0] 结尾的连续子数组最大和为 nums[0] 。

返回值： 返回 dp 列表中的最大值，代表全局最大值。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cassielcode/p/12469290.html