算法leetcode

leetcode第320场周赛：树结构专场

字数统计: 3.3k字   |   阅读时长: 14分
,

摘要: 本文是 leetcode 第 320 周赛的记录。主要涉及的算法包括暴力、二叉查找树、树的遍历、动态规划。

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

总览

2022 年 11 月 20 日进行了 leetcode 第 320 场周赛，之前参加了这场比赛但是文章一直拖着没有写，这里补一下。本场比赛由诺基亚贝尔公司赞助，奖品如下：

诺基亚贝尔是诺基亚集团与中国保利集团下属华信邮电合资的企业，是国务院国资委直接监管的央企中的唯一一家合资企业，在上海。它是诺基亚在中国的独家运营平台，员工 15000 人。主要为运营商和非运营商客户提供端到端的信息通信解决方案和服务，并且涉足IP网络、光网络、固网以及下一代 5G 网络。详见官网：

1
https://www.nokia-sbell.com/

本场比赛前三题难度感觉不高，提交的也很快。D 题还是有点难度的，比赛时没写出来。最后成绩却还行，估计是 D 题做对的人不多，并且自己前三题交的很快。成绩如下：

A 题是暴力枚举。B 题和 C 题考察的都是树上的问题，B 题用到是二叉搜索树的排序特性，C 题是在树的遍历过程中统计信息。

D 题赛后解决了，是一个动态规划。状态有两个维度，其中一个是阶段，另一个是附加信息。也就是带有一个附加信息维度的单串线性 DP 问题。

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

A 题

给你一个下标从 0 开始的正整数数组 nums 。请你找出并统计满足下述条件的三元组 (i, j, k) 的数目：

  • 0 <= i < j < k < nums.length
  • nums[i]、nums[j] 和 nums[k] 两两不同 。

换句话说：nums[i] != nums[j]、nums[i] != nums[k] 且 nums[j] != nums[k] 。

返回满足上述条件三元组的数目。

提示：

1
2
3 <= nums.length <= 100
1 <= nums[i] <= 1000

示例 1：
输入：nums = [4,4,2,4,3]
输出：3
解释：下面列出的三元组均满足题目条件：

  • (0, 2, 4) 因为 4 != 2 != 3
  • (1, 2, 4) 因为 4 != 2 != 3
  • (2, 3, 4) 因为 2 != 4 != 3
    共计 3 个三元组，返回 3 。
    注意 (2, 0, 4) 不是有效的三元组，因为 2 > 0 。

示例 2：
输入：nums = [1,1,1,1,1]
输出：0
解释：不存在满足条件的三元组，所以返回 0 。

算法1：暴力

由于数据范围很小，暴力枚举所有三元组，判断三个元素是否相等是最快的办法，这也是比赛时的做法。时间复杂度 $O(N^{3})$

代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                if nums[i] == nums[j]:
                    continue
                for k in range(j + 1, n):
                    if nums[k] == nums[j] or nums[k] == nums[i]:
                        continue
                    ans += 1
        return ans

算法2：哈希表

建立哈希映射 mapping，mapping[x] 表示 nums 中 x 的个数。枚举 nums 然后填充 mapping。

枚举从 mapping 中取 3 个键的所有取法 $(x, y, z)$，这种取法对答案的贡献如下：

元素的种类数为 $U$ 的话，这种做法的时间复杂度为 $O(N + U^{3})$。

根据实际问题如果元素种类数很少，重复的非常多，这种做法是更高效的。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        mapping = Counter(nums)
        ans = 0
        keys = list(mapping.keys())
        m = len(keys)
        for i in range(m - 2):
            ni = mapping[keys[i]]
            for j in range(i + 1, m - 1):
                nj = mapping[keys[j]]
                for k in range(j + 1, m):
                    nk = mapping[keys[k]]
                    ans += ni * nj * nk
        return ans

B 题

给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。

请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：

  • mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
  • maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。

返回数组 answer 。

提示：

1
2
3
4
5
树中节点的数目在范围 [2, 1e5] 内
1 <= Node.val <= 1e6
n == queries.length
1 <= n <= 1e5
1 <= queries[i] <= 1e6

示例 1 ：

