DSA-模版题

算法

简单记录一下LC相关模版, 方便后续看到类似的题目好处理. 主要针对近期看到的以前没用过的东西, 也包括一些图论相关.

字符串

字符串相关还是有不少相关知识和算法的

z函数

具体可以看Z 函数（扩展 KMP）【力扣周赛 383】

区别kmp对前后缀匹配: 前指针i, 后指针j, 找i往后,j往前的最长匹配

z函数是从前往后的匹配: 前指针i, 后指针j, 找i往后,j往后的最长匹配

一些例子

  • z(aaaaa) = [0, 4, 3, 2, 1]
  • z(aaabaab) = [0, 2, 1, 0, 2, 1, 0]
  • z(abacaba) = [0, 0, 1, 0, 3, 0, 1]

原理

本质是开了一个数组和一个动窗口, 然后依据动窗口里面的信息做流程简化.

动窗口表示截止目前最长的匹配, 如果i落入窗口(zbox), 那么z[i]的最大值一定小于等于z[i-l]和r-i+1.

其中z[i-l]表示窗口匹配去掉s[l:i]这部分, 然后r-i+1是到右窗口的最大距离.

题目

3303. 第一个几乎相等子字符串的下标

给你两个字符串 s 和 pattern 。

如果一个字符串 x 修改 至多 一个字符会变成 y ，那么我们称它与 y 几乎相等 。

请你返回 s 中下标 最小 的子字符串，它与 pattern 几乎相等 。如果不存在，返回 -1 。

子字符串 是字符串中的一个 非空、连续的字符序列。

示例 1：

输入：s = "abcdefg", pattern = "bcdffg"

输出：1

解释：

将子字符串 s[1..6] == "bcdefg" 中 s[4] 变为 "f" ，得到 "bcdffg" 。

示例 2：

输入：s = "ababbababa", pattern = "bacaba"

输出：4

解释：

将子字符串 s[4..9] == "bababa" 中 s[6] 变为 "c" ，得到 "bacaba" 。

示例 3：

输入：s = "abcd", pattern = "dba"

输出：-1

示例 4：

输入：s = "dde", pattern = "d"

输出：0

提示：

  • 1 <= pattern.length < s.length <= 105
  • s 和 pattern 都只包含小写英文字母。

进阶：如果题目变为 至多 k 个 连续 字符可以被修改，你可以想出解法吗？https://leetcode.cn/problems/find-the-occurrence-of-first-almost-equal-substring/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def z_func(self, s):
        n = len(s)
        z = [0] * n
        l = r = 0
        for i in range(1, n):
            if i <= r:
                z[i] = min(z[i-l], r-i+1)
            while i + z[i] < n and s[z[i]] == s[i+z[i]]:
                l, r = i, i + z[i]
                z[i] += 1
        return z

    def minStartingIndex(self, s: str, pattern: str) -> int:
        prez = self.z_func(pattern + s)
        suf_z = self.z_func(pattern[::-1] + s[::-1])
        suf_z.reverse()
        m = len(pattern)
        for i in range(m, len(s)+1):
            if prez[i] + suf_z[i-1] >= m - 1:
                return i - m
        return -1

字典树

本质很简单, 就是字符的前缀树, 每个node带有is_end标记表示是否是字符串结尾.

关键部分是构造函数和insert函数

415周赛第三题就可以字典树加记忆化搜索过.

3291. 形成目标字符串需要的最少字符串数 I

给你一个字符串数组 words 和一个字符串 target。

如果字符串 x 是 words 中 任意 字符串的前缀，则认为 x 是一个 有效 字符串。

现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。

示例 1：

输入： words = ["abc","aaaaa","bcdef"], target = "aabcdabc"

输出： 3

解释：

target 字符串可以通过连接以下有效字符串形成：

  • words[1] 的长度为 2 的前缀，即 "aa"。
  • words[2] 的长度为 3 的前缀，即 "bcd"。
  • words[0] 的长度为 3 的前缀，即 "abc"。

示例 2：

输入： words = ["abababab","ab"], target = "ababaababa"

输出： 2

解释：

target 字符串可以通过连接以下有效字符串形成：

  • words[0] 的长度为 5 的前缀，即 "ababa"。
  • words[0] 的长度为 5 的前缀，即 "ababa"。

示例 3：

输入： words = ["abcdef"], target = "xyz"

输出： -1

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 5 * 103
  • 输入确保 sum(words[i].length) <= 105。
  • words[i] 只包含小写英文字母。
  • 1 <= target.length <= 5 * 103
  • target 只包含小写英文字母。

https://leetcode.cn/problems/minimum-number-of-valid-strings-to-form-target-i/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# https://leetcode.cn/problems/minimum-number-of-valid-strings-to-form-target-i/solutions/2918047/zi-dian-shu-ji-yi-hua-sou-suo-bao-li-fan-6mjw
class Trie:
    """前缀树模板"""
    def __init__(self):
        self.children = dict()
        self.isEnd = False

    def insert(self, word: str) -> None:
        node = self
        for s in word:
            if s not in node.children:
                node.children[s] = Trie()
            node = node.children[s]
        node.isEnd = True
    
    def searchPrefix(self, prefix: str) -> 'Trie':
        node = self
        for s in prefix:
            if s not in node.children:
                return None
            node = node.children[s]
        return node


    def search(self, word: str) -> bool:
        node = self.searchPrefix(word)
        return node is not None and node.isEnd


    def startsWith(self, prefix: str) -> bool:
        return self.searchPrefix(prefix) is not None


class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        trie = Trie()
        for word in words:
            trie.insert(word)
        
        @cache
        def dfs(start: int, end: int) -> int:
            if trie.searchPrefix(target[start: end + 1]):
                return 1
            res = inf
            node = trie
            for k in range(start, end + 1):
                # 从左往右遍历，这样可以直接移动node的位置
                # 不需要每次都重新遍历字典树判断前缀
                if target[k] not in node.children:
                    # 当前位置匹配不上，最长可能前缀遍历完成，直接返回res
                    return res if res < inf else -1
                n1 = dfs(k + 1, end)
                if n1 != -1:
                    # 找到合法方案，更新最小值
                    res = min(res, n1 + 1)
                node = node.children[target[k]]  # 直接向后移动node指针
        
        return dfs(0, len(target) - 1)

KMP

解决问题: 从一个string里面找到所有的substring的匹配.

前缀函数

