力扣 算法面试题汇总 Python

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

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

字符串

 1. 验证回文串

【问题描述】

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

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

【样例】

【解析及代码】

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 所有可能的分割方案。

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

【样例】

【解析及代码】

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

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 。

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

【样例】

【解析及代码】

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

首先初始化一维列表 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 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序返回所有这些可能的句子。

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

【样例】

【解析及代码】

一手 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 位整数。

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

【样例】

【解析及代码】

​​​​​​提示里面有个比较关键的信息：数组中的每个数的取值都是整数，这意味着能让乘积变小的只有 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 ⌋ 的元素。

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

【样例】

【解析及代码】

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

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

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

作者：数据结构和算法
https://leetcode-cn.com/leetbook/read/top-interview-questions/xm77tm/?discussion=POk1ka

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

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. 每列的元素从上到下升序排列。

【样例】

【解析及代码】

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

 当前值 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 。

【样例】

【解析及代码】

初始化两个指针 p1、p2，并指向两个数组的尾部，比较指针对应的数字，然后从 nums1 后面开始插入数字 —— 再加一个 blank 指明插入位置。以 nums1 = [2, 4, 6, 0, 0, 0]，nums2 = [1, 3, 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 以内的答案将被接受。

【样例】

【解析及代码】

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

• 每次添加整数，先轮流加入 大根堆、小根堆，目的是维持两个堆的结点数差值 <= 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) 的解决方案。

【样例】

【解析及代码】

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

假设给定 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() 。

【样例】

【解析及代码】

首先介绍一个函数：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 = [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 。返回这一子串的长度。

【样例】

【解析及代码】

在可以分治的情况下就不要考虑什么动态规划了，如果一个字符串里面某一个字符出现的次数小于 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 ，找出其中 最长递增路径 的长度。

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

【样例】

【解析及代码】

图 + 记忆化 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 ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

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

【样例】

【解析及代码】

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

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

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

2. 阶乘后的零

【问题描述】

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

【样例】

【解析及代码】

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] 这个范围内没有出现在数组中的那个数。

【样例】

【解析及代码】

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)