《剑指Offer》第1-11题

AcWing 13. 找出数组中重复的数字

给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；

样例 给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

from collections import defaultdict class Solution(object): def duplicateInArray(self, nums): """ :type nums: List[int] :rtype int """ mp = defaultdict(int) res = -1 for it in nums: if it >= len(nums) or it <0: #遗漏 return -1 if mp[it] != 0: res = it mp[it] += 1 return res # 遗漏

(数组遍历) O(n) 首先遍历一遍数组，如果存在某个数不在0到n-1的范围内，则返回-1。

下面的算法的主要思想是把每个数放到对应的位置上，即让 nums[i] = i。

从前往后遍历数组中的所有数，假设当前遍历到的数是 nums[i]=x，那么：

如果x != i && nums[x] == x，则说明 x出现了多次，直接返回 x即可； 如果nums[x] != x，那我们就把 x 交换到正确的位置上，即 swap(nums[x], nums[i])，交换完之后如果nums[i] != i，则重复进行该操作。由于每次交换都会将一个数放在正确的位置上，所以swap操作最多会进行 n 次，不会发生死循环。

循环结束后，如果没有找到任何重复的数，则返回-1。

时间复杂度分析 每次swap操作都会将一个数放在正确的位置上，最后一次swap会将两个数同时放到正确位置上，一共只有 n 个数和 n 个位置，所以swap最多会进行 n−1次。所以总时间复杂度是 O(n)。

class Solution { public: int duplicateInArray(vector<int>& nums) { int n = nums.size(); for (auto x : nums) if (x < 0 || x >= n) return -1; for (int i = 0; i < n; i ++ ) { while (nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]); if (nums[i] != i) return nums[i]; } return -1; } };

AcWing 14. 不修改数组找出重复的数字

给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例 给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。 思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？ yxc大佬 (分治，抽屉原理) O(nlogn) 这道题目主要应用了抽屉原理和分治的思想。

抽屉原理：n+1 个苹果放在 n 个抽屉里，那么至少有一个抽屉中会放两个苹果。

用在这个题目中就是，一共有 n+1 个数，每个数的取值范围是1到n，所以至少会有一个数出现两次。

然后我们采用分治的思想，将每个数的取值的区间[1, n]划分成[1, n/2]和[n/2+1, n]两个子区间，然后分别统计两个区间中数的个数。 注意这里的区间是指 数的取值范围，而不是 数组下标。即这题跟题目给的数的顺序无关

划分之后，左右两个区间里一定至少存在一个区间，区间中数的个数大于区间长度。 这个可以用反证法来说明：如果两个区间中数的个数都小于等于区间长度，那么整个区间中数的个数就小于等于n，和有n+1个数矛盾。

因此我们可以把问题划归到左右两个子区间中的一个，而且由于区间中数的个数大于区间长度，根据抽屉原理，在这个子区间中一定存在某个数出现了两次。

依次类推，每次我们可以把区间长度缩小一半，直到区间长度为1时，我们就找到了答案。

复杂度分析 时间复杂度：每次会将区间长度缩小一半，一共会缩小 $O(logn)$次。每次统计两个子区间中的数时需要遍历整个数组，时间复杂度是 O(n)。所以总时间复杂度是 $O(nlogn)$。 空间复杂度：代码中没有用到额外的数组，所以额外的空间复杂度是 O(1)。

二分经典问题

class Solution(object): def duplicateInArray(self, nums): """ :type nums: List[int] :rtype int """ n = len(nums) l = 1 r = n while l < r: mid = (l + r) >> 1 s = 0 for it in nums: if it >= l and it <= mid: s += 1 # print(mid, s) if s > mid - l + 1: r = mid else: l = mid + 1 return l

AcWing 15. 二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例

输入数组：

[ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false。

yxc 大佬做法 算法 (单调性扫描) $O(n+m)$ 核心在于发现每个子矩阵右上角的数的性质：

如下图所示，x左边的数都小于等于x，x下边的数都大于等于x。

因此我们可以从整个矩阵的右上角开始枚举，假设当前枚举的数是 xx：

如果 x等于target，则说明我们找到了目标值，返回true；如果 x 小于target，则 x左边的数一定都小于target，我们可以直接排除当前一整行的数；如果 x 大于target，则 x下边的数一定都大于target，我们可以直接排序当前一整列的数；

排除一整行就是让枚举的点的横坐标加一，排除一整列就是让纵坐标减一。 当我们排除完整个矩阵后仍没有找到目标值时，就说明目标值不存在，返回false。

时间复杂度分析 每一步会排除一行或者一列，矩阵一共有 n 行，mm 列，所以最多会进行 n+m 步。所以时间复杂度是 O(n+m)。

class Solution(object): def searchArray(self, array, target): """ :type array: List[List[int]] :type target: int :rtype: bool """ if len(array) == 0 or len(array[0]) == 0: return False i = 0 j = len(array[0]) - 1 while i < len(array) and j >=0: if target == array[i][j]: return True elif target > array[i][j]: i += 1 elif target < array[i][j]: j -= 1 return False

AcWing 16. 替换空格

请实现一个函数，把字符串中的每个空格替换成"%20"。

你可以假定输入字符串的长度最大是1000。 注意输出字符串的长度可能大于1000。

样例 输入：“We are happy.”

输出：“We%20are%20happy.”

class Solution(object): def replaceSpaces(self, s): """ :type s: str :rtype: str """ return s.replace(" ","%20")

AcWing 17. 从尾到头打印链表

输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

样例 输入：[2, 3, 5] 返回：[5, 3, 2]

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def printListReversingly(self, head): """ :type head: ListNode :rtype: List[int] """ res = [] while head != None: res.append(head.val) head = head.next res.reverse() return res

AcWing 18. 重建二叉树

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

注意:

二叉树中每个节点的值都互不相同； 输入的前序遍历和中序遍历一定合法； 样例

给定： 前序遍历是：[3, 9, 20, 15, 7] 中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]

返回的二叉树如下所示： 3 / \ 9 20 / \ 15 7

算法 (递归) O(n) 递归建立整棵二叉树：先递归创建左右子树，然后创建根节点，并让指针指向两棵子树。

具体步骤如下：

先利用前序遍历找根节点：前序遍历的第一个数，就是根节点的值；在中序遍历中找到根节点的位置 k，则 k左边是左子树的中序遍历，右边是右子树的中序遍历；假设左子树的中序遍历的长度是 l，则在前序遍历中，根节点后面的 l个数，是左子树的前序遍历，剩下的数是右子树的前序遍历；有了左右子树的前序遍历和中序遍历，我们可以先递归创建出左右子树，然后再创建根节点；

时间复杂度分析 我们在初始化时，用哈希(unordered_map<int,int>)记录每个值在中序遍历中的位置，这样我们在递归到每个节点时，在中序遍历中查找根节点位置的操作，只需要 O(1)的时间。此时，创建每个节点需要的时间是 O(1)，所以总时间复杂度是 O(n)。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def buildTree(self, preorder, inorder): """ :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """ if len(preorder) == 0: return None pos = [None for i in range(max(inorder) + 1)] for i in range(len(inorder)): pos[inorder[i]] = i def build(il, ir, pl, pr): if pl > pr: return None root = TreeNode(preorder[pl]) k = pos[root.val] if il < k: root.left = build(il, k - 1, pl + 1, pl + (k - 1 - il) + 1) if ir > k: root.right = build(k+1 , ir, pl + k - il + 1, pr) return root return build(0, len(preorder) - 1, 0, len(preorder) - 1)

AcWing 19. 二叉树的下一个节点

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

如果给定的节点是中序遍历序列的最后一个，则返回空节点; 二叉树一定不为空，且给定的节点一定不是空节点； 样例

假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。

则应返回值等于3的节点。

解释：该二叉树的结构如下，2的后继节点是3。 2 / \ 1 3

算法 (模拟) O(h) 这道题目就是让我们求二叉树中给定节点的后继。

分情况讨论即可，如下图所示：

如果当前节点有右儿子，则右子树中最左侧的节点就是当前节点的后继。比如F的后继是H；如果当前节点没有右儿子，则需要沿着father域一直向上找，找到第一个是其father左儿子的节点，该节点的father就是当前节点的后继。比如当前节点是D，则第一个满足是其father左儿子的节点是F，则C的father就是D的后继，即F是D的后继。

时间复杂度分析 不论往上找还是往下找，总共遍历的节点数都不大于树的高度。所以时间复杂度是 O(h)，其中 h 是树的高度。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None # self.father = None class Solution(object): def inorderSuccessor(self, q): """ :type q: TreeNode :rtype: TreeNode """ if q.right != None: p = q.right while p.left != None: p = p.left return p else: p = q while p.father != None and p.father.right == p: p = p.father return p.father

AcWing 20. 用两个栈实现队列

请用栈实现一个队列，支持如下四种操作：

push(x) – 将元素x插到队尾； pop() – 将队首的元素弹出，并返回该元素； peek() – 返回队首元素； empty() – 返回队列是否为空； 注意：

