Leet Code 刷题笔记 - - 不求最快最省，但求最短最优雅 🌿，Shorter is better here.
- 代码精炼是 Python 的核心，同时能够反应对于语言的熟练程度，本项目目的在于汇总 leet code 最短最优雅的解法，拒绝长篇大论，缩短学习周期，掌握各种技巧，助您在面试中写出令人眼前一亮的解答，给考官留个好印象。
- 项目持续更新中，默认使用 python3，如果已编辑题目中有更短更优雅的解法欢迎联系我更新~ [直接发issue 或 fork 或 联系 QQ1272068154 微信ly18597591102，记得留下署名和联系方式 🐼]
- 由于CSDN博客更新需要人工审核比较慢，所以迁移到github上，优先更新github内容。
- 为了快速找到题目可以按 [Ctrl键 + F键] 输入题目序号或名字定位。
默认已看过题目，🤡 没看过的话点标题可以跳转链接
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
d = {target - n: i for i, n in enumerate(nums)}
return [[d[n], i] for i, n in enumerate(nums) if n in d and d[n] > i][0]
-
O(N)时间效率的快速解法，用字典记录 需要的值:当前索引
-
如果字典中存在相同的数字，那么将会记录比较大的那个索引，因此可以用
d[n] > i来避免一个元素重复选择 -
改成 for 循环加 break 再加动态修改字典能更快一点
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: d = {} for i, n in enumerate(nums): if n in d: return [d[n], i] d[target-n] = i
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode, carry=0) -> ListNode:
if not (l1 or l2): return ListNode(1) if carry else None
l1, l2 = l1 or ListNode(0), l2 or ListNode(0)
val = l1.val + l2.val + carry
l1.val, l1.next = val % 10, self.addTwoNumbers(l1.next, l2.next, val > 9)
return l1
- int(True) 等于 1
- None or 7 等于 7
- 用 carry 记录是否应该进位
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
b, m, d = 0, 0, {}
for i, l in enumerate(s): b, m, d[l] = max(b, d.get(l, -1) + 1), max(m, i - b), i
return max(m, len(s) - b)
- b代表起始位置，m代表上一步的最大无重复子串，d是一个字典，记录着到当前步骤出现过的字符对应的最大位置
- 每次迭代过程中，遇到遇见过的字符时，b就会变为那个字符上一次出现位置+1，m记录上一次应该达到的全局最大值，所以最后需要再比较一次
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
a, b, m = *sorted((nums1, nums2), key=len), (len(nums1) + len(nums2) - 1) // 2
self.__class__.__getitem__ = lambda self, i: m-i-1 < 0 or a[i] >= b[m-i-1]
i = bisect.bisect_left(self, True, 0, len(a))
r = sorted(a[i:i+2] + b[m-i:m-i+2])
return (r[0] + r[1 - (len(a) + len(b)) % 2]) / 2
- 本题思路与官方题解类似，时间复杂度O(log(min(m, n)))，没看过的话建议先大体了解一下
- python 中 bisect 模块针对的是 list, 如果直接构造 list，时间复杂度为 O(min(m, n))，因此我们修改当前类的魔法方法伪造 list
- 在一个有序递增数列中，中位数左边的那部分的最大值一定小于或等于右边部分的最小值
- 如果总数组长度为奇数，m 代表中位数的索引，否则 m 代表用于计算中位数的那两个数字的左边一个。比如输入为[1,2]，[3]，那么m应该为[1,2,3]中位数2的索引1，如果输入为[1,3]，[2,4]，那么m应该为[1,2,3,4]中2的索引1
- 使用二分搜索找到 m 对应的值在a或b中对应的索引，也就是说，我们要找的中位数或中位数左部应该是 a[i] 或者 b[m-i]
- bisect.bisect_left 搜索列表中保持列表升序的情况下，True应该插入的位置（从左侧），比如 [F,F,T] 返回 2，[F,F] 返回 2
- 这里保证 a 是 nums1 和 nums2 中较短的那个，是为了防止二分搜索的时候索引越界
- sorted返回一个list，假设返回值是 [nums1, nums2]，那么前面加个 * 号就代表取出列表的所有内容，相当于一个迭代器，结果相当于直接写 nums1, nums2
class Solution:
def longestPalindrome(self, s: str) -> str:
for i, j in [(i, j) for i in range(len(s)) for j in (0, 1)]:
while i > -1 and i + j < len(s) and s[i] == s[i + j]: i, j = i - 1, j + 2
r = max(locals().get('r', s[i]), s[i + 1:i + j], key=len)
return '' if not s else r
- 遍历字符串的每个索引 i，判断能否以 s[i] 或 s[i:i+j+1] 为中心向往拓展回文字符串
- 如果 r 已经初始化则
locals().get('r', s[i])返回 r 的值，否则返回 s[i]
class Solution:
def reverse(self, x):
r = x // max(1, abs(x)) * int(str(abs(x))[::-1])
return r if r.bit_length() < 32 or r == -2**31 else 0
- x // max(1, abs(x))意味着 0：x为0， 1：x为正， -1：x为负，相当于被废弃的函数cmp
- [::-1]代表序列反转
- 2^31 和 -2^31 的比特数为32，其中正负号占用了一位
- 32位整数范围 [−2^31, 2^31 − 1] 中正数范围小一个是因为0的存在
class Solution:
def myAtoi(self, s: str) -> int:
return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
- 使用正则表达式
^：匹配字符串开头，[\+\-]：代表一个+字符或-字符，?：前面一个字符可有可无，\d：一个数字，+：前面一个字符的一个或多个，\D：一个非数字字符，*：前面一个字符的0个或多个 max(min(数字, 2**31 - 1), -2**31)用来防止结果越界
class Solution:
def isPalindrome(self, x: int) -> bool:
return str(x) == str(x)[::-1]
不使用字符串的进阶解法：
class Solution:
def isPalindrome(self, x: int) -> bool:
r = list(map(lambda i: int(10**-i * x % 10), range(int(math.log10(x)), -1, -1))) if x > 0 else [0, x]
return r == r[::-1]
- 思路是一样的，这里把整数转成了列表而不是字符串
- 比如一个整数12321，我想取出百位数可以这么做：12321 * 10^{int(log_{10}12321)} % 10 = 123 % 10 = 3
class Solution:
def maxArea(self, height: List[int]) -> int:
res, l, r = 0, 0, len(height) - 1
while l < r: res, l, r = (max(res, height[l] * (r - l)), l + 1, r) if height[l] < height[r] else (max(res, height[r] * (r - l)), l, r - 1)
return res
- 双指针 O(N) 解法
- res：结果，l：容器左壁索引，r：容器右壁索引
- 如果 height[l] < height[r] 那么 l += 1 否则 r -= 1，说明：如果 height[0] < height[3] 那么(0, 1), (0, 2)对应的容器体积一定小于(0, 3)的，因为此时计算体积的时候高为 height(0)，容器的宽减少而高不增加，面积必然缩小
class Solution:
def romanToInt(self, s: str) -> int:
d = {'I':1, 'IV':3, 'V':5, 'IX':8, 'X':10, 'XL':30, 'L':50, 'XC':80, 'C':100, 'CD':300, 'D':500, 'CM':800, 'M':1000}
return sum([d.get(s[max(i-1, 0):i+1], d[n]) for i, n in enumerate(s)])
- 构建一个字典记录所有罗马数字子串，注意长度为2的子串记录的值是（实际值-子串内左边罗马数字代表的数值）
- 这样一来，遍历整个s的时候判断当前位置和前一个位置的两个字符组成的字符串是否在字典内，如果在就记录值，不在就说明当前位置不存在小数字在前面的情况，直接记录当前位置字符对应值
- 举个例子，遍历经过IV的时候先记录I的对应值1再往前移动一步记录IV的值3，加起来正好是IV的真实值4。max函数在这里是为了防止遍历第一个字符的时候出现[-1:0]的情况
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
r = [len(set(c)) == 1 for c in zip(*strs)] + [0]
return strs[0][:r.index(0)] if strs else ''
- 利用好zip和set
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums, r = sorted(nums), set()
for i in [i for i in range(len(nums)-2) if i < 1 or nums[i] > nums[i-1]]:
d = {-num
1031D
s[i]-n: j for j, n in enumerate(nums[i + 1:])}
r.update([(nums[i], n, -nums[i]-n) for j, n in enumerate(nums[i+1:]) if n in d and d[n] > j])
return list(map(list, r))
- 时间复杂度：O(N^2)
- 这里 sort 一是为了避免重复，这一点可以体现在我们输出的结果都是升序的，如果不这么做 set 无法排除一些相同结果，而是为了节省计算，防止超时
- for 循环内部的代码思想同
第一题 Two Sum，用字典记录｛需要的值:当前索引｝，如果字典中存在相同的数字，那么将会记录比较大的那个索引，因此可以用d[n] > i来避免一个元素重复选择 (nums[i], n, -nums[i]-n)保证了列表升序
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums, r, end = sorted(nums), float('inf'), len(nums) - 1
for c in range(len(nums) - 2):
i, j = max(c + 1, bisect.bisect_left(nums, target - nums[end] - nums[c], c + 1, end) - 1), end
while r != target and i < j:
s = nums[c] + nums[i] + nums[j]
r, i, j = min(r, s, key=lambda x: abs(x - target)), i + (s < target), j - (s > target)
return r
- float('inf') = 正无穷
- 排序，遍历，双指针，O(N^2) 时间复杂度，二分法初始化
- 排序是为了使用双指针，首先遍历得到索引 c，然后计算 c，左指针 i，右指针 j 对应数字之和，如果大于 target，j 向内移动，否则 i 向内移动
- i 的初始值不是 c + 1，是为了减少计算量，用二分法得到一个合理的初始值
class Solution:
def isValid(self, s: str) -> bool:
while any(('()' in s, '[]' in s, '{}' in s)): s = s.replace('()', '').replace('[]', '').replace('{}', '')
return not s
-
不断删除有效括号直到不能删除，思路简单效率低。另外，stack的方法也很简单，而且快多了。
class Solution: def isValid(self, s: str) -> bool: stack, d = [], {'{': '}', '[': ']', '(': ')'} for p in s: if p in '{[(': stack += [p]; elif not (stack and d[stack.pop()] == p): return False return not stack
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 and l2:
l1, l2 = sorted((l1, l2), key=lambda x: x.val)
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
- 7 or 9 等于 7
- None and 7 等于 None
- sorted用在这里为了保证 l1 的值小于等于 l2 的值
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
r, n, p = [], lists and lists.pop(), None
while lists or n: r[len(r):], n = ([n], n.next or lists and lists.pop()) if n else ([], lists.pop())
for n in sorted(r, key=lambda x: x.val, reverse=True): n.next, p = p, n
return n if r else []
- 第一行：初始化一些变量，r：结果，n：节点，p：前一个节点
- 第二行：把所有节点放进列表 r
- 第三行：按顺序排列所有节点并构建连接
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
for i in range(len(nums)-1, 0, -1):
if nums[i] == nums[i-1]: nums.pop(i)
return len(nums)
- 时间效率O(N)空间效率O(1)，逆遍历可以防止删除某个元素后影响下一步索引的定位。
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
return haystack.find(needle)
-
不用内置函数也可以
class Solution: def strStr(self, haystack: 'str', needle: 'str') -> 'int': for i in range(0, len(haystack) - len(needle) + 1): if haystack[i:i+len(needle)] == needle: return i return -1
class Solution:
def search(self, nums, target):
self.__class__.__getitem__ = lambda self, m: not(target < nums[0] <= nums[m] or nums[0] <= nums[m] < target or nums[m] < target <= nums[-1])
i = bisect.bisect_left(self, True, 0, len(nums))
return i if target in nums[i:i+1] else -1
- 作出数列的函数图像，可以看作是一个含断点的局部递增函数，形如:zap:，前面一段总是比较高
- python 中 bisect 模块针对的是 list, 如果直接构造 list，相当于遍历所有元素，时间复杂度为 O(N) 而不是 O(logN)，因此我们修改当前类的魔法方法伪造 list，然后用当前类代替list
- 用二分搜索时，m 代表 middle，low 代表 low，hi 代表 high，当满足任一条件｛① targe < middle 且 middle 在前一段上 且 target < nums[0] ② target > middle 且 middle 在第一段上 ③ target > middle 且 middle 在第二段上 且 target <= nums[-1]｝时，应该向右搜索，因此 getitem 返回 False。
class Solution:
def countAndSay(self, n: int) -> str:
return '1' * (n is 1) or re.sub(r'(.)\1*', lambda m: str(len(m.group())) + m.group(1), self.countAndSay(n - 1))
- 正则表达式 re.sub(正则，替换字符串或函数，被替换字符串，是否区分大小写)
- . 可匹配任意一个除了\n的字符 (.) 匹配任意一个除了\n的字符并把这个匹配结果放进第一组 (.)\1 匹配一个任意字符的二次重复并把那个字符放入数组 (.)\1* 匹配一个任意字符的多次重复并把那个字符放入数组
- group(default=0)可以取匹配文本 group(1)取第一个括号内的文本
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return [[n] + sub for i, n in enumerate(nums) for sub in self.permute(nums[:i] + nums[i+1:])] or [nums]
-
每次固定第一个数字递归地排列数组剩余部分
-
python 有内置函数可以直接实现
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: from itertools import permutations return list(permutations(nums))
class Solution:
def maxSubArray(self, nums):
from functools import reduce
return reduce(lambda r, x: (max(r[0], r[1]+x), max(r[1]+x,x)), nums, (max(nums), 0))[0]
-
r[0]代表以当前位置为结尾的局部最优解
-
r[1]代表全局最优解
-
直接DP的解法更好理解一些
class Solution: def maxSubArray(self, nums: List[int]) -> int: for i in range(1, len(nums)): nums[i] = max(nums[i], nums[i] + nums[i-1]) return max(nums)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))
- 题目可以转换为排列组合问题，解是C(min(m,n), m+n)，从m+n个中选出m个下移或n个右移。
- 用DP做也很快，以后自己算 C(a, b) 也可以用算这题的DP法代替
- math.factorial 的速度不亚于DP，可能内部有优化
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
return list(map(int, str(int(''.join(map(str, digits))) + 1)))
class Solution:
def mySqrt(self, x: int) -> int:
return int(x ** 0.5)
出题者应该是希望看到下面的答案：
class Solution:
def mySqrt(self, x: int) -> int:
r = x
while r*r > x:
r = (r + x/r) // 2
return int(r)
- 基本不等式(a+b)/2 >=√ab 推导自 (a-b)^2 >= 0，注意 a>0 且 b>0
- r 代表 result
class Solution:
def climbStairs(self, n: int) -> int:
from functools import reduce
return reduce(lambda r, _: (r[1], sum(r)), range(n), (1, 1))[0]
- dp递归方程：到达当前楼梯的路径数 = 到达上个楼梯的路径数 + 到达上上个楼梯的路径数
- 这里用一个元组 r 来储存（当前楼梯路径数，下一层楼梯路径数）
- 利用 reduce 来代替for循环，reduce 函数详解。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
while n > 0: nums1[m+n-1], m, n = (nums1[m-1], m-1, n) if m and nums1[m-1] > nums2[n-1] else (nums2[n-1], m, n-1)
-
这种题倒着算更容易
-
上面那行代码其实就相当于：
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ while n > 0: if m and nums1[m-1] > nums2[n-1]: nums1[m+n-1], m, n = nums1[m-1], m-1, n else: nums1[m+n-1], m, n = nums2[n - 1], m, n-1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
return max(map(self.maxDepth,(root.left, root.right))) + 1 if root else 0
- 利用map函数递归左右节点获取最大值，map函数会将参数一所指向的函数应用于参数二里的所有对象并返回所有结果。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
from functools import reduce
return reduce(int.__xor__, nums)
- 这里用到了异或（xor），相同的数字异或后为0，0异或任何数都等于那个数，用reduce在列表所有元素之间使用异或^，那么留下的就是那个单独的数字了。
class Solution:
def rob(self, nums: List[int]) -> int:
from functools import reduce
return reduce(lambda r, n: (max(r[0], n + r[1]), r[0]), nums, (0, 0))[0]
- DP递归方程：一直偷到这家的钱 = max（一直偷到上一家的钱，一直偷到上上家的钱 + 这家的钱）😃有点小绕
- 以上为下面代码的化简版，reduce 函数详解。
class Solution:
def rob(self, nums: List[int]) -> int:
last, now = 0, 0
for i in nums:
last, now = now, max(last + i, now)
return now
- DP不一定要数组，这里两个变量就够了，空间复杂度为O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode, tail=None) -> ListNode:
head.next, tail, head = tail, head, head.next
return self.reverseList(head, tail) if head else tail
- 递归解法
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
p = None
while head: head.next, p, head = p, head, head.next
return p
- 迭代解法
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return int(len(nums) * (len(nums) + 1) / 2 - sum(nums))
- 等差数列求和公式
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s.reverse()
class Solution:
def fizzBuzz(self, n):
return ['Fizz' * (not i % 3) + 'Buzz' * (not i % 5) or str(i) for i in range(1, n+1)]
- 7 or 8 = 7
- 0 or 8 = 8
注：此处贡献名单仅代表汇总搜集贡献，不代表全部原创，欢迎所有更短的解法🤓
- Knife丶[QQ1272068154 微信ly18597591102]