大家好，我是讯享网，很高兴认识大家。

近期在刷力扣官网的这份题，因为我是因为报名了蓝桥杯才刷算法题的，所以我会选择性地写一些题解 (不包括太简单的、太难的、不在我考试范围的)

讯享网

以下都是我觉得比较有思考价值的题 

字符串

 1. 验证回文串

【问题描述】

        如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。

        给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

【样例】

输入	输出
s = "A man, a plan, a canal: Panama"	true
s = "race a car"	false
s = " "	true

【解析及代码】

class Solution(object): def isPalindrome(self, s): import re s = ''.join(re.findall(r'[A-Z]|[a-z]|[0-9]', s)).lower() return s == s[::-1]

讯享网

2. 分割回文串

【问题描述】

        给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串 。返回 s 所有可能的分割方案。

        回文串是正着读和反着读都一样的字符串。

【样例】

输入	输出
s = "aab"	[["a","a","b"],["aa","b"]]
s = "a"	[["a"]]

【解析及代码】

 创建邻接表，然后利用递归函数搜索可行解

讯享网class Solution(object): def partition(self, s): # 使用 set 提高 in 判断的效率 adj = {i: {i} for i in range(len(s))} # 2 字符回文串 for i in range(len(s) - 1): if s[i] == s[i + 1]: adj[i].add(i + 1) # 枚举子串步长 for p in range(2, len(s)): for i in range(len(s) - p): j = i + p # 是否为回文串: 子串为回文串 and 两端字符相同 if s[i] == s[j] and j - 1 in adj[i + 1]: adj[i].add(j) result = [] def dfs(i, state): if i == len(s): result.append(state) else: for j in adj[i]: dfs(j + 1, state[:] + [s[i:j + 1]]) dfs(0, []) return result

3. 单词拆分

【问题描述】

        给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

        注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

【样例】

输入	输出
s = "leetcode", wordDict = ["leet", "code"]	true
s = "applepenapple", wordDict = ["apple", "pen"]	true
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]	false

【解析及代码】

第一遍做的时候用了递归，因为回溯太多导致超时，所以改用了动态规划

首先初始化一维列表 dp，记录是否可以以对应索引为单词起始点，dp[3] 表示 s[:3] 已经由单词组合好，新的单词可以从该位置开始组合

class Solution(object): def wordBreak(self, s, wordDict): dp = [True] + [False for _ in range(len(s))] # dict: 长度 -> 单词 mydict = {} for w in wordDict: mydict.setdefault(len(w), set()).add(w) for i in filter(dp.__getitem__, range(len(s))): # 枚举子串长度 for p in mydict: j = i + p # 该子串是单词 if j <= len(s) and s[i:j] in mydict[p]: dp[j] = True return dp[-1]

dp[-1] 即 dp[len(s)]，表示索引 len(s) 是否可作为单词起始点，即是最终答案

4. 单词拆分Ⅱ

【问题描述】

        给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序返回所有这些可能的句子。

        注意：词典中的同一个单词可能在分段中被重复使用多次。

【样例】

输入	输出
s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]	["cats and dog","cat sand dog"]
s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]	["pine apple pen apple","pineapple pen apple","pine applepen apple"]
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]	[]

【解析及代码】

一手 DFS 就游戏结束了

讯享网class Solution(object): def wordBreak(self, s, wordDict): result = [] # 长度 -> 单词 mydict = {} for w in wordDict: mydict.setdefault(len(w), set()).add(w) def dfs(i, state): if i == len(s): return result.append(" ".join(state)) # 枚举子串长度 for p in mydict: j = i + p # 终点合法、该子串是单词 if j <= len(s) and s[i:j] in wordDict: dfs(j, state[:] + [s[i:j]]) dfs(0, []) return result

数组

1. 乘积最大子数组

【问题描述】

        给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

        测试用例的答案是一个 32 位整数。

        子数组是数组的连续子序列。

【样例】

输入	输出
nums = [2,3,-2,4]	6
nums = [-2,0,-1]	0

【解析及代码】

​​​​​​提示里面有个比较关键的信息：数组中的每个数的取值都是整数，这意味着能让乘积变小的只有 0 和负数

