🎯 字符串
验证回文串简单双指针
- 双指针，非原地查找
class Solution: def isPalindrome(self, s: str) -> bool: s = [i.upper() for i in s if i.isalnum()] i, j = 0, len(s) - 1 while i < j: if s[i] != s[j]: return False i += 1 j -= 1 return True
- 双指针，原地查找
class Solution: def isPalindrome(self, s: str) -> bool: s = [i.upper() for i in s if i.isalnum()] i, j = 0, len(s) - 1 while i < j: while i < j and not s[i].isalnum(): i += 1 while i < j and not s[j].isalnum(): j -= 1 if i < j and s[i].upper() != s[j].upper(): return False i += 1 j -= 1 return True
分割回文串中等动态规划回溯DFS
最长回文子串中等动态规划
- 中心扩展法
class Solution: def longestPalindrome(self, s: str) -> str: if len(s) == 0: return '' start = 0 end = 0 for i in range(len(s)): left1, right1 = self.expendCenter(s, i, i) # 奇数回文 left2, right2 = self.expendCenter(s, i, i + 1) # 偶数回文 if right1 - left1 > end - start: start, end = left1, right1 if right2 - left2 > end - start: start, end = left2, right2 return s[start:end + 1] def expendCenter(self, s: str, left: int, right: int) -> int: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return left + 1, right - 1
- 动态规划
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] start, end = 0, 0 # 判断dp[i][j]需要用dp[i+1][j-1]，所以必须要把j-1列给算出来，也就是固定j按列计算 for j in range(n): for i in range(j): if s[i] == s[j]: if j - i < 3: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] if dp[i][j] and j - i > end - start: start, end = i, j return s[start: end + 1]
实现Trie前缀树中等字典树
class Trie: def __init__(self): self.lookup = {} def insert(self, word: str) -> None: root = self.lookup for i in word: if i not in root: root[i] = {} root = root[i] root['#'] = '#' def search(self, word: str) -> bool: root = self.lookup for i in word: if i not in root: return False root = root[i] if '#' not in root: return False else: return True def startsWith(self, prefix: str) -> bool: root = self.lookup for i in prefix: if i not in root: return False root = root[i] return True
有效的字母异位词简单排序哈希表
class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False words = {} for i in s: words[i] = words.get(i, 0) + 1 for i in t: if i in words and words[i] > 0: words[i] -= 1 else: return False return True
字符串的第一个唯一字符简单哈希表
class Solution: def firstUniqChar(self, s: str) -> int: words = {} for i in s: words[i] = words.get(i, 0) + 1 for i, v in enumerate(s): if words[v] == 1: return i return -1
反转字符串简单双指针
class Solution: def reverseString(self, s: List[str]) -> None: i, j = 0, len(s) - 1 while i < j: s[i], s[j] = s[j], s[i] i += 1 j -= 1
第一个只出现一次的字符简单
class Solution: def firstUniqChar(self, s: str) -> str: dict_ = {} for i in range(len(s)): dict_[s[i]] = not s[i] in dict_ for j in dict_: if dict_[j]: return j return ' '
🍭 数组
两数之和简单哈希表双指针
- 非单调递增，哈希表 => https://leetcode-cn.com/problems/two-sum/
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: map = dict() for i, num in enumerate(nums): if target - num in map: return [map.get(target - num), i] map[num] = i return []
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: i, j = 0, len(nums) - 1 while i < j: if nums[i] < target - nums[j]: i += 1 elif nums[i] > target - nums[j]: j -= 1 else: return [nums[i], nums[j]]
合并两个有序数组简单
- 双指针
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: tmp = nums1[:m] p1, p2 = 0, 0 cur = 0 while p1 < m and p2 < n: if tmp[p1] >= nums2[p2]: nums1[cur] = nums2[p2] p2 += 1 else: nums1[cur] = tmp[p1] p1 += 1 cur += 1 if p1 < m: nums1[p1+p2:] = tmp[p1:] if p2 < n: nums1[p1+p2:] = nums2[p2:]
乘积最大子数组中等动态规划
class Solution: def maxProduct(self, nums: List[int]) -> int: if not nums: return res = nums[0] pre_max = nums[0] pre_min = nums[0] for num in nums[1:]: cur_max = max(pre_max * num, pre_min * num, num) cur_min = min(pre_max * num, pre_min * num, num) res = max(res, cur_max) pre_max = cur_max pre_min = cur_min return res
多数元素简单
- 先排序，再取中点
class Solution: def majorityElement(self, nums: List[int]) -> int: nums.sort() return nums[len(nums) // 2]
- 遍历列表，通过哈希表保存元素和统计的个数，个数达到半数就返回当前元素
class Solution: def majorityElement(self, nums: List[int]) -> int: tmp = dict() n = len(nums) for i in nums: tmp[i] = tmp.get(i, 0) + 1 if tmp[i] > n // 2: return i return -1
- 位运算
- 摩尔投票
class Solution: def majorityElement(self, nums: List[int]) -> int: major = None cnt = 0 for i in nums: if cnt == 0: major = i if major == i: cnt += 1 else: cnt -= 1 return major
旋转数组中等
- 暴力法，切片再拼接
class Solution: def rotate(self, nums: List[int], k: int) -> None: k %= len(nums) nums[:] = nums[-k:] + nums[:-k]
- 用临时数组，重新修改原数组
class Solution: def rotate(self, nums: List[int], k: int) -> None: n = len(nums) tmp = [] for i in nums: tmp.append(i) for i in range(n): nums[(k + i) % n] = tmp[i]
- 整体反转，左右分别反转
class Solution: def rotate(self, nums: List[int], k: int) -> None: def reverse(nums, start, end): while start < end: nums[start], nums[end] = nums[end], nums[start] start += 1 end -= 1 n = len(nums) k %= n reverse(nums, 0, n - 1) reverse(nums, 0, k - 1) reverse(nums, k, n - 1)
存在重复元素简单哈希表
- 哈希表统计元素个数
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: s = set() for i in nums: if i in s: return True s.add(i) return False
移动零简单双指针
- 类似 快速排序 原理，右指针右移，遇到非0就和左指针交换，左指针右移
class Solution: def moveZeroes(self, nums: List[int]) -> None: n = len(nums) i, j = 0, 0 while j < n: if nums[j] != 0: nums[i], nums[j] = nums[j], nums[i] i += 1 j += 1
- 右指针右移，遇到非0就替换掉左指针的值，最后左指针右移走完，全替换成0
class Solution: def moveZeroes(self, nums: List[int]) -> None: n = len(nums) i, j = 0, 0 while j < n: if nums[j] != 0: nums[i] = nums[j] i += 1 j += 1 while i < n: nums[i] = 0 i += 1
打乱数组中等
- Fisher-Yates 洗牌算法
两个数组的交集 Ⅱ简单哈希表
- 哈希计数，先遍历小数组构造哈希表保存元素个数，遍历大数组，消耗哈希表的同元素次数
class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: if len(nums2) > len(nums1): return self.intersect(nums2, nums1) d = {} for i in nums1: d[i] = d.get(i, 0) + 1 res = [] for i in nums2: if i in d and d[i] > 0: res.append(i) d[i] -= 1 return res
递增的三元子序列中等双指针动态规划
- 双指针，遍历数组遇到小于等于小值替换前指针，小于等于中值替换后指针，大于中值则发现大值
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: m = n = float('inf') for i in nums: if i <= m: m = i elif i <= n: n = i else: return True return False
- 动态规划
搜索二维矩阵 Ⅱ中等
- 暴力法
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0: return False for i in matrix: for j in i: if j == target: return True
- 线性搜索，以右上角为起点，大于目标则向左移动减小，小于目标则向下移动增大
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0: return False i , j = 0, len(matrix[0]) - 1 while i < len(matrix) and j >= 0: if matrix[i][j] > target: j -= 1 elif matrix[i][j] < target: i += 1 else: return True return False
- 二分查找
除自身以外数组的乘积中等
- 双向遍历，先遍历左上三角，后遍历右下三角
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: res = [1] tmp = 1 for i in range(1, len(nums)): res.append(res[i-1] * nums[i-1]) for i in range(len(nums)-2, -1, -1): tmp *= nums[i+1] res[i] *= tmp return res
🍰 堆、栈与队列
最小栈简单栈
- 辅助栈
class MinStack: def __init__(self): self.stack = [] self.min = [] def push(self, val: int) -> None: self.stack.append(val) if not self.min or val <= self.min[-1]: self.min.append(val) def pop(self) -> None: if self.stack.pop() == self.min[-1]: self.min.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min[-1]
数组中的第K个最大元素中等堆分治算法
- 暴力法
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: nums.sort() return nums[-k]
- 快速排序，双边循环（双指针）
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: def partition(nums, lo, hi): if lo == hi: return lo # 随机初始化pivot，否则遇到有序数组，递归树退化为链表，时间复杂度为O(n^2) rand = random.randint(lo, hi) nums[lo], nums[rand] = nums[rand], nums[lo] pivot = nums[lo] left, right = lo + 1, hi while left <= right: while left <= right and nums[left] < pivot: left += 1 while left <= right and nums[right] >= pivot: right -= 1 if left > right: break nums[left], nums[right] = nums[right], nums[left] nums[lo], nums[right] = nums[right], nums[lo] return right target = len(nums) - k left = 0 right = len(nums) - 1 while True: # 切分得到搜索范围内某个元素的确定位置 p = partition(nums, left, right) # 缩小搜索范围，实现减治 if p > target: right = p - 1 elif p < target: left = p + 1 else: return nums[target]
- 堆排序，维护大小为k+1的最小堆，添加并弹出n-k个元素，最后堆顶就是第k大的元素
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: hp = nums[:k] heapq.heapify(hp) for i in nums[k:]: heapq.heappush(hp, i) heapq.heappop(hp) return hp[0] """ 如果k比较大，可以用最大堆，注意需要弹出k-1个元素 hp = [-i for i in nums[k-1:]] heapq.heapify(hp) for i in nums[:k-1]: heapq.heappush(hp, -i) heapq.heappop(hp) return -hp[0] """
有序矩阵中第K小的元素中等堆二分查找
- 直接排序
class Solution: def kthSmallest(self, matrix: List[List[int]], k: int) -> int: tmp = sorted(sum(matrix, [])) return tmp[k-1]
- 归并排序（小根堆）
class Solution: def kthSmallest(self, matrix: List[List[int]], k: int) -> int: n = len(matrix) hq = [(matrix[i][0], i, 0) for i in range(n)] heapq.heapify(hq) for i in range(k - 1): num, x, y = heapq.heappop(hq) if y < n - 1: new_item = (matrix[x][y + 1], x, y + 1) heapq.heappush(hq, new_item) return heapq.heappop(hq)[0]
前K个高频元素中等堆哈希表
- 维护大小为K的最小堆，遍历计数器，如果次数大于堆顶，则替换堆顶
class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: c = collections.Counter(nums) # 直接暴力取 # return heapq.nlargest(k, count.keys(), key=count.get) hq = [] for i, j in c.items(): if len(hq) == k: if hq[0][0] < j: heapq.heapreplace(hq, (j , i)) else: heapq.heappush(hq, (j, i)) return [i[1] for i in hq]
- 维护大小为n - K的最小堆，适合K比较大的情况
滑动窗口最大值困难滑动窗口堆
- 最大堆
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) # 注意 Python 默认的优先队列是小根堆 q = [(-nums[i], i) for i in range(k)] heapq.heapify(q) ans = [-q[0][0]] for i in range(k, n): heapq.heappush(q, (-nums[i], i)) while q[0][1] <= i-k: print(1, q) heapq.heappop(q) ans.append(-q[0][0]) return ans
基本计算器 Ⅱ中等栈
- 栈
class Solution: def calculate(self, s: str) -> int: n = len(s) stack = [] num = 0 flag = '+' for i in range(n): if s[i].isdigit(): num = num * 10 + ord(s[i]) - ord('0') if s[i] in '+-*/' or i == n - 1: if flag == '+': stack.append(num) if flag == '-': stack.append(-num) if flag == '*': stack.append(stack.pop() * num) if flag == '/': stack.append(int(stack.pop() / num)) flag = s[i] num = 0 return sum(stack)
扁平化嵌套列表迭代器中等栈队列
- 递归（队列）
class NestedIterator: def __init__(self, nestedList: [NestedInteger]): self.q = deque() self.__dfs(nestedList) def __dfs(self, nests): for nest in nests: if nest.isInteger(): self.q.append(nest.getInteger()) else: self.__dfs(nest.getList()) def next(self) -> int: return self.q.popleft() def hasNext(self) -> bool: return len(self.q) > 0
- 迭代（栈）
class NestedIterator: def __init__(self, nestedList: [NestedInteger]): self.stack = [] for _ in range(len(nestedList) - 1, -1, -1): self.stack.append(nestedList[_]) def next(self) -> int: item = self.stack.pop() return item.getInteger() def hasNext(self) -> bool: while self.stack: if self.stack[-1].isInteger(): return True else: item = self.stack.pop().getList() for _ in range(len(item) - 1, -1, -1): self.stack.append(item[_]) return False
逆波兰表达式求值中等栈中序遍历
- 栈，中序遍历，遇到数字进栈，遇到运算符弹两个元素出栈，结合运算符计算后结果入栈
class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] def cal(num1, num2, opt): if t == '+': return num1 + num2 elif t == '-': return num1 - num2 elif t == '*': return num1 * num2 else: return int(num1 / num2) for t in tokens: try: stack.append(int(t)) except ValueError: num2, num1 = stack.pop(), stack.pop() stack.append(cal(num1, num2, t)) return stack.pop()
最小的k个数简单最小堆
也叫top k问题
- 堆排序
import heapq class Solution: def getLeastNumbers(self, arr: List[int], k: int) -> List[int]: if not k: return list() hp = [-x for x in arr[:k]] heapq.heapify(hp) for i in arr[k:]: if -hp[0] > i: heapq.heappop(hp) heapq.heappush(hp, -i) return [-x for x in hp]
- 快排
class Solution: def getLeastNumbers(self, arr: List[int], k: int) -> List[int]: def quick_sort(arr, l, r): # 子数组长度为 1 时终止递归 if l >= r: return # 哨兵划分操作（以 arr[l] 作为基准数） i, j = l, r while i < j: while i < j and arr[j] >= arr[l]: j -= 1 while i < j and arr[i] <= arr[l]: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[l], arr[i] = arr[i], arr[l] # 递归左（右）子数组执行哨兵划分 quick_sort(arr, l, i - 1) quick_sort(arr, i + 1, r) quick_sort(arr, 0, len(arr) - 1) return arr[:k]
🍩 链表
复制带随机指针的链表中等哈希表
- 回溯（递归）
class Solution: def __init__(self): self.visited = {} def copyRandomList(self, head: 'Node') -> 'Node': if not head: return if head in self.visited: return self.visited[head] new_node = Node(head.val) self.visited[head] = new_node new_node.next = self.copyRandomList(head.next) new_node.random = self.copyRandomList(head.random) return self.visited[head]
- 迭代
class Solution: def __init__(self): self.visited = {} def copyRandomList(self, head: 'Node') -> 'Node': if not head: return old_node = head new_node = self.copy_node(old_node) self.visited[old_node] = new_node while old_node: new_node.next = self.copy_node(old_node.next) new_node.random = self.copy_node(old_node.random) new_node = new_node.next old_node = old_node.next return self.visited[head] def copy_node(self, node): if node: if node not in self.visited: self.visited[node] = Node(node.val) return self.visited[node] else: return
环形链表简单哈希表快慢指针
- 哈希表
class Solution: def hasCycle(self, head: ListNode) -> bool: visited = set() while head: if head in visited: return True visited.add(head) head = head.next return False
- 快慢指针
class Solution: def hasCycle(self, head: ListNode) -> bool: if not head or not head.next: return False slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False
排序链表中等归并排序
- 归并排序，自顶向下时间：O(nlogn)空间：O(logn)
- 归并排序，自底向上时间：O(nlogn)空间：O(1)
相交链表简单哈希表双指针
- 哈希表：时间：O(m+n)，空间：O(m)或O(n)
class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: visited = set() while headA: visited.add(headA) headA = headA.next while headB: if headB in visited: return headB headB = headB.next return
- 双指针：时间：O(m+n)，空间：O(1)
两个指针走到头后，切换到另个链表头结点，两个指针会在交点相遇
class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: newA = headA newB = headB while newA != newB: if not newA: newA = headB else: newA = newA.next if not newB: newB = headA else: newB = newB.next return newA
反转链表简单双指针递归
- 迭代（双指针）
class Solution: def reverseList(self, head: ListNode) -> ListNode: prev = None curr = head while curr: tmp = curr.next curr.next = prev prev = curr curr = tmp return prev
- 递归
class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head tail = self.reverseList(head.next) head.next.next = head head.next = None return tail
回文链表简单递归快慢指针
- 递归
class Solution: def isPalindrome(self, head: ListNode) -> bool: self.ptr = head def helper(node): if not node: if not helper(node.next): return False if node.val != self.ptr.val: return False self.ptr = self.ptr.next return True return helper(head)
- 反转列表
class Solution: def isPalindrome(self, head: ListNode) -> bool: copy = [] while head: copy.append(head.val) head = head.next return copy == copy[::-1]
- 快慢指针
class Solution: def isPalindrome(self, head: ListNode) -> bool: if head is None or head.next is None: return True fast = slow = head prev = None while fast is not None and fast.next is not None: fast = fast.next.next tmp = slow.next slow.next = prev prev = slow slow = tmp if fast is not None: slow = slow.next while slow is not None and prev is not None: if slow.val != prev.val: return False slow = slow.next prev = prev.next return True
删除链表中的节点简单
class Solution: def deleteNode(self, node): node.val = node.next.val node.next = node.next.next node.next.next = None
奇偶链表中等
class Solution: def oddEvenList(self, head: ListNode) -> ListNode: if head is None or head.next is None: return head odd, even = head, head.next even_head = head.next while even and even.next: odd.next = even.next odd = odd.next even.next = odd.next even = even.next odd.next = even_head return head
链表中倒数第k个节点简单双指针
class Solution: def getKthFromEnd(self, head: ListNode, k: int) -> ListNode: former = latter = head for i in range(k): former = former.next while former: former, latter = former.next, latter.next return latter
🍨 哈希与映射
Excel表列序号简单
class Solution: def titleToNumber(self, columnTitle: str) -> int: res = 0 for i in columnTitle: num = ord(i) - ord('A') + 1 res = res * 26 + num return res
四位相加 Ⅱ简单
class Solution: def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int: res = 0 counter = Counter(-a - b for a in A for b in B) for c in C: for d in D: if c + d in counter: res += counter[c + d] return res
🍵 树
二叉搜索树中第K小的元素中等BFS中序遍历
- 递归（BFS，中序遍历）
class Solution: def kthSmallest(self, root: TreeNode, k: int) -> int: def inorder(root): if not root: return [] return inorder(root.left) + [root.val] + inorder(root.right) return inorder(root)[k - 1]
- 迭代（BFS，中序遍历）
class Solution: def kthSmallest(self, root: TreeNode, k: int) -> int: stack =[] while True: while root: stack.append(root) root = root.left root = stack.pop() k -= 1 if k == 0: return root.val root = root.right
二叉树的最近公共祖先中等DFS
- 递归（后序遍历）
class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root or root == p or root == q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if right and left: return root elif left: return left elif right: return right else: return
相关题目：二叉搜索树的最近公共祖先简单
- 递归
class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if root.val < p.val and root.val < q.val: return self.lowestCommonAncestor(root.right, p, q) if root.val > p.val and root.val > q.val: return self.lowestCommonAncestor(root.left, p, q) return root
- 迭代
class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': while True: if root.val < p.val and root.val < q.val: root = root.right if root.val > p.val and root.val > q.val: root = root.left else: break return root
二叉树的序列化与反序列化困难
- BFS（前序遍历，递归）
class Codec: def serialize(self, root): if not root: return 'x' left = self.serialize(root.left) right = self.serialize(root.right) return f'{root.val},{left},{right}' def deserialize(self, data): nodes = data.split(',')[::-1] def helper(nodes): val = nodes.pop() if val == 'x': return node = TreeNode(val) node.left = helper(nodes) node.right = helper(nodes) return node return helper(nodes)
- DFS（迭代，队列）
class Codec: def serialize(self, root): queue = deque([root]) res = [] while queue: node = queue.popleft() if not node: res.append('x') else: res.append(str(node.val)) queue.append(node.left) queue.append(node.right) return ','.join(res) def deserialize(self, data): if data == 'x': return None vals = data.split(',') root = TreeNode(vals[0]) queue = deque([root]) ptr = 1 while ptr < len(vals) - 1: node = queue.popleft() left = vals[ptr] right = vals[ptr + 1] if left != 'x': node.left = TreeNode(int(left)) queue.append(node.left) if right != 'x': node.right = TreeNode(int(right)) queue.append(node.right) ptr += 2 return root
天际线问题困难
🍉 排序与检索
最大数中等
class Solution: def largestNumber(self, nums: List[int]) -> str: sorted_nums = ''.join(sorted(map(str, nums), key=Compare, reverse=True)) if sorted_nums[0] == '0': return 0 else: return sorted_nums class Compare(str): def __gt__(x, y): return x + y > y + x
摆动排序 Ⅱ中等
寻找峰值中等
寻找重复数中等
计算右侧小于当前元素的个数困难
🍊 动态规划
至少有K个重复字符的最长子串中等
- 分治，递归
class Solution: def longestSubstring(self, s: str, k: int) -> int: if len(s) < k: return 0 for ch in set(s): if s.count(ch) < k: return max(self.longestSubstring(i, k) for i in s.split(ch)) return len(s)
股票的最大利润中等动态规划
class Solution: def maxProfit(self, prices: List[int]) -> int: # 转移方程：dp[i] = max(dp[i-1], price[i] - min(prices[:i])) cost, profit = float('inf'), 0 for price in prices: cost = min(cost, price) profit = max(profit, price - cost) return profit
无重复字符的最长子串中等动态规划哈希表双指针
- 双指针 + 哈希表
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: dict = {} prev = -1 res = 0 for next in range(len(s)): if s[next] in dict: prev = max(dict[s[next]], prev) dict[s[next]] = next res = max(res, next-prev) return res
- 动态规划 + 哈希表
🍒 数学与位运算
只出现一次的数字简单
- 通过 位运算（异或） 解决
def singleNumber(self, nums): tmp = 0 for i in nums: tmp ^= i return tmp
- 通过 集合（Set） 解决
def singleNumber(self, nums): tmp = set() for i in nums: if i in tmp: tmp.remove(i) else: tmp.add(i) return tmp.pop()
直线上最多的点数困难
分数到小数中等
阶乘后的零简单
- 暴力计算阶乘后整除10的次数
class Solution: def trailingZeroes(self, n: int) -> int: res = 1 while n > 0: res *= n n -= 1 cnt = 0 while res % 10 == 0: cnt += 1 res //= 10 return cnt
- 计算5的个数
class Solution: def trailingZeroes(self, n: int) -> int: cnt = 0 for i in range(1, n+1): num = i while num % 5 == 0: cnt += 1 num /= 5 return cnt
- 优化，不断叠加除以5得到以5、25、75的因数的数的个数
class Solution: def trailingZeroes(self, n: int) -> int: cnt = 0 while n > 0: cnt += n // 5 n = n // 5 return cnt
颠倒二进制位简单
- 位运算，把res左移一位，和n的末位进行或（相当于赋给res末位），n右移一位
class Solution: def reverseBits(self, n: int) -> int: res = 0 for i in range(32): res = (res << 1) | (n & 1) n >>= 1 return res
位1的个数简单
- 位运算，每轮和1按位与统计末位1，右移1位
class Solution: def hammingWeight(self, n: int) -> int: cnt = 0 while n: cnt += n & 1 n >>= 1 return cnt
计数质数简单
- 暴力枚举，判断整数n是否是质数，它的质因数一定在[2, √n]区间
class Solution: def countPrimes(self, n: int) -> int: cnt = 0 for i in range(2, n): j = 2 flag = True while j * j <= i: if i % j == 0: flag = False break j += 1 cnt += flag return cnt
- 埃式筛
class Solution: def countPrimes(self, n: int) -> int: cnt = 0 array = [1] * n for i in range(2, n): if array[i]: cnt += 1 for j in range(i*2, n, i): array[j] = 0 return cnt
缺失数字简单二分查找
- 二分查找，迭代
class Solution: def missingNumber(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if mid == nums[mid]: left = mid + 1 else: right = mid - 1 return left
3的幂简单
- 迭代
class Solution: def isPowerOfThree(self, n: int) -> bool: if n <= 0: return False while n > 1: if n // 3 != n / 3: return False n = n / 3 return True
- 递归
class Solution: def isPowerOfThree(self, n: int) -> bool: if n == 1: return True if n < 1: return False return self.isPowerOfThree(n / 3)
单词分割
网易面试题
from functools import cmp_to_key def sort_versions(versions): # Python3的写法 return sorted(versions, key=cmp_to_key(cmp_versions)) def cmp_versions(version1, version2): version1, version2 = version1.split('.'), version2.split('.') p1, p2 = 0, 0 n1, n2 = len(version1), len(version2) while p1 < n1 or p2 < n2: num1 = int(version1[p1]) if p1 < n1 else 0 num2 = int(version2[p2]) if p2 < n2 else 0 if num1 > num2: return 1 if num1 < num2: return -1 p1 += 1 p2 += 1 return 0 versions = ['1.0.1', '2.0.0', '1', '1.0.0', '1.2.3', '0.1.0', '1.12.0', '1.0.10'] print(sort_versions(versions))
基本计算器
class Solution: def calculate(self, s: str) -> int: res = 0 stack = [] n = len(s) sign = '+' num = 0 for i in range(n): if s[i].isdigit(): num = num * 10 + ord(s[i]) - ord('0') if s[i] in '+-*/' or i == n - 1: if sign == '+': stack.append(num) if sign == '-': stack.append(-num) if sign == '*': stack.append(stack.pop() * num) if sign == '/': stack.append(int(stack.pop() / num)) num = 0 sign = s[i] return sum(stack)