你只能使用栈的标准操作：push to top，peek/pop from top, size 和 is empty； 如果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作； 输入数据保证合法，例如，在队列为空时，不会进行pop或者peek等操作； 样例 MyQueue queue = new MyQueue();

queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false

class MyQueue(object): def __init__(self): """ Initialize your data structure here. """ self.sta = [] def push(self, x): """ Push element x to the back of queue. :type x: int :rtype: void """ self.sta.append(x) def pop(self): """ Removes the element from in front of queue and returns that element. :rtype: int """ return self.sta.pop(0) def peek(self): """ Get the front element. :rtype: int """ return self.sta[0] def empty(self): """ Returns whether the queue is empty. :rtype: bool """ if len(self.sta) == 0: return True return False # Your MyQueue object will be instantiated and called as such: # obj = MyQueue() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.peek() # param_4 = obj.empty()

AcWing 21. 斐波那契数列

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从0开始，第0项为0。(n<=39)

样例 输入整数 n=5

返回 5

class Solution(object): def Fibonacci(self, n): """ :type n: int :rtype: int """ if n == 0: return 0 a = 0 b = 1 for i in range(2, n+1): a, b = b, a + b return b

生成器 生成器讲解

class Solution(object): def Fibonacci(self, n): """ :type n: int :rtype: int """ if n == 0: return 0 def f(n): a = 0 b = 1 for i in range(n): yield b # 生成器 a, b = b, a + b res = 0 for it in f(n): res = it return res

AcWing 22. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

数组可能包含重复项。

注意：数组内所含元素非负，若数组大小为0，请返回-1。

样例 输入：nums=[2,2,2,0,1]

输出：0

class Solution: def findMin(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == 0: return -1 else: return min(nums)

yxc 大佬 算法 (二分) O(n) 为了便于分析，我们先将数组中的数画在二维坐标系中，横坐标表示数组下标，纵坐标表示数值，如下所示：

图中水平的实线段表示相同元素。

我们发现除了最后水平的一段（黑色水平那段）之外，其余部分满足二分性质：竖直虚线左边的数满足 nums[i]≥nums[0]；而竖直虚线右边的数不满足这个条件。 分界点就是整个数组的最小值。

所以我们先将最后水平的一段删除即可。

另外，不要忘记处理数组完全单调的特殊情况：

当我们删除最后水平的一段之后，如果剩下的最后一个数大于等于第一个数，则说明数组完全单调。

时间复杂度分析 二分的时间复杂度是 O(logn)，删除最后水平一段的时间复杂度最坏是 O(n)，所以总时间复杂度是 O(n)。

class Solution: def findMin(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == 0: return -1 n = len(nums) - 1 while nums[n] == nums[0]: n -= 1 l = 0 r = n while l < r: mid = (l + r ) >> 1 if nums[mid] >= nums[0]: l = mid + 1 else : r = mid return min(nums[0], nums[l])

AcWing 23. 矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

输入的路径不为空； 所有出现的字符均为大写英文字母；

样例 matrix= [ [“A”,“B”,“C”,“E”], [“S”,“F”,“C”,“S”], [“A”,“D”,“E”,“E”] ]

str=“BCCE” , return “true”

str=“ASAE” , return “false”

算法 DFS $O(n^2{3}^k)$ 在深度优先搜索中，最重要的就是考虑好搜索顺序。

我们先枚举单词的起点，然后依次枚举单词的每个字母。 过程中需要将已经使用过的字母改成一个特殊字母，以避免重复使用字符。

时间复杂度分析：单词起点一共有 $n^2$ 个，单词的每个字母一共有上下左右四个方向可以选择，但由于不能走回头路，所以除了单词首字母外，仅有三种选择。所以总时间复杂度是 $O(n^2{3}^k)$

class Solution(object): def hasPath(self, matrix, string): """ :type matrix: List[List[str]] :type string: str :rtype: bool """ for i in range(len(matrix)): for j in range(len(matrix[i])): st = [[0 for j in range(len(matrix[i]))] for i in range(len(matrix))] if self.dfs(i, j, 0, st, matrix, string) == True: return True return False def dfs(self, i, j, u, st, matrix, string): dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] if matrix[i][j] != string[u] : return False st[i][j] = 1 #print(i, j, matrix[i][j], u) #print(st) if u == len(string) - 1: return True for t in range(4): x = i + dx[t] y = j + dy[t] if x < len(matrix) and x >= 0 and y < len(matrix[x]) and y >= 0 and st[x][y] == 0 : st[x][y] = 1 if self.dfs(x, y, u + 1, st, matrix, string) == True: return True st[x][y] = 0 return False