只要子数组里面出现 0 乘积就为 0，所以先把数组按 0 拆分成若干个子数组

而对于任意一个不包括 0 的子数组，如果里面的符号数为偶数的时候，全部相乘就是最大乘积；如果里面的符号数为奇数，那么第一个负号之后的乘积、最后一个负号的乘积中必有一个是最大值

再考虑一些特殊情况，如：[-2, 0, -1]，[0]。用 if 分支处理好即可

class Solution(object): def maxProduct(self, nums): import math have_zero = False # 按照 0 将数组分割成若干段 arrays = [] while nums: try: i, have_zero = nums.index(0), True except: i = len(nums) if nums[:i]: arrays.append(nums[:i]) nums = nums[i + 1:] def solve(arr): sign = tuple(map((0).__gt__, arr)) # 子数组中的负号数为偶数: 直接累乘 if not sum(sign) & 1 or len(arr) == 1: return math.prod(arr) # 子数组中的负号数为奇数: 去除第一个/最后一个负号 (只有一个负数时不能去除) return max(map(math.prod, (arr[sign.index(True) + 1:], arr[:len(sign) - 1 - sign[::-1].index(True)]))) # 特殊情况: 如 [-2, 0, -1] 这种, 利用算法得到的是 -1, 所以需要考虑 0 res = [] if arrays: res.append(max(map(solve, arrays))) if have_zero: res.append(0) return max(res) 

 

2. 多数元素 

【问题描述】 

        给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

        你可以假设数组是非空的，并且给定的数组总是存在多数元素。

【样例】

输入	输出
nums = [3,2,3]	3
nums = [2,2,1,1,1,2,2]	2

【解析及代码】

这道题用的是摩尔投票法：​​​​​​

假设数组中每个不同的数字就代表一个国家，而数字的个数就代表这个国家的人数，他们在一起混战，就是每两个两个同归于尽。我们就可以知道那个人数大于数组长度一半的肯定会获胜。

就算退一万步来说，其他的所有人都来攻击这个人数最多的国家，他们每两个两个同归于尽，最终剩下的也是那个众数。

 参照两两同归于尽的思路，代码很简单

讯享网class Solution(object): def majorityElement(self, nums): # 取出第 1 个元素作为主势力 count, major = 1, nums[0] for new in nums[1:]: # 人数 +1 if new == major: count += 1 # 换一个主势力 elif count == 0: count, major = 1, new # 干翻 1人 else: count -= 1 return major

3. 搜索二维矩阵

【问题描述】

        编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

        1. 每行的元素从左到右升序排列。

        2. 每列的元素从上到下升序排列。

【样例】

输入	输出	说明
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5	true
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20	false

【解析及代码】

 按照二分的思想，找到一个可以左右横跳的位置，即右上角或左下角 —— 以右上角为例：

 当前值 value 初始化为右上角，与目标值 target 比较：

• 若 value > target，则向左移动
• 若 value < target，则向下移动
• 若 value == target，则返回 True
• 如果移动后出界，则返回 False

class Solution(object): def searchMatrix(self, matrix, target): rows, cols = len(matrix), len(matrix[0]) r, c = 0, cols - 1 value = matrix[r][c] while value != target: # 向左搜索 if value > target: c -= 1 # 向下搜索 else: r += 1 if c < 0 or r >= rows: return False value = matrix[r][c] return True

 4. 合并两个有序数组

【问题描述】

        给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

        请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

        注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

【样例】

输入	输出
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3	[1,2,2,3,5,6]
nums1 = [1], m = 1, nums2 = [], n = 0	[1]
nums1 = [0], m = 0, nums2 = [1], n = 1	[1]

【解析及代码】

初始化两个指针 p1、p2，并指向两个数组的尾部，比较指针对应的数字，然后从 nums1 后面开始插入数字 —— 再加一个 blank 指明插入位置。以 nums1 = [2, 4, 6, 0, 0, 0]，nums2 = [1, 3, 7] 为例

