Leet Code 刷题笔记 - - 不求最快最省,但求最短最优雅 🌿,Shorter is better here.
- 代码精炼是 Python 的核心,同时能够反应对于语言的熟练程度,本项目目的在于汇总 leet code 最短最优雅的解法,拒绝长篇大论,缩短学习周期,掌握各种技巧,助您在面试中写出令人眼前一亮的解答,给考官留个好印象。
- 为什么我们追求最短?1.短代码更pythonic,而且通常能够避免一些冗余过程。2.除了刷题掌握算法思路之外,我们更追求深入理解和掌握python,学会套用技巧,举一反三。3.真正面试的时候不一定要这么短,可以适当展开几行(O_o除非你就是想秀其他人一脸😅),保证思路更清晰,相信就算展开几行也会比其他题解短很多吧。4.刷题很累,找点乐子,送给自己一些成就感吧。
- 项目持续更新中,默认使用 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 = {-nums[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。
- 对这个列表 r 中的所有节点进行从大到小的排序。O(NlogN)
- 把每个节点的指针指向前一个节点。(第一个节点,也就是最大的那个,指向None。)
- 返回最后一个节点,也就是整个新链表的开头。
-
如何把所有节点放进 r(result link)?
我们首先初始化 r 为空列表,初始化 n(node) 为题目所给的第一个链表的开头节点,并删除lists中的这个节点,接着进入while循环,如果 n 不为空,那么 r += [n],这里使用了切片的技巧(r[len(r):]=[n]相当于r=r+[n]),n=n.next,如果n是第一个链表的最后一个节点的话n.next就是None,下一次while的时候如果lists不为空就说明还有别的链表,此时n为None,我们让 r 不变,n=lists.pop(),也就是从lists中再取下一个节点赋值给n,重复以上步骤直到 lists 为空,我们就把所有节点放进 r 了。
-
怎么对 r 排序?
用了sorted函数,其中key定义了排序时用来比较的是每个元素的val属性,同时设置reverse为True代表降序排序。
-
如何修改每个节点的指针?
我们初始化 p(previous node) 为None。遍历降序排好的列表 r,r中的第一个元素就是值最大的元素,也就是我们应该返回的链表的结尾,我们设置它指向None,然后让p=这个节点,继续for循环。之后每经过一个节点 n 就把这个节点的next属性设置为上一个节点 p,遍历完成之后的 n,也就是我们遍历经过的最后一个元素,拥有最小的值,自然就是整个新链表的起始节点,我们将其作为输出值,函数返回。
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,当满足任一条件{1 targe < middle 且 middle 在前一段上 且 target < nums[0] 2 target > middle 且 middle 在第一段上 3 target > middle 且 middle 在第二段上 且 target <= nums[-1]}时,应该向右搜索,因此 getitem 返回 False。
- 另外还有一种简单的思路:二分法找到断点的位置恢复原始数组,然后正常二分法即可
class Solution: def search(self, nums, target): lo, hi, k = 0, len(nums) - 1, -1 while lo <= hi: m = (lo + hi) // 2 if m == len(nums) - 1 or nums[m] > nums[m+1]: k = m + 1 break elif m == 0 or nums[m] < nums[m-1]: k = m break if nums[m] > nums[0]: lo = m + 1 else: hi = m - 1 i = (bisect.bisect_left(nums[k:] + nums[:k], target) + k) % max(len(nums), 1) return i if nums and nums[i] == target else -1
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 multiply(self, num1: str, num2: str) -> str:
d = {}
for i, n1 in enumerate(num1[::-1]):
for j, n2 in enumerate(num2[::-1]): d[i + j] = d.get(i + j, 0) + int(n1) * int(n2)
for k in [*d]: d[k + 1], d[k] = d.get(k + 1, 0) + int(d[k] * 0.1), d[k] % 10
return re.sub('^0*', '', ''.join(map(str, d.values()))[::-1]) or '0'
- 本题的难点在于计算整数的时候不能超过32bits,因此使用竖式计算
- 我们遍历num1中的每个数字n1,然后带着这个数字遍历num2中的每个数字n2做乘法,所得乘积放进 d 中相应的位置然后逐位计算结果
- i + j 正好对应俩个数字相乘后所在的位置,比如 0 + 0 就应该是个位, 0 + 1 就是十位, 1 + 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 spiralOrder(self, matrix: List[List[int]]) -> List[int]:
return matrix and [*matrix.pop(0)] + self.spiralOrder([*zip(*matrix)][::-1])
- 为什么是
[*matrix.pop(0)]而不是matrix.pop(0)?因为对于后面的递归,传进来的列表中元素是tuple
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
r, n = [[n**2]], n**2
while n > 1: n, r = n - len(r), [[*range(n - len(r), n)]] + [*zip(*r[::-1])]
return r
- 流程图
|| => |9| => |8| |6 7| |4 5| |1 2 3|
|9| => |9 8| => |9 6| => |8 9 4|
|8 7| |7 6 5|
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 subsets(self, nums: List[int]) -> List[List[int]]:
from itertools import combinations
return sum([list(combinations(nums, i)) for i in range(len(nums) + 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: 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
class Solution:
def grayCode(self, n: int) -> List[int]:
return (lambda r: r + [x | 1<<n-1 for x in r[::-1]])(self.grayCode(n-1)) if n else [0]
- 前4个结果:
[0] [0 1] [00 01 11 10] [000 001 011 010 110 111 101 100] - 递归方程:这一步结果 = 上一步结果 + 上一步结果的镜像并在每个二进制数字前面加一位1
- << 左移符号,即在二进制表示后加一位 0 ,例子:3<<1 等于 6
(011 → 110),相当于 3 * 2的1次方 - x | 1<<n-1 就是在十进制数字 x 的二进制前面加一位1之后的十进制结果,比如 x = 1,有 1 | 10 等于 110
- 循环可以避免一些不必要的操作,会比递归快一些:
class Solution: def grayCode(self, n: int) -> List[int]: r = [0] for i in range(n): r.extend([x | 1<<i for x in r[::-1]]) return r - 或者直接背格雷码的公式吧:
class Solution:
def grayCode(self, n: int) -> List[int]:
return [i ^ i >> 1 for i in range(1 << n)]
# 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 maxProfit(self, prices: List[int]) -> int:
from functools import reduce
return reduce(lambda r, p: (max(r[0], p-r[1]), min(r[1], p)), prices, (0, float('inf')))[0]
- r = (结果,之前遍历过的所有元素中的最小值)
- reduce 函数详解
class Solution:
def maxProfit(self, prices: List[int]) -> int:
return sum(b - a for a, b in zip(prices, prices[1:]) if b > a)
- 本题可以在同一天买入和卖出,因此只要当天票价比昨天的高就可以卖出
class Solution:
def singleNumber(self, nums: List[int]) -> int:
from functools import reduce
return reduce(int.__xor__, nums)
- 这里用到了异或(xor),相同的数字异或后为0,0异或任何数都等于那个数,用reduce在列表所有元素之间使用异或^,那么留下的就是那个单独的数字了。
class MinStack:
def __init__(self):
self.data = [(None, float('inf'))]
def push(self, x: 'int') -> 'None':
self.data.append((x, min(x, self.data[-1][1])))
def pop(self) -> 'None':
if len(self.data) > 1: self.data.pop()
def top(self) -> 'int':
return self.data[-1][0]
def getMin(self) -> 'int':
return self.data[-1][1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
a, b = (headA, headB) if headA and headB else (None, None)
while a != b: a, b = not a and headB or a.next, not b and headA or b.next
return a
- 这题不支持 Python3 所以只能用 Python2 做了
- 把第一条链表的尾部接到第二条链表的开头,第二条接到第一条的开头,就能消除俩条链表的长度差,并在某一时刻在第一个交叉点相遇,或在走完俩条链表长度的时候同时为 None
class Solution:
def majorityElement(self, nums: List[int]) -> int:
return sorted(nums)[len(nums) // 2]
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:
if head: 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 findKthLargest(self, nums: List[int], k: int) -> int:
return sorted(nums)[-k]
- O(NlogN)调库
- 面试官一般不会接受以上答案的,可以参考下面这个2行的quick-selection,思路借鉴的quick-sort
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # return sorted(nums)[-k] l, m, r = [x for x in nums if x > nums[0]], [x for x in nums if x == nums[0]], [x for x in nums if x < nums[0]] return self.findKthLargest(l, k) if k <= len(l) else nums[0] if k <= len(l) + len(m) else self.findKthLargest(r, k - len(l) - len(m))
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len(nums) != len(set(nums))
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and n & n - 1 == 0
- 2 的幂的二进制形式最高位一定是1,其余为0
- 用常规思路也行
class Solution: def isPowerOfTwo(self, n: int) -> bool: return n > 0 and not n & 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 lowestCommonAncestor(self, root, p, q):
while (root.val - p.val) * (root.val - q.val) > 0: root = (root.left, root.right)[p.val > root.val]
return root
- 最近公共祖先的值一定介于p、q值之间(闭区间)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
l, r = map(lambda x: x and self.lowestCommonAncestor(x, p, q), (root.left, root.right))
return (root in (p, q) or l and r) and root or l or r
- 递归全部节点,p 的祖先节点全部返回 p,q 的祖先节点全部返回 q,除非它同时是俩个节点的最近祖先,也就是 p,q 分别位于左右子树,那么返回自身
- 这思路用在235也行
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val, node.next = node.next.val, node.next.next
node = node.next是不行的,因为这里只是改了函数参数引用的对象,而原来传进来的 node 没有任何改变
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
res, l, r = [1] * len(nums), 1, 1
for i, j in zip(range(len(nums)), reversed(range(len(nums)))):
res[i], l = res[i] * l, l * nums[i]
res[j], r = res[j] * r, r * nums[j]
return res
- O(N)双指针双向遍历
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return int(len(nums) * (len(nums) + 1) / 2 - sum(nums))
- 等差数列求和公式
class Solution:
def canWinNim(self, n: int) -> bool:
return bool(n % 4)
- 只要轮到你的时候剩余石头数量不是 4 的倍数都是完胜,因为你有办法使得每次轮到对方的时候剩余石头数量都为 4 的倍数
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
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(s.split(' ')[::-1])[::-1]
注:此处贡献名单仅代表汇总搜集贡献,不代表全部原创,欢迎所有更短的解法🤓
- Knife丶[QQ1272068154 微信ly18597591102]