输入：root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
输出：[[2,2],[4,6],[15,-1]]
解释：按下面的描述找出并返回查询的答案：

  • 树中小于等于 2 的最大值是 2 ，且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。
  • 树中小于等于 5 的最大值是 4 ，且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。
  • 树中小于等于 16 的最大值是 15 ，且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。

示例 2 ：

输入：root = [4,null,9], queries = [3]
输出：[[-1,4]]
解释：树中不存在小于等于 3 的最大值，且大于等于 3 的最小值是 4 。所以查询的答案是 [-1,4] 。

算法：二叉查找树

由于给定的是二叉搜索树，因此中序遍历后可以得到一个有序数组。

之后对于 queries 中的每个查询值 x，lower_bound 可以得到大于等于 x 的最小值的位置，upper_bound 可以得到大于 x 的最小值的位置。因此答案如下：

1
2
int max_idx = lower_bound(nums.begin(), nums.end(), x) - nums.begin();
int min_idx = upper_bound(nums.begin(), nums.end(), x) - nums.begin() - 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
class Solution {
public:
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        nums = vector<int>();
        inOrder(root);
        int N = nums.size();
        int n = queries.size();
        vector<vector<int>> result(n, vector<int>(2, -1));
        for(int i = 0; i < n; ++i)
        {
            int x = queries[i];
            int min_idx = upper_bound(nums.begin(), nums.end(), x) - nums.begin() - 1;
            if(min_idx >= 0)
                result[i][0] = nums[min_idx];
            int max_idx = lower_bound(nums.begin(), nums.end(), x) - nums.begin();
            if(max_idx < N)
                result[i][1] = nums[max_idx];
        }
        return result;
    }

    vector<int> nums;

    void inOrder(TreeNode* node)
    {
        if(node -> left)
            inOrder(node -> left);
        nums.push_back(node -> val);
        if(node -> right)
            inOrder(node -> right);
    }
};

C 题

给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。

每个城市里有一个代表，他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

提示：

1
2
3
4
5
6
7
1 <= n <= 1e5
roads.length == n - 1
roads[i].length == 2
0 <= ai, bi < n
ai != bi
roads 表示一棵合法的树。
1 <= seats <= 1e5

示例 1：

输入：roads = [[0,1],[0,2],[0,3]], seats = 5
输出：3
解释：

  • 代表 1 直接到达首都，消耗 1 升汽油。
  • 代表 2 直接到达首都，消耗 1 升汽油。
  • 代表 3 直接到达首都，消耗 1 升汽油。
    最少消耗 3 升汽油。

示例 2：

输入：roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
输出：7
解释：

  • 代表 2 到达城市 3 ，消耗 1 升汽油。
  • 代表 2 和代表 3 一起到达城市 1 ，消耗 1 升汽油。
  • 代表 2 和代表 3 一起到达首都，消耗 1 升汽油。
  • 代表 1 直接到达首都，消耗 1 升汽油。
  • 代表 5 直接到达首都，消耗 1 升汽油。
  • 代表 6 到达城市 4 ，消耗 1 升汽油。
  • 代表 4 和代表 6 一起到达首都，消耗 1 升汽油。
    最少消耗 7 升汽油。

示例 3：

输入：roads = [], seats = 1
输出：0
解释：没有代表需要从别的城市到达首都。

算法：树的遍历

对树进行 DFS 遍历，在访问到 $u$ 时，先递归地遍历 $u$ 的各个子节点 $v$ 并返回以 $v$ 为根的子树的节点数目。整合各子树的结果，得到以当前节点 $u$ 为根的子树的节点数目。

由于每个节点只有一个代表，因此以当前节点 $u$ 为根的子树的节点数目 $n_{u}$ 就是从 $u$ 往其父节点 $fa$ 这段路的代表人数 n_representatives。

代表可以在路程中换车，因此在当前节点 $u$ 可以把乘坐的车整合一下，这样 $u$ 到 $fa$ 这一段路只需要 $\left\lceil\frac{n_{u}}{seats}\right\rceil$ 辆车。

由于相邻节点之间的油耗都是 1，于是 $u$ 到 $fa$ 这一段的油耗自然就是 $\left\lceil\frac{n_{u}}{seats}\right\rceil$。

在回溯前，把上述油耗加到总油耗里即可。