前置问题: 前缀函数, 求到索引i的最长相等前后缀

举例来说，对于字符串 abcabcd，

pi[0]=0，因为 a 没有真前缀和真后缀，根据规定为 0

pi[1]=0，因为 ab 无相等的真前缀和真后缀

pi[2]=0，因为 abc 无相等的真前缀和真后缀

pi[3]=1，因为 abca 只有一对相等的真前缀和真后缀：a，长度为 1

pi[4]=2，因为 abcab 相等的真前缀和真后缀只有 ab，长度为 2

pi[5]=3，因为 abcabc 相等的真前缀和真后缀只有 abc，长度为 3

pi[6]=0，因为 abcabcd 无相等的真前缀和真后缀

同理可以计算字符串 aabaaab 的前缀函数为 [0, 1, 0, 1, 2, 2, 3]。

直观暴力解

不需要多说, 最暴力的解法, O(n^3)

1
2
3
4
5
6
7
8
9
def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        for j in range(i, -1, -1):
            if s[0:j] == s[i - j + 1 : i + 1]:
                pi[i] = j
                break
    return pi

优化1

i每次增加1, 那么最优情况pi增加1, 所以直接从pi[i]倒序即可.

1
2
3
4
5
6
7
8
9
def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        for j in range(pi[i - 1] + 1, -1, -1):
            if s[0:j] == s[i - j + 1 : i + 1]:
                pi[i] = j
                break
    return pi

dp

注意到s[pi[i-1]] == s[i]的时候我们直接pi[i] = pi[i-1] + 1即可.

如果不等的话呢? 注意, 即使不等的情况下, s[0]到s[pi[i-1]]这个串依旧是s[i-1-pi[i-1]]到s[i-1]的最长匹配前后缀.

我们假设pi[i]为x, 假设我们最后找到了目标值, 我们有s[0]到s[x]和s[i-1-x]到s[i-1]相等, 此时

由此我们有了第三版

1
2
3
4
5
6
7
8
9
10
11
def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

KMP

有了前缀函数, KMP就很好理解了

我们前缀函数可以求出任意位置最长前缀.

那么字符串t中对子字符串s的包含可以转化为s+t中寻找最大前缀为t的位置.(注意s和t中间加分隔符)

1
2
3
4
5
6
7
8
9
def find_occurrences(t, s):
    cur = s + "#" + t
    sz1, sz2 = len(t), len(s)
    ret = []
    lps = prefix_function(cur)
    for i in range(sz2 + 1, sz1 + sz2 + 1):
        if lps[i] == sz2:
            ret.append(i - 2 * sz2)
    return ret

AC自动机

解决多模式匹配问题, 其本质为对Trie的字符串匹配, 不过匹配失败的时候会依据fail指针进行跳转, 从而对字符串进行一次扫描就可以记录所有待检测子字符串.

贴一个灵神的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 从根到 node 的字符串是某个（某些）words[i] 的前缀
class Node:
    __slots__ = 'son', 'fail', 'len'

    def __init__(self, len=0):
        self.son = [None] * 26
        self.fail = None  # 当 cur.son[i] 不能匹配 target 中的某个字符时，cur.fail.son[i] 即为下一个待匹配节点（等于 root 则表示没有匹配）
        self.len = len  # 从根到 node 的字符串的长度，也是 node 在 trie 中的深度

class AhoCorasick:
    def __init__(self):
        self.root = Node()

    def put(self, s: str) -> None:
        cur = self.root
        for b in s:
            b = ord(b) - ord('a')
            if cur.son[b] is None:
                cur.son[b] = Node(cur.len + 1)
            cur = cur.son[b]

    def build_fail(self) -> None:
        self.root.fail = self.root
        q = deque()
        for i, son in enumerate(self.root.son):
            if son is None:
                self.root.son[i] = self.root
            else:
                son.fail = self.root  # 第一层的失配指针，都指向根节点 ∅
                q.append(son)
        # BFS
        while q:
            cur = q.popleft()
            for i, son in enumerate(cur.son):
                if son is None:
                    # 虚拟子节点 cur.son[i]，和 cur.fail.son[i] 是同一个
                    # 方便失配时直接跳到下一个可能匹配的位置（但不一定是某个 words[k] 的最后一个字母）
                    cur.son[i] = cur.fail.son[i]
                    continue
                son.fail = cur.fail.son[i]  # 计算失配位置
                q.append(son)

单调队列

解决动窗口最大值问题

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释： 滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

https://leetcode.cn/problems/sliding-window-maximum/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        ans = []
        for i, x in enumerate(nums):
            # 存index的单调栈,保证最大值
            while q and nums[q[-1]] <= x:
                q.pop()
            q.append(i)
            # 一旦超过窗口,弹出队首
            if i-q[0] >= k:
                q.popleft()
            
            if i >= k - 1:
                ans.append(nums[q[0]])
        return ans

2398. 预算内的最多机器人数目

你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。

运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。

请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。

示例 1：

输入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
输出：3
解释：
可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。
选择前 3 个机器人，可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。
可以看出无法在 budget 以内连续运行超过 3 个机器人，所以我们返回 3 。

示例 2：

输入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
输出：0
解释：即使运行任何一个单个机器人，还是会超出 budget，所以我们返回 0 。

提示：

  • chargeTimes.length == runningCosts.length == n
  • 1 <= n <= 5 * 104
  • 1 <= chargeTimes[i], runningCosts[i] <= 105
  • 1 <= budget <= 1015

https://leetcode.cn/problems/maximum-number-of-robots-within-budget/description/?envType=daily-question&envId=2024-09-13

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        n = len(chargeTimes)
        ans = 0
        curr_sum = 0
        q = deque()
        l = 0
        for i in range(n):
            # 单调队列保证最大值, 同时维护窗口和
            while q and chargeTimes[q[-1]] <= chargeTimes[i]:
                q.pop()
            q.append(i)
            curr_sum += runningCosts[i]

            total = (i - l + 1) * curr_sum + chargeTimes[q[0]]

            # 大于budget, 左指针移动
            while total > budget:
                l += 1
                curr_sum -= runningCosts[l-1]
                if l > q[0]:
                    q.popleft()
                if q:
                    total = (i - l + 1) * curr_sum + chargeTimes[q[0]]
                else:
                    total = 0

            ans = max(ans, i-l+1)
        return ans

树状数组

解决可变前缀和问题

1395. 统计作战单位数

 n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。

