算法leetcode

leetcode第392场周赛：贪心专场

字数统计: 3.6k字   |   阅读时长: 15分
,

摘要: 本文是 leetcode 第 392 场周赛的记录。主要涉及的算法包括贪心、双指针、排序、带权并查集

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

2024 年 4 月 6 日进行了 leetcode 第 375 场周赛，本场比赛没有赞助公司，奖品力扣周边，具体如下：

本场比赛的难度并不大，并且几个题都有贪心的影子，可以说是贪心专场。除了贪心以外，还考察了双指针, 排序, 带权并查集等算法点，成绩如下：

各个题目涉及到的知识点汇总如下：

往期参加比赛的记录如下：

【连载】leetcode周赛

A 题

给你一个整数数组 nums 。

返回数组 nums 中 严格递增 或 严格递减 的最长非空子数组的长度。

提示：

1
2
1 <= nums.length <= 50
1 <= nums[i] <= 50

示例 1：
输入：nums = [1,4,3,3,2]
输出：2
解释：
nums 中严格递增的子数组有[1]、[2]、[3]、[3]、[4] 以及 [1,4] 。
nums 中严格递减的子数组有[1]、[2]、[3]、[3]、[4]、[3,2] 以及 [4,3] 。
因此，返回 2 。

示例 2：
输入：nums = [3,3,3,3]
输出：1
解释：
nums 中严格递增的子数组有 [3]、[3]、[3] 以及 [3] 。
nums 中严格递减的子数组有 [3]、[3]、[3] 以及 [3] 。
因此，返回 1 。

示例 3：
输入：nums = [3,2,1]
输出：3
解释：
nums 中严格递增的子数组有 [3]、[2] 以及 [1] 。
nums 中严格递减的子数组有 [3]、[2]、[1]、[3,2]、[2,1] 以及 [3,2,1] 。
因此，返回 3 。

算法：单串单向双指针

数组长度为 $n$，维护两个指针 $l, r$，$l$ 从 0 开始向右走，直至 n 结束，过程如下：

$l$ 每走一步，就固定 $l$ 的位置，然后让 $r$ 从 $l+1$ 开始出发向右走，直至走到 $nums[r - 1] >= nums[r]$ 为止，这样 $nums[l..r-1]$ 就是一个可能的最长严格递增子数组。此后 $l$ 走到当前 $r$ 的位置，然后继续进行。

求最长严格递减子序列的过程与上面一样，只是在固定 $l$ 推进 $r$ 时，对于 $r$ 停止推进的条件改为 $nums[r - 1] >= nums[r]$ 即可。

代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        l = 0
        ans = 0
        while l < n:
            r = l + 1
            while r < n and nums[r - 1] < nums[r]:
                r += 1
            ans = max(ans, r - l)
            l = r
        l = 0
        while l < n:
            r = l + 1
            while r < n and nums[r - 1] > nums[r]:
                r += 1
            ans = max(ans, r - l)
            l = r
        return ans

B 题

给你一个字符串 s 和一个整数 k 。

定义函数 distance(s1, s2) ，用于衡量两个长度为 n 的字符串 s1 和 s2 之间的距离，即：

  • 字符 ‘a’ 到 ‘z’ 按 循环 顺序排列，对于区间 [0, n - 1] 中的 i ，计算所有「 s1[i] 和 s2[i] 之间 最小距离」的 和 。

例如，distance(“ab”, “cd”) == 4 ，且 distance(“a”, “z”) == 1 。

你可以对字符串 s 执行 任意次 操作。在每次操作中，可以将 s 中的一个字母 改变 为 任意 其他小写英文字母。

返回一个字符串，表示在执行一些操作后你可以得到的 字典序最小 的字符串 t ，且满足 distance(s, t) <= k 。

提示：

1
2
3
1 <= s.length <= 100
0 <= k <= 2000
s 只包含小写英文字母。

示例 1：
输入：s = “zbbz”, k = 3
输出：”aaaz”
解释：在这个例子中，可以执行以下操作：
将 s[0] 改为 ‘a’ ，s 变为 “abbz” 。
将 s[1] 改为 ‘a’ ，s 变为 “aabz” 。
将 s[2] 改为 ‘a’ ，s 变为 “aaaz” 。
“zbbz” 和 “aaaz” 之间的距离等于 k = 3 。
可以证明 “aaaz” 是在任意次操作后能够得到的字典序最小的字符串。
因此，答案是 “aaaz” 。

示例 2：
输入：s = “xaxcd”, k = 4
输出：”aawcd”
解释：在这个例子中，可以执行以下操作：
将 s[0] 改为 ‘a’ ，s 变为 “aaxcd” 。
将 s[2] 改为 ‘w’ ，s 变为 “aawcd” 。
“xaxcd” 和 “aawcd” 之间的距离等于 k = 4 。
可以证明 “aawcd” 是在任意次操作后能够得到的字典序最小的字符串。
因此，答案是 “aawcd” 。