代码(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
using ll = long long;

class Solution {
public:
    ll minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        vector<vector<int>> g(n);
        for(const vector<int> &e: roads)
        {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }

        ll ans = 0;
        dfs(g, 0, -1, ans, seats);
        return ans;
    }

    int dfs(const vector<vector<int>>& g, int u, int fa, ll& ans, const int seats)
    {
        int n_representatives = 1;
        for(int v: g[u])
        {
            if(v == fa)
                continue;
            n_representatives += dfs(g, v, u, ans, seats);
        }
        if(u != 0)
            ans += ceil(n_representatives / (double)seats);
        return n_representatives;
    }
};

D 题

给你一个字符串 s ，每个字符是数字 ‘1’ 到 ‘9’ ，再给你两个整数 k 和 minLength 。

如果对 s 的分割满足以下条件，那么我们认为它是一个 完美 分割：

  • s 被分成 k 段互不相交的子字符串。
  • 每个子字符串长度都 至少 为 minLength 。
  • 每个子字符串的第一个字符都是一个 质数 数字，最后一个字符都是一个 非质数 数字。质数数字为 ‘2’ ，’3’ ，’5’ 和 ‘7’ ，剩下的都是非质数数字。

请你返回 s 的 完美 分割数目。由于答案可能很大，请返回答案对 1e9 + 7 取余 后的结果。

一个 子字符串 是字符串中一段连续字符串序列。

提示：

1
2
1 <= k, minLength <= s.length <= 1000
s 每个字符都为数字 '1' 到 '9' 之一。

示例 1：
输入：s = “23542185131”, k = 3, minLength = 2
输出：3
解释：存在 3 种完美分割方案：
“2354 | 218 | 5131”
“2354 | 21851 | 31”
“2354218 | 51 | 31”

示例 2：
输入：s = “23542185131”, k = 3, minLength = 3
输出：1
解释：存在一种完美分割方案：”2354 | 218 | 5131” 。

示例 3：
输入：s = “3312958”, k = 3, minLength = 1
输出：1
解释：存在一种完美分割方案：”331 | 29 | 58” 。

算法：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
状态定义：
dp[i][j] = splits[0..i] 上分 j 段的方案数

答案：
dp[m - 1][k]

初始化：
dp[0][0] = 1;
dp[0][j] = 0; j > 0
dp[i][0] = 0; i > 0
dp[i][j] = 0; i < j

状态转移：
dp[i][j] = sum(dp[l][j - 1])
其中 0 <= l < i 且 splits[i] - splits[l] >= minLength

代码(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
const int MOD = 1e9 + 7;
using ll = long long;

class Solution {
public:
    int beautifulPartitions(string s, int k, int minLength) {
        vector<int> splits; // 合法分割点的位置
        int n = s.size();
        if(is_prime(s[0]))
            splits.push_back(0);
        for(int i = 0; i < n - 1; ++i)
        {
            if(!is_prime(s[i]) && is_prime(s[i + 1]))
                splits.push_back(i + 1);
        }
        if(!is_prime(s[n - 1]))
            splits.push_back(n);

        if(splits.empty())
            return 0;
        int m = splits.size();
        if(splits[0] != 0 || splits[m - 1] != n)
            return 0;
        if(k >= m)
            return 0;

        vector<vector<int>> dp(m, vector<int>(k + 1, -1));
        dp[0][0] = 1;
        for(int j = 1; j <= k; ++j)
            dp[0][j] = 0;
        for(int i = 1; i < m; ++i)
            dp[i][0] = 0;

        return solve(splits, m - 1, k, dp, minLength);

    }

    int solve(const vector<int>& splits, int i, int j, vector<vector<int>>& dp, const int minLength)
    {
        if(dp[i][j] != -1)
            return dp[i][j];
        if(i < j)
            return dp[i][j] = 0;
        int ans = 0;
        for(int l = 0; l < i; ++l)
        {
            if(splits[i] - splits[l] < minLength)
                break;
            ans = ((ll)ans + solve(splits, l, j - 1, dp, minLength)) % MOD;
        }
        return dp[i][j] = ans;
    }

    bool is_prime(const char& ch)
    {
        return ch == '2' || ch == '3' || ch == '5' || ch == '7';
    }
};
Share