从中选出 3 个士兵组成一个作战单位，规则如下：

  • 从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
  • 作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中  0 <= i < j < k < n

请你返回按上述条件组建的作战单位的方案数。

示例 1：

输入：rating = [2,5,3,4,1]
输出：3
解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。

示例 2：

输入：rating = [2,1,3]
输出：0
解释：根据题目条件，我们无法组建作战单位。

示例 3：

输入：rating = [1,2,3,4]
输出：4

提示：

  • n == rating.length
  • 3 <= n <= 1000
  • 1 <= rating[i] <= 10^5
  • rating 中的元素都是唯一的

https://leetcode.cn/problems/count-number-of-teams/solutions/1460260/by-flix-3lu9/

不算很困难, 但是解法却很多, 除了我自己想出来的暴力, 每个都比我想的好.

『 一题四解 』 暴力枚举 + 有序数组 + 树状数组 + 线段树

  1. 暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        ans = 0
        for i in range(1,n):
            pre = 0
            post = 0
            for j in range(i):
                if rating[j] < rating[i]:
                    pre += 1
            for j in range(i,n):
                if rating[j] > rating[i]:
                    post += 1
            ans += pre * post
            ans += (i - pre) * (n-i-1-post)
        return ans
  1. SortedList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from sortedcontainers import SortedList
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        sl1 = SortedList()
        sl2 = SortedList(rating)
        ans = 0
        n = len(rating)
        for i in range(n):
            sm1 = sl1.bisect_left(rating[i])
            lg1 = i - sm1

            sl1.add(rating[i])
            sl2.remove(rating[i])

            sm2 = sl2.bisect_left(rating[i])
            lg2 = n - 1 - i - sm2

            ans += sm1 * lg2 + sm2 * lg1
        return ans
  1. 树状数组

树状数组是一种支持单点修改和区间查询的代码量最小的数据结构,具体可以点上面的wiki看.

这里也可以用树状数组来做.

存数字的rank的前缀和, query[rank-1]的数值表示在这个数前面小于rank的数字数量, 而i - sm1就是在这个数前面且大于这个数的数量, rank表示总共小于这个数的数量, 所以可以推出在这个数后面小于这个数的数量和大于这个数的数量.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        keys = sorted(rating)
        rank_map = {v:i+1 for i, v in enumerate(keys)}
        n = len(rank_map)
        tree = [0] * (n + 1)
        def lowbit(x):
            return x & (-x)

        def add(x, delta):
            if x > 0:
                while x < len(tree):
                    tree[x] += delta
                    x += lowbit(x)

        def query(x):
            res = 0
            while x > 0:
                res += tree[x]
                x -= lowbit(x)
            return res
        
        ans = 0
        for i in range(n):
            rank = rank_map[rating[i]]
            add(rank, 1)
            sm1 = query(rank - 1)
            lg1 = i - sm1
            sm2 = rank - 1 - sm1
            lg2 = n-1-i - sm2
            ans += sm1 * lg2 + sm2 * lg1
        return ans

同样, 树状数组可以做的题, 线段树也可以.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution:
    def numTeams(self, rating: List[int]) -> int:

        '''线段树模板'''
        def add(i, delta):          # 坐标i处依次添加delta
            i += len(tree)//2       # 转换到线段树下标
            while i > 0:
                tree[i] += delta
                i //= 2
        
        def query(i, j):            # 区域和检索 range sum
            i += len(tree) // 2     # 转换到线段树下标
            j += len(tree) // 2
            summ = 0
            while i <= j:
                if i % 2 == 1:      # i为右子树
                    summ += tree[i]
                    i += 1
                if j % 2 == 0:      # i为左子树
                    summ += tree[j]
                    j -= 1
                i //= 2
                j //= 2
            return summ

        '''主程序'''
        # 离散化：绝对数值转秩次rank
        uniques = sorted(rating)        # rating没有重复值
        rank_map = {v:i for i,v in enumerate(uniques)}    #【注意：rank从0开始】
        # print(rank_map)

        # 构建线段树
        tree = [0] * (len(rank_map) * 2)

        # 枚举中间点
        ans = 0
        n = len(rating)
        add(rank_map[rating[0]], 1)     # 先将第一个元素入列
        for i in range(1, n-1):         # 从第二个元素开始遍历，直至倒数第二个元素
            rank = rank_map[rating[i]]  # 当前元素的排名/秩次

            small1 = query(0, rank-1)   # 查询前序元素中排名<rank的元素数目
            large1 = i - small1         # small1 + large1 = i

            small2 = rank - small1      # small1 + small2 = rank
            large2 = n-1 - i - small2   # small2 + large2 = n-1-i

            add(rank, 1)                # 当前元素入列

            ans += small1*large2 + large1*small2
        
        return ans

线段树

699. 掉落的方块

在二维平面上的 x 轴上，放置着一些方块。

给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。

每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。

在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。

返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。

示例 1：

输入：positions = [[1,2],[2,3],[6,1]]
输出：[2,5,5]
解释：
第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。
第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 。
第 3 个方块掉落后，最高的堆叠仍然由方块 1 和 2 组成，堆叠的最高高度为 5 。
因此，返回 [2, 5, 5] 作为答案。

示例 2：

输入：positions = [[100,100],[200,100]]
输出：[100,100]
解释：
第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 100 。
第 2 个方块掉落后，最高的堆叠可以由方块 1 组成也可以由方块 2 组成，堆叠的最高高度为 100 。
因此，返回 [100, 100] 作为答案。
注意，方块 2 擦过方块 1 的右侧边，但不会算作在方块 1 上着陆。

提示：

  • 1 <= positions.length <= 1000
  • 1 <= lefti <= 108
  • 1 <= sideLengthi <= 106

https://leetcode.cn/problems/falling-squares/description/?envType=daily-question&envId=2024-07-28

听说过但是没写过, 看到这个题第一眼感觉好像是线段树, 但是从来没写过. 找了个板子, 做个记录. 其中pushdown是用父节点的add来更新子节点, 写成方法方便递归的时候顺便调用来维护子节点和父节点一致, pushup则是用子节点更新父节点, 与pushdown类似.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
# https://leetcode.cn/problems/falling-squares/solutions/2859880/python3javacgotypescript-yi-ti-yi-jie-xi-ju2s
class Node:
    def __init__(self, l, r):
        self.left = None
        self.right = None
        self.l = l
        self.r = r
        self.mid = (l + r) >> 1
        self.v = 0
        self.add = 0