示例 3：
输入：s = “lol”, k = 0
输出：”lol”
解释：在这个例子中，k = 0，更改任何字符都会使得距离大于 0 。
因此，答案是 “lol” 。

算法：贪心

原字符串 s 长度为 n，修改 s 中任意字符形成结果字符串 result。

由于我们想要 result 在满足要求的情况下字典序最小，因此只要在满足要求的前提下我们希望 result 中靠左边的字符尽可能大。由此我们有了以下的贪心思路：

从 i = 0 开始，依次构造 result[i] 。过程中每个字符 result[i] 都贪心地构造，即将其改为满足要求前提下最小的字符，直至 n 为止。

按照字符串距离 distance(s1, s2) 的定义方式，它等于各个字符间距离之和，需要满足的要求是 distance(s, result) <= k。也就是说对 s 的各个字符进行改变时，所有字符的改变量最大为 k，这可以直观理解为一种额度限制。

当考虑 result[0] 时，此时的总额度 k 还没用，我们在 k 的限制下将 result[0] 取到最小字符 $ch$，这步修改使用的额度为 s[0] 和 result[0] 之间的距离。将额度 k 更新，然后考虑 result[1]，以此类推。

当考虑 result[i] 时，result[0..i-1] 都已经贪心地构造好，而额度 k 也随着前面字符的构造有所消耗。

由于字符可以向两个方向变化，因此只要 $k >= 13$，result[i] 的结果直接就是 a，因为额度足够。如果 $k < 13$，在某些情况下 result[i] 就取不到 a 了，此时就要看 s[i] 从两个方向到 a 的距离：

  • 如果这个距离 k 额度能覆盖， result[i] 还是可以设为 a；
  • 如果不能覆盖，就将 result[i] 设为可以达到的最小的那个字符。

代码(Python)

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
def order(ch: str) -> int:
    return ord(ch) - ord('a')

def char(c: int) -> str:
    return chr(c + ord('a'))

def diff(ch1: str, ch2: str) -> int:
    ans = abs(ord(ch1) - ord(ch2))
    ans = min(ans, abs(26 + ord(ch1) - ord(ch2)))
    ans = min(ans, abs(26 + ord(ch2) - ord(ch1)))
    return ans

def step(ch: str, k: int) -> str:
    # ch 在上下变化幅度为 k 的范围内，返回字典序最小的字符
    if k >= 13:
        return 'a'
    ans = ch
    if order(ch) + k >= 26:
        return 'a'
    if order(ch) - k <= 0:
        return 'a'
    return char(order(ch) - k)

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        n = len(s)
        result = [''] * n
        for i in range(n):
            result[i] = step(s[i], k)
            k -= diff(result[i], s[i])
        return "".join(result)

C 题

给你一个整数数组 nums 和一个 非负 整数 k 。一次操作中，你可以选择任一元素 加 1 或者减 1 。

请你返回将 nums 中位数 变为 k 所需要的 最少 操作次数。

一个数组的中位数指的是数组按非递减顺序排序后最中间的元素。如果数组长度为偶数，我们选择中间两个数的较大值为中位数。

提示：

1
2
3
1 <= nums.length <= 2e5
1 <= nums[i] <= 1e9
1 <= k <= 1e9

示例 1：
输入：nums = [2,5,6,8,5], k = 4
输出：2
解释：我们将 nums[1] 和 nums[4] 减 1 得到 [2, 4, 6, 8, 4] 。现在数组的中位数等于 k 。

示例 2：
输入：nums = [2,5,6,8,5], k = 7
输出：3
解释：我们将 nums[1] 增加 1 两次，并且将 nums[2] 增加 1 一次，得到 [2, 7, 7, 8, 5] 。

示例 3：
输入：nums = [1,2,3,4,5,6], k = 4
输出：0
解释：数组中位数已经等于 k 了。

算法：排序、贪心

如果我们将长为 n 的数组 nums 排序，记 mid = n // 2，由于数组长度为偶数时，中位数为中间两个中最大的，这样 nums[mid] 就是中位数的位置。

因此我们只需要调整 nums 使得，排序后 mid 位置的元素为 k 即可。

假设 nums 已经排序，我们看 nums[mid] 与 k 的关系，如果 nums[mid] = k 那么中位数已经是 k，无需调整，否则：

  • 如果 nums[mid] < k，那么我们只需要将 mid 左侧小于 k 的元素都调整为 k；
  • 如果 nums[mid] > k，那么我们只需要将 mid 右侧大于 k 的元素都调整为 k。

上述做法的思路是先将数组排序，然后将中位数位置的元素置为 k，然后看为了满足这个中位数位置为 k 的条件，要保持 nums 有序的话，最少要做什么样的调整，这是一种贪心策略。