p1	p2	blank	nums1
2	2	5	[2, 4, 6, 0, 0, 7]
2	1	4	[2, 4, 6, 0, 6, 7]
1	1	3	[2, 4, 6, 4, 6, 7]
0	1	2	[2, 4, 3, 4, 6, 7]
0	0	1	[2, 2, 3, 4, 6, 7]
-1	0	0	[1, 2, 3, 4, 6, 7]
-1	-1	-1	[1, 2, 3, 4, 6, 7]

合并过程结束的标志就是 p2 < 0。在比较指针对应位置的值的时候，考虑 p1 < 0的情况就可以了

讯享网class Solution(object): def merge(self, nums1, m, nums2, n): p1, p2 = m - 1, n - 1 blank = p1 + n while p2 >= 0: # 注意 p1 < 0 的情况 if p1 < 0 or nums2[p2] >= nums1[p1]: nums1[blank] = nums2[p2] p2 -= 1 else: nums1[blank] = nums1[p1] p1 -= 1 blank -= 1

堆、栈与队列

1. 数据流中的中位数

【问题描述】

        中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

        实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

【样例】

输入	输出
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]	[null, null, null, 1.5, null, 2.0]

【解析及代码】

 初始序列是空列，这个题的基本思路就是：

• 每次添加整数，先轮流加入 大根堆、小根堆，目的是维持两个堆的结点数差值 <= 1
• 大根堆的特点是根结点的值最大，小根堆同理。当大根堆的根结点值 <= 小根堆的根结点值，大根堆中的元素即为有序序列的前一半元素，小根堆中的元素即为有序序列的后一半元素
• 在需要查找中位数的时候，调整至 大根堆的根结点值 <= 小根堆的根结点值，然后就知道怎么干了

堆因为是完全二叉树的结构，所以直接用 list 存储。这个库其实还有大根堆的函数，但是功能不完全，函数名也对外隐藏了，所以不建议直接调用。用小根堆的函数来做大根堆的话，就是每一个元素都取反：push 和 pop 都要加负号

import heapq class MedianFinder(object): def __init__(self): self.max_heap, self.min_heap = [], [] self._flag = True def addNum(self, num): num = float(num) # 大根堆和小根堆长度相等: 新元素 -> 大根堆 # 大根堆结点数 - 小根堆结点数 == 1: 新元素 -> 小根堆 heapq.heappush(self.max_heap, -num) if self._flag \ else heapq.heappush(self.min_heap, num) self._flag = not self._flag def findMedian(self): # 确保小根堆不为空 if self.min_heap: while - self.max_heap[0] > self.min_heap[0]: # 大根堆堆顶 -> 小根堆 pop = - heapq.heappop(self.max_heap) pop = - heapq.heappushpop(self.min_heap, pop) # 小根堆堆顶 -> 大根堆 heapq.heappush(self.max_heap, pop) # 大根堆和小根堆长度相等 return (self.min_heap[0] - self.max_heap[0]) / 2 if self._flag else - self.max_heap[0]

原本一直超时 —— 但修改完、提交最后一次的时候，没想到过了

2. 有序矩阵中第 k 小的元素

【问题描述】

        给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

        你必须找到一个内存复杂度优于 O(n2) 的解决方案。

【样例】

输入	输出
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8	13
matrix = [[-5]], k = 1	-5

【解析及代码】

 有个思路我觉得在这个题作用不大，但是还是觉得有必要说一下

假设给定 9 * 9 的矩阵，推测前 9 个最小元素的分布情况发现，这几个最小元素总是聚在一起，从此我们可以把搜索区域收缩到这个范围内

• row = 1，col = k // 1 = 9，即全分布在第一行
• row = 2，col = k // 2 = 4，即前两行各分布 4 个，余下 1 个在第一行
• row = 3，col = k // 3 = 3，即前三行各分布 3 个
• row = 4，col = k // 4 = 2，即前四行各分布 2 个，余下 1 个在第一行
• row = 5，col = k // 5 = 1，以此类推

 把这个区域的元素整理成列表，然后用堆排找到目标就可以了