class SegmentTree:
    def __init__(self):
        self.root = Node(1, int(1e9))

    def modify(self, l, r, v, node=None):
        if l > r:
            return
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            node.v = v
            node.add = v
            return
        self.pushdown(node)
        if l <= node.mid:
            self.modify(l, r, v, node.left)
        if r > node.mid:
            self.modify(l, r, v, node.right)
        self.pushup(node)

    def query(self, l, r, node=None):
        if l > r:
            return 0
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            return node.v
        self.pushdown(node)
        v = 0
        if l <= node.mid:
            v = max(v, self.query(l, r, node.left))
        if r > node.mid:
            v = max(v, self.query(l, r, node.right))
        return v

    def pushup(self, node):
        node.v = max(node.left.v, node.right.v)

    def pushdown(self, node):
        if node.left is None:
            node.left = Node(node.l, node.mid)
        if node.right is None:
            node.right = Node(node.mid + 1, node.r)
        if node.add:
            node.left.v = node.add
            node.right.v = node.add
            node.left.add = node.add
            node.right.add = node.add
            node.add = 0


class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        ans = []
        mx = 0
        tree = SegmentTree()
        for l, w in positions:
            r = l + w - 1
            h = tree.query(l, r) + w
            mx = max(mx, h)
            ans.append(mx)
            tree.modify(l, r, h)
        return ans

也存在二分做法, 用一个列表维护区间, 一个列表维护高度.

1
2
3
4
5
6
7
8
9
10
# https://leetcode.cn/problems/falling-squares/solutions/2859890/er-fen-chu-li-ji-jian-shu-xing-dai-ma-by-ezgn
class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        lstp, lsth, ma, ans = [0, inf], [0], 0, [0]
        for x, a in positions:
            i, j = bisect_right(lstp, x), bisect_left(lstp, x + a)
            ma = max(lsth[i - 1 : j]) + a
            lstp, lsth = lstp[: i] + [x, x + a] + lstp[j :], lsth[: i] + [ma] + lsth[j - 1 :]                
            ans.append(max(ans[-1], ma))
        return ans[1 :]

差分数组

第一次见, 先熟悉一下.

1094. 拼车

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengers_i, from_i, to_i] 表示第 i 次旅行有 numPassengers_i 乘客，接他们和放他们的位置分别是 from_i 和 to_i 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2：

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

提示：

  • 1 <= trips.length <= 1000
  • trips[i].length == 3
  • 1 <= numPassengersi <= 100
  • 0 <= fromi < toi <= 1000
  • 1 <= capacity <= 105

https://leetcode.cn/problems/car-pooling/description/

明确一点, 原数组某一段子数组同增同减某个数字可以看作差分数组首位的变化.

具体可以看【算法小课堂】差分数组（附题单）Python/Java/C++/Go/JS/Rust

这里通过记录某节点的增减, 直接构造差分数组, 然后从差分数组还原原数组, 判断所有节点是否超过capacity.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        d = [0] * 1001
        for num, from_, to in trips:
            d[from_] += num
            d[to] -= num
        start = 0
        for i in d:
            start += i
            if start > capacity:
                return False
        return True

100329. 使数组等于目标数组所需的最少操作次数

给你两个长度相同的正整数数组 nums 和 target。

在一次操作中，你可以选择 nums 的任何子数组，并将该子数组内的每个元素的值增加或减少 1。

返回使 nums 数组变为 target 数组所需的 最少 操作次数。

示例 1：

输入： nums = [3,5,1,2], target = [4,6,2,4]

输出： 2

解释：

执行以下操作可以使 nums 等于 target：
- nums[0..3] 增加 1，nums = [4,6,2,3]。
- nums[3..3] 增加 1，nums = [4,6,2,4]。

示例 2：

输入： nums = [1,3,2], target = [2,1,4]

输出： 5

解释：

执行以下操作可以使 nums 等于 target：
- nums[0..0] 增加 1，nums = [2,3,2]。
- nums[1..1] 减少 1，nums = [2,2,2]。
- nums[1..1] 减少 1，nums = [2,1,2]。
- nums[2..2] 增加 1，nums = [2,1,3]。
- nums[2..2] 增加 1，nums = [2,1,4]。

提示：

  • 1 <= nums.length == target.length <= 105
  • 1 <= nums[i], target[i] <= 108

https://leetcode.cn/problems/minimum-operations-to-make-array-equal-to-target/description/

同样是对子数组处理, 我们可以直接构造差分数组, 然后前面每有值加一就可以免费让后面值减一, 最终结果是所有正数和和所有负数和的绝对值里面取.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minimumOperations(self, nums: List[int], target: List[int]) -> int:
        n = len(nums)
        diff = [nums[i]-target[i] for i in range(n)]
        pos = 0
        neg = 0
        for i in range(n-1,0,-1):
            diff[i] -= diff[i-1]
            if diff[i] >= 0:
                pos += diff[i]
            else:
                neg -= diff[i]
        if diff[0] > 0:
            pos += diff[0]
        else:
            neg -= diff[0]
        return max(pos, neg)

并查集

721. 账户合并

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

示例 1：