代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        mid = n // 2
        i = mid
        ans = 0
        if nums[mid] < k:
            while i < n and nums[i] < k:
                ans += k - nums[i]
                i += 1
        else:
            while i >= 0 and nums[i] > k:
                ans += nums[i] - k
                i -= 1
        return ans

D 题

给你一个 n 个节点的带权无向图，节点编号为 0 到 n - 1 。

给你一个整数 n 和一个数组 edges ，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间有一条权值为 wi 的无向边。

在图中，一趟旅途包含一系列节点和边。旅途开始和结束点都是图中的节点，且图中存在连接旅途中相邻节点的边。注意，一趟旅途可能访问同一条边或者同一个节点多次。

如果旅途开始于节点 u ，结束于节点 v ，我们定义这一趟旅途的 代价 是经过的边权按位与 AND 的结果。换句话说，如果经过的边对应的边权为 w0, w1, w2, …, wk ，那么代价为w0 & w1 & w2 & … & wk ，其中 & 表示按位与 AND 操作。

给你一个二维数组 query ，其中 query[i] = [si, ti] 。对于每一个查询，你需要找出从节点开始 si ，在节点 ti 处结束的旅途的最小代价。如果不存在这样的旅途，答案为 -1 。

返回数组 answer ，其中 answer[i] 表示对于查询 i 的 最小 旅途代价。

提示：

1
2
3
4
5
6
7
8
9
1 <= n <= 1e5
0 <= edges.length <= 1e5
edges[i].length == 3
0 <= ui, vi <= n - 1
ui != vi
0 <= wi <= 1e5
1 <= query.length <= 1e5
query[i].length == 2
0 <= si, ti <= n - 1

示例 1：
输入：n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
输出：[1,-1]
解释：

第一个查询想要得到代价为 1 的旅途，我们依次访问：0->1（边权为 7 ）1->2 （边权为 1 ）2->1（边权为 1 ）1->3 （边权为 7 ）。
第二个查询中，无法从节点 3 到节点 4 ，所以答案为 -1 。

示例 2：
输入：n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]
输出：[0]
解释：

第一个查询想要得到代价为 0 的旅途，我们依次访问：1->2（边权为 1 ），2->1（边权 为 6 ），1->2（边权为 1 ）。

算法：带权并查集

由于旅途中每个节点和每条边都可以经过无数次，而代价是所经过的边权按位与。因此直观上想，为了让代价最小，我们应该尽可能的多访问边，因为每多访问一条边，当前的代价与新的边权按位与之后就可能变得更小。

因此从 $u$ 出发，我们就希望把与 $u$ 相连的连通分量中所有的边都访问一遍，过程中始终记录按位与的结果，这个结果就是从 $u$ 出发到任何可以到达的节点的最小代价。

带权并查集就是这种维护连通分量上的性质的数据结构，其中权值是连通分量上所有边权的按位与。由于这种权值与树的具体结构无关，因此是一种集合级的权。

关于带集合级信息的并查集，参考文章 含集合级信息的并查集。

有了上述带权并查集，我们要做的就是枚举所有的边 (u, v, w)，合并 u 和 v，并用 w 更新集合级的权。枚举完成后，并查集也就预处理完了，之后枚举所有查询，如果 u, v 在同一个连通分量，则返回其对应的权，否则返回 -1。

代码(C++)

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
88
89
90
91
class UnionFindSet {
public:
    UnionFindSet(int n)
    {
        _set_size = n;
        _father = vector<int>(n, -1);
        _rank = vector<int>(n, 0);
        _weight = vector<int>(n, 0xffffffff);
        for(int i = 0; i < n; ++i)
            _father[i] = i;
    }

    ~UnionFindSet(){}

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    void merge(int x, int y, int w)
    {
        x = _find(x);
        y = _find(y);

        int tmp = _weight[x] & _weight[y];
        _weight[x] = tmp & w;
        _weight[y] = tmp & w;

        if(x == y) return;

        // 此时 x, y 是所在树的根
        if(_rank[x] < _rank[y])
            _father[x] = y;
        else
        {
            _father[y] = x;
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }

        --_set_size;
    }

    int query(int s, int t)
    {
        if(s == t)
            return 0;

        if(!same(s, t))
            return -1;
        return _weight[_find(s)];
    }

    int set_size()
    {
        return _set_size;
    }

private:
    vector<int> _father;
    vector<int> _rank;
    vector<int> _weight;
    int _set_size;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        else
            return _father[x] = _find(_father[x]); // 路径压缩
    }
};


class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        UnionFindSet unionfindset(n);
        for(vector<int>& e: edges)
        {
            unionfindset.merge(e[0], e[1], e[2]);
        }
        int m = query.size();
        vector<int> result(m);
        for(int i = 0; i < m; ++i)
        {
            result[i] = unionfindset.query(query[i][0], query[i][1]);
        }
        return result;
    }
};
Share