灵茶山艾府力扣题单follow

type

status

date

slug

summary

python


from typing import List
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right

滑动窗口与双指针（定长/不定长/至多/至少/恰好/单序列/双序列/三指针）

一、定长滑动窗口

定长滑窗套路：入-更新-出。 - 入：下标为

i

的元素进入窗口，更新相关统计量。如果

i<k−1

则重复第一步。 - 更新：更新答案。一般是更新最大值/最小值。 - 出：下标为

i−k+1

的元素离开窗口，更新相关统计量。以上三步适用于所有定长滑窗题目。

§1.1 基础

1456. 定长子串中元音的最大数目

python



# * √
# * T(n) S(1)
class Solution:
  def maxVowels(self, s: str, k: int) -> int:
    vowels = {'a', 'e', 'i', 'o', 'u'}
    cnt = 0; res = 0
    for i, c in enumerate(s):
      # * 入窗
      cnt += c in vowels
      # * 不到k跳过
      if i < k - 1: continue
      # * 刚好为k(下标>= k - 1)时开始滑窗的逻辑
      # * 入后更新，然后出
      
      # * 更新
      res = max(res, cnt)
      # * 出
      cnt -= s[i - k + 1] in vowels
    return res

643. 子数组最大平均数 I

python



# * T(n) S(1)
class Solution:
  def findMaxAverage(self, nums: List[int], k: int) -> float:
    sum_ = 0; res = -inf
    for i, v in enumerate(nums):
      sum_ += v
      
      if i < k - 1: continue
      res = max(res, sum_ / k)
      
      sum_ -= nums[i - k + 1]
    return res

1343. 大小为 K 且平均值大于等于阈值的子数组数目

python



# * T(n) S(1)
class Solution:
  def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
    sum_ = 0; res = 0
    for i, v in enumerate(arr):
      sum_ += v
      
      if i < k - 1: continue
      if sum_ / k >= threshold: res += 1
      
      sum_ -= arr[i - k + 1]
    return res

2090. 半径为 k 的子数组平均值

python