输入：accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
输出：[["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'], ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']， ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。

示例 2：

输入：accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]
输出：[["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

提示：

  • 1 <= accounts.length <= 1000
  • 2 <= accounts[i].length <= 10
  • 1 <= accounts[i][j].length <= 30
  • accounts[i][0] 由英文字母组成
  • accounts[i][j] (for j > 0) 是有效的邮箱地址

https://leetcode.cn/problems/accounts-merge/description/?envType=daily-question&envId=2024-07-21

见过并查集, 但是没完全理解. 这里邮箱之间可以建立连接关系, 所以可以用并查集, 并查集可以缩短路径减少查找时间.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class UnionFind:
    def __init__(self):
        self.node = {}
        self.size = {}

    def find(self, node):
        if self.node.get(node) is None:
            self.node[node] = node
            self.size[node] = 1
        while self.node[node] != node:
            self.node[node] = self.node[self.node[node]]
            node = self.node[node]
        return node

    def union(self, p, q):
        root_p = self.find(p)
        root_q = self.find(q)
        if root_p == root_q:
            return True
        if self.size[root_p] > self.size[root_q]:
            self.node[root_q] = root_p
            self.size[root_p] += self.size[root_q]
        else:
            self.node[root_p] = root_q
            self.size[root_q] += self.size[root_p]

        return False

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        email_to_name = {}
        uf = UnionFind()
        for account in accounts:
            name = account[0]
            for i in range(1, len(account)):
                email_to_name[account[i]] = name
                if i < len(account) - 1:
                    uf.union(account[i],account[i+1])

        d = defaultdict(set)
        for email in email_to_name:
            d[uf.find(email)].add(email)
        ans = []
        for k, v in d.items():
            ans.append([email_to_name[k]] + list(sorted(v)))
        return ans

图

tarjan

1568. 使陆地分离的最少天数

给你一个大小为 m x n ，由若干 0 和 1 组成的二维网格 grid ，其中 1 表示陆地， 0 表示水。岛屿 由水平方向或竖直方向上相邻的 1 （陆地）连接形成。

如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。

一天内，可以将 任何单个 陆地单元（1）更改为水单元（0）。

返回使陆地分离的最少天数。

示例 1：

输入：grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
输出：2
解释：至少需要 2 天才能得到分离的陆地。
将陆地 grid[1][1] 和 grid[0][2] 更改为水，得到两个分离的岛屿。

示例 2：

输入：grid = [[1,1]]
输出：2
解释：如果网格中都是水，也认为是分离的 ([[1,1]] -> [[0,0]])，0 岛屿。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 30
  • grid[i][j] 为 0 或 1

https://leetcode.cn/problems/minimum-number-of-days-to-disconnect-island/solutions/2754484/tarjansuan-fa-mo-ban-ti-qiu-qiang-lian-t-41ve/

可以很简单, 直接当岛屿数量来做, 然后枚举所有1, 一旦成功返回1, 否则返回2.

也可以很难, 需要用到tarjan算法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# https://leetcode.cn/problems/minimum-number-of-days-to-disconnect-island/solutions/2754484/tarjansuan-fa-mo-ban-ti-qiu-qiang-lian-t-41ve
class Solution:
    def minDays(self, grid: List[List[int]]) -> int:
        # 先用并查集看有多少个连通块，若不等于1，返回0
        # 若等于1，tarjan算法求割点，若不存在，返回2，反之返回1
        m = len(grid)
        n = len(grid[0])
        fa = list(range(m * n))

        def find(x_: int) -> int:
            if fa[x_] != x_:
                fa[x_] = find(fa[x_])
            return fa[x_]

        g = [[] for _ in range(m * n)]
        vis = [[0] * n for _ in range(m)]
        cc = 0
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v == 0 or vis[i][j] == 1:
                    continue
                cur = [(i, j)]
                vis[i][j] = 1
                while cur:
                    pre = cur
                    cur = []
                    for x0, y0 in pre:
                        cc += 1
                        x = x0 * n + y0
                        fx = find(x)
                        for x1, y1 in (x0 + 1, y0), (x0 - 1, y0), (x0, y0 + 1), (x0, y0 - 1):
                            if 0 <= x1 < m and 0 <= y1 < n and vis[x1][y1] == 0 and grid[x1][y1] == 1:
                                y = x1 * n + y1
                                g[x].append(y)
                                g[y].append(x)
                                fy = find(y)
                                fa[fy] = fx
                                cur.append((x1, y1))
                    cur = list(set(cur))
                    for x, y in cur:
                        vis[x][y] = 1

        st = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    st.add(find(i * n + j))
        if len(st) != 1:
            return 0
        if cc == 1:
            return 1
        # tarjan
        t = TARJAN(m*n, g)
        t.tarjan(list(st)[0], -1, 0)
        return 1 if any(x for x in t.flag) else 2


class TARJAN:
    def __init__(self, n: int, g: List[List[int]]):
        # 记录结点的当前时间戳和最早时间戳,从根开始的一条路径上dfn 严格递增，low 严格非降
        self.dfn = [-1] * n
        self.low = [-1] * n
        self.bridge = []  # 桥
        self.flag = [False] * n  # 是否是割点
        self.g = g

    def tarjan(self, o: int, f: int, t: int) -> None:
        self.dfn[o] = t
        self.low[o] = t
        c = 0
        for child in self.g[o]:
            if child != f:
                if self.dfn[child] == -1:
                    c += 1
                    self.tarjan(child, o, t + 1)
                    self.low[o] = min(self.low[o], self.low[child])
                    # 找到割点, 非root,有儿子
                    if self.dfn[o] <= self.low[child] and f != -1 and not self.flag[o]:
                        self.flag[o] = True
                    # 找到桥
                    if self.dfn[o] < self.low[child]:
                        self.bridge.append([o, child])
                else:
                    self.low[o] = min(self.low[o], self.dfn[child])
        # root点 儿子数大于等于2
        if f == -1 and c >= 2 and not self.flag[o]:
            self.flag[o] = True

拓扑排序

2392. 给定条件下构造矩阵

给你一个 正 整数 k ，同时给你：

  • 一个大小为 n 的二维整数数组 rowConditions ，其中 rowConditions[i] = [abovei, belowi] 和
  • 一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [lefti, righti] 。

两个数组里的整数都是 1 到 k 之间的数字。

你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。

矩阵还需要满足以下条件：

  • 对于所有 0 到 n - 1 之间的下标 i ，数字 abovei 所在的 行 必须在数字 belowi 所在行的上面。
  • 对于所有 0 到 m - 1 之间的下标 i ，数字 lefti 所在的 列 必须在数字 righti 所在列的左边。

返回满足上述要求的 任意 矩阵。如果不存在答案，返回一个空的矩阵。

示例 1：

输入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
输出：[[3,0,0],[0,0,1],[0,2,0]]
解释：上图为一个符合所有条件的矩阵。
行要求如下：
- 数字 1 在第 1 行，数字 2 在第 2 行，1 在 2 的上面。
- 数字 3 在第 0 行，数字 2 在第 2 行，3 在 2 的上面。
列要求如下：
- 数字 2 在第 1 列，数字 1 在第 2 列，2 在 1 的左边。
- 数字 3 在第 0 列，数字 2 在第 1 列，3 在 2 的左边。
注意，可能有多种正确的答案。

示例 2：

输入：k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
输出：[]
解释：由前两个条件可以得到 3 在 1 的下面，但第三个条件是 3 在 1 的上面。
没有符合条件的矩阵存在，所以我们返回空矩阵。

提示：

  • 2 <= k <= 400
  • 1 <= rowConditions.length, colConditions.length <= 104
  • rowConditions[i].length == colConditions[i].length == 2
  • 1 <= abovei, belowi, lefti, righti <= k
  • abovei != belowi
  • lefti != righti

https://leetcode.cn/problems/build-a-matrix-with-conditions/description/

可以回想之前课程表那些题, 也是拓扑排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def toposort(edges):
            graph = [[] for _ in range(k)]
            in_deg = [0] * k
            for u, v in edges:
                graph[u-1].append(v-1)
                in_deg[v-1] += 1
            
            order = []
            q = deque(i for i, u in enumerate(in_deg) if u == 0 )
            while q:
                node = q.popleft()
                order.append(node)
                for target in graph[node]:
                    in_deg[target] -= 1
                    if in_deg[target] == 0:
                        q.append(target)
            return order if len(order) == k else None
        
        row = toposort(rowConditions)
        col = toposort(colConditions)
        if row is None or col is None:
            return []
        
        pos = {x:i for i, x in enumerate(col)}
        ans = [[0] * k for _ in range(k)]
        for i, x in enumerate(row):
            ans[i][pos[x]] = x + 1
        return ans

floyd算法

2959. 关闭分部的可行集合数目

一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。

公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（也可能不关闭任何分部），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。

两个分部之间的 距离 是通过道路长度之和的 最小值 。

给你整数 n ，maxDistance 和下标从 0 开始的二维整数数组 roads ，其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi 长度为 wi的 无向 道路。

请你返回关闭分部的可行方案数目，满足每个方案里剩余分部之间的最远距离不超过 maxDistance。

注意，关闭一个分部后，与之相连的所有道路不可通行。

注意，两个分部之间可能会有多条道路。

示例 1：

输入：n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]
输出：5
解释：可行的关闭分部方案有：
- 关闭分部集合 [2] ，剩余分部为 [0,1] ，它们之间的距离为 2 。
- 关闭分部集合 [0,1] ，剩余分部为 [2] 。
- 关闭分部集合 [1,2] ，剩余分部为 [0] 。
- 关闭分部集合 [0,2] ，剩余分部为 [1] 。
- 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。
总共有 5 种可行的关闭方案。

示例 2：

输入：n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]]
输出：7
解释：可行的关闭分部方案有：
- 关闭分部集合 [] ，剩余分部为 [0,1,2] ，它们之间的最远距离为 4 。
- 关闭分部集合 [0] ，剩余分部为 [1,2] ，它们之间的距离为 2 。
- 关闭分部集合 [1] ，剩余分部为 [0,2] ，它们之间的距离为 2 。
- 关闭分部集合 [0,1] ，剩余分部为 [2] 。
- 关闭分部集合 [1,2] ，剩余分部为 [0] 。
- 关闭分部集合 [0,2] ，剩余分部为 [1] 。
- 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。
总共有 7 种可行的关闭方案。