讯享网class Solution(object): def kthSmallest(self, matrix, k): import heapq seq, cols = [], len(matrix[0]) # 得出行的搜索边界 for i in range(min(k, len(matrix))): seq += matrix[i][:min(cols, k // (i + 1))] # 堆排得出前 k 个元素 return heapq.nsmallest(k, seq)[-1]

3. 基本计算器 Ⅱ

【问题描述】

        给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

        整数除法仅保留整数部分。

        你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

        注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

【样例】

输入	输出
s = "3+2*2"	7
s = " 3/2 "	1
s = " 3+5 / 2 "	5

【解析及代码】

首先介绍一个函数：eval(string)，可以把字符串转化成变量 return，如 string = "2 * 3 + 2"，则得到 8 —— 所以这个题完全可以一行代码结束

 重在过程，我们还是用多行代码实现一下。如果给定 "1 * 2 + 3"：

• 从头开始扫描，读到 "1 * 2" 的时候我们并不能确定是否可以计算 (假设存在比 * 优先级更高的运算符)
• 读到 "1 * 2 + 3"，我们就可以确定 2 这个数字是跟 1 还是 3 一起算了 —— 因为 * 的优先级高于 +，所以是否可计算的条件就是：前一个运算符的优先级 >= 当前运算符

本题的运算符只有 +、-、*、/，考虑边界条件，添加 起始符、结束符 就可以了

import re class Solution(object): def calculate(self, s): # re 正则表达式: 把数字和操作符分开 s = re.findall(r'[+\-*/]|\d+', s) + ['$'] # 初始化数值栈、操作符栈 oper, num = ['#'], [] # 优先级: # 起始标志, $ 结束标志 priority = {'#': -1, '$': 0, '+': 1, '-': 1, '*': 2, '/': 2} for ele in s: # 运算符: 先与前一个运算符比较，计算后再进栈 if ele in priority: # 前一个运算符优先级 >= 当前运算符 while priority[oper[-1]] >= priority[ele]: last_oper = oper.pop() # 弹出操作数 num1 = num.pop() num2 = num.pop() num.append(eval('{}{}{}'.format(num2, last_oper, num1))) oper.append(ele) # 数字: 直接进栈 else: num.append(ele) return int(num.pop())

排序与检索

1. 最大数

【问题描述】

        给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

        注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

【样例】

输入	输出
nums = [10,2]	"210"
nums = [3,30,34,5,9]	""

【解析及代码】

第二个样例给的是：nums = [3, 30, 34, 5, 9]，理想的排序是 [9, 5, 34, 3, 30]，这和按字典序排序的结果有点像 —— 字典序排序结果是 [9, 5, 34, 30, 3]，在 Python 里面把所有元素转成字符类，排序后就可以得到这个和答案接近的结果，利用字符类型的这个特性，来对字符类做个小改编

讯享网class Solution: def largestNumber(self, nums): class NewStr(str): def __lt__(self, other): return self + other < other + self return str(int(''.join(sorted(map(NewStr, nums), reverse=True))))

原本 "9" 和 "30" 比较是直接 "9" > "30"，现在是 "930" > "309"，得出 "9" > "30"

原本 "3" 和 "30" 比较是直接 "3" < "30"，现在是 "330" > "303"，得出 "3" > "30"，达成目的

动态规划

这里的题目不太完整，关于动态规划的题目，我主要写在了另一篇文章里：力扣 动态规划题集 Python

1. 至少有 k 个重复字符的最长子串

【问题描述】

        给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

【样例】

输入	输出
s = "aaabb", k = 3	3
s = "ababbc", k = 2	5

【解析及代码】

在可以分治的情况下就不要考虑什么动态规划了，如果一个字符串里面某一个字符出现的次数小于 k，那么就把字符串按这个字符分割成若干个字符串，然后对每个子字符串做同样的操作，写出来就是递归

from collections import Counter class Solution: def longestSubstring(self, s, k): if len(s) < k: return 0 for alpha, time in Counter(s).items(): if time < k: return max(map( lambda s: self.longestSubstring(s, k), s.split(alpha))) return len(s)

2. 矩阵中的最长递增路径

【问题描述】

        给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

        对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

【样例】

