《剑指offer》第二版

2023-02-26 14:08| 来源: 网络整理| 查看: 265

剑指offer 03. 数组中重复的数字04. 二维数组中的查找05. 替换空格06. 从尾到头打印链表07. 重建二叉树（🎂）剑指 Offer 09. 用两个栈实现队列10- I. 斐波那契数列（🎂 自己实现LRU）10- II. 青蛙跳台阶问题11. 旋转数组的最小数字（🎂）12. 矩阵中的路径（🎂）14- I. 剪绳子14- II. 剪绳子 II15. 二进制中1的个数16. 数值的整数次方（🎂 快速幂）17. 打印从1到最大的n位数18. 删除链表的节点21. 调整数组顺序使奇数位于偶数前面22. 链表中倒数第k个节点24. 反转链表25. 合并两个排序的链表26. 树的子结构（🎂两个函数递归调用）27. 二叉树的镜像28. 对称的二叉树30. 包含min函数的栈31. 栈的压入、弹出序列32 - I. 从上到下打印二叉树32 - II. 从上到下打印二叉树 II32 - III. 从上到下打印二叉树 III33. 二叉搜索树的后序遍历序列（🎂）34. 二叉树中和为某一值的路径（🎂 回溯）35. 复杂链表的复制38. 字符串的排列（🎂回溯）39. 数组中出现次数超过一半的数字40. 最小的k个数（🎂 快排、堆）42. 连续子数组的最大和46. 把数字翻译成字符串（🎂）47. 礼物的最大价值48. 最长不含重复字符的子字符串50. 第一个只出现一次的字符52. 两个链表的第一个公共节点插一道非剑指Offer：42. 接雨水II 100. 三角形中最小路径之和53 - I. 在排序数组中查找数字 I53 - II. 0～n-1中缺失的数字54. 二叉搜索树的第k大节点55 - I. 二叉树的深度55 - II. 平衡二叉树（🎂）56 - I. 数组中数字出现的次数（🎂）56 - II. 数组中数字出现的次数 II57. 和为s的两个数字57 - II. 和为s的连续正数序列58 - I. 翻转单词顺序58 - II. 左旋转字符串59 - I. 滑动窗口的最大值（🎂）62. 圆圈中最后剩下的数字63. 股票的最大利润64. 求1+2+…+n66. 构建乘积数组68 - I. 二叉搜索树的最近公共祖先68 - II. 二叉树的最近公共祖先（🎂）59 - II. 队列的最大值61. 扑克牌中的顺子

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 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 int: # 强行递归，会超时 if n int: # 强行递归，会超时 if n } cur = head while cur: dic[cur] = Node(cur.val) cur = cur.next # 复制指针 cur = head while cur: dic[cur].next = dic.get(cur.next) dic[cur].random = dic.get(cur.random) cur = cur.next return dic[head] 38. 字符串的排列（🎂回溯） class Solution: def permutation(self, s: str) -> List[str]: paths = [] if not s: return paths path = '' used = [False] * len(s) def backtracking(s, path, used): if len(path) == len(s): paths.append(path) return for i in range(len(s)): if not used[i]: if i > 0 and s[i-1] == s[i] and not used[i-1]: continue used[i] = True path += s[i] backtracking(s, path, used) path = path[:-1] used[i] = False s = sorted(s) backtracking(s, path, used) return paths 39. 数组中出现次数超过一半的数字 class Solution: def majorityElement(self, nums: List[int]) -> int: if len(nums) int: dic = {} for num in nums: if num not in dic: dic[num] = 0 else: dic[num] += 1 for k, v in dic.items(): if v >= len(nums) // 2: return k 40. 最小的k个数（🎂 快排、堆） class Solution: def getLeastNumbers(self, arr: List[int], k: int) -> List[int]: arr.sort() return arr[:k] class Solution: def getLeastNumbers(self, arr: List[int], k: int) -> List[int]: nums = self.quickSort(arr, 0, len(arr) - 1) return nums[:k] def quickSort(self, nums, i, j): # 快排一定要记住 # https://zhuanlan.zhihu.com/p/63227573 if i > j: return pivot = nums[i] low = i high = j while i } for c in s: if c not in dic: dic[c] = 1 else: dic[c] += 1 for c in s: if dic[c] == 1: return c return ' ' 52. 两个链表的第一个公共节点 class Solution: def getIntersectionNode(self, l1: ListNode, l2: ListNode) -> ListNode: p1, p2 = l1, l2 while p1 != p2: p1 = p1.next if p1 else l2 p2 = p2.next if p2 else l1 return p1 插一道非剑指Offer：42. 接雨水 class Solution: def trap(self, height: List[int]) -> int: # 双指针多次遍历 n = len(height) # 先找到位置i+1左边最高的柱子，虽然我们dp的时候求的是第i列左边，含第i列最大的柱子，但是实际上使用的时候是看i+1列 maxLeft = [0] * n maxLeft[0] = height[0] for i in range(1, n): maxLeft[i] = max(maxLeft[i-1], height[i]) # 再找到i-1列右边最高的柱子 maxRight = [0] * n maxRight[-1] = height[-1] for i in range(n-2, -1, -1): maxRight[i] = max(maxRight[i+1], height[i]) # 求和 res = 0 for i in range(1, n-1): tmp = min(maxLeft[i-1], maxRight[i+1]) - height[i] res += tmp if tmp > 0 else 0 return res II 100. 三角形中最小路径之和