示例 3：

输入：n = 1, maxDistance = 10, roads = []
输出：2
解释：可行的关闭分部方案有：
- 关闭分部集合 [] ，剩余分部为 [0] 。
- 关闭分部集合 [0] ，关闭后没有剩余分部。
总共有 2 种可行的关闭方案。

提示：

  • 1 <= n <= 10
  • 1 <= maxDistance <= 105
  • 0 <= roads.length <= 1000
  • roads[i].length == 3
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 1 <= wi <= 1000
  • 一开始所有分部之间通过道路互相可以到达。

https://leetcode.cn/problems/number-of-possible-sets-of-closing-branches/description/?envType=daily-question&envId=2024-07-21

生成所有可能组合, 然后对所有组合做floyd求出最大的最短路径. 非常暴力, 但是floyd板子可以看下.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def floyd(self, node_lst, graph):
        if len(node_lst) <= 1:
            return 0
        shortest = float('-inf')
        d = copy.deepcopy(graph)
        for mid in node_lst:
            for u in node_lst:
                for v in node_lst:
                    if d[u][v] > d[u][mid] + d[mid][v]:
                        d[u][v] = d[u][mid] + d[mid][v]
                        d[v][u] = d[u][v]
        for u in node_lst:
            for v in node_lst:
                if d[u][v] > shortest:
                    shortest = d[u][v]
        del d
        return shortest

    def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
        graph = [[float('inf') for i in range(n)] for j in range(n)]
        for i in range(n):
            graph[i][i] = 0
        for u, v, w in roads:
            dis = min(w, graph[u][v])
            graph[u][v] = dis
            graph[v][u] = dis

        ans = 0
        for i in range(2 ** n):
            node_lst = [j for j in range(n) if (i >> j) & 1]
            shortest = self.floyd(node_lst, graph)
            if shortest <= maxDistance:
                ans += 1
        return ans

1334. 阈值距离内邻居最少的城市

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

返回在路径距离限制为 distanceThreshold 以内可到达城市最少的城市。如果有多个这样的城市，则返回编号最大的城市。

注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

示例 1：

输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2] 
城市 1 -> [城市 0, 城市 2, 城市 3] 
城市 2 -> [城市 0, 城市 1, 城市 3] 
城市 3 -> [城市 1, 城市 2] 
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。

示例 2：

输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出：0
解释：城市分布图如上。 
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1] 
城市 1 -> [城市 0, 城市 4] 
城市 2 -> [城市 3, 城市 4] 
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3] 
城市 0 在阈值距离 2 以内只有 1 个邻居城市。

提示：

  • 2 <= n <= 100
  • 1 <= edges.length <= n * (n - 1) / 2
  • edges[i].length == 3
  • 0 <= fromi < toi < n
  • 1 <= weighti, distanceThreshold <= 10^4
  • 所有 (fromi, toi) 都是不同的。

https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/description/

floyd和dijkstra都可以.

floyd写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def floyd(self, graph, n):
        for mid in range(n):
            for u in range(n):
                for v in range(n):
                    if graph[u][v] > graph[u][mid] + graph[mid][v]:
                        graph[u][v] = graph[u][mid] + graph[mid][v]
                        graph[v][u] = graph[u][v]
        return graph
 
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            graph[i][i] = 0
        for u,v,w in edges:
            graph[u][v] = w
            graph[v][u] = w
        
        graph = self.floyd(graph, n)

        ans = 0
        min_count = float('inf')
        for u in range(n):
            curr = sum(1 if x <= distanceThreshold else 0 for x in graph[u])
            if curr <= min_count:
                min_count = curr
                ans = u
        return ans