输入	输出	说明
matrix = [[9,9,4],[6,6,8],[2,1,1]]	4
matrix = [[3,4,5],[3,2,6],[2,2,1]]	4

【解析及代码】

图 + 记忆化 DFS，基本步骤是：

1. 写个把二维坐标展平成一维索引的函数，预处理得到邻接表
2. 初始化记忆表 memory，memory[idx] 表示以索引 idx 为起点的最长递增路径
3. 记忆化深度优先搜索：边调用有用的记忆，边存储新的记忆
4. 最终答案为 memory 的最大值

这里不使用 Floyd 做多源最短路的原因是：这是个有向图，而且每个点的出度不大于 4，这表明这个图对应的邻接矩阵是个稀疏矩阵，Floyd 算法会耗费很多不必须的空间

讯享网class Solution: def longestIncreasingPath(self, matrix): from functools import lru_cache rows, cols = len(matrix), len(matrix[0]) adj = [[] for _ in range(rows * cols)] # 行列坐标 -> 一维索引 loc2idx = lambda r, c: r * cols + c for r in range(rows): for c in range(cols): i, data = loc2idx(r, c), matrix[r][c] # 枚举矩阵中的每个单元格 for r_, c_ in ((0, 1), (1, 0)): new_r, new_c = r + r_, c + c_ # 枚举四个相邻格 if 0 <= new_r < rows and 0 <= new_c < cols: j, next_ = loc2idx(new_r, new_c), matrix[new_r][new_c] if data != next_: # 添加到邻接表 adj[i].append(j) if data < next_ else adj[j].append(i) @lru_cache(maxsize=None) def dfs(i): # 取最优路径 + 本身 / 走到死角，以该点为出发点的递增路径长度为 1 return (max(map(dfs, adj[i])) + 1) if adj[i] else 1 return max(map(dfs, range(rows * cols)))

我的这个思路相对直接记忆化深搜的做法比较清晰，但同时耗费的执行时间、空间也比较多。我觉得，在比赛的时候，还是要注意平衡性能 和 可读性。可读性强 -> 查 bug 容易，如果一味追求性能没有兼顾可读性，一旦出了 bug 会耗费大量时间

数学 & 位运算

 1. 只出现一次的数字

【问题描述】

        给你一个 非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

        你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

【样例】

输入	输出
nums = [2,2,1]	1
matrix = [[3,4,5],[3,2,6],[2,2,1]]	4

【解析及代码】

读题之后可以找到两个重点：只有一个元素只出现了一次、其余每个元素均出现两次

“相同为0，相异为1”，马上想到异或运算。所有元素都异或在一起，最终的数值就是只出现一次的元素

class Solution(object): def singleNumber(self, nums): x = nums.pop() while nums: x ^= nums.pop() return x

2. 阶乘后的零

【问题描述】

        给定一个整数 n ，返回 n! 结果中尾随零的数量。

【样例】

输入	输出
n = 3	0
n = 5	1
n = 0	0

【解析及代码】

10 的除了本身的因数有 1、2、5，也就是阶乘结果尾随 0 的个数是由因数 5 的个数决定的 (因数 2 的个数总是大于因数 5 的个数)。所有因数分解出几个 5，结果就有几个尾随 0

n! 因数分解中素数 p 的指数是：

讯享网class Solution(object): def trailingZeroes(self, n): cnt, power = 0, 1 while True: contri = n // 5 power if contri == 0: return cnt power += 1 cnt += contri return cnt

   

3. 缺失数字 

【问题描述】

        给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

【样例】

输入	输出
nums = [3,0,1]	2
nums = [0,1]	2
nums = [9,6,4,2,3,5,7,0,1]	8
nums = [0]	1

【解析及代码】

1. 位运算

长度为 n，则数字范围是 [0, n]，把这个范围的所有数添加到数组，就变成了“只有一个元素只出现了一次、其余每个元素均出现两次”

class Solution: def missingNumber(self, nums): x = 0 for i in range(1, len(nums) + 1): x ^= i for i in nums: x ^= i return x

2. 等差数列

讯享网class Solution: def missingNumber(self, nums)t: n = len(nums) return n * (n + 1) // 2 - sum(nums)