小红书推荐算法面试题，不难，dp很容易做。

class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: # 2 # 3 4 # 5 6 7 # 8 9 10 11 m = len(triangle) if m int: n = len(triangle) dp = [[0] * i for i in range(1, n+1)] dp[0][0] = triangle[0][0] for i in range(1, n): dp[i][0] = triangle[i][0] + dp[i-1][0] for j in range(1, i): dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j] dp[i][-1] = triangle[i][-1] + dp[i-1][-1] return min(dp[-1]) 53 - I. 在排序数组中查找数字 I class Solution: def search(self, nums: List[int], target: int) -> int: dic = collections.Counter(nums) return dic[target]

很明显不是最优解，因为原始数组是有序的，因此肯定可以使用二分，二分找出左右边界，然后求差即可。

class Solution: def search(self, nums: List[int], target: int) -> int: # 使用二分查到target出现的左边界和有边界 # 之后左右边界之差加上1就行了 if not nums: return 0 leftBorder, rightBorder = self.searchLeft(nums, target), self.searchRight(nums, target) if leftBorder == -2 or rightBorder == -2: return 0 if nums[leftBorder+1] != nums[rightBorder-1]: return 0 return rightBorder - leftBorder - 1 def searchRight(self, nums, target): l, r = 0, len(nums) - 1 rightBorder = -2 while l int: def dfs(root): if not root: return 0 leftDepth = dfs(root.left) rightDepth = dfs(root.right) depth = max(leftDepth, rightDepth) + 1 return depth return dfs(root) 55 - II. 平衡二叉树（🎂） class Solution: def isBalanced(self, root: TreeNode) -> bool: # def recur(root): if not root: return 0 left = recur(root.left) if left == -1: return -1 right = recur(root.right) if right == -1: return -1 return max(left, right) + 1 if abs(right - left) bool: if not root: return True left_depth = self.getDepth(root.left) right_depth = self.getDepth(root.right) return abs(right_depth - left_depth) List[int]: # x ^ x == 0 # x ^ 0 = x n = 0 for num in nums: n = n ^ num # 因为有两个只出现过一次的数，因此一次异或得到的结果只是x^y # 因为x，y不一样，所以x与y必然至少有一个不一样，因此找到其中一位 m = 1 while n & m == 0: m List[int]: dic = {} for i, num in enumerate(nums): if target - num in dic: return [num, target - num] else: dic[num] = i return [-1, -1] class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: l, r = 0, len(nums) - 1 while l target: r -= 1 elif s List[List[int]]: # 因为都是正数，所以在一个区间内去掉一个数和必然会减小，加上一个数和必然会增加 l, r = 1, 2 s = 3 res = [] while l str: # 删除前缀空格和后缀空格 s = s.strip() words = s.split() return ' '.join(words[::-1]) 58 - II. 左旋转字符串 class Solution: def reverseLeftWords(self, s: str, n: int) -> str: return s[n:] + s[:n] 59 - I. 滑动窗口的最大值（🎂） class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: if not nums: return [] deque = collections.deque() # 先构造一个初始的队列 for i in range(k): while deque and deque[-1] 1: for _ in range(m % n): tmp = deque.popleft() deque.append(tmp) deque.pop() return deque[0]

递归法：

class Solution: def lastRemaining(self, n: int, m: int) -> int: def dfs(n, m): if n == 1: return 0 x = dfs(n-1, m) return (x + m) % n return dfs(n, m) 63. 股票的最大利润 class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 res = 0 min_price = prices[0] for price in prices: if price int: def recur(n, s): if n == 1: return s + 1 return recur(n-1, s) + n return recur(n, 0) class Solution: def sumNums(self, n: int) -> int: # 因为不能使用循环，因此只能使用递归来实现 # 但是递归需要有终止条件，终止条件通常都是if语句 # 所以，还需要解决if语句代替问题，在python中，当and前为false时，后面的运算会自动终止 # 因此，可以使用and来代替 return n and (n + self.sumNums(n-1)) 66. 构建乘积数组 class Solution: def constructArr(self, a: List[int]) -> List[int]: n = len(a) if n 'TreeNode': if not root: return if p.val = root.val: return root if p.val >= root.val and q.val TreeNode: if not root or root.val == p.val or root.val == q.val: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if not left and not right: return # 左右都为空，没有p，q if not left and right: return right # pq走在右侧 if not right and left: return left， # pq都在左侧 return root # 左右都不为空，说明pq在异侧 59 - II. 队列的最大值

这题稍微有点问题，max操作不可能是 O ( 1 ) O(1) O(1)的

class MaxQueue: def __init__(self): self.data = [] self.deque = collections.deque() def max_value(self) -> int: if not self.deque: return -1 return self.deque[0] def push_back(self, value: int) -> None: while self.deque and self.deque[-1] int: if not self.data: return -1 ans = self.data.pop(0) if ans == self.deque[0]: self.deque.popleft() return ans 61. 扑克牌中的顺子 class Solution: def isStraight(self, nums: List[int]) -> bool: repeat = set() mi, ma = float('inf'), -float('inf') for num in nums: if num == 0: continue ma = max(ma, num) mi = min(mi, num) if num in repeat: return False repeat.add(num) return True if ma - mi

【本文地址】

《剑指offer》第二版

《剑指offer》第二版

今日新闻

推荐新闻