dijkstra写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def dijkstra(self, graph, u, n):
        ans = [-1] * n
        ans[u] = 0
        q = [(0,u)]
        while q:
            w, v = heapq.heappop(q)
            if w > ans[v]:
                continue
            for node, weight in enumerate(graph[v]):
                new_dist = weight + w
                if ans[node] > new_dist or ans[node] < 0:
                    ans[node] = new_dist
                    heapq.heappush(q, (new_dist, node))
        return ans
 
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            graph[i][i] = 0
        for u,v,w in edges:
            graph[u][v] = w
            graph[v][u] = w
        
        ans = 0
        min_count = float('inf')
        for u in range(n):
            lst = self.dijkstra(graph, u, n)
            curr = sum(1 if x <= distanceThreshold else 0 for x in lst)
            if curr <= min_count:
                min_count = curr
                ans = u
        return ans

dijkstra算法

3112. 访问消失节点的最少时间

给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。

同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。

注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。

请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，那么 answer[i] 为 -1 。

示例 1：

输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]

输出：[0,-1,4]

解释：

我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。

  • 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
  • 对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。但当我们到达的时候，它已经消失了，所以我们无法到达它。
  • 对于节点 2 ，我们需要至少 4 单位时间，通过 edges[2] 到达。

示例 2：

输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]

输出：[0,2,3]

解释：

我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。

  • 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
  • 对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。
  • 对于节点 2 ，我们需要至少 3 单位时间，通过 edges[0] 和 edges[1] 到达。

示例 3：

输入：n = 2, edges = [[0,1,1]], disappear = [1,1]

输出：[0,-1]

解释：

当我们到达节点 1 的时候，它恰好消失，所以我们无法到达节点 1 。

提示：

  • 1 <= n <= 5 * 104
  • 0 <= edges.length <= 105
  • edges[i] == [ui, vi, lengthi]
  • 0 <= ui, vi <= n - 1
  • 1 <= lengthi <= 105
  • disappear.length == n
  • 1 <= disappear[i] <= 105

https://leetcode.cn/problems/minimum-time-to-visit-disappearing-nodes/description/?envType=daily-question&envId=2024-07-21

比较基础的dijkstra.

  1. 存graph
  2. 初始化ans全-1
  3. 初始化queue为(0,0), 每次用优先队列取(distance, node)
  4. 循环读queue, 且将读取的节点当中间节点来更新ans
  5. 返回ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        graph = [[] for i in range(n)]
        for u,v,w in edges:
            graph[u].append([v,w])
            graph[v].append([u,w])
        
        ans = [-1 for i in range(n)]
        ans[0] = 0
        # distance, target
        q = [(0,0)]
        while q:
            dist, target = heapq.heappop(q)
            if dist > ans[target]:
                continue
            for node, weight in graph[target]:
                new_dist = dist + weight
                if new_dist < disappear[node] and (new_dist < ans[node] or ans[node] < 0):
                    ans[node] = new_dist
                    heapq.heappush(q, (new_dist, node))
        return ans

2045. 到达目的地的第二短时间

城市用一个 双向连通 图表示，图中有 n 个节点，从 1 到 n 编号（包含 1 和 n）。图中的边用一个二维整数数组 edges 表示，其中每个 edges[i] = [ui, vi] 表示一条节点 ui 和节点 vi 之间的双向连通边。每组节点对由 最多一条 边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 time 分钟。

每个节点都有一个交通信号灯，每 change 分钟改变一次，从绿色变成红色，再由红色变成绿色，循环往复。所有信号灯都 同时 改变。你可以在 任何时候 进入某个节点，但是 只能 在节点 信号灯是绿色时 才能离开。如果信号灯是  绿色 ，你 不能 在节点等待，必须离开。

第二小的值 是 严格大于 最小值的所有值中最小的值。

  • 例如，[2, 3, 4] 中第二小的值是 3 ，而 [2, 2, 4] 中第二小的值是 4 。

给你 n、edges、time 和 change ，返回从节点 1 到节点 n 需要的 第二短时间 。

注意：

  • 你可以 任意次 穿过任意顶点，包括 1 和 n 。
  • 你可以假设在 启程时 ，所有信号灯刚刚变成 绿色 。

示例 1：

       

输入：n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
输出：13
解释：
上面的左图展现了给出的城市交通图。
右图中的蓝色路径是最短时间路径。
花费的时间是：
- 从节点 1 开始，总花费时间=0
- 1 -> 4：3 分钟，总花费时间=3
- 4 -> 5：3 分钟，总花费时间=6
因此需要的最小时间是 6 分钟。

右图中的红色路径是第二短时间路径。
- 从节点 1 开始，总花费时间=0
- 1 -> 3：3 分钟，总花费时间=3
- 3 -> 4：3 分钟，总花费时间=6
- 在节点 4 等待 4 分钟，总花费时间=10
- 4 -> 5：3 分钟，总花费时间=13
因此第二短时间是 13 分钟。

示例 2：

输入：n = 2, edges = [[1,2]], time = 3, change = 2
输出：11
解释：
最短时间路径是 1 -> 2 ，总花费时间 = 3 分钟
第二短时间路径是 1 -> 2 -> 1 -> 2 ，总花费时间 = 11 分钟

提示：

  • 2 <= n <= 104
  • n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2)
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • 不含重复边
  • 每个节点都可以从其他节点直接或者间接到达
  • 1 <= time, change <= 103

https://leetcode.cn/problems/second-minimum-time-to-reach-destination/description/

单源次短路径, 还是dijkstra, 不过最短路径开两个, 同时注意循环回路, 取消visited的使用, 改为一旦路径更新就入堆.

