Leet Code 刷题笔记 - - 不求最快最省,但求最短最优雅,Shorter is better here.
Leet Code 刷题笔记 - - 不求最快最省,但求最短最优雅 🌿,Shorter is better here.
此专栏追求代码的精简和技巧性,默认已看过题目,🤡 没看过的话点标题可以跳转链接,咱们一起体验炫酷的 Python
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
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
i, r, d = 0, 0, {}
for j, c in enumerate(s): i, r, d[c] = max(i, d.get(c, -1) + 1), max(r, j - i), j
return max(r, len(s) - i)
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
class Solution:
def longestPalindrome(self, s: str) -> str:
r = ''
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(r, s[i + 1:i + j], key=len)
return '' if not s else r
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
class Solution:
def myAtoi(self, s: str) -> int:
return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
^:匹配字符串开头,[\+\-]:代表一个+字符或-字符,?:前面一个字符可有可无,\d:一个数字,+:前面一个字符的一个或多个,\D:一个非数字字符
max(min(数字, 2**31 - 1), -2**31)
用来防止结果越界class Solution:
def isPalindrome(self, x: int) -> bool:
return (k:=str(x)) == k[::-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]
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
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))
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 ''
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
return os.path.commonprefix(strs)
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))
第一题 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
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
from itertools import product
l = '- - abc def ghi jkl mno pqrs tuv wxyz'.split()
return [''.join(c) for c in product(*[l[int(i)] for i in digits])] if digits else []
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
from itertools import combinations as com
dic, l = collections.defaultdict(list), [*com(range(len(nums)), 2)]
for a, b in l: dic[target - nums[a] - nums[b]].append((a, b))
r = [(*ab, c, d) for c, d in l for ab in dic[nums[c] + nums[d]]]
return [*set(tuple(sorted(nums[i] for i in t)) for t in r if len(set(t)) == 4)]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
l = []
while head: l, head = l + [head], head.next
if n != len(l): l[-n-1].next = l[-n].next
del l[-n]
return l and l[0]
class Solution:
def isValid(self, s: str) -> bool:
while any(('()' in s, '[]' in s, '{}' in s)): s = s.replace('()', '').replace('[]', '').replace('{}', '')
return not s
# 国际站上有一种写法是这样的,相比于上面,下面的写法更加优雅(好理解)一点
class Solution:
def isValid(self, s: str) -> bool:
while s:
l = len(s)
s = s.replace('()', '').replace('[]', '').replace('{}', '')
if l == len(s): break
return not s
不断删除有效括号直到不能删除,思路简单效率低。另外,stack的方法也很简单,而且快多了。
class Solution:
def isValid(self, s: str) -> bool:
stack, d = [], {'{': '}', '[': ']', '(': ')'}
for p in s:
if p in d:
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:
if l1.val > l2.val: l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or 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(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,也就是我们遍历经过的最后一个元素,拥有最小的值,自然就是整个新链表的起始节点,我们将其作为输出值,函数返回。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head and head.next:
head.next.next, head.next, head = head, self.swapPairs(head.next.next), head.next
return head
这里
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)
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
nums[i + 1] = nums[j]
i += 1
return i + 1 if nums else 0
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 divide(self, dividend: int, divisor: int) -> int:
a, b, r, t = abs(dividend), abs(divisor), 0, 1
while a >= b or t > 1:
if a >= b: r += t; a -= b; t += t; b += b
else: t >>= 1; b >>= 1
return min((-r, r)[dividend ^ divisor >= 0], (1 << 31) - 1)
a * 2**b
,a >> b 相当于 a // 2**b
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
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 searchRange(self, nums: List[int], target: int) -> List[int]:
# if not nums or target not in nums: return [-1, -1]
return [bisect.bisect_left(nums, target), bisect.bisect_right(nums, target)-1] \
if nums and target in nums else [-1, -1]
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect.bisect_left(nums, target, 0, len(nums))
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row = [[x for x in y if x != '.'] for y in board]
col = [[x for x in y if x != '.'] for y in zip(*board)]
pal = [[board[i+m][j+n] for m in range(3) for n in range(3) if board[i+m][j+n] != '.'] for i in (0, 3, 6) for j in (0, 3, 6)]
return all(len(set(x)) == len(x) for x in (*row, *col, *pal))
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))
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'
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) + (ord(n1) - 48) * (ord(n2) - 48)
for k in [*d]:
d[k + 1], d[k] = d.get(k + 1, 0) + math.floor(d[k] * 0.1), d[k] % 10
return re.sub('^0*', '', ''.join(map(str, d.values()))[::-1]) or '0'
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 rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
matrix[:] = [i[::-1] for i in zip(*matrix)]
加 [:] 才会修改原列表
class Solution:
def groupAnagrams(self, strs):
return [[*x] for _, x in itertools.groupby(sorted(strs, key=sorted), sorted)]
class Solution:
def myPow(self, x, n, r=1) -> float:
x, n = n < 0 and 1 / x or x, abs(n)
return self.myPow(x * x, n // 2, r * (not n % 2 or x)) if n else r
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)
?因为对于后面的递归,传进来的列表中元素是tupleclass Solution:
def lengthOfLastWord(self, s: str) -> int:
return len(s.strip(' ').split(' ')[-1])
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|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
l = []
while head: l[len(l):], head = [head], head.next
if l: l[-1].next, l[-1 - k % len(l)].next = l[0], None
return l[- k % len(l)] if l else None
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))
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
return list(map(int, str(int(''.join(map(str, digits))) + 1)))
class Solution:
def addBinary(self, a: str, b: str) -> str:
return bin(int(a, 2) + int(b, 2))[2:]
class Solution:
def addBinary(self, a: str, b: str) -> str:
r, p = '', 0
d = len(b) - len(a)
a = '0' * d + a
b = '0' * -d + b
for i, j in zip(a[::-1], b[::-1]):
s = int(i) + int(j) + p
r = str(s % 2) + r
p = s // 2
return '1' + r if p else r
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)
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]
class Solution:
def simplifyPath(self, path: str) -> str:
r = []
for s in path.split('/'):
r = {'':r, '.':r, '..':r[:-1]}.get(s, r + [s])
return '/' + '/'.join(r)
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
row = [[0] * len(i) if 0 in i else i for i in matrix]
col = [[0] * len(j) if 0 in j else list(j) for j in zip(*matrix)]
col2row = list(map(list, zip(*col)))
# 上面一行效果等同:
# col2row = [list(i) for i in zip(*col)]
for i in range(len(matrix)):
matrix[i] = col2row[i] if row[i] != [0] * len(matrix[0]) else row[i]
matrix
中有0的列全为0,行不变zip(*col)
返回的是zip
类型,需要转换成list,其中元素类型为元组col2row
对应的各行class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]: return False
col = list(list(zip(*matrix))[0]) # set() -> list()
index = bisect.bisect_left(col, target, 0, len(matrix)-1) # 二分查找
return target in (matrix[index] + matrix[index-1])
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)], [])
def removeDuplicates(nums: [int]) -> int:
for i in range(len(nums)-3, -1, -1):
if nums[i] == nums[i+1] and nums[i] == nums[i+2]:
nums.pop(i)
return len(nums)
def search(nums: [int], target: int) -> bool:
return target in nums
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head:
head.next = self.deleteDuplicates(head.next)
return head.next if head.next and head.val == head.next.val else head
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]
[0]
[0 1]
[00 01 11 10]
[000 001 011 010 110 111 101 100]
(011 → 110)
,相当于 3 * 2的1次方 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)]
class Solution:
def numDecodings(self, s: str) -> int:
pp, p = 1, int(s[0] != '0')
for i in range(1, len(s)):
pp, p = p, pp * (9 < int(s[i-1:i+1]) <= 26) + p * (int(s[i]) > 0)
return p
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
f = self.inorderTraversal
return f(root.left) + [root.val] + f(root.right) if root else []
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
r, stack = [], []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return r
node = stack.pop()
r.append(node.val)
root = node.right
return r
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode, first=True) -> bool:
if not root: return first or []
l = self.isValidBST(root.left, 0) + [root.val] + self.isValidBST(root.right, 0)
return all([a > b for a, b in zip(l[1:], l)]) if first else l
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root or root.left is root.right: return True
l, r, i, o = root.left, root.right, TreeNode(0), TreeNode(0)
if (l and l.val) != (r and r.val): return False
i.left, i.right, o.left, o.right = l.left, r.right, l.right, r.left
return self.isSymmetric(i) and self.isSymmetric(o)
# 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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode, first=True) -> bool:
if not root: return first or 0
l, r = map(lambda x: self.isBalanced(x, False), [root.left, root.right])
return max(l,r)+1 if min(l,r)>-1 and abs(l-r)<=1 else (-1, False)[first]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: return False
l, r, f = root.left, root.right, lambda x: self.hasPathSum(x, sum - root.val)
return l is r and sum == root.val or f(l) or f(r)
sum - node.val
即为 原始的sum - 整条路径的总和
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
return [[math.factorial(i)//math.factorial(i-j)//math.factorial(j) for j in range(i+1)] for i in range(numRows)]
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
r = [[1]]
for i in range(1, numRows):
r.append([1] + [sum(r[-1][j:j+2]) for j in range(i)])
return numRows and r or []
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]
class Solution:
def maxProfit(self, prices: List[int]) -> int:
r, m = 0, float('inf')
for p in prices:
r, m = max(r, p - m), min(m, p)
return r
class Solution:
def maxProfit(self, prices: List[int]) -> int:
return sum(b - a for a, b in zip(prices, prices[1:]) if b > a)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxPathSum(self, root: TreeNode, ok=True) -> int:
if not root: return 0
l, r = self.maxPathSum(root.left, False), self.maxPathSum(root.right, False)
self.max = max(getattr(self, 'max', float('-inf')), l + root.val + r)
return self.max if ok else max(root.val + max(l, r), 0)
max(以当前节点为结尾的最大路径和,0)
。并更新最大值全局最大路径和=max(全局最大路径和,当前节点值+左子树返回结果+右子树返回结果)
"""
# Definition for a Node.
class Node:
def __init__(self, val, neighbors):
self.val = val
self.neighbors = neighbors
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
return copy.deepcopy(node)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
from functools import reduce
return reduce(xor, nums)
"""
# Definition for a Node.
class Node:
def __init__(self, val, next, random):
self.val = val
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
return copy.deepcopy(head)
class Solution:
def wordBreak(self, s, wordDict):
def f(s, d={}):
if not s in d:
for i in range(1, 1 + len(s)):
d[s[:i]] = s[:i] in wordDict and (i == len(s) or f(s[i:]))
if d[s[:i]]: return True
return False
return d[s]
return f(s)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
while head and head.val != None: head.val, head = None, head.next
return head != None
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
slow = fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
return True
return False
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
s = {None}
while head not in s:
s.add(head)
head = head.next
return head
2(H + D) = H + D + nL
,因此可以推出 H = nL - D
,这意味着如果我们让俩个慢指针一个从 head 出发,一个从 X 出发的话,他们一定会在节点 E 相遇
_____
/ \
head___________E \
\ /
X_____/
class Solution(object):
def detectCycle(self, head):
slow = fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
break
else:
return None
while head is not slow:
head = head.next
slow = slow.next
return head
class LRUCache(object):
def __init__(self, capacity):
self.od, self.cap = collections.OrderedDict(), capacity
def get(self, key):
if key not in self.od: return -1
self.od.move_to_end(key)
return self.od[key]
def put(self, key, value):
if key in self.od: del self.od[key]
elif len(self.od) == self.cap: self.od.popitem(False)
self.od[key] = value
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not (head and head.next): return head
pre, slow, fast = None, head, head
while fast and fast.next: pre, slow, fast = slow, slow.next, fast.next.next
pre.next = None
return self.mergeTwoLists(*map(self.sortList, (head, slow)))
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 and l2:
if l1.val > l2.val: l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
def partition(start, end):
node = start.next.next
pivotPrev = start.next
pivotPrev.next = end
pivotPost = pivotPrev
while node != end:
temp = node.next
if node.val > pivotPrev.val:
node.next = pivotPost.next
pivotPost.next = node
elif node.val < pivotPrev.val:
node.next = start.next
start.next = node
else:
node.next = pivotPost.next
pivotPost.next = node
pivotPost = pivotPost.next
node = temp
return [pivotPrev, pivotPost]
def quicksort(start, end):
if start.next != end:
prev, post = partition(start, end)
quicksort(start, prev)
quicksort(post, end)
newHead = ListNode(0)
newHead.next = head
quicksort(newHead, None)
return newHead.next
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
t, f = tokens.pop(), self.evalRPN
if t in '+-*/':
b, a = f(tokens), f(tokens)
t = eval('a' + t + 'b')
return int(t)
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
# 假设有两条链表1→2→3→4和①→②→③,模拟一下算法流程 ↓
1 → 2 ↘ ↗ → 4 1 → 2 ↘ ↗ → 4 → ① → → → 3(②) ❤ 相遇了
① → → → 3(②) → ③ 把4接到①前面,把③接到1前面 ① → → → 3(②) → ③ → 1 → 2 ↗ 若非相交链表则同时走到None
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
self.__class__.__getitem__ = lambda self, i: i and nums[i - 1] > nums[i]
return bisect.bisect_left(self, True, 0, len(nums)) - 1
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
v1, v2 = [*map(int, version1.split('.'))], [*map(int, version2.split('.'))]
d = len(v2) - len(v1)
v1, v2 = v1 + [0] * d, v2 + [0] * -d
return (v1 > v2) - (v1 < v2)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
return sorted(nums)[len(nums) // 2]
class Solution:
def titleToNumber(self, s: str) -> int:
return sum((ord(c) - 64) * 26**i for i, c in enumerate(s[::-1]))
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
def __init__(self, root: TreeNode):
self.s = []
while root: self.s[len(self.s):], root = [root], root.left
def next(self) -> int:
"""
@return the next smallest number
"""
r, root = self.s[-1], self.s.pop().right
while root: self.s[len(self.s):], root = [root], root.left
return r.val
def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return bool(self.s)
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
self.s
进行深度优先搜索from itertools import chain
class BSTIterator:
def __init__(self, root: TreeNode):
def gen(root): yield from chain(gen(root.left), [root.val], gen(root.right)) if root else ()
self.iter, self.len = gen(root), 0
for _ in gen(root): self.len += 1
def next(self) -> int:
"""
@return the next smallest number
"""
self.len -= 1
return next(self.iter)
def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return bool(self.len)
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums[:] = nums[len(nums) - k:] + nums[:len(nums) - k]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
for _ in range(k % len(nums)): nums[-1:], nums[:0] = [], nums[-1:]
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
return int(bin(n)[2:].zfill(32)[::-1], 2)
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
return bin(n).count('1')
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]
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
class Solution(object):
def numIslands(self, grid):
def sink(i, j):
if 0 <= i < len(grid) and 0 <= j < len(grid[i]) and int(grid[i][j]):
grid[i][j] = '0'
for i, j in zip((i, i+1, i, i-1), (j+1, j, j-1, j)): sink(i, j)
return 1
return 0
return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))
class Solution:
def isHappy(self, n: int) -> bool:
return self.isHappy(sum(int(i) ** 2 for i in str(n))) if n > 4 else n == 1
class Solution:
def isHappy(self, n: int) -> bool:
seen = {1}
while n not in seen:
seen.add(n)
n = sum(int(i) ** 2 for i in str(n))
return n == 1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
if head: head.next = self.removeElements(head.next, val)
return head.next if head and head.val == val else head
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
return [*map(s.index, s)] == [*map(t.index, t)]
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
return all(s.index(i) == t.index(j) for i,j in zip(s,t))
# 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]
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
l = [x for x in nums if x > nums[0]]
m = [x for x in nums if x == nums[0]]
r = [x for x in nums if x < nums[0]]
f = self.findKthLargest
if k <= len(l):
return f(l, k)
elif k <= len(l) + len(m):
return nums[0]
return f(r, k - len(l) - len(m))
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return nlargest(k,nums)[-1]
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len(nums) != len(set(nums))
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
r, d = k + 1, {}
for i, n in enumerate(nums):
r, d[n] = min(r, i - d.get(n, -k - 1)), i
return r <= k
class MyStack:
def __init__(self):
self.q = collections.deque()
def push(self, x):
self.q.append(x)
for _ in range(len(self.q) - 1): self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return not len(self.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 kthSmallest(self, root, k):
from itertools import chain, islice
def gen(x): yield from chain(gen(x.left), [x.val], gen(x.right)) if x else ()
return next(islice(gen(root), k - 1, k))
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
res = []
self.visitNode(root, res)
return res[k - 1]
# 中序遍历
def visitNode(self, root, res):
if root is None:
return
self.visitNode(root.left, res)
res.append(root.val)
self.visitNode(root.right, res)
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
"""
:type n: int
:rtype: bool
"""
return n > 0 and n & n - 1 == 0
class Solution(object):
def isPowerOfTwo(self, n):
return n > 0 and 2**int(math.log2(n)) == n
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
temp = []
while self.stack: temp.append(self.stack.pop())
r = temp.pop()
while temp: self.stack.append(temp.pop())
return r
def peek(self) -> int:
"""
Get the front element.
"""
temp = []
while self.stack: temp.append(self.stack.pop())
r = temp[-1]
while temp: self.stack.append(temp.pop())
return r
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return not self.stack
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
def gen(n):
while n: yield n.val; n = n.next
return [*gen(head)] == [*gen(head)][::-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
# 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
# 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 没有任何改变node = node.next
,那么我们只是换了钥匙,变成了打开 A.next 的门的对应的钥匙,因此链表没有被修改, A没有被修改,只是我们手里的钥匙变了。而如果我们直接写node.val, node.next = node.next.val, node.next.next
,就相当于我们先用钥匙找到 A 的门,然后修改了 A 的属性,链表发生变化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
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
return any(target in row for row in matrix)
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
j = -1
for row in matrix:
while j > -len(row) and row[j] > target:
j -= 1
if row and row[j] == target:
return True
return False
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)
class Solution:
def addDigits(self, num: int) -> int:
return num % 9 or 9 * bool(num)
'abc'
,则这个数字代表a*100 + b*10 + c
,转换后成为a + b + c
,可见每次转换相当于把原数字减去a*99 + b*9 = 9 * (a*11 + b)
,可以推出只要高于个位的位置上有数字,算法就会减去一个小于原数字的9的倍数,这就相当于数字 % 9
。但9 % 9 = 0
,而 9 本身就没有十位,因此需要考虑原数字是 0 或 9 的倍数的特殊情况num % 9
,若结果为 0 则考虑num
本身是否为 0,若不为 0 返回 9class Solution:
def addDigits(self, num: int) -> int:
while num > 9:
num = eval('+'.join(n for n in str(num)))
return num
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return sum(range(len(nums) + 1)) - sum(nums)
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return int(len(nums) * (len(nums) + 1) / 2 - sum(nums))
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
self.__class__.__getitem__ = lambda self, x: isBadVersion(x)
return bisect.bisect_left(self, True, 1, n)
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
l, h = 1, n
while l <= h:
m = (l + h) // 2
if isBadVersion(m) > m * isBadVersion(m - 1):
return m
elif isBadVersion(m):
h = m - 1
else:
l = m + 1
m *
的作用是避免 m - 1
为负数,如果 m 为 0,则代表左边没有版本,只需判断当前版本是否为 Trueclass Solution:
def numSquares(self, n: int) -> int:
dp = [0]
for i in range(1, n+1):
dp.append(min(dp[-j*j] for j in range(1, 1 + int(i**0.5))) + 1)
return dp[-1]
class Solution:
def numSquares(self, n: int) -> int:
while n % 4 == 0:
n /= 4
if n % 8 == 7:
return 4
a = 0
while a**2 <= n:
b = int((n - a**2)**0.5)
if a**2 + b**2 == n:
return bool(a) + bool(b)
a += 1
return 3
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.sort(key=bool, reverse=True)
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = 0
for i, n in enumerate(filter(lambda x: x, nums)):
nums[i] = n
for i in range(i + 1, len(nums)):
nums[i] = 0
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
self.__class__.__getitem__ = lambda sef, m: sum(n <= m for n in nums) > m
return bisect.bisect_left(self, True, 1, len(nums) - 1)
class Solution:
def canWinNim(self, n: int) -> bool:
return bool(n % 4)
class Solution:
def isPowerOfThree(self, n: int) -> bool:
return n > 0 and 3 ** round(math.log(n, 3)) == n
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
r, odd, p, head = head, head, head.next, head.next.next
while head:
odd.next, head.next, p.next = head, odd.next, head.next
p, odd, head = p.next, head, p.next and p.next.next
return r
class Solution:
def isPowerOfFour(self, num: int) -> bool:
return num > 0 and not math.log(num, 4) % 1
num
为 4 的幂class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s.reverse()
class Solution:
def reverseVowels(self, s: str) -> str:
vowels = re.findall('(?i)[aeiou]', s)
return re.sub('(?i)[aeiou]', lambda m: vowels.pop(), s)
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
return [*next(zip(*collections.Counter(nums).most_common(k)))]
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
d = {n: 0 for n in nums}
for n in nums:
d[n] += 1
r = []
for _ in range(k):
n = max(d, key=d.get)
r.append(n)
d[n] = -1
return r
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return [*set(nums1) & set(nums2)]
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
return [*(collections.Counter(nums1) & collections.Counter(nums2)).elements()]
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
r = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] == nums2[j]:
r.append(nums1[i])
i += 1
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return r
class Solution:
def isPerfectSquare(self, num: int) -> bool:
r = num
while r * r > num:
r = (r + num / r) // 2
return r * r == num
(r + num / r) / 2
>= √num 而 r > num / r 保证每次迭代 r 在不断减小,而//
的存在保证最接近的时候能够逃离循环体class Solution:
def firstUniqChar(self, s: str) -> int:
d = {c: s.count(c) for c in set(s)}
return ([i for i, c in enumerate(s) if d[c] == 1] + [-1])[0]
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
return chr(sum(map(ord, t)) - sum(map(ord, s)))
class Solution:
def decodeString(self, s: str) -> str:
stack = [['', 1, '']]
a = n = ''
for c in s:
if c.isalpha():
a += c
elif c.isdigit():
n += c
elif c == '[':
stack.append([a, int(n), ''])
a = n = ''
else:
p, t, b = stack.pop()
stack[-1][-1] += p + t * (b + a)
a = ''
return stack.pop()[-1] + a
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)]
class Solution:
def thirdMax(self, nums: List[int]) -> int:
nums = set(nums)
for _ in range((2, 0)[len(nums) < 3]): nums.remove(max(nums))
return max(nums)
"""
# Definition for a Node.
class Node:
def __init__(self, val, prev, next, child):
self.val = val
self.prev = prev
self.next = next
self.child = child
"""
from itertools import chain
class Solution:
def flatten(self, head: 'Node') -> 'Node':
def gen(n): yield from chain([n], gen(n.child), gen(n.next)) if n else ()
iters = gen(head); p = head and next(iters)
for n in iters: p.next, n.prev, p.child, n.child, p = n, p, None, None, n
return head
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
s = set(nums)
return [i for i in range(1, len(nums) + 1) if i not in s]
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for n in nums:
nums[abs(n) - 1] = -abs(nums[abs(n) - 1])
return [i + 1 for i, n in enumerate(nums) if n > 0]
8
,2
,-3,-1]class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
dic = collections.Counter(a + b for a in A for b in B)
return sum(dic.get(- c - d, 0) for c in C for d in D)
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x ^ y).count('1')
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
return len(max(''.join(map(str, nums)).split('0')))
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
def dfs(cur, i, d = {}):
if i < len(nums) and (i, cur) not in d: # 搜索周围节点
d[(i, cur)] = dfs(cur + nums[i], i + 1) + dfs(cur - nums[i], i + 1)
return d.get((i, cur), int(cur == S))
return dfs(0, 0)
class Solution:
def findPoisonedDuration(self, t: List[int], d: int) -> int:
return len(t) and sum(min(t[i] - t[i-1], d) for i in range(1, len(t))) + d
class Solution:
def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
m, n, r = len(matrix), len(matrix) and len(matrix[0]), []
for l in range(m + n - 1):
temp = [matrix[i][l - i] for i in range(max(0, l+1 - n), min(l+1, m))]
r += temp if l % 2 else temp[::-1]
return r
class Solution:
def checkPerfectNumber(self, num: int) -> bool:
return num in (6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128)
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(s.split(' ')[::-1])[::-1]
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
return sum(sorted(nums)[::2])
class Solution:
def distributeCandies(self, candies: List[int]) -> int:
return min(len(set(candies)), len(candies) // 2)
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
diff = [i for i, (a, b) in enumerate(zip(nums, sorted(nums))) if a != b]
return len(diff) and max(diff) - min(diff) + 1
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def preorder(self, root: 'Node') -> List[int]:
return root and sum([[root.val], *map(self.preorder, root.children)], []) or []
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children):
self.val = val
self.children = children
"""
class Solution:
def preorder(self, root: 'Node') -> List[int]:
s = bool(root) * [root]
r = []
while s:
root = s.pop()
r.append(root.val)
s += root.children[::-1]
return r
[]
时 bool 值为 False
同 0
,乘法结果为 []
,即可跳过 while
children
是由于栈的 FILO(先入后出)
特性class Solution:
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
d = {x: list1.index(x) + list2.index(x) for x in set(list1) & set(list2)}
return [x for x in d if d[x] == min(d.values())]
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
s = "".join(str(i) for i in [0, *flowerbed, 0]).split("1")
return n <= sum((len(i) - 1) // 2 for i in s)
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
presum = [0, *accumulate(nums, add)]
return max(presum[i + 1] - presum[i + 1 - k] for i in range(k - 1, len(nums))) / float(k)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def findDuplicateSubtrees(self, root):
d = collections.defaultdict(list)
def dfs(root):
if not root: return ''
s = ' '.join((str(root.val), dfs(root.left), dfs(root.right)))
d[s].append(root)
return s
dfs(root)
return [l[0] for l in d.values() if len(l) > 1]
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
return sorted(heapq.nsmallest(k, arr, key=lambda n:(abs(n - x), n)))
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
l, h = 0, len(arr) - 1
while l < h:
m = (l + h) // 2
if arr[m] >= x:
h = m
else:
l = m + 1
return sorted(sorted(arr[max(0, l-k) : l+k], key=lambda y: abs(y - x))[:k])
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
return root and (root.val == val and root or self.searchBST((root.left, root.right)[root.val < val], val))
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k, self.n = k, sorted(nums)
def add(self, val: int) -> int:
self.n.insert(bisect.bisect_left(self.n, val, 0, len(self.n)), val)
return self.n[-self.k]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
class KthLargest:
def __init__(self, k: int, nums):
self.k, self.nums = k, heapq.nlargest(k, nums + [float('-inf')])
heapq.heapify(self.nums)
def add(self, val: int) -> int:
heapq.heappushpop(self.nums,val)
return self.nums[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
l, r, diff = 0, 0, [0] * len(nums)
for i, j in zip(range(len(nums)), range(len(nums) - 1, -1, -1)):
diff[i] += l; l += nums[i]; diff[j] -= r; r += nums[j]
return diff.index(0) if 0 in diff else -1
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
前缀和 = [0, *list(accumulate(nums, add))]
return next((i for i in range(len(nums)) if 前缀和[i] == 前缀和[-1] - 前缀和[i + 1]), -1)
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
if image[sr][sc] != newColor: # 根剪枝
old, image[sr][sc], m, n = image[sr][sc], newColor, len(image), len(image[0])
for i, j in zip((sr, sr+1, sr, sr-1), (sc+1, sc, sc-1, sc)): # 放入周围节点
if 0 <= i < m and 0 <= j < n and image[i][j] == old: # 邻剪枝
self.floodFill(image, i, j, newColor)
return image
class Solution(object):
def dailyTemperatures(self, T):
stack, r = [], [0] * len(T)
for i, t in enumerate(T):
while stack and T[stack[-1]] < t: r[stack.pop()] = i - stack[-1]
stack.append(i)
return r
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
l = [x > target for x in letters]
return letters[l.index(max(l))]
class Solution:
def dominantIndex(self, nums: List[int]) -> int:
a, b = ([0] + sorted(nums))[-2:]
return (-1, nums.index(b))[b >= 2 * a]
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if '0000' in deadends: return -1
deadends, q = set(deadends), [('0000', 0)]
while q:
node, step = q.pop(0)
for i, add in zip([*range(4)] * 2, [1] * 4 + [-1] * 4):
cur = node[:i] + str((int(node[i]) + add) % 10) + node[i+1:]
if cur == target: return step + 1
if not cur in deadends:
q.append((cur, step + 1))
deadends.add(cur)
return -1
class Solution:
def numJewelsInStones(self, J: str, S: str) -> int:
return sum(S.count(i) for i in J)
class Solution:
def numJewelsInStones(self, J: str, S: str) -> int:
j = set(J)
return sum(s in j for s in S)
class Solution:
def transpose(self, A: List[List[int]]) -> List[List[int]]:
return [*zip(*A)]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
return root and root.val * (L <= root.val <= R) + self.rangeSumBST(root.left, L, R) + self.rangeSumBST(root.right, L, R) or 0
class Solution(object):
def isAlienSorted(self, words, order):
return words == sorted(words, key=lambda w: [order.index(x) for x in w])
充分利用 python 序列比较的特点,sorted 的参数 key 可传入一个函数,sorted 函数会将每个元素作为输入,输入到 key 函数并获得返回值,整个序列将按此值的大小来排序。此处 key 函数为lambda w: [order.index(x) for x in w]
,其为words中每个单词 word 返回一个 list,list 中每个元素为单词中字母 x 在 order 中的索引。比如当 order 为 ‘abcde……’ 时,单词 ‘cab’ 将返回 [3, 2, 1]。关于俩个 list 的大小比较,服从 python 序列比较的特性,请参考官方文档教程 5.8 节内容。
另外一个通用的方法是简单的数学计算,给每个单词赋予一个数字然后排序对比和原来的数组是否一致即可,每个字母的价值按字母表顺序,第几个就代表几,每进一位需要*10^-2
避免冲突,比如字母表是abcde……
,单词 cab 的价值就是 3 * 1 + 1 * 0.01 + 2 * 0.0001
,价值越小的单词位置应该越靠前
class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
d = {c: i + 1 for i, c in enumerate(order)}
return sorted(words, key=lambda x: sum(d[c] * 10**(-2 * i) for i, c in enumerate(x))) == words
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
return sorted(points, key=lambda x: x[0]**2 + x[1]**2)[:K]
class Solution:
def largestPerimeter(self, A: List[int]) -> int:
A.sort(reverse=True)
return next((i+j+k for i,j,k in zip(A,A[1:],A[2:]) if j+k>i ),0)
class Solution:
def addToArrayForm(self, A: List[int], K: int) -> List[int]:
return map(int,str(int(''.join(map(str,A)))+K))
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getDecimalValue(self, head: ListNode) -> int:
r = 0
while head: r, head = r << 1 | head.val, head.next
return r
以上是一张互联网公司面试中经常考察的问题类型总结的思维导图,此栏目将根据 LeetCode 中文版探索板块给出的路线制作题解,各专栏将尽力覆盖各大知识要点并总结知识点和套路。相比于题库解析部分追求代码的绝对精简,本专题追求以高可读性呈现各大专题的常规思路,为后续的题库解析部分做铺垫。俩部分题目可能重复,但专题部分会有更详细的解析,且可能运用不同解法。
☄ 队列:先入先出的数据结构
class MyCircularQueue:
def __init__(self, k: int):
"""
Initialize your data structure here. Set the size of the queue to be k.
:param k:
:return:
"""
self.size = 0
self.max_size = k
self.data = [0] * k
self.front = self.rear = -1
def enQueue(self, value: int) -> bool:
"""
Insert an element into the circular queue. Return true if the operation is successful.
:param value:
:return:
"""
if self.isFull():
return False
if self.rear == -1:
self.rear = self.front = 0
else:
self.rear = (self.rear + 1) % self.max_size
self.data[self.rear] = value
self.size += 1
return True
def deQueue(self) -> bool:
"""
Delete an element from the circular queue. Return true if the operation is successful.
:return:
"""
if self.isEmpty():
return False
if self.front == self.rear:
self.front = self.rear = -1
else:
self.front = (self.front + 1) % self.max_size
self.size -= 1
return True
def Front(self) -> int:
"""
Get the front item from the queue.
:return:
"""
return self.data[self.front] if self.size != 0 else -1
def Rear(self) -> int:
"""
Get the last item from the queue.
:return:
"""
return self.data[self.rear] if self.size != 0 else -1
def isEmpty(self) -> bool:
"""
Checks whether the circular queue is empty or not.
:return:
"""
return self.size == 0
def isFull(self) -> bool:
"""
Checks whether the circular queue is full or not.
:return:
"""
return self.size == self.max_size
# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()
☄ 队列和广度优先搜索
遍历
和 搜索最短路径
class Solution(object):
def BFS(self):
# 1.使用 queue.Queue 初始化队列
# 2.选择合适的根节点压入队列
# 3.使用 wile 进入队列循环,直到搜索完毕
# {
# 4.取出一个节点
# 5.放入这个节点周围的节点
# }
from queue import Queue
class Solution(object):
def numIslands(self, grid):
try:
r = 0; m = len(grid); n = len(grid[0])
around = ((0, 1), (1, 0), (0, -1), (-1, 0))
except:
return 0
for i in range(m):
for j in range(n):
if int(grid[i][j]):
r += 1
#---------------------------BFS 开始-----------------------------
# 把根节点投入队列
q = Queue()
q.put((i, j))
# 开始循环
while not q.empty():
# 取出还未沉没的陆地节点并沉没陆地(防止下次遍历到的时候再算一遍)
x, y = q.get()
if int(grid[x][y]):
grid[x][y] = '0'
# 放入周围的陆地节点
for a, b in around:
a += x; b += y;
if 0 <= a < m and 0 <= b < n and int(grid[a][b]):
q.put((a, b))
#----------------------------------------------------------------
return r
from queue import Queue
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
deadends = set(deadends) # in 操作在set中时间复杂度为O(1)
if '0000' in deadends:
return -1
if target == '0000':
return 0
# -------------------------------BFS 开始----------------------------------
# 初始化根节点
q = Queue()
q.put(('0000', 0)) # (当前节点值,转动步数)
# 开始循环队列
while not q.empty():
# 取出一个节点
node, step = q.get()
# 放入周围节点
for i in range(4):
for add in (1, -1):
cur = node[:i] + str((int(node[i]) + add) % 10) + node[i+1:]
if cur == target:
return step + 1
if not cur in deadends:
q.put((cur, step + 1))
deadends.add(cur) # 避免重复搜索
# -------------------------------------------------------------------------
return -1
from queue import Queue
class Solution:
def numSquares(self, n: int) -> int:
around = []
for i in range(1, n + 1):
if i**2 <= n:
around.append(i**2)
else:
break;
r = 0
seen = set() # 防止重复运算
# ----------------BFS 开始----------------------
# 初始化根节点
q = Queue()
q.put((0, r))
# 进入队列循环
while not q.empty():
# 取出一个元素
cur, step = q.get()
step += 1
# 放入周围元素
for a in around:
a += cur
if a == n:
return step
if a < n and (a, step) not in seen:
seen.add((a, step))
q.put((a, step))
# ----------------------------------------------
return 0
☄ 栈:后入先出的数据结构
嵌套关系
的题目class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
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()
class Solution:
def isValid(self, s: str) -> bool:
stack = []
d = {'(': ')', '[': ']', '{': '}'}
for p in s:
if p in '{[(':
stack.append(p)
else:
if not stack or d[stack.pop()] != p:
return False
return not stack
class Solution(object):
def dailyTemperatures(self, T):
stack = []
r = [0] * len(T)
for i, t in enumerate(T):
while stack and T[stack[-1]] < t:
c = stack.pop()
r[c] = i - c
stack.append(i)
return r
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
# 初始化栈,用栈储存未处理的数字
stack = []
# 遍历元素
for t in tokens:
if not t in '+-*/': # 规定入栈条件
stack.append(int(t))
else: # 出栈:从栈顶弹出元素与新的栈顶做运算
a = stack.pop()
stack[-1] = int(eval(str(stack[-1]) + t + 'a'))
return stack[-1]
☄ 栈和深度优先搜索
前序遍历
,中序遍历
和 后序遍历
。在这三个遍历顺序中有一个共同的特性:除非我们到达最深的结点,否则我们永远不会回溯class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
try:
m = len(grid)
n = len(grid[0])
except:
return 0
# -------------------------DFS 开始------------------------
# 定义dfs递归方程
def dfs(i, j):
if 0 <= i < m and 0 <= j < n and int(grid[i][j]):
grid[i][j] = '0'
for a, b in ((1, 0), (0, -1), (-1, 0), (0, 1)):
dfs(i + a, j + b)
# ---------------------------------------------------------
r = 0
for i in range(m):
for j in range(n):
r += int(grid[i][j])
dfs(i, j) # 调用dfs沉没一整块陆地
return r
"""
# Definition for a Node.
class Node:
def __init__(self, val, neighbors):
self.val = val
self.neighbors = neighbors
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
d = {}
def dfs(old):
if old not in d:
# 每遍历一个节点就创建一个它的副本到哈希表
d[old] = new = Node(old.val, None)
# 当所有节点进入哈希表之时开始回溯,修改邻居
new.neighbors = [*map(dfs, old.neighbors)]
return d[old]
return dfs(node)
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
def dfs(cur, i, d = {}):
if i < len(nums) and (i, cur) not in d: # 搜索周围节点
d[(i, cur)] = dfs(cur + nums[i], i + 1) + dfs(cur - nums[i], i + 1)
return d.get((i, cur), int(cur == S))
return dfs(0, 0)
{}
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
r = []
# 初始化栈
stack = []
# 进入堆栈循环
while stack or root:
if root: # 入栈条件
stack.append(root)
root = root.left
else: # 出栈条件
root = stack.pop()
r.append(root.val)
root = root.right
return r
☄ 小结
class Solution(object):
def BFS(self):
# 1.BFS 使用 queue.Queue, DFS 使用 queue.LifoQueue
# 2.选择合适的根节点压入队列
# 3.使用 wile 进入循环,直到搜索完毕
# {
# 4.取出一个节点
# 5.放入这个节点周围的节点
# }
class Solution:
def dfs(self, root):
if ...: # 根剪枝
root = ... # 根处理
for node in around: # 放入周围节点
if node == ...: # 邻剪枝
self.dfs(node) # 递归
return image # 终止返回
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
temp = []
while self.stack:
temp.append(self.stack.pop())
r = temp.pop()
while temp:
self.stack.append(temp.pop())
return r
def peek(self) -> int:
"""
Get the front element.
"""
temp = []
while self.stack:
temp.append(self.stack.pop())
r = temp[-1]
while temp:
self.stack.append(temp.pop())
return r
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return not self.stack
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
from queue import Queue
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.q = Queue()
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.q.put(x)
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
for _ in range(self.q.qsize() - 1):
self.q.put(self.q.get())
return self.q.get()
def top(self) -> int:
"""
Get the top element.
"""
for _ in range(self.q.qsize() - 1):
self.q.put(self.q.get())
r = self.q.get()
self.q.put(r)
return r
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return self.q.empty()
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
class Solution:
def decodeString(self, s: str) -> str:
stack = [['', 1, '']]
a = n = ''
for c in s:
if c.isalpha():
a += c
elif c.isdigit():
n += c
elif c == '[':
stack.append([a, int(n), ''])
a = n = ''
else:
p, t, b = stack.pop()
stack[-1][-1] += p + t * (b + a)
a = ''
return stack.pop()[-1] + a
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
m, n = map(len, (image, image[0]))
around = ((1, 0), (0, 1), (-1, 0), (0, -1))
oldColor = image[sr][sc]
# 创建栈放入根节点
stack = [(sr, sc)]
# 进入循环放入邻居
while stack:
r, c = stack.pop()
if oldColor != newColor: # 根剪枝
image[r][c] = newColor
for x, y in around:
x, y = x + r, y + c
if 0 <= x < m and 0 <= y < n and image[x][y] == oldColor: # 邻剪枝
image[x][y] = newColor
stack.append((x, y))
return image
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
m, n = len(matrix), len(matrix[0])
r = [[0] * n for _ in range(m)]
around = ((0, 1), (1, 0), (0, -1), (-1, 0))
for i in range(m):
for j in range(n):
# -------------------------BFS 开始--------------------------
# 放入根节点
q = collections.deque([(i, j, 0)])
seen = {(i, j)}
# 循环取节点
while q:
a, b, t = q.popleft()
if not matrix[a][b]:
r[i][j] = t
break
# 放入邻节点
for x, y in around:
x, y = x + a, y + b
if 0 <= x < m and 0 <= y < n and (x, y) not in seen:
seen.add((x, y))
q.append((x, y, t + 1))
# ----------------------------------------------------------
return r
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
seen = {0}
# 创建队列放入根节点
q = [0]
# 循环取节点
while q:
cur = q.pop(0)
# 放入周围节点
for i in set(rooms[cur]):
if i not in seen: # 剪枝
seen.add(i)
q.append(i)
return len(seen) == len(rooms)
☄ 数组简介
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
l, r, diff = 0, 0, [0] * len(nums)
for i, j in zip(range(len(nums)), range(len(nums) - 1, -1, -1)):
diff[i] += l
l += nums[i]
diff[j] -= r
r += nums[j]
return diff.index(0) if 0 in diff else -1
class Solution:
def dominantIndex(self, nums: List[int]) -> int:
m = max(nums)
r = nums.index(m)
nums.remove(m)
return (-1, r)[not nums or m >= 2 * max(nums)]
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
return list(map(int, str(int(''.join(map(str, digits))) + 1)))
☄ 二维数组简介
class Solution:
def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
m, n, r = len(matrix), len(matrix) and len(matrix[0]), []
for l in range(m + n - 1):
temp = [matrix[i][l - i] for i in range(max(0, l+1 - n), min(l+1, m))]
r += temp if l % 2 else temp[::-1]
return r
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
return matrix and [*matrix.pop(0)] + self.spiralOrder([*zip(*matrix)][::-1])
|1 2 3| |6 9| |8 7| |4| => |5| => | |
|4 5 6| => |5 8| => |5 4| => |5|
|7 8 9| |4 7|
[*matrix.pop(0)]
而不是matrix.pop(0)
?因为对于后面的递归,传进来的列表中元素是tupleclass Solution:
def generate(self, numRows: int) -> List[List[int]]:
r = [[1]]
for i in range(1, numRows):
r.append([1] + [sum(r[-1][j:j+2]) for j in range(i)])
return numRows and r or []
☄ 字符串简介
class Solution:
def addBinary(self, a: str, b: str) -> str:
r, p = '', 0
d = len(b) - len(a)
a = '0' * d + a
b = '0' * -d + b
for i, j in zip(a[::-1], b[::-1]):
s = int(i) + int(j) + p
r = str(s % 2) + r
p = s // 2
return '1' + r if p else r
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 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 ''
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
return os.path.commonprefix(strs)
☄ 双指针技巧
不同位置
出发:一个从始端开始,另一个从末端开始
不同速度
移动:一个指针快一些,另一个指针慢一些
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
i, j = 0, len(s) - 1
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
return sum(sorted(nums)[::2])
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i, j = 0, len(numbers) - 1
while numbers[i] + numbers[j] != target:
if numbers[i] + numbers[j] > target:
j -= 1
else:
i += 1
return [i+1, j+1]
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
j = 0
for i in range(len(nums)):
if val != nums[i]:
nums[j] = nums[i]
j += 1
return j
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
r = c = 0
for n in nums:
if n:
c += 1
else:
r = max(r, c)
c = 0
return max(r, c)
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
i, a, r = 0, 0, float('inf')
for j in range(len(nums)):
a += nums[j]
while a >= s:
r = min(r, j - i + 1)
a -= nums[i]
i += 1
return 0 if r == float('inf') else r
☄ 小结
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
for _ in range(k % len(nums)): nums[-1:], nums[:0] = [], nums[-1:]
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
r = [1]
for i in range(1, rowIndex + 1):
r = [1] + [sum(r[j:j+2]) for j in range(i)]
return r
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join(s.split()[::-1])
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(s.split()[::-1])[::-1]
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return len(nums) and i + 1
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = 0
for j in range(len(nums)):
if nums[j]:
nums[i] = nums[j]
i += 1
while i < len(nums):
nums[i] = 0
i += 1
☄ 单链表
class Node:
def __init__(self, v, p=None, n=None):
self.val = v
self.prev = p
self.next = n
class MyLinkedList:
def __init__(self):
"""
Initialize your data structure here.
"""
self.key = Node(-1)
self.key.prev = self.key.next = self.key
def get(self, index: int) -> int:
"""
Get the value of the index-th node in the linked list. If the index is invalid, return -1.
"""
i, node = 0, self.key.next
while i < index and node != self.key:
node = node.next
i += 1
return node.val if index >= 0 else -1
def addAtHead(self, val: int) -> None:
"""
Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
"""
self.key.next.prev = self.key.next = Node(val, p=self.key, n=self.key.next)
def addAtTail(self, val: int) -> None:
"""
Append a node of value val to the last element of the linked list.
"""
self.key.prev.next = self.key.prev = Node(val, p=self.key.prev, n=self.key)
def addAtIndex(self, index: int, val: int) -> None:
"""
Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
"""
index = max(0, index)
i, node = 0, self.key.next
while i < index and node != self.key:
node = node.next
i += 1
if node != self.key or i == index:
node.prev.next = node.prev = Node(val, p=node.prev, n=node)
def deleteAtIndex(self, index: int) -> None:
"""
Delete the index-th node in the linked list, if the index is valid.
"""
if index < 0: return
i, node = 0, self.key.next
while i < index and node != self.key:
node = node.next
i += 1
if node != self.key:
node.prev.next = node.next
node.next.prev = node.prev
del node
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
☄ 双指针技巧
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
slow = fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
return True
return False
class Solution(object):
def detectCycle(self, head):
slow = fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
break
else:
return None
while head is not slow:
head = head.next
slow = slow.next
return head
2(H + D) = H + D + nL
,因此可以推出 H = nL - D
,这意味着如果我们让俩个慢指针一个从 head 出发,一个从 X 出发的话,他们一定会在节点 E 相遇
_____
/ \
head___________E \
\ /
X_____/
# 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
# 假设有两条链表1→2→3→4和①→②→③,模拟一下算法流程 ↓
1 → 2 ↘ ↗ → 4 1 → 2 ↘ ↗ → 4 → ① → → → 3(②) ❤ 相遇了
① → → → 3(②) → ③ 把4接到①前面,把③接到1前面 ① → → → 3(②) → ③ → 1 → 2 ↗ 若非相交链表则同时走到None
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
link = []
while head:
link.append(head)
head = head.next
if n != len(link):
link[-n - 1].next = link[-n].next
del link[-n]
return link and link[0]
☄ 经典问题
# 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, head, p = p, head.next, head
return p
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
while head and head.val == val:
head = head.next
pre, cur = head, head and head.next
while cur:
if cur.val == val:
pre.next = cur = cur.next
else:
pre, cur = cur, cur.next
return head
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
r, odd, p, head = head, head, head.next, head.next.next
while head:
odd.next, head.next, p.next = head, odd.next, head.next
p, odd, head = p.next, head, p.next and p.next.next
return r
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
s, f, p = head, head, None
while f and f.next:
s.next, p, s, f = p, s, s.next, f.next.next
if f: s = s and s.next
while s and p and s.val == p.val:
p, s = p.next, s.next
return s == p == None
☄ 双链表
☄ 小结
# 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:
if l1.val > l2.val: l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
[] and 7
等于 []
# 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
"""
# Definition for a Node.
class Node:
def __init__(self, val, prev, next, child):
self.val = val
self.prev = prev
self.next = next
self.child = child
"""
class Solution:
def flatten(self, head: 'Node') -> 'Node':
stack = [head] if head else []
p = None
while stack:
node = stack.pop()
if node.next:
stack.append(node.next)
if node.child:
stack.append(node.child)
if p:
p.next = node
node.prev = p
p.child = node.child = None
p = node
return head
"""
# Definition for a Node.
class Node:
def __init__(self, val, next, random):
self.val = val
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
d, node = {None: None}, head
while node:
d[node] = Node(node.val, None, None)
node = node.next
node = head
while node:
d[node].next = d[node.next]
d[node].random = d[node.random]
node = node.next
return d[head]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
l = []
while head:
l.append(head)
head = head.next
if l:
l[-1].next, l[-1 - k % len(l)].next = l[0], None
return l[- k % len(l)]
return None
☄ 设计哈希表
class Node:
def __init__(self, val, nex):
self.val = val
self.nex = nex
class MyHashSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.size = 1000
self.h = [Node(None, None) for _ in range(self.size)]
def add(self, key: int) -> None:
p = self.h[key % self.size]
node = p.nex
while node:
if node.val == key:
break
p = node
node = node.nex
else:
p.nex = Node(key, None)
def remove(self, key: int) -> None:
p = self.h[key % self.size]
node = p.nex
while node:
if node.val == key:
p.nex = node.nex
break
p = node
node = node.nex
def contains(self, key: int) -> bool:
"""
Returns true if this set contains the specified element
"""
node = self.h[key % self.size]
while node:
if node.val == key:
return True
node = node.nex
return False
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
class Node:
def __init__(self, key=None, val=None, nex=None):
self.key = key
self.val = val
self.nex = nex
class MyHashMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.size = 1000
self.h = [Node() for _ in range(self.size)]
def put(self, key: int, value: int) -> None:
"""
value will always be non-negative.
"""
p = self.h[key % self.size]
c = p.nex
while c:
if c.key == key:
c.val = value
break
p = c
c = c.nex
else:
p.nex = Node(key, value)
def get(self, key: int) -> int:
"""
Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
"""
c = self.h[key % self.size]
while c:
if c.key == key:
return c.val
c = c.nex
return -1
def remove(self, key: int) -> None:
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
"""
p = self.h[key % self.size]
c = p.nex
while c:
if c.key == key:
p.nex = c.nex
break
p = c
c = c.nex
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)
☄ 实际应用 - 哈希集合
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len(set(nums)) != len(nums)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
from functools import reduce
return reduce(int.__xor__, nums)
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return [*set(nums1) & set(nums2)]
class Solution:
def isHappy(self, n: int) -> bool:
seen = {1}
while n not in seen:
seen.add(n)
n = sum(int(i) ** 2 for i in str(n))
return n == 1
☄ 实际应用 - 哈希映射
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
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
return [*map(s.index, s)] == [*map(t.index, t)]
class Solution:
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
d = {x: list1.index(x) + list2.index(x) for x in set(list1) & set(list2)}
return [x for x in d if d[x] == min(d.values())]
class Solution:
def firstUniqChar(self, s: str) -> int:
d = {c: s.count(c) for c in set(s)}
for i, c in enumerate(s):
if d[c] == 1:
return i
return -1
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
return [*(collections.Counter(nums1) & collections.Counter(nums2)).elements()]
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
r = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] == nums2[j]:
r.append(nums1[i])
i += 1
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return r
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
r = float('inf')
d = {}
for i, n in enumerate(nums):
r = min(r, i - d.get(n, float('-inf')))
d[n] = i
return r <= k
☄ 实际应用 - 设计键
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = collections.defaultdict(list)
for s in strs:
d[''.join(sorted(s))].append(s)
return [*d.values()]
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row, col, pal = eval(','.join(['[[0] * 9 for _ in range(9)]'] * 3))
for i, r in enumerate(board):
for j, n in enumerate(r):
if n == '.': continue
n = int(n) - 1
if row[i][n] or col[j][n] or pal[i // 3 * 3 + j // 3][n]: return False
row[i][n] = col[j][n] = pal[i // 3 * 3 + j // 3][n] = 1
return True
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
d, r = {}, []
def dfs(root):
if not root: return '#'
s = '# ' + ' '.join((str(root.val), dfs(root.left), dfs(root.right)))
d[s] = d.get(s, 0) + 1
if d[s] == 2: r.append(root)
return s
dfs(root)
return r
☄ 小结
class Solution:
def numJewelsInStones(self, J: str, S: str) -> int:
j = set(J)
return sum(bool(s in j) for s in S)
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
i, r, d = -1, 0, {}
for j, c in enumerate(s):
i = max(i, d.get(c, -1))
r = max(r, j - i)
d[c] = j
return r
class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
dic = {}
for a in A:
for b in B:
dic[a + b] = dic.get(a + b, 0) + 1
r = 0
for c in C:
for d in D:
r += dic.get(- c - d, 0)
return r
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
d = {n: 0 for n in nums}
for n in nums:
d[n] += 1
r = []
for _ in range(k):
n = max(d, key=d.get)
r.append(n)
d[n] = -1
return r
class RandomizedSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.d = {}
self.l = []
def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val in self.d:
return False
else:
self.d[val] = len(self.l)
self.l.append(val)
return True
def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val in self.d:
self.d[self.l[-1]] = self.d[val]
self.l[self.d.pop(val)] = self.l[-1]
self.l.pop()
return True
else:
return False
def getRandom(self) -> int:
"""
Get a random element from the set.
"""
return self.l[random.randint(0, len(self.l) - 1)]
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
self.__class__.__getitem__ = lambda self, x: 向左搜索的条件(不包括target)
寻找的索引 = bisect.bisect_left(self, True, 0, len(nums)) - 1
self.__class__.__getitem__ = lambda self, x: 向左搜索的条件(包括target)
寻找的索引 = bisect.bisect_left(self, True, 0, len(nums) - 1)
class Solution:
def 二分查找二岔模板(self, nums: List[int], target: int):
l, h = 0, len(nums)
while l < h:
m = (l + h) // 2
if 必须向左搜索的条件:
h = m
else:
l = m + 1
return l - 1
class Solution:
def 二分查找二岔模板(self, nums: List[int], target: int):
l, h = 0, len(nums) - 1
while l < h:
m = (l + h) // 2
if 满足目标或向左搜索的条件:
h = m
else:
l = m + 1
return l
☄ 背景
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, h = 0, len(nums) - 1
while l <= h:
m = (l + h) // 2
if nums[m] == target:
return m
elif nums[m] > target:
h = m - 1
else:
l = m + 1
return -1
☄ 模板 I
class Solution:
def mySqrt(self, x: int) -> int:
l, h = 0, x
while l < h:
m = (l + h) // 2
if m**2 <= x < (m+1)**2:
return m
elif m**2 < x:
l = m + 1
else:
h = m - 1
return l
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num):
class Solution(object):
def guessNumber(self, n):
"""
:type n: int
:rtype: int
"""
l, h = 1, n
while l <= n:
m = (l + h) // 2
r = guess(m)
if not r:
return m
elif r == 1:
l = m + 1
else:
h = m - 1
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 寻找断点
k, l, h = 0, 1, len(nums) - 1
while l <= h:
m = (l + h) // 2
if nums[m] < nums[m - 1]:
k = m
break
elif nums[m] > nums[0]:
l = m + 1
else:
h = m - 1
# 恢复升序
nums[k:], nums[:0] = [], nums[k:]
# 搜索目标
l, h = 0, len(nums) - 1
while l <= h:
m = (l + h) // 2
if nums[m] == target:
return (m + k) % len(nums)
elif nums[m] < target:
l = m + 1
else:
h = m - 1
return -1
☄ 模板 II
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
l, h = 1, n
while l <= h:
m = (l + h) // 2
if isBadVersion(m) > m * isBadVersion(m - 1):
return m
elif isBadVersion(m):
h = m - 1
else:
l = m + 1
m *
的作用是避免 m - 1
为负数,如果 m 为 0,则代表左边没有版本,只需判断当前版本是否为 Trueclass Solution:
def findPeakElement(self, nums: List[int]) -> int:
l, h = 0, len(nums) - 1
while l <= h:
m = (l + h) // 2
if (not m or nums[m-1] < nums[m]) and (m == len(nums) - 1 or nums[m] > nums[m+1]):
return m
elif not m or nums[m] > nums[m-1]:
l = m + 1
else:
h = m - 1
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
self.__class__.__getitem__ = lambda self, m: m and nums[m-1] > nums[m]
return bisect.bisect_left(self, True, 0, len(nums)) - 1
class Solution:
def findMin(self, nums: List[int]) -> int:
l, h = 0, len(nums) - 1
while l < h:
m = (l + h) // 2
if nums[m] < nums[-1]:
h = m
else:
l = m + 1
return nums[l]
class Solution:
def findMin(self, nums: List[int]) -> int:
self.__class__.__getitem__ = lambda self, m: nums[m] <= nums[-1]
return nums[bisect.bisect_left(self, True, 0, len(nums))]
☄ 模板 III
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
r = [-1, -1]
l, h = 0, len(nums) - 1
while l < h:
m = (l + h) // 2
if target <= nums[m]:
h = m
else:
l = m + 1
if nums and nums[l] == target:
r[0] = l
l, h = 0, len(nums) - 1
while l < h:
m = (l + h) // 2
if target < nums[m] or (target == nums[m] and (m == len(nums) - 1 or nums[m] < nums[m+1])):
h = m
else:
l = m + 1
if nums and nums[l] == target:
r[1] = l
return r
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
l, h = 0, len(arr) - 1
while l < h:
m = (l + h) // 2
if arr[m] >= x:
h = m
else:
l = m + 1
return sorted(sorted(arr[max(0, l-k) : l+k], key=lambda y: abs(y - x))[:k])
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l, h = 0, len(nums) - 1
while l <= h:
m = (l + h) // 2
if (not m or nums[m-1] < nums[m]) and (m == len(nums) - 1 or nums[m] > nums[m+1]):
return m
elif not m or nums[m] > nums[m-1]:
l = m + 1
else:
h = m - 1
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
self.__class__.__getitem__ = lambda self, m: m and nums[m-1] > nums[m]
return bisect.bisect_left(self, True, 0, len(nums)) - 1
☄ 小结
class Solution:
def myPow(self, x, n, r=1) -> float:
x, n = n < 0 and 1 / x or x, abs(n)
return self.myPow(x * x, n // 2, r * (not n % 2 or x)) if n else r
class Solution:
def isPerfectSquare(self, num: int) -> bool:
l, h = 0, num
while l < h:
m = (l + h) // 2
if m * m >= num:
h = m
else:
l = m + 1
return l * l == num
[0, num]
的范围内,且待选答案呈升序排列,故可用二分查找class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
l, h = 0, len(letters) - 1
while l < h:
m = (l + h) // 2
if letters[m] > target:
h = m
else:
l = m + 1
return letters[l] if letters[l] > target else letters[0]
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
self.__class__.__getitem__ = lambda self, m: target < letters[m]
i = bisect.bisect_left(self, True, 0, len(letters) - 1)
return letters[i] if letters[i] > target else letters[0]
☄ 更多练习
class Solution:
def findMin(self, nums: List[int]) -> int:
l, h = 0, len(nums) - 1
while l < h:
m = (l + h) // 2
if nums[m] < nums[-1]:
h = m
else:
l = m + 1
return nums[l]
-标准二岔二分搜索
class Solution:
def findMin(self, nums: List[int]) -> int:
self.__class__.__getitem__ = lambda self, m: nums[m] <= nums[-1]
return nums[bisect.bisect_left(self, True, 0, len(nums))]
class Solution:
def findMin(self, nums: List[int]) -> int:
l, h = 0, len(nums) - 1
while l < h:
m = (l + h) // 2
if nums[m] < nums[h]:
h = m
elif nums[m] == nums[h]:
h -= 1
else:
l = m + 1
return nums[l]
h -= 1
),反正他们所代表的数字还有至少一个在搜索范围内class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return [*set(nums1) & set(nums2)]
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
return [*(collections.Counter(nums1) & collections.Counter(nums2)).elements()]
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
r = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] == nums2[j]:
r.append(nums1[i])
i += 1
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return r
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i, j = 0, len(numbers) - 1
while numbers[i] + numbers[j] != target:
if numbers[i] + numbers[j] > target:
j -= 1
else:
i += 1
return [i+1, j+1]
☄ 更多练习 II
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
l, h = 0, len(nums) - 1
while l < h:
m = (l + h) >> 1
if sum(n <= m for n in nums) > m:
h = m
else:
l = m + 1
return l
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
self.__class__.__getitem__ = lambda sef, m: sum(n <= m for n in nums) > m
return bisect.bisect_left(self, True, 1, len(nums) - 1)
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) < len(nums2):
a, b = nums1, nums2
else:
a, b = nums2, nums1
m = (len(nums1) + len(nums2) - 1) >> 1
l, h = 0, len(a)
while l < h:
i = (l + h) >> 1
if m-i-1 < 0 or a[i] >= b[m-i-1]:
h = i
else:
l = i + 1
r = sorted(a[l: l + 2] + b[m - l: m - l + 2])
return (r[0] + r[1 - (len(a) + len(b)) % 2]) / 2
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
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
nums.sort()
l, h = 0, max(nums) - min(nums)
while l < h:
m = (l + h) >> 1
# 滑动窗口求小于 m 的对数
c = j = 0
for i, n in enumerate(nums[:-1]):
while j < len(nums) and nums[j] - nums[i] <= m:
j += 1
c += j - i - 1
if c >= k:
h = m
else:
l = m + 1
return l
[0, max(nums) - min(nums)]
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
l, h = 0, sum(nums)
while l < h:
mid = (l + h) >> 1
# 贪心试错
c = 1; r = s = 0
for i, n in enumerate(nums):
if s + n > mid:
c += 1
r = max(r, s)
s = n
else:
s += n
r = max(r, s)
if c <= m and r <= mid:
h = mid
else:
l = mid + 1
return l
☄ 树的遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
return root and sum(([root.val], *map(self.preorderTraversal, [root.left, root.right])), []) or []
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
r, stack = [], root and [root] or []
while stack:
root = stack.pop()
r.append(root.val)
stack += root.right and [root.right] or []
stack += root.left and [root.left] or []
return r
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
r = []
# 初始化栈
stack = []
# 进入堆栈循环
while stack or root:
if root: # 入栈条件
stack.append(root)
root = root.left
else: # 出栈条件
root = stack.pop()
r.append(root.val)
root = root.right
return r
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
return root and sum((*map(self.postorderTraversal, [root.left, root.right]), [root.val]), []) or []
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
r, stack = [], root and [root] or []
while stack:
root = stack.pop()
r.append(root.val)
stack += root.left and [root.left] or []
stack += root.right and [root.right] or []
return r[::-1]
根-右-左
,我们的目标(后序遍历)为 左-右-根
,因此只需对调整后的 DFS 逆序输出即为后序遍历# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
q = root and collections.deque([(root, 0)])
r = []
while q:
node, layer = q.popleft()
if len(r) < layer + 1:
r.append([])
r[layer].append(node.val)
if node.left:
q.append((node.left, layer + 1))
if node.right:
q.append((node.right, layer + 1))
return r
☄ 运用递归解决树的问题
# 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:
if not root:
return 0
f = self.maxDepth
l = f(root.left)
r = f(root.right)
return max(l, r) + 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 isSymmetric(self, root: TreeNode) -> bool:
if not root or root.left is root.right:
return True
l, r = root.left, root.right
if (l and l.val) != (r and r.val):
return False
i, o = TreeNode(0), TreeNode(0)
i.left, i.right = l.left, r.right
o.left, o.right = l.right, r.left
return self.isSymmetric(i) and self.isSymmetric(o)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if root:
if root.left is root.right:
return sum == root.val
else:
l = root.left and self.hasPathSum(root.left, sum - root.val)
r = root.right and self.hasPathSum(root.right, sum - root.val)
return l or r
else:
return False
sum - node.val
即为 原始的sum - 整条路径的总和
☄ 总结
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not postorder:
return None
root = TreeNode(postorder[-1])
n = inorder.index(root.val)
root.left = self.buildTree(inorder[:n],postorder[:n])
root.right = self.buildTree(inorder[n+1:],postorder[n:-1])
return root
左, 右, 根
,因此后序遍历的末尾一定为根节点[左子树中序序列, 根节点, 右子树中序序列]
[左子树后序序列, 右子树后序序列, 根节点]
index
函数确定根节点在中序列表的位置,进而确定左右子树各自包含的节点总数,将中序与后序列表划分开# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not inorder:
return None
root = TreeNode(preorder[0])
n = inorder.index(root.val)
root.left = self.buildTree(preorder[1:n+1], inorder[:n])
root.right = self.buildTree(preorder[n+1:], inorder[n+1:])
return root
根, 左, 右
,因此前序遍历的开端一定为根节点[左子树中序序列, 根节点, 右子树中序序列]
[根节点, 左子树后序序列, 右子树后序序列]
index
函数确定根节点在中序列表的位置,进而确定左右子树各自包含的节点总数,将中序与前序列表划分开"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root and root.left:
root.left.next = root.right
if root.next:
root.right.next = root.next.left
self.connect(root.left)
self.connect(root.right)
return root
root.next
的左子节点"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root and (root.left or root.right):
if root.left and root.right:
root.left.next = root.right
node = root.right or root.left
head = root.next
while head and not (head.left or head.right):
head = head.next
node.next = head and (head.left or head.right)
self.connect(root.right)
self.connect(root.left)
return root
next
属性设置为同层的下一个节点,即为 root.next
的最左边的一个节点,如果 root.next
没有子节点,则考虑 root.next.next
,依次类推# 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 = root.left and self.lowestCommonAncestor(root.left, p, q)
r = root.right and self.lowestCommonAncestor(root.right, p, q)
return root if root in (p, q) or l and r else l or r
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
l = []
q = collections.deque([root])
while q:
root = q.popleft()
if root:
l.append(root.val)
q.extend([root.left, root.right])
else:
l.append(None)
return str(l)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
l = eval(data)
head = TreeNode(l[0]) if l[0] is not None else None
q = collections.deque([head])
i = 1
while q:
root = q.popleft()
if root is not None:
root.left = TreeNode(l[i]) if l[i] is not None else None
root.right = TreeNode(l[i + 1]) if l[i + 1] is not None else None
i += 2
q.extend([root.left, root.right])
return head
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
☄ 二叉搜索树简介
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode, first=True) -> bool:
if not root:
return first or []
f = self.isValidBST
l = f(root.left, 0) + [root.val] + f(root.right, 0)
return all([a > b for a, b in zip(l[1:], l)]) if first else l
first
为 True
)则判断遍历结果是否呈升序,否则返回中序遍历列表用于拼接# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
def __init__(self, root: TreeNode):
self.s = []
while root:
self.s.append(root)
root = root.left
def next(self) -> int:
"""
@return the next smallest number
"""
r = self.s.pop()
root = r.right
while root:
self.s.append(root)
root = root.left
return r.val
def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return bool(self.s)
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
self.s
进行深度优先搜索☄ 在二叉搜索树中实现搜索操作
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
if not root or root.val == val:
return root
else:
root = root.right if root.val < val else root.left
return self.searchBST(root, val)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
root = copy.deepcopy(root)
stack = [root]
while stack:
node = stack.pop()
if node.val > val:
if node.left:
stack.append(node.left)
else:
node.left = TreeNode(val)
else:
if node.right:
stack.append(node.right)
else:
node.right = TreeNode(val)
return root
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
dummy = TreeNode(float('-inf'))
dummy.right = root
root = dummy
while root:
child_str = 'root.left' if root.val > key else 'root.right'
child = eval(child_str)
if not child or child.val != key: # 继续搜索删除目标的父节点
root = child
else: # 已经找到删除目标的父节点 root 和目标 child
if child.left is child.right: # 情况1.目标没有子节点
exec(f'{child_str} = None')
elif not (child.left and child.right): # 情况2.目标只有左子或右子
exec(f'{child_str} = child.left or child.right')
else: # 情况3.目标有左子和右子
parent = child
root = parent.right
while root and root.left: # 搜索中序后继节点
parent, root = root, root.left
child.val = root.val
side = 'right' if parent is child else 'left'
exec(f'parent.{side} = root.right')
return dummy.right
☄ 小结
class KthLargest:
def __init__(self, k: int, nums):
self.k, self.nums = k, heapq.nlargest(k, nums + [float('-inf')])
heapq.heapify(self.nums)
def add(self, val: int) -> int:
heapq.heappushpop(self.nums,val)
return self.nums[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
# 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 = root.left and self.lowestCommonAncestor(root.left, p, q)
r = root.right and self.lowestCommonAncestor(root.right, p, q)
if root in (p, q) or l and r:
return root
else:
return l or r
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
l = []
for j, n in enumerate(nums):
if j > k: # 滑动窗口
del l[bisect.bisect_left(l, nums[j - k - 1], 0, len(l))]
i = bisect.bisect_left(l, n, 0, len(l))
l.insert(i, n)
if i and abs(l[i] - l[i - 1]) <= t or i < len(l) - 1 and abs(l[i] - l[i + 1]) <= t:
return True
return False
☄ 附录:高度平衡的二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode, first=True) -> bool:
if not root:
return True if first else 0
l = self.isBalanced(root.left, False)
r = self.isBalanced(root.right, False)
if l is False or r is False:
return False
return abs(l - r) <= 1 and max(l, r) + 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 sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if nums:
m = len(nums) // 2
r = TreeNode(nums[m])
r.left, r.right = map(self.sortedArrayToBST, [nums[:m], nums[m+1:]])
return r
☄ 遍历
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children):
self.val = val
self.children = children
"""
class Solution:
def preorder(self, root: 'Node') -> List[int]:
s = bool(root) * [root]
r = []
while s:
root = s.pop()
r.append(root.val)
s += root.children[::-1]
return r
[]
时 bool 值为 False
同 0
,乘法结果为 []
,即可跳过 while
children
是由于栈的 FILO(先入后出)
特性"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def postorder(self, root: 'Node') -> List[int]:
s = bool(root) * [root]
r = []
while s:
root = s.pop()
r.append(root.val)
s += root.children
return r[::-1]
左右根
,只需将前序遍历 根左右
的子节点遍历顺序逆转并倒序输出即可,大体做法同前一题"""
# Definition for a Node.
class Node:
def __init__(self, val, children):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
q = root and collections.deque([(root, 0)])
r = []
while q:
root, layer = q.pop()
if len(r) < layer + 1:
r.append([])
r[layer].append((root.val))
q.extendleft([(child, layer + 1) for child in root.children])
return r
☄ 递归
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
return root and 1 + max(map(self.maxDepth, root.children or [None])) or 0
☄ 递归原理
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
for i in range(len(s) - 1, 0, -1):
s.insert(i, s.pop(0))
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head and head.next:
seco = head.next
head.next = self.swapPairs(seco.next)
seco.next = head
return seco
return head
head
和 head.next(seco)
seco
指向 head
,head
指向递归 seco.next
后返回的后序链表的头结点seco
☄ 递推关系
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows <= 1:
return numRows * [[1]]
prev = self.generate(numRows - 1)
last = [sum(prev[-1][j-1:j+1]) for j in range(1, numRows-1)]
prev.append([1, *last, 1])
return prev
numRows
为 0 则返回 []
,为 1 返回 [[1]]
prev
last
,f(i,j) = f(i−1, j−1) + f(i−1, j)
(两边的 1 会在下一行代码中另外加)class Solution:
def getRow(self, rowIndex: int) -> List[int]:
if rowIndex == 0:
return [1]
prev = self.getRow(rowIndex - 1)
last = [sum(prev[j-1:j+1]) for j in range(1, rowIndex)]
return [1, *last, 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)
return tail
next
属性指向前一个节点,然后递归调用下一个节点None
则返回上一个节点,否则返回递归一下个节点的结果☄ Memoization(记忆化)技术
递归 + 记忆
= 动态规划
class Solution:
cache = {0:0, 1:1}
def fib(self, N: int) -> int:
if N not in self.cache:
self.cache[N] = sum(map(self.fib, [N - 1, N - 2]))
return self.cache[N]
class Solution:
d = {0:0, 1:1, 2:2}
def climbStairs(self, n: int) -> int:
if n not in self.d:
self.d[n] = sum(map(self.climbStairs, [n - 1, n - 2]))
return self.d[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, prev=0) -> int:
if not root:
return 0
f = self.maxDepth
l = f(root.left)
r = f(root.right)
return max(l, r) + 1
class Solution:
def myPow(self, x: float, n: int) -> float:
if abs(n) <= 1:
return (1, x, 1/x)[n]
root = self.myPow(x, n // 2)
return (1, x)[n % 2] * root * root
☄ 总结
# 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:
if l1.val > l2.val: l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
class Solution:
def kthGrammar(self, N: int, K: int) -> int:
return 0 if N == 1 else (K + 1) % 2 ^ self.kthGrammar(N - 1, (K + 1) // 2);
N
行的第 K
个数计算自第 N - 1
行的第 (K + 1) // 2
个数N
行的第 K
个数为C,第 N - 1
行的第 (K + 1) // 2
个数为 P0 → 01
,1 → 10
,可见变换后实际上是在原来的数字后加了相对的数(这里称 0 与 1 相对),那么如果 K 为奇数则 C = P
,否则 C = P 的相对数
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x, l=None, r=None):
self.val = x
self.left = l
self.right = r
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def gen(num):
if not num: yield None
for i, n in enumerate(num):
for l in gen(num[:i]):
for r in gen(num[i + 1:]):
yield TreeNode(n, l, r)
return bool(n) * [*gen([*range(1, 1 + n)])]
gen
,输入是一系列升序的数字,返回这些数字可能构成的所有二叉树结构num
作为根num[:i]
就是左子树所有的可能结构,同理可获得右子树所有可能的结构root
,即为整棵树所有可能的结构a * 2**b
,a >> b 相当于 a // 2**b
a,b = b,a
的方式指定a
为第一个数字比较小的那个列表。这样可以避免使用if
语句而重复相似的代码if ...: return ...
,而不必引入else
[True, False, 0].index(0)
输出为 1,因为 False == 0 为真,但 False is 0 为假/
为浮点数除法,//
为整数除法。eg. 8 / 2.5 = 3.2, 8 // 2.5 = 3.0
,注意 //
的结果不一定为整数型,a//b
的结果值等价于 math.floor(a / b)
注:此处贡献名单仅代表汇总搜集贡献,不代表全部原创,欢迎所有更短的解法🤓