# * T(n) S(1)
class Solution:
  def getAverages(self, nums: List[int], k: int) -> List[int]:
    n = len(nums)
    res = [-1] * n
    sum_ = 0
    k = 2 * k + 1
    for i, v in enumerate(nums):
      sum_ += v
      
      if i < k - 1: continue
      res[i - (k - 1) // 2] = max(res[i], sum_ // k)
      
      sum_ -= nums[i - k + 1]
    
    return res

2379. 得到 K 个黑块的最少涂色次数

python



# * T(n) S(1)
class Solution:
  def minimumRecolors(self, blocks: str, k: int) -> int:
    n = len(blocks)
    cnt = 0; res = n
    for i, v in enumerate(blocks):
      cnt += v == 'W'
      if i < k - 1: continue
      res = min(res, cnt)
      cnt -= blocks[i - k + 1] == 'W'
    return res

1052. 爱生气的书店老板

python



# * T(n) S(n)
class Solution:
  def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
    # * 一位前缀和 + 定长minutes滑窗
    n = len(customers)
    # * 也可以n，python可以逆序访问
    # * 意味着pre[0] = pre[-1] + ...
    # * pre[-1]总会是还未访问过的
    # * 要么是遥远的最右端，要么是还未修改的自己
    pre = [0] * (n + 1)
    for i, (u, v) in enumerate(zip(customers, grumpy)):
      # * 0时有效，取反乘入
      pre[i + 1] = pre[i] + u * (not v)
    sum_ = 0; res = 0
    for i, v in enumerate(customers):
      sum_ += v
      if i < minutes - 1: continue
      # * 1开始，两个下标都加1
      # * i - k + 1是左元素下标
      # * 前缀和退一步，下标偏移再加回来一步
      l = pre[i - minutes + 1]
      # * 当前已在退格出，补加1偏移
      r = pre[-1] - pre[i + 1]
      res = max(res, sum_ + l + r)
      sum_ -= customers[i - minutes + 1]
    return res

1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

python



# * T(n) [不计字符串构造] S(2^k) [m中元素个数，辅助队列大小不超过k，不占主导]
class Solution:
  def hasAllCodes(self, s: str, k: int) -> bool:
    # * 记录已经找到的种类，只要数量够就行
    m = {}
    sub = deque([])
    for i, v in enumerate(s):
      sub.append(v)
      if i < k - 1: continue
      m[''.join(sub)] = 1
      sub.popleft()
    
    return len(m) == 2 ** k

2841. 几乎唯一子数组的最大和

python



# * T(n) S(min(m, k))
class Solution:
  def maxSum(self, nums: List[int], m: int, k: int) -> int:
    d = defaultdict(int); sum_ = 0; res = 0
    for i, v in enumerate(nums):
      d[v] += 1
      sum_ += v
      if i < k - 1: continue
      # * m个不同
      if len(d) >= m:
        res = max(res, sum_)
      # * 删除一次（集合不能用于多次删，所以用字典）
      d[nums[i - k + 1]] -= 1
      # * 删完移除键
      if d[nums[i - k + 1]] == 0: del d[nums[i - k + 1]]
      sum_ -= nums[i - k + 1]
    return res

2461. 长度为 K 子数组中的最大和

python



# * T(n) S(k)
class Solution:
  def maximumSubarraySum(self, nums: List[int], k: int) -> int:
    d = defaultdict(int); sum_ = 0; res = 0
    for i, v in enumerate(nums):
      sum_ += v
      d[v] += 1
      if i < k - 1: continue
      if len(d) == k: res = max(res, sum_)
      d[nums[i - k + 1]] -= 1
      if d[nums[i - k + 1]] == 0: del d[nums[i - k + 1]]
      sum_ -= nums[i - k + 1]
    return res

1423. 可获得的最大点数

python



# * T(k) S(1)
class Solution:
  def maxScore(self, cardPoints: List[int], k: int) -> int:
    # * 要么左要么右，很容易想到二者有效部分拼接
    # * 拼完后前半表示选右个数，后半选左个数
    # * 全部为有效选择，可以直接滑窗
    seq = cardPoints[-k:] + cardPoints[:k]
    sum_ = 0; res = 0
    for i, v in enumerate(seq):
      sum_ += v
      if i < k - 1: continue
      res = max(res, sum_)
      sum_ -= seq[i - k + 1]      
    return res

1652. 拆炸弹

python



# * T(n) S(1) 不计构造答案
from typing import List
class Solution:
  def decrypt(self, code: List[int], k: int) -> List[int]:
    n = len(code)
    if k == 0: return [0] * n
    sum_ = 0; res = []; 
    # * l, r 确定滑窗左右起始边界
    if k < 0:
      l = (-1 + k + 1) % n
      r = (-1) % n
    if k > 0:
      l = 1 % n
      r = (l + k - 1) % n
    # * 统计初始窗口和，由于循环数组，可能l在r右侧，手动统计
    i = l
    # * 不能取等，由于取模，可能陷入死循环
    # * n = 4， i % n = 3， r = 3,
    # * 进行后 i % n = 0
    while i % n < r:
      sum_ += code[i % n]
      i += 1
    # * 补上r处值
    sum_ += code[r]
    # * 第一个窗口和
    res.append(sum_)
    # * 构造完全部答案前循环
    while len(res) != n:
      # * 入
      r = (r + 1) % n
      sum_ += code[r]
      # * 出
      sum_ -= code[l]
      l = (l + 1) % n
      # * 构造答案
      res.append(sum_)
    return res
Solution().decrypt([2,4,9,3], -2)

1297. 子串的最大出现次数

python



# * T(n^2) S(?)
class Solution:
  def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
    m1 = defaultdict(int)
    sub1 = deque([])
    d = defaultdict(int)
    # * 双重滑窗
    for i, v in enumerate(s):
      sub1.append(v)
      m1[v] += 1
      if i < minSize - 1: continue
      if len(m1) <= maxLetters: d[''.join(sub1)] += 1
      m2 = m1.copy()
      sub2 = sub1.copy()
      for j in range(i + 1, min(i + maxSize - minSize + 1, len(s))):
        sub2.append(s[j])
        m2[s[j]] += 1
        if len(m2) > maxLetters: break
        d[''.join(sub2)] += 1
      v = sub1.popleft()
      m1[v] -= 1
      if m1[v] == 0: del m1[v]
    return max((d.values()), default=0)
# Solution().maxFreq("abcabababacabcabc", 3, 3, 10)
Solution().maxFreq("aababcaab", 2, 3, 4)

二分算法（二分答案/最小化最大值/最大化最小值/第K小）

二分查找-开区间写法，结果r为第一个>=的下标

34. 在排序数组中查找元素的第一个和最后一个位置

python



# * 标准库写法
# * T(logn) S(1)
class Solution:
  def searchRange(self, nums: List[int], target: int) -> List[int]:
    l = bisect_left(nums, target)
    r = bisect_right(nums, target)
    if l == r: return [-1, -1] # * 相等说明不在数组，插入左边界与右边界等同
    return [l, r - 1]

python



# * 标准库思想
# * T(logn) S(1)
class Solution:
  def searchRange(self, nums: List[int], target: int) -> List[int]:
    # * [[>= target], [>= target + 1] - 1]
    def bsearch(nums, target):
      l, r = -1, len(nums)
      while l + 1 < r:
        m = (l + r) >> 1
        if nums[m] < target: l = m
        else: r = m
      return r
    l = bsearch(nums, target)
    r = bsearch(nums, target + 1)
    if l == r: return [-1, -1]
    return [l, r - 1]

35. 搜索插入位置

python



# * T(logn) S(1)
class Solution:
  def searchInsert(self, nums: List[int], target: int) -> int:
    # * bisect_left
    l, r = -1, len(nums) 
    while l + 1 < r:
      m = (l + r) >> 1
      if nums[m] < target: l = m
      else: r = m
    return r

704. 二分查找

python



# * T(logn) S(1)
class Solution:
  def search(self, nums: List[int], target: int) -> int:
    # * 找的是>=，可能不等于target，返回值范围[0, n]
    # * 不存在-> [r] != target / r == n
    n = len(nums)
    l, r = -1, n
    while l + 1 < r:
      m = (l + r) >> 1
      if nums[m] < target: l = m
      else: r = m
    return r if r != n and nums[r] == target else -1

744. 寻找比目标字母大的最小字母

python



# * T(logn) S(1)
class Solution:
  def nextGreatestLetter(self, letters: List[str], target: str) -> str:
    n = len(letters)
    l, r = -1, n
    # * [> target] = [>= target + 1]
    while l + 1 < r:
      m = (l + r) >> 1
      if ord(letters[m]) < ord(target) + 1: l = m
      else: r = m
    return letters[r] if r != n else letters[0]

2529. 正整数和负整数的最大计数

python



# * T(logn) S(1)
class Solution:
  def maximumCount(self, nums: List[int]) -> int:
    # * 由于不包括0 neg + pos可能 < n
    # * neg: [<0] = [>=0] - 1
    # * pos: [>=1]
    def bsearch(nums, target):
      l, r = -1, len(nums)
      while l + 1 < r:
        m = (l + r) >> 1
        if nums[m] < target: l = m
        else: r = m
      return r
    # * 下标
    neg = bsearch(nums, 0) - 1
    pos = bsearch(nums, 1)
    # * 负下标左起，+1得长度，正下标右边算，开区间n - 闭区间下标pos得长度
    return max(neg + 1, len(nums) - pos)

1385. 两个数组间的距离值

python



# * T(mlogm + nlogm) 排序arr2 + arr1逐元素二分 S(1)
class Solution:
  def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
    # * 对arr[i]，每次在arr2中寻找其d领域外的元素，即
    # * 领域内需要同时满足边界两边约束，不便于二分
    # * [< [i] - d] = [>= [i] - d] - 1
    # * [> [i] + d] = [>= [i] + d + 1]
    # * 二者元素数量和 == len(arr2)，结果集+1
    res = 0
    arr2.sort()
    n, m = len(arr1), len(arr2)
    def bsearch(nums, target):
      l, r = -1, len(nums)
      while l + 1 < r:
        m = (l + r) >> 1
        if nums[m] < target: l = m
        else: r = m
      return r
    for v in arr1:
      l = bsearch(arr2, v - d) - 1
      r = bsearch(arr2, v + d + 1)
      if l + 1 + m - r == m: res += 1
    return res

2300. 咒语和药水的成功对数

python


class Solution:
  def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
    # * 要使spells[i] * potions[j] >= success
    # * 只需在potions排序后二分找 potions[j] >= upper(success / spells[i])
    potions.sort()
    n, m = len(spells), len(potions)
    def bsearch(nums, target):
      l, r = -1, len(nums)
      while l + 1 < r:
        m = (l + r) >> 1
        if nums[m] < target: l = m
        else: r = m
      return r
    for i, v in enumerate(spells):
      # * 向上取整
      spells[i] = m - bsearch(potions, (success // v) + (success % v > 0))
    return spells

单调栈（矩形面积/贡献法/最小字典序）

739. 每日温度

python


class Solution:
  def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    st = []; res = [0] * len(temperatures)
    for j, v in enumerate(temperatures):
      while st and temperatures[st[-1]] < v:
        i = st.pop()
        res[i] = j - i
      st.append(j)
    return res

1475. 商品折扣后的最终价格

python


class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    st = []
    for j, v in enumerate(prices):
      while st and prices[st[-1]] >= v:
        i = st.pop()
        prices[i] -= prices[j]
      st.append(j)
    return prices

496. 下一个更大元素 I

python


class Solution:
  def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
    m = {v: -1 for v in nums1}; st = []
    for j, v in enumerate(nums2):
      while st and nums2[st[-1]] < v:
        i = st.pop(); 
        if nums2[i] in m: m[nums2[i]] = v
      st.append(j)
    return [m[v] for v in nums1]

503. 下一个更大元素 II

python


class Solution:
  def nextGreaterElements(self, nums: List[int]) -> List[int]:
    n = len(nums); st = []; res = [-1] * n
    for j in range(2 * n):
      while st and nums[st[-1]] < nums[j % n]:
        i = st.pop(); res[i] = nums[j % n]
      st.append(j % n)
    return res

1019. 链表中的下一个更大节点

python


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
  def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
    cur = head; n = 0
    while cur: cur = cur.next; n += 1
    res = [0] * n; st = []; cur = head; j = 0
    for j in range(n):
      while st and st[-1][1] < cur.val:
        res[st.pop()[0]] = cur.val
      st.append((j, cur.val))
      cur = cur.next
    return res

962. 最大宽度坡

python



# ! WA
class Solution:
  def maxWidthRamp(self, nums: List[int]) -> int:
    res = [0] * len(nums); st = []
    for j, v in enumerate(nums):
      while st and nums[st[-1]] <= v:
        res[st.pop()] = j
      st.append(j)
    ma = -1; mi = inf; mii = 0
    for j, v in enumerate(res):
      ma = max(ma, v)
      if v < mi and v != 0:
        mi = v
        mii = j
    return ma - mii
    # [2, 5, 0, 5, 5, 0]
    # [5, 5, 4, 4, 9, 0, 8, 8, 0, 0]

python



# ! TE
class Solution:
  def maxWidthRamp(self, nums: List[int]) -> int:
    res = 0
    for i, v in enumerate(nums):
      for j in range(len(nums) - 1, i, -1):
        if nums[j] >= v:
          res = max(res, j - i)
    return res

python



# * √
# * T(n) S(n)
class Solution:
  def maxWidthRamp(self, nums: List[int]) -> int:
    # * 对于之前的题目都是求最近的下一个更大
    # * 现在改为求最远的下一个最大
    # * 仅添加仍未求出且可能为答案的左下标
    # * 然后枚举右下标计算答案
    res = 0; st = []
    for i, v in enumerate(nums):
      if not st or nums[st[-1]] > v: # * 靠右只有更小的数才可能为答案
        st.append(i)
    for j in range(len(nums) - 1, -1, -1):
      if j < res: break
      while st and nums[st[-1]] <= nums[j]:
        res = max(res, j - st.pop())
    return res

853. 车队

python



# ! WA
# * 循环找到下一个最大，找到并入同一集合，修改出栈位置到达时间
class Solution:
  def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
    arrives = [((target - p) // s) + ((target - p) % s > 0) for p, s in zip(position, speed)]
    n = len(position)
    father = [i for i in range(n)]
    def find(u):
      if u != father[u]:
        father[u] = find(father[u])
      return father[u]
    def join(u, v):
      u = find(u)
      v = find(v)
      if u != v: father[v] = u
    st = []
    for j in range(2 * n):
      while st and arrives[st[-1]] >= arrives[j % n] and speed[st[-1]] <= speed[j % n] and position[st[-1]] >= position[j % n]:
        i = st.pop()
        join(i, j % n)
        arrives[i] = arrives[j % n]
      st.append(j % n)
    res = 0
    for i, v in enumerate(father):
      if v == i: res += 1
    return res

python



# * T(nlogn) 排序主导 S(n)
class Solution:
  def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
    arrives = [((target - p) / s) for p, s in sorted(zip(position, speed))]
    st = []
    for v in arrives:
      while st and st[-1] <= v:
        st.pop()
      st.append(v)
    return len(st)

图论算法

DFS

547. 省份数量

python



# * 并查集作法 T(n^2) S(n)
class Solution:
  def findCircleNum(self, isConnected: List[List[int]]) -> int:
    n = len(isConnected)
    father = [i for i in range(n)]
    def find(u):
      if u != father[u]:
        father[u] = find(father[u])
      return father[u]
    def is_same(u, v):
      return find(u) == find(v)
    def join(u, v):
      u = find(u)
      v = find(v)
      if u == v:
        return
      father[v] = u
    for i in range(n):
      for j in range(n):
        if isConnected[i][j]:
          join(i, j)
    return len(set(find(i) for i in range(n)))

python



# * T(n^2) S(n)
class Solution:
  def findCircleNum(self, isConnected: List[List[int]]) -> int:
    n = len(isConnected)
    visited = [False] * n
    def dfs(i):
      for j in range(n):
        if isConnected[i][j] and not visited[j]:
          visited[j] = True
          dfs(j)
    res = 0
    for i in range(n):
      if visited[i]: continue
      dfs(i)
      res += 1
    return res

1971. 寻找图中是否存在路径

python



# * 并查集，甚至不用建图
# * T(E) S(V)
class Solution:
  def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
    father = [i for i in range(n)]
    def find(u):
      if u != father[u]:
        father[u] = find(father[u])
      return father[u]
    def join(u, v):
      u = find(u)
      v = find(v)
      if u == v:
        return
      father[v] = u
    def is_same(u, v):
      return find(u) == find(v)
    for u, v in edges:
      join(u, v)
    return is_same(source, destination)

python



# * T(E) S(V)
class Solution:
  def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
    graph = defaultdict(list)
    visited = [False] * n
    for u, v in edges:
      graph[u].append(v)
      graph[v].append(u)
    def dfs(u):
      for v in graph[u]:
        if visited[v]: continue
        visited[v] = True
        dfs(v)
    dfs(source)
    return visited[destination] or (source == destination)

797. 所有可能的路径

python



# * T(E) S(1)
import copy
class Solution:
  def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
    n = len(graph)
    res = []
    path = [0]
    def dfs(u):
      if u == n - 1:
        res.append(copy.deepcopy(path))
        return
      for v in graph[u]:
        path.append(v)
        dfs(v)
        path.pop()
    dfs(0)
    return res

841. 钥匙和房间

python



# * 仍需要dfs搜索，并查集无意义
class Solution:
  def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    n = len(rooms)
    visited = [False] * n
    def dfs(u):
      for v in rooms[u]:
        if visited[v]: continue
        visited[v] = True
        dfs(v)
    visited[0] = True
    dfs(0)
    return all(visited)

2316. 统计无向图中无法互相到达点对数

python



# * 并查集查出各集合cardinality，然后组合乘积求和
# ! TE T(n^2) 暴力计算和超时 S(n)
class Solution:
  def countPairs(self, n: int, edges: List[List[int]]) -> int:
    father = [i for i in range(n)]
    def find(u):
      if u != father[u]:
        father[u] = find(father[u])
      return father[u]
    def join(u, v):
      u = find(u)
      v = find(v)
      if u == v:
        return
      father[v] = u
    for u, v in edges:
      join(u, v)
    m = defaultdict(int)
    for i in range(n):
      m[find(i)] += 1
    m = [*m.values()]
    res = 0
    for i in range(len(m)):
      for j in range(i + 1, len(m)):
        res += m[i] * m[j]
    return res

python



# * 并查集查出各集合cardinality，然后组合乘积求和
# * T(n) S(n)
class Solution:
  def countPairs(self, n: int, edges: List[List[int]]) -> int:
    father = [i for i in range(n)]
    def find(u):
      if u != father[u]:
        father[u] = find(father[u])
      return father[u]
    def join(u, v):
      u = find(u)
      v = find(v)
      if u == v:
        return
      father[v] = u
    for u, v in edges:
      join(u, v)
    m = defaultdict(int)
    s = 0
    for i in range(n):
      m[find(i)] += 1
      s += 1
    m = [*m.values()]
    res = 0
    for v in m:
      s -= v
      res += v * s
    return res

3108. 带权图里旅途的最小代价

python



# * 并查集，如果能到达，要最小代价，必然经过最小边，只需要合并所有边的权值即可
# * 每一个连通分量对应一个集合 对应一个最小权值
# * 遍历一次边：先得到所有连通分量集合点
# * 再次遍历：计算权值
# * 处理查询
# * T(E + Q) S(V)
from collections import defaultdict
class Solution:
  def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
    father = [i for i in range(n)]
    res = []
    m = defaultdict(lambda: 0x3f3f3f3f)
    def find(u):
      if u != father[u]:
        father[u] = find(father[u])
      return father[u]
    def join(u, v):
      u = find(u)
      v = find(v)
      if u == v:
        return
      father[v] = u
    for u, v, _ in edges:
      join(u, v)
    for u, v, w in edges:
      m[find(u)] &= w
    for u, v in query:
      uu = find(u)
      vv = find(v)
      res.append(m[uu] if uu == vv else -1)
    return res

BFS

3243. 新增道路查询后的最短距离 I

python



# * T(Q(N + Q)) N - 1 + Q = E 
# * S(N + Q)
from math import inf
from collections import deque
class Solution:
  def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
    graph = defaultdict(list)
    for i in range(n - 1):
      graph[i].append(i + 1)
    res = []
    visited = [-1] * n
    def bfs(i):
      q = deque([(0, 0)])
      while q:
        x, d = q.popleft()
        for y in graph[x]:
          if y == n - 1: return d + 1
          if visited[y] != i:
            q.append((y, d + 1))
            visited[y] = i
        
    for i, (u, v) in enumerate(queries):
      graph[u].append(v)
      res.append(bfs(i))
    return res

1311. 获取你好友已观看的视频

python


class Solution:
  def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
    n = len(watchedVideos)
    visited = [False] * n
    m = defaultdict(int)
    def bfs():
      q = deque([(id, 0)])
      visited[id] = True
      while q: 
        x, d = q.popleft()
        for y in friends[x]:
          if not visited[y]:
            visited[y] = True
            if d + 1 == level:
              for video in watchedVideos[y]:
                m[video] += 1
            else:
              q.append((y, d + 1))
    bfs()
    res = [*m.items()]
    res.sort(key=lambda x: (x[1], x[0]))
    res = [*map(lambda x: x[0], res)]
    return res

1129. 颜色交替的最短路径

python



# ! TE
class Solution:
  def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
    red_visited = [False] * n
    blue_visited = [False] * n
    graph = defaultdict(list)
    dist = [inf] * n
    for u, v in redEdges:
      graph[u].append((v, 'r'))
    for u, v in blueEdges:
      graph[u].append((v, 'b'))
    def bfs():
      red_visited[0] = True
      blue_visited[0] = True
      dist[0] = 0
      q = deque([(a, b, 1) for a, b in graph[0]])
      for a, b in graph[0]:
        if b == 'r':
          red_visited[a] = True
        else:
          blue_visited[a] = True
      while q:
        x, tx, d = q.popleft()
        dist[x] = min(dist[x], d)
        for y, ty in graph[x]:
          if tx != ty and (not red_visited[y] or not blue_visited[y]):
            if ty == 'r':
              red_visited[y] = True
            else:
              blue_visited[y] = True
            q.append((y, ty, d + 1))
    bfs()
    return [v if v != inf else -1 for v in dist]

python


class Solution:
  def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
    graph = defaultdict(list)
    for u, v in redEdges:
      graph[u].append((v, 'r'))
    for u, v in blueEdges:
      graph[u].append((v, 'b'))
    dist = [-1] * n
    level = 0
    q = [(0, 'r'), (0, 'b')]
    visited = {(0, 'r'), (0, 'b')}
    while q:
      nq = []
      for x, tx in q:
        if dist[x] == -1:
          dist[x] = level
        for y, ty in graph[x]:
          if tx != ty and (y, ty) not in visited:
            visited.add((y, ty))
            nq.append((y, ty))
      q = nq
      level += 1
    return dist

拓扑排序

1462. 课程表 IV

python


class Solution:
  def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
    n = numCourses
    f = [[False] * n for _ in range(n)]
    for u, v in prerequisites:
      f[u][v] = True
    for k in range(n):
      for i in range(n):
        for j in range(n):
          if f[i][k] and f[k][j]:
            f[i][j] = True
    return [f[u][v] for u, v in queries]

2115. 从给定原材料中找到所有可以做出的菜

python


class Solution:
  def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
    n = len(recipes)
    f = defaultdict(list)
    ins = [0] * n
    for i in range(len(ingredients)):
      ingredients[i] = [v for v in ingredients[i] if v not in supplies]
      for v in ingredients[i]:
        f[v].append(i)
        ins[i] += 1
    res = [recipes[i] for i in range(n) if ins[i] == 0]
    for u in res:
      for v in f[u]:
        ins[v] -= 1
        if ins[v] == 0:
          res.append(recipes[v])
    return res

最短路

743. 网络延迟时间

python


class Solution:
  def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for u, v, w in times:
      graph[u].append((v, w))
    
    dist = [inf] * (n + 1)
    dist[k] = 0
    visited = [False] * (n + 1)
    
    for _ in range(n):
      u = -1
      for i in range(1, n + 1):
        if not visited[i] and (u == -1 or dist[i] < dist[u]):
          u = i
      if dist[u] == inf:
        break
        
      visited[u] = True
      
      for v, w in graph[u]: 
        if dist[u] + w < dist[v]:
          dist[v] = dist[u] + w
    dist[0] = -inf
    d = max(dist)
    return  d if d != inf else -1

python


class Solution:
  def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for u, v, w in times:
      graph[u].append((v, w))
    
    dist = [inf] * (n + 1)
    dist[k] = 0
    queue = deque([k])
    in_queue = [False] * (n + 1)
    in_queue[k] = True
    
    while queue:
      u = queue.popleft()
      in_queue[u] = False
      for v, w in graph[u]:
        if dist[u] + w < dist[v]:
          dist[v] = dist[u] + w
          if not in_queue[v]:
            queue.append(v)
            in_queue[v] = True
    
    dist[0] = -inf
    d = max(dist)
    return  d if d != inf else -1

最小生成树

1584. 连接所有点的最小费用

typescript


class Solution:
  def minCostConnectPoints(self, points: List[List[int]]) -> int:
    n = len(points)
    edges = []
    for i in range(n):
      for j in range(i + 1, n):
        edges.append((i, j, abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])))
    father = list(range(n))
    def find(u):
      if u != father[u]:
        father[u] = find(father[u])
      return father[u]
    def join(u, v):
      u = find(u)
      v = find(v)
      if u == v: return False
      father[v] = u
      return True
    edges.sort(key=lambda x: x[2])
    # mst = []
    res = 0
    for u, v, w in edges:
      if join(u, v):
        # mst.append((u, v, w))
        res += w
    return res

常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）

零、常用枚举技巧-§0.1 枚举右，维护左

对于双变量问题，例如两数之和

a_{i}+a_{j}=t

，可以枚举右边的

a_{j}

，转换成单变量问题，也就是在

a_{j}

左边查找是否有

a_{i}=t-a_{j}

，这可以用哈希表维护。

1. 两数之和

python



# * T(n) S(n) 
# * √
class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    idx = {}
    n = len(nums)
    for j in range(n):
      if target - nums[j] in idx:
        return [idx[target - nums[j]], j]
      idx[nums[j]] = j

1512. 好数对的数目

python



# * T(n) S(n)
class Solution:
  def numIdenticalPairs(self, nums: List[int]) -> int:
    res = 0; n = len(nums)
    idx = defaultdict(list)
    for j in range(n):
      if nums[j] in idx:
        res += len(idx[nums[j]])
      idx[nums[j]].append(j)
    return res

219. 存在重复元素 II

python


class Solution:
  def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    idx = {}
    n = len(nums)
    for j in range(n):
      if nums[j] in idx and j - idx[nums[j]] <= k: return True
      idx[nums[j]] = j
    return False

121. 买卖股票的最佳时机

python


class Solution:
  def maxProfit(self, prices: List[int]) -> int:
    res = 0; min_price = inf
    for v in prices:
      res = max(res, v - min_price)
      min_price = min(min_price, v)
    return res

2815. 数组中的最大数对和

python


class Solution:
  def maxSum(self, nums: List[int]) -> int:
    def get_max_digit(v):
      t = []
      t.extend(str(v))
      return max(t)
    max_digits = [get_max_digit(v) for v in nums]
    vx = defaultdict(int)
    res = -1
    for j, v in enumerate(nums):
      if max_digits[j] in vx:
        res = max(res, v + vx[max_digits[j]])
      vx[max_digits[j]] = max(vx[max_digits[j]], v)
    return res

2342. 数位和相等数对的最大和

python


class Solution:
  def maximumSum(self, nums: List[int]) -> int:
    def get_digit_sum(v):
      t = []
      t.extend(str(v))
      return sum(int(x) for x in t)
    sum_digits = [get_digit_sum(v) for v in nums]
    vx = defaultdict(int); res = -1
    for j, v in enumerate(nums):
      if sum_digits[j] in vx:
        res = max(res, v + vx[sum_digits[j]])
      vx[sum_digits[j]] = max(vx[sum_digits[j]], v)
    return res

1679. K 和数对的最大数目

python


class Solution:
  def maxOperations(self, nums: List[int], k: int) -> int:
    idx = defaultdict(list); res = 0
    for j, v in enumerate(nums):
      if k - v in idx and len(idx[k - v]) != 0: idx[k - v].pop(); res += 1; continue
      idx[v].append(j)
    return res

2260. 必须拿起的最小连续卡牌数

python


class Solution:
  def minimumCardPickup(self, cards: List[int]) -> int:
    res = inf
    idx = {}
    for j, v in enumerate(cards):
      if v in idx: res = min(res, j - idx[v] + 1)
      idx[v] = j
    return res if res != inf else -1

1010. 总持续时间可被 60 整除的歌曲

python


class Solution:
  def numPairsDivisibleBy60(self, time: List[int]) -> int:
    res = 0; idx = defaultdict(int); cnt = 0
    for v in time:
      v = v % 60
      cnt += 1 if v == 0 else 0
      if 60 - v in idx: res += idx[60 - v]
      idx[v] += 1
    return res + ((cnt - 1) * cnt // 2)

3185. 构成整天的下标对数目 II

python


class Solution:
  def countCompleteDayPairs(self, hours: List[int]) -> int:
    res = 0; idx = defaultdict(int); cnt = 0
    for v in hours:
      v = v % 24
      cnt += 1 if v == 0 else 0
      if 24 - v in idx: res += idx[24 - v]
      idx[v] += 1
    return res + ((cnt - 1) * cnt // 2)

2748. 美丽下标对的数目

python


class Solution:
  def countBeautifulPairs(self, nums: List[int]) -> int:
    def gcd(a, b): return a if b == 0 else gcd(b, a % b) 
    res = 0; idx = defaultdict(int)
    coprimes = [[0] * 10 for _ in range(10)]
    for i in range(10):
      for j in range(10):
        if gcd(i, j) == 1: coprimes[i][j] = 1
    print(coprimes)
    for v in nums:
      s = str(v)
      fd, ld = int(s[0]), int(s[-1])
      res += sum(idx[fd] for fd in range(10) if coprimes[fd][ld] == 1)
      idx[fd] += 1
    return res

2874. 有序三元组中的最大值 II

python



# ! WA
class Solution:
  def maximumTripletValue(self, nums: List[int]) -> int:
    res = 0
    ma = nums[0]
    mi = nums[1]
    for k in range(2, len(nums)):
      res = max(res, nums[k] * (ma - mi))
      ma = max(ma, nums[k - 1])
      mi = min(mi, nums[k])
    return res

python



# ! TE
class Solution:
  def maximumTripletValue(self, nums: List[int]) -> int:
    # * 定k枚举j O(1) 找 i
    n = len(nums); res = 0
    for k in range(2, n):
      ma = nums[0]
      for j in range(1, k):
        res = max(res, (ma - nums[j]) * nums[k])
        ma = max(ma, nums[j])
    return res

python


class Solution:
  def maximumTripletValue(self, nums: List[int]) -> int:
    n = len(nums); res = 0
    mas = [0] * n
    # * 先算出到i为止的最大值
    for i, v in enumerate(nums):
      # * py -1
      mas[i] = max(mas[i - 1], v)
    # * 接着使用上式，算出到j为止的最大差
    diff = [-inf] * n
    for j in range(1, n):
      diff[j] = max(diff[j - 1], mas[j - 1] - nums[j])
    # * 接着使用上式，算出到k-1为止的最大差 * 乘nums[k]
    for k in range(2, n):
      res = max(res, diff[k - 1] * nums[k])
    return res

454. 四数相加 II

python



# ! TE
class Solution:
  def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
    idx = defaultdict(int); res = 0
    for v in nums1:
      idx[v] += 1
    for a in nums3:
      for b in nums4:
        for c in nums2:
          res += idx[-(a + b + c)]
    return res

python




class Solution:
  def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
    idx = defaultdict(int); res = 0
    # * a + b + c + d = 0 => A + B = 0
    for a in nums1:
      for b in nums2:
        idx[a + b] += 1
    for c in nums3:
      for d in nums4:
        res += idx[-(c + d)]
    return res

1014. 最佳观光组合

python


class Solution:
  def maxScoreSightseeingPair(self, values: List[int]) -> int:
    ma = values[0] - 1; res = 0
    for j, v in enumerate(values):
      if j == 0: continue
      res = max(res, v + ma)
      if v >= ma: ma = v; 
      ma -= 1
    return res

1814. 统计一个数组中好对子的数目

python


class Solution:
  def countNicePairs(self, nums: List[int]) -> int:
    # * n[i] + r[j] = n[j] + r[i] => r[j] - n[j] = r[i] - n[i]
    nums = [int(str(v)[::-1]) - v for v in nums]
    mod = int(1e9 + 7); res = 0; idx = defaultdict(int)
    for v in nums:
      if v in idx: res += idx[v]
      idx[v] += 1
    return (res % mod)

2905. 找出满足差值条件的下标 II

python


class Solution:
  def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
    ma = -inf; mi = inf; mai = -1; mii = -1;
    i = 0; j = indexDifference; n = len(nums)
    while j < n:
      if nums[i] > ma:
        ma = nums[i]
        mai = i
      if nums[i] < mi:
        mi = nums[i]
        mii = i
      if abs(ma - nums[j]) >= valueDifference: return [mai, j]
      if abs(mi - nums[j]) >= valueDifference: return [mii, j]
      i += 1
      j += 1
    return [-1, -1]

1031. 两个非重叠子数组的最大和

python



# ! WA
class Solution:
  def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
    if firstLen > secondLen: firstLen, secondLen = secondLen, firstLen  
    fs, fe, s = -1, -1, 0                  
    first = 0
    for i, v in enumerate(nums):
      s += v
      if i < firstLen - 1: continue
      if s >= first: first = s; fs = i - firstLen + 1; fe = i
      s -= nums[i - firstLen + 1]
    s = 0; second = 0
    for i, v in enumerate(nums):
      s += v
      if i < secondLen - 1: continue
      if s >= second and (i < fs or i - secondLen + 1 > fe): second = s
      s -= nums[i - secondLen + 1]
    return first + second

python



# * 暴力
class Solution:
  def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
    n = len(nums); pre = [0] * (n + 1)
    for i in range(n): pre[i + 1] = pre[i] + nums[i]
    res = 0
    for i in range(n - firstLen + 1):
      fs, fe = i, i + firstLen - 1
      for j in range(n - secondLen + 1):
        ss, se = j, j + secondLen - 1
        if se < fs or ss > fe:
          res = max(res, pre[fe + 1] - pre[fs] + pre[se + 1] - pre[ss])
    return res

回溯

46. 全排列

python



# * T(n*n!) S(n)
class Solution:
  def permute(self, nums: List[int]) -> List[List[int]]:
    path = []
    n = len(nums)
    res = []
    # * 叶子个数 * 根到叶子的路径长
    def dfs(i, s):
      if i == n:
        res.append(path.copy())
        return
      for x in s:
        path.append(x)
        dfs(i + 1, s - {x})
        path.pop()
    dfs(0, set(nums))
    return res

python



# * T(n*n!) S(n)
class Solution:
  def permute(self, nums: List[int]) -> List[List[int]]:
    path = []
    n = len(nums)
    res = []
    visited = [False] * n
    # * 叶子个数 * 根到叶子的路径长
    def dfs(i):
      if i == n:
        res.append(path.copy())
        return
      for j in range(n):
        if not visited[j]:
          path.append(nums[j])
          visited[j] = True
          dfs(i + 1)
          visited[j] = False
          path.pop()
    dfs(0)
    return res

51. N 皇后

python


class Solution:
  def solveNQueens(self, n: int) -> List[List[str]]:
    res = []
    col = []
    def valid(r, c):
      for R in range(r):
        C = col[R]
        if r + c == R + C or r - c == R - C:
          return False
      return True
        
    def dfs(r, s):
      if r == n:
        res.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in col])
        return
      for c in s:
        if valid(r, c):
          col.append(c)
          dfs(r + 1, s - {c})
          col.pop()
    
    dfs(0, set(range(n)))
    return res

python



# * T(n^2*n!) S(n)
class Solution:
  def solveNQueens(self, n: int) -> List[List[str]]:
    res = []
    col = []
    visited = [False] * n
    diag1 = [False] * (2 * n - 1)
    diag2 = [False] * (2 * n - 1)

    def dfs(r):
      if r == n:
        res.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in col])
        return
      for c in range(n):
        if not visited[c] and not diag1[r + c] and not diag2[r - c]:
          col.append(c)
          visited[c] = diag1[r + c] = diag2[r - c] = True
          dfs(r + 1)
          visited[c] = diag1[r + c] = diag2[r - c] = False
          col.pop()
    
    dfs(0)
    return res

52. N 皇后 II

python


class Solution:
  def totalNQueens(self, n: int) -> List[List[str]]:
    res = 0
    col = []
    def valid(r, c):
      for R in range(r):
        C = col[R]
        if r + c == R + C or r - c == R - C:
          return False
      return True
        
    def dfs(r, s):
      nonlocal res
      if r == n:
        res += 1
        return
      for c in s:
        if valid(r, c):
          col.append(c)
          dfs(r + 1, s - {c})
          col.pop()
    
    dfs(0, set(range(n)))
    return res

357. 统计各位数字都不同的数字个数

python


class Solution:
  def countNumbersWithUniqueDigits(self, n: int) -> int:
    res = 1 # * 补上一位0的计数
    visited = [False] * 10
    if n == 0: return 1
    if n == 1: return 10
    def dfs(i):
      nonlocal res
      if i == n:
        res += 1
        return
      for j in range(10):
        if i == 0 and j == 0: continue
        if not visited[j]:
          visited[j] = True
          dfs(i + 1)
          visited[j] = False
    for i in range(1, n + 1):
      dfs(0, i)
    return res

2850. 将石头分散到网格图的最少移动次数

python


from itertools import permutations
class Solution:
  def minimumMoves(self, grid: List[List[int]]) -> int:
    res = inf
    fr = []
    to = []
    for i, row in enumerate(grid):
      for j, v in enumerate(row):
        if v > 1:
          fr.extend([(i, j) for _ in range(v - 1)]) 
        elif v == 0:
          to.append((i, j))
    for p in permutations(fr):
      total = 0
      for (xf, yf), (xt, yt) in zip(p, to):
        total += abs(xf - xt) + abs(yf - yt)
      res = min(res, total)
    return res

其他

TODO