//https://leetcode.cn/problems/second-minimum-time-to-reach-destination/solutions/1229095/gong-shui-san-xie-yi-ti-shuang-jie-dui-y-88np/
维护次短路是容易的，基本思路为：
- 若当前距离 dist 小于 dist1[x]，原本的最短路 dist1[x] 沦为次短路 dist2[x]，即先用 dist1[x] 更新 dist2[x] 后，再用 dist 更新 dist1[x]；
- 若当前距离 dist 等于 dist1[x]，不符合「严格次短路」，忽略；
- 若当前距离 dist 大于 dist1[x]，且 dist 小于 dist2[x]，则使用 dist 更新 dist2[x]。
- 同时，由于处理「严格次短路包含重复边」的情况，我们无须使用 vis[] 数组记录处理过的点，而要确保每次「最短路」或者「次短路」被更新时，都进行入堆操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        def dijkstra():
            ans = [[float('inf')] * 2 for _ in range(n)]
            ans[0][0] = 0
            q = [(0, 0)]
            while ans[-1][-1] == float('inf'):
                dist, u = heapq.heappop(q)
                for v in graph[u]:
                    if ans[v][0] > dist + 1:
                        ans[v][1] = ans[v][0]
                        ans[v][0] = dist + 1
                        heapq.heappush(q, (dist+1, v))
                    elif ans[v][0] < dist + 1 < ans[v][1]:
                        ans[v][1] = dist + 1
                        heapq.heappush(q, (dist+1, v)) 
            return ans[-1][-1]

        graph = [[] for _ in range(n)]
        for x, y in edges:
            graph[x-1].append(y-1)
            graph[y-1].append(x-1)
        
        step = dijkstra()
        ans = 0
        for _ in range(step):
            if ans % (change * 2) >= change:
                ans += change * 2 - ans % (change * 2)
            ans += time
        return ans

bitset

简单遍历题

2101. 引爆最多的炸弹

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。

炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。

你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。

给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。

示例 1：

输入：bombs = [[2,1,3],[6,1,4]]
输出：2
解释：
上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹，右边的炸弹不会被影响。
但如果我们引爆右边的炸弹，两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。

示例 2：

输入：bombs = [[1,1,5],[10,10,5]]
输出：1
解释：
引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。

示例 3：

输入：bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
输出：5
解释：
最佳引爆炸弹为炸弹 0 ，因为：
- 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。
- 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。
- 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。
所以总共有 5 个炸弹被引爆。

提示：

  • 1 <= bombs.length <= 100
  • bombs[i].length == 3
  • 1 <= xi, yi, ri <= 105

https://leetcode.cn/problems/detonate-the-maximum-bombs/description/?envType=daily-question&envId=2024-07-21

bfs做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        source_target = defaultdict(set)
        center = [(x,y) for x,y,r in bombs]
        ctr = Counter(center)
        center = set(center)
        for x,y,r in bombs:
            for cx, cy in center:
                if (x-cx) ** 2 + (y-cy) ** 2 <= r ** 2:
                    source_target[(x,y)].add((cx,cy))

        ans = 1
        while center:
            x, y = center.pop()
            curr = ctr[(x,y)]
            visited = set()
            visited.add((x,y))
            stack = set()
            stack.add((x,y))
            while stack:
                x, y = stack.pop()
                for nx, ny in source_target[(x,y)]:
                    if (nx,ny) not in visited:
                        stack.add((nx,ny))
                        visited.add((nx,ny))
                        curr += ctr[(nx,ny)]
                        center -= {(nx,ny)}
            ans = max(ans, curr)
        return ans

bitset做法, f存的数字的二进制位数表示了可以引爆的数量, 解法蛮暴力的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        f = [0] * n
        for i, (x, y, r) in enumerate(bombs):
            for j, (x2, y2, _) in enumerate(bombs):
                dx = x - x2
                dy = y - y2
                if dx * dx + dy * dy <= r * r:
                    f[i] |= 1 << j

        for k in range(n):
            for i in range(n):
                if f[i] >> k & 1:
                    f[i] |= f[k]

        return max(s.bit_count() for s in f)

dp题

3181. 执行操作可获得的最大总奖励 II

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

  • 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
  • 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。

以整数形式返回执行最优操作能够获得的 最大 总奖励。

示例 1：

输入：rewardValues = [1,1,3,3]

输出：4

解释：

依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]

输出：11

解释：

依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

提示：

  • 1 <= rewardValues.length <= 5 * 104
  • 1 <= rewardValues[i] <= 5 * 104

https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/description/

这题在dp里面也记录了下, 因为状态转移是直接平移, 所以可以用bit来做, 进行一个计算加速同时节省空间.

1
2
3
4
5
6
class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        f = 1
        for v in sorted(set(rewardValues)):
            f |= (f & ((1<<v)-1)) << v
        return f.bit_length() - 1

数位dp

600. 不含连续1的非负整数

给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。

示例 1:

输入: n = 5
输出: 5
解释:
下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数 3 违反规则（有两个连续的 1 ），其他 5 个满足规则。

示例 2:

输入: n = 1
输出: 2

示例 3:

输入: n = 2
输出: 3

提示:

  • 1 <= n <= 109

https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/description/?envType=daily-question&envId=2024-08-05

暴力肯定是不行的, 想了一下发现后状态和前状态有关, 所以一开始写了个移位的bit set写法, 但是因为最后统计数量用到了bit_count,复杂度O(n)直接爆掉了. 看了下答案解法, 一种是灵神的数位dp, 另一个是官方的loop写法(其实bitset后续优化就是这个方向, 但很可惜没写出来).

数位dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findIntegers(self, n: int) -> int:
        @cache
        def dfs(i, prev_1, is_limit):
            if i < 0:
                return 1
            # 上界
            up = (n >> i) & 1 if is_limit else 1
            # 填0
            res = dfs(i-1, False, is_limit and up == 0)
            if not prev_1 and up == 1:
                # 填1
                res += dfs(i-1, True, is_limit)
            return res
        # bit_length和索引i差1, 所以减掉1
        return dfs(n.bit_length()-1, False, True)

bitset(TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
VALUE = 7
count = 4
lgn = 29
for i in range(lgn - 1):
    VALUE |= (VALUE & ((1 << (count >> 1)) - 1)) << count
    count *= 2

class Solution:
    def findIntegers(self, n: int) -> int:
        if n <= 2:
            return n+1
        elif n == 3:
            return 3
        # 0,1,2满足,3不满足,所以是0111,即7

        return (((1<<(n+1)) - 1) & VALUE).bit_count()

官方优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def findIntegers(self, n: int) -> int:
        dp = [0] * 31
        dp[0] = 1
        dp[1] = 1
        for i in range(2, 31):
            dp[i] = dp[i - 1] + dp[i - 2]

        pre = 0
        res = 0

        for i in range(29, -1, -1):
            val = (1 << i)
            if n & val:
                res += dp[i + 1]
                if pre == 1:
                    break
                pre = 1
            else:
                pre = 0

            if i == 0:
                res += 1

        return res