知识迁移能力举一反三：能力是培养的，加油吧。题 53：在排序数组中查找数字题目一：数字在排序数组中出现的次数统计一个数字在排序数组中出现的次数。例如，输入排序数组{1，2，3，3，3，3，4，5}和数字 3，由于 3 在这个数组中出现了 4 次，因此输出 4.题目二：0~n-1 中缺失的数字一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0~n-1 之内。在范围 0~n-1 之内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。题目三：数组中数值和下标相等的元素假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{-3， -1， 1， 3， 5}中，数字 3 和它的下标相等。解法：# -*- coding:utf-8 -*- class Solution: def GetNumberOfK(self, data, k): """计算排序数组中数字出现的次数 Arguments: data {list} -- 数组 k {int} -- 待寻找数字 Returns: int -- 找到返回个数，找不到返回 0 """ if k is None or len(data) < 1: return 0 if k < data[0] or k > data[-1]: return 0 first = self.get_occur_location(data, k, True) last = self.get_occur_location(data, k, False) if first == last and first == -1: return 0 else: return last - first + 1 def get_occur_location(self, data, k, first): right = len(data) - 1 left = 0 while left <= right: middle = left + ((right - left) >> 1) if data[middle] == k: if first: if middle - 1 > -1 and data[middle-1] == k: right = middle - 1 else: return middle else: if middle + 1 < len(data) and data[middle+1] == k: left = middle + 1 else: return middle elif data[middle] > k: right = middle - 1 else: left = middle + 1 return -1 def get_missing_number(self, arr): """找到长度为 n-1 的递增排序数组中不在 0~n-1 范围内的数字 Arguments: arr {list} -- 长度为 n-1 的递增排序数组 """ if arr is None or len(arr) < 1: return None return self.binary_find_missing_number(arr) def binary_find_missing_number(self, arr): left, right = 0, len(arr) - 1 while left <= right: middle = left + ((right - left) >> 1) if arr[middle] == middle: left = middle + 1 elif middle == 0 or (middle - 1 >= 0 and arr[middle-1] == middle-1): return middle else: right = middle - 1 return -1 def find_index_equls_value_item(self, arr): """找到单调递增且不重复数组中数值和下标相等的元素 Arguments: arr {list} -- 数组 Returns: int -- 找到返回下标，找不到返回 1 """ if arr is None or len(arr) < 1: return None return self.binary_find_equls_item(arr) def binary_find_equls_item(self, arr): left, right = 0, len(arr) - 1 while left <= right: middle = left + ((right - left) >> 1) if arr[middle] == middle: return middle elif arr[middle] < middle: left = middle + 1 else: right = middle - 1 return -1 if __name__ == "__main__": nums = [1, 2, 3, 3, 3, 3] nums2 = [0, 1, 2, 3, 5] nums3 = [1, 2, 3, 4] nums4 = [-3, -1, 1, 3, 5] ex = Solution() print(ex.GetNumberOfK(nums, 3)) print(ex.get_missing_number(nums2)) print(ex.get_missing_number(nums3)) print(ex.find_index_equls_value_item(nums4)) 题 54：二叉搜索树的第 K 大节点题目：给定一颗二叉搜索树，请找出第 k 大的节点。解法：利用二叉搜索树的中序遍历为递增数组的特性，即可得结果。# -*- coding:utf-8 -*- class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # 返回对应节点 TreeNode def KthNode(self, pRoot, k): if pRoot is None or k < 1: return None cur = pRoot res = -1 while cur: most_right = cur.left if most_right: while most_right.right and most_right.right != cur: most_right = most_right.right # 第一次遍历到 cur 节点 if most_right.right is None: most_right.right = cur cur = cur.left continue # 第二次遍历到 cur 节点 if most_right.right == cur: most_right.right = None k -= 1 if k == 0: # 为了不破坏原二叉树结构，没有直接返回 cur 节点 res = cur cur = cur.right return None if res == -1 else res if __name__ == "__main__": root = TreeNode(5) root.left = TreeNode(3) root.right = TreeNode(7) root.left.left = TreeNode(2) root.left.right = TreeNode(4) root.right.left = TreeNode(6) root.right.right = TreeNode(8) ex = Solution() print(ex.KthNode(root, 4)) # The answer is TreeNode(5) 题 55： 二叉树的深度题目一： 求二叉树的深度输入一课二叉树的根节点，求该树的深度。class Solution: def TreeDepth(self, pRoot): if pRoot is None: return 0 depthl = self.TreeDepth(pRoot.left) depthr = self.TreeDepth(pRoot.right) return max(depthl, depthr) + 1 题目二： 平衡二叉树输入一课二叉树的根节点，判断该树是不是平衡二叉树。解法：这个题在我前面关于树形 dp 的帖子里。题 56：数组中数字出现的次数题目一：数组中只出现一次的两个数字一个整型数组里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n),空间复杂度是 O(1).解法：空间复杂度 O(1)意味着我们不能借用辅助数组。解法如下：# -*- coding:utf-8 -*- class Solution: # 返回[a,b] 其中 ab 是出现一次的两个数字 def FindNumsAppearOnce(self, array): if array is None or len(array) < 2: return [] res = self.get_xor(array) flag = self.get_index(res) help_arr1, help_arr2 = [], [] for item in array: res = self.get_bit(item, flag) if res: help_arr1.append(item) else: help_arr2.append(item) return [self.get_xor(help_arr1), self.get_xor(help_arr2)] def get_xor(self, arr): res = 0 for item in arr: res = res ^ item return res def get_index(self, res): """得到异或结果其中一位为 1 的位置 Arguments: res {int} -- 原数组异或结果 """ period = 0 while period < 32: if res & 1 == 1: return period res = res >> 1 period += 1 def get_bit(self, num, index): # 将给定 index 位置的 bit 移到最低位 while index > 0: num = num >> 1 index -= 1 return num & 1 if __name__ == "__main__": ex = Solution() nums = [2, 4, 3, 6, 3, 2, 5, 5] print(ex.FindNumsAppearOnce(nums)) # The answer is [6, 4]. 题目二：数组中唯一只出现一次的数字。在一个数组中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现了一次的数字。解法：# -*- coding=utf-8 -*- class Solution(): def find_item(self, arr): if arr is None or len(arr) < 4 or len(arr) % 3 != 1: return None temp = [0 for i in range(32)] for item in arr: bit_mark = 1 for i in range(31, -1, -1): # 使用 bit_mark 每次左移结果去与可以防止溢出 bit = item & bit_mark if bit != 0: temp[i] += 1 bit_mark = bit_mark << 1 res = 0 # 注意生成数时候的顺序 for _ in temp: res = res << 1 res += _ % 3 return res if __name__ == "__main__": ex = Solution() arr = [3, 3, 3, 1] print(ex.find_item(arr)) 题 57：和为 s 的数字题目一：和为 s 的两个数字输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。解法：因为数组是递增的，那就好办了，首尾相加求和，然后往里推进。# -*- coding=utf-8 -*- def two_sum(arr, g_sum): if arr is None or len(arr) < 2: return None start, end = 0, len(arr) -1 while start < end: if arr[start] + arr[end] == g_sum: return arr[start], arr[end] elif arr[start] + arr[end] < g_sum: start += 1 else: end -= 1 return None if __name__ == "__main__": arr = [1, 2, 4, 7, 11, 15] g_sum = 15 print(two_sum(arr, g_sum)) 题目二：和为 s 的连续正数序列输入一个正数 s，打印出所有和为 s 的连续正数序列（至少含有两个数）。例如，输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以打印出 3 个连续序列 1~5，4~6 和 7~8.解法：类比题目一，构建初始区间，然后检测条件，根据条件更改区间。def get_sequence(g_sum): if g_sum < 3: return None small, big = 1, 2 res = [] while small <= g_sum // 2: cur_sum = sum(range(small, big+1)) if cur_sum == g_sum: res.append((small, big)) big += 1 elif cur_sum < g_sum: big += 1 else: small += 1 return res if __name__ == "__main__": print(get_sequence(15)) 题 58：翻转字符串题目一：翻转单词顺序输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序保持不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串“I am a student.”,则输出“student. a am I”.解法：这个题用 Python 写也跟作弊似的。但是有正经解法的，正经解法是先把字符串整个翻转，然后再以空格为区分，翻转字符串里的每一个单词。# -*- coding:utf-8 -*- class Solution: def ReverseSentence(self, s): if s is None or len(s) < 1: return s # 排除只含有空格的字符串 if s.strip() == '': return s s = s.split() return ' '.join(s[::-1]) 题目二：左旋转字符串字符串的左旋转操作是字符串前面的若干个字符转移到字符串尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefgt" 和数字 2，该函数将返回左旋转两位得到的结果“cdefgab" ”解法：这个用 Python 切片可以作弊式完成。但建议非 Python 语言使用者还是用正经解法把：1.首先用给定数字把字符分成两部分，第一部分为待左移字符串，第二部分为原剩余字符串；2.再分别翻转这两个部分；3.将这两个部分合并起来，然后再翻转合并后的字符串。# -*- coding:utf-8 -*- class Solution: def LeftRotateString(self, s, n): if s is None or len(s) < 1: return s n = n % len(s) pre, post = s[:n], s[n:] return post + pre 题 59：队列的最大值题目一：滑动窗口的最大值给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组{2，3，4，2，6，2，5，1}及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，它们的最大值分别为{4，4，6，6，6，5}.解法：# -*- coding:utf-8 -*- from collections import deque class Solution: def maxInWindows(self, num, size): if num is None or size is None: return [] if size < 1 or size > len(num): return [] res = [] helper = deque() for i in range(size): self.expand(num, i, helper) res.append(num[helper[0]]) l = 0 for i in range(size, len(num)): self.expand(num, i, helper) l += 1 self.shrink(num, l, helper) res.append(num[helper[0]]) return res def expand(self, num, index, helper): if not helper: helper.append(index) elif num[index] < helper[-1]: helper.append(index) else: while helper and num[index] >= num[helper[-1]]: helper.pop() helper.append(index) def shrink(self, num, l, helper): while helper and helper[0] < l: helper.popleft() if __name__ == "__main__": ex = Solution() num = [2, 3, 4, 2, 6, 2, 5, 1] print(ex.maxInWindows(num, 3)) 题目二：队列的最大值请定义一个队列并实现 max 得到队列里的最大值，要求函数max，push_back 和pop_front的时间复杂度都是 O(1)。解法：借用上题的思想，给队列建立一个影子队列用来存放最大值，当队列添加一个元素的时候，影子队列执行expand操作，当队列pop_front的时候，影子队列执行一次shrink操作。# -*- coding=utf-8 -*- from collections import deque class WithMaxQueue(): """能 O(1)时间复杂度返回队列最大值的队列实现： 实现了 pop_front 以及 push_back 方法 """ def __init__(self): """初始化，self.__l, self.__r 两个参数很重要 params: self.__queue: 存储数据的队列 self.__shadow: 存储数据队列中最大值的队列 self.__l: 等价于滑动窗口左边界，表示当前队列头部是第几个添加进来的元素 self.__r: 等价于滑动窗口右边界，表示当前队列尾部是第几个添加进来的元素 """ self.__queue = deque() self.__shadow = deque() self.__l, self.__r = 0, 0 def push_back(self, item): self.__queue.append(item) self.expand(item) self.__r += 1 def pop_front(self): if self.__queue: self.__queue.popleft() self.__l += 1 self.shrink() else: raise IndexError("pop from emtpy queue") def expand(self, item): """滑动窗口的扩大过程：即当有新元素时，对最大值队列的调整 """ if not self.__shadow: self.__shadow.append((self.__r, item)) else: if item < self.__shadow[-1][-1]: self.__shadow.append((self.__r, item)) else: while self.__shadow and item >= self.__shadow[-1][-1]: self.__shadow.pop() self.__shadow.append((self.__r, item)) def shrink(self): """滑动窗口的缩小过程（窗口左边界右移）即：当弹出元素时，对最大值队列的调整 """ while self.__shadow and self.__l > self.__shadow[0][0]: self.__shadow.popleft() def get_max(self): return self.__shadow[0][-1] if __name__ == "__main__": ex = WithMaxQueue() num = [2, 3, 4, 2, 6, 2, 5, 1] # The anster is 4, 4, 6, 6, 6, 5 for i in range(3): ex.push_back(num[i]) print(ex.get_max()) for i in range(3, len(num)): ex.push_back(num[i]) ex.pop_front() print(ex.get_max()) 抽象建模能力建模两步走：选择合理的数据结构来表述问题；分析模型中的内在规律，并用编程语言表述这种规律。题 60：n 个骰子的点数把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 s。输入 n，打印出 s 的所有可能值出现的概率。解法：# -*- coding=utf-8 -*- import numbers import time class Solution(): """求 n 个骰子扔在地上，所有骰子正面向上点数和 s 的各种情况及其出现概率 """ def __init__(self, dice=6): self.dice_numbers = dice def get_sum_recur(self, n): """递归求解版本 Arguments: n {int} -- 骰子个数 Returns: list -- 包含元素为（s, probability）, s 为和，probability 为 s 出现概率。 """ assert isinstance(n, numbers.Integral) if n < 1: return [(0, 1)] res_arr = [0 for i in range((self.dice_numbers - 1) * n + 1)] self.recur_process(n, res_arr) total = self.dice_numbers ** n res_arr = [(i + n, res_arr[i] / total) for i in range(len(res_arr))] return res_arr def recur_process(self, n, res_arr): for i in range(1, self.dice_numbers + 1): self.process(n, n, i, res_arr) def process(self, n, remain, cur_sum, res_arr): if remain == 1: res_arr[cur_sum - n] += 1 else: for i in range(1, self.dice_numbers+1): self.process(n, remain-1, cur_sum+i, res_arr) def get_sum(self, n): """非递归求解版本 """ assert isinstance(n, numbers.Integral) if n < 1: return [(0, 1)] p1 = [0] * 2 p1[0] = [0 for i in range(self.dice_numbers*n+2)] p1[1] = [0 for i in range(self.dice_numbers*n+2)] # flag 用来每次循环时，复用上轮循环的结果 flag = 0 for i in range(1, self.dice_numbers+1): p1[flag][i] = 1 for i in range(2, n+1): for j in range(i): # 和不可能小于 i p1[1-flag][j] = 0 for j in range(i, self.dice_numbers*i+1): p1[1-flag][j] = 0 k = 1 while k <= self.dice_numbers and k < j: p1[1-flag][j] += p1[flag][j-k] k += 1 flag = 1 - flag total = self.dice_numbers ** n res = [] for i in range(n, self.dice_numbers*n+1): res.append((i, p1[flag][i]/total)) return res if __name__ == "__main__": n = 10 print('{}个骰子的情况下：'.format(n)) ex = Solution() start = time.time() print("递归求解结果：\n{}".format(ex.get_sum_recur(n))) first_period = time.time() - start print("非递归求解结果：\n{}".format(ex.get_sum(n))) second_period = time.time() - start - first_period print("递归用时：{}, 非递归用时：{} \n 递归用时是非递归用时的 {} 倍。".format( first_period, second_period, first_period/second_period)) 当 n=10 的时候，就已经能看见巨大差距了：递归用时：24.436681985855103, 非递归用时：0.0007491111755371094 递归用时是非递归用时的 32620.90165499682 倍。 题 61：扑克牌中的顺子从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这五张牌是不是连续的。2~10 为数字本身，A 为 1， J 为 11， Q 为 12，K 为 13，而大小王可以看成任意数字。解法： 这类题就是看看代码能力了。有两点需要注意：1.数组中不能出现除了 0 之外的重复数字； 2.连续的非零数字之间的正常间距为 1# -*- coding:utf-8 -*- class Solution: def IsContinuous(self, numbers): if numbers is None or len(numbers) != 5: return [] numbers.sort() length = len(numbers) times = numbers.count(0) for i in range(length-1): if numbers[i] == 0: continue delta = numbers[i+1] - numbers[i] if delta == 0: return False elif delta - 1 <= times: times -= delta - 1 else: return False return True if __name__ == "__main__": nums = [1, 3, 2, 6, 4] ex = Solution() print(ex.IsContinuous(nums)) 题 62：圆圈中最后剩下的数字0,1,…, n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里出去第 m 个数字，求这个圆圈里剩下的最后一个数字。解法：# -*- coding:utf-8 -*- class Solution: def LastRemaining_Solution_1(self, n, m): """利用辅助数组解法 Arguments: n {int} -- 人数 m {int} -- 删除第 m 个元素 Returns: int -- 最后剩余人代号 """ if n < 1 or m < 0: return -1 arr = [i for i in range(n)] cur = 0 while len(arr) != 1: period = m - 1 while period: cur = self.next_index(arr, cur) period -= 1 arr.pop(cur) if cur >= len(arr): cur = 0 return arr[-1] def next_index(self, arr, cur): return 0 if cur >= len(arr) - 1 else cur + 1 def LastRemaining_Solution_2(self, n, m): """f(n, m) = (f(n - 1, m) + m) % n 如果不做映射，f(n-1, m)结果相当于 f(n, m)淘汰第一个人之后的下一步，但调整了剩余的 n-1 人的代号之后，我们需要确定的映射关系，能把调整之后的代号转换到初始包含 n 个人的情况下的代号 这样返回的结果也是和最初数据对应的。 """ if n < 1 or m < 1: return -1 last = 0 for i in range(2, n+1): last = (last + m) % i return last if __name__ == "__main__": ex = Solution() n, m = 5, 3 print(ex.LastRemaining_Solution_2(n, m)) 题 63：股票的最大利润假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？例如，一只股票在某些时间节点的价格为{9， 11， 8，5，7， 12， 16， 14}。如果我们能在价格为 5 的时候买入并在价格为 16 时卖出，则能收获最大利润 11.# -*- coding=utf-8 -*- def get_max_profit(arr): if arr is None or len(arr) < 2: return 0 min_price = arr[0] max_profit = arr[1] - min_price for item in arr[2:]: if item < min_price: min_price = item max_profit = max(max_profit, item - min_price) return max_profit if __name__ == "__main__": num = [9, 11, 8, 5, 7, 12, 16, 14] print(get_max_profit(num)) # The anster is 11 发散思维能力：积累越多，发散能力自然越强，加油！题 64：求 1+2+…+n求 1+2+…+n，要求不能用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A?B:C）解法：短路求值：对于 Python 来说：a and b if a return b else return a# -*- coding:utf-8 -*- class Solution: def Sum_Solution(self, n): if n < 1: return 0 ans = n emp = n and self.Sum_Solution(n-1) ans += temp return ans 题 65：不用加减乘除做加法写一个函数，求两个整数之和，要求函数体内不得使用“+”、“_”、“*”、“/”四则运算符号解法： Python 中的位操作和其他语言是有些许不同的。# -*- coding:utf-8 -*- class Solution: def Add(self, a, b): while(b & 0xFFFFFFFF > 0): # 防止 b 溢出 32 位范围 a, b = (a ^ b), ((a & b) << 1) # 判断 a 是否溢出 if abs(a) >= 0xFFFFFFFF: return a & 0xFFFFFFFF return a 题 66：构建乘积数组给定一个数组 A[0,1, … n-1], 请构建一个数组 B[0,1,…,n-1],其中 B 中的元素 B[i] = A[0]xA[1]x…xA[i-1]xA[i+1]x..xA[n-1]。不能使用除法。解法：这个题如果自己解，就只有用笨办法了，但剑指 offer 提供的这种解法未免太 6 了，分成两部分，同时代码实现也很巧妙，Python 版如下，请飨。# -*- coding=utf-8 -*- def get_multi_list(arr): if arr is None or len(arr) < 1: return -1 if len(arr) == 1: return arr length = len(arr) res = [0 for i in range(len(arr))] res[0] = 1 for i in range(1, length): res[i] = res[i-1]*arr[i-1] temp = 1 for j in range(length-2, -1, -1): temp *= arr[j+1] res[j] *= temp return res if __name__ == "__main__": num = [1, 2, 3, 4, 5] print(get_multi_list(num))