且听疯吟

leetcode contest 320

2022-11-25

leetcode contest 320

题目质量确实很不错，适合用来作为面试题目。

2475. 数组中不等三元组的数目

给你一个下标从 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：

输入：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 。

提示：

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

地址

https://leetcode.cn/problems/number-of-unequal-triplets-in-array/

题意

直接遍历即可

思路

  1. 直接遍历数组中所有元素即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k]) {
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

2476. 二叉搜索树最近节点查询

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

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

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

示例 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] 。

提示：

  • 树中节点的数目在范围 [2, 105] 内
  • 1 <= Node.val <= 106
  • n == queries.length
  • 1 <= n <= 105
  • 1 <= queries[i] <= 106

地址

https://leetcode.cn/contest/weekly-contest-320/problems/closest-nodes-queries-in-a-binary-search-tree/

题意

二分查找

思路

  1. 简单题目，直接利用二分查找即可非常简单的题目。中序遍历二叉查找树即可使得数组遍历结果有序。
  2. 利用二分查找给定的元素大于等于该元素的最小值即可。
  3. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n + m \log n)$，其中 $n$ 为节点的数目，$m$ 表示查询的次数。
  • 空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 为节点的数目。

代码

class Solution {
public:
    bool dfs(TreeNode *root, vector<int> &res) {
        if(!root) {
            return false;
        }    
        dfs(root->left, res);
        res.emplace_back(root->val);
        dfs(root->right, res);
        return true;
    }
    
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        vector<int> arr;
        vector<vector<int>> res;
        dfs(root, arr);
        for (auto v : queries) {
            vector<int> curr = {-1, -1};
            auto it = lower_bound(arr.begin(), arr.end(), v);
            if (it != arr.end()) {
                curr[1] = *it;
                if (*it == v) {
                    curr[0] = *it;
                    res.emplace_back(curr);
                    continue;
                }
            }
            
            if (it != arr.begin()) {
                curr[0] = *(--it);
            }
            res.emplace_back(curr);
        }
        return res;
    }
};

2477. 到达首都的最少油耗

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

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

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

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

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

示例 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
解释：没有代表需要从别的城市到达首都。

提示：

  • 1 <= n <= 105
  • roads.length == n - 1
  • roads[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • roads 表示一棵合法的树。
  • 1 <= seats <= 105

地址

https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/description/

题意

贪心算法

思路

  1. 涉及到一个比较有意思的贪心算法，题目中有几个重要的前提如下:
  • 每个代表走不会走回头路，即每个代表只会从 $a\rightarrow b$，路劲不会是 $a \rightarrow c \rightarrow d \rightarrow c \rightarrow b$；
  • 对于每个代表的行程可以不是连续的，比如代表 $1$ 可以先到达 $a$，等待空闲车辆到达，然后共享车辆一起到达 $c$。
  1. 我们设 $tot(x)$ 表示到达节点 $x$ 的人数之和，则所有人到达节点 $x$ 后，总共需要的车辆数目最少为 $\lceil \dfrac{tot[x]}{seats}\rceil$，则此时这些车辆移动一步需要的油耗最少为 $\lceil \dfrac{tot[ch(x)]}{seats}\rceil$，我们依次求出即可，此时从节点 $x$ 出发的车辆总数为 $\lceil \dfrac{tot[x]}{seats}\rceil + 1$。
  2. 复杂度分析
  • 时间复杂度：时间复杂度为 $O(n)$，$n$ 为给定的节点的数目。
  • 空间复杂度：空间复杂度为 $O(n)$，$n$ 为给定的节点的数目。

代码

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        vector<vector<int>> graph(n);
        for (auto v : roads) {
            graph[v[0]].emplace_back(v[1]);
            graph[v[1]].emplace_back(v[0]);
        }
        vector<bool> visit(n, false);
        long long res = 0;
        function<int(int)> dfs = [&](int curr)->int {
            visit[curr] = true;
            int totSum = 0;
            for (auto next : graph[curr]) {
                if (visit[next]) continue;
                int tot = dfs(next);
                res += ceil((double)tot / seats);
                totSum += tot;
            }
            return totSum + 1;
        };
        dfs(0);
        return res;
    }
};

2478. 完美分割的方案数

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

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

  • s 被分成 k 段互不相交的子字符串。
  • 每个子字符串长度都 至少 为 minLength 。
    每个子字符串的第一个字符都是一个 质数 数字，最后一个字符都是一个 非质数 数字。质数数字为 '2' ，'3' ，'5' 和 '7' ，剩下的都是非质数数字。
    请你返回 s 的 完美 分割数目。由于答案可能很大，请返回答案对 109 + 7 取余 后的结果。

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

示例 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 <= k, minLength <= s.length <= 1000
  • s 每个字符都为数字 '1' 到 '9' 之一。

地址

https://leetcode.cn/problems/number-of-beautiful-partitions/description/

题意

动态规划

思路

  1. 设 $dp[i][j]$ 表示前 $j$ 个字母存在长度为 $i$ 的完美分割的方案数，如果我们按照常规的动态规划可以知道，一定需要满足如下才可以完成分割:
  • $s[j]$ 一定为非质数的数字；
  • 假设以 $s[j]$ 为末尾的最后一个分割的起点为 $k$，则此时一定满足:
    • $s[k]$ 一定为质数；
    • $s[k-1]$ 要么不存在要么为非质数的数字；
    • 前 $k-1$ 个字母一定存在长度为 $i-1$ 段的完美分割；
    • 最后的分段长度一定满足 $j - k \ge minLength$;
      综上，我们可以得到递推公式如下:
      $$
      dp[i][j] = \sum_{k = 0}^{j - minLength}dp[i-1][k] \quad (dp[i-1][k] > 0, s[k] \in {1,4,6,8,9}, s[k+1] \in {2,3,5,7})
      $$

可以参考题解，难点在于计算 $dp[i][j]$ 时，我们同时计算 $dp[i-1][j-l]$，不太好思考上述的解法细节问题。这样保证所有满足 $dp[i-1][k] > 0, s[k] \in {1,4,6,8,9}, s[k+1] \in {2,3,5,7}$ 的值全部都被计算出来，确实是个不错的思考题目。

  1. 复杂度分析：
  • 时间复杂度：$O(n \times k)$，其中 $n$ 表示给定的字符串的长度, $k$ 表示分段。
  • 空间复杂度：$O(n \times k)$，其中 $n$ 表示给定的字符串的长度, $k$ 表示分段

代码

class Solution {
public:
    bool isPrime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }

    bool canPartition(const string &s, int i) {
        return i == 0 || i == s.size() || (!isPrime(s[i - 1]) && isPrime(s[i]));
    }

    int beautifulPartitions(string s, int k, int minLength) {
        int n = s.size();
        long long mod = 1e9 + 7;
        if (!isPrime(s[0]) || isPrime(s[n - 1])) {
            return 0;
        }
        vector<vector<long long>> dp(k + 1, vector<long long>(n + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            int sum = 0;
            for (int j = i * minLength; j <= n; j++) {
                if (canPartition(s, j - minLength)) {
                    sum = (sum + dp[i-1][j - minLength]) % mod;
                }
                if (canPartition(s, j)) {
                    dp[i][j] = sum;
                }
            }
        }
        return dp[k][n];
    }
};

1977. 划分数字的方案数

你写下了若干 正整数 ，并将它们连接成了一个字符串 num 。但是你忘记给这些数字之间加逗号了。你只记得这一列数字是 非递减 的且 没有 任何数字有前导 0 。

请你返回有多少种可能的 正整数数组 可以得到字符串 num 。由于答案可能很大，将结果对 109 + 7 取余 后返回。

示例 1：

输入：num = "327"
输出：2
解释：以下为可能的方案：
3, 27
327

示例 2：

输入：num = "094"
输出：0
解释：不能有数字有前导 0 ，且所有数字均为正数。

示例 3：

输入：num = "0"
输出：0
解释：不能有数字有前导 0 ，且所有数字均为正数。

示例 4：

输入：num = "9999999999999"
输出：101

提示：

  • 1 <= num.length <= 3500
  • num 只含有数字 '0' 到 '9' 。

地址

https://leetcode.cn/problems/number-of-ways-to-separate-numbers/description/

题意

前缀和 + 动态规划

思路

  1. 题目还是非常难和有意思的题目，我们设 $dp[i][j]$ 前 $i$ 个字母且最后一个数字长度为 $j$ 组成的合法的方案数，此时我们可以知道最后一个数字的长度为 $j$，起点为 $num[i - j]$，最后一个数字一定为 $num[i-j,\cdots,i - 1]$，则可以分析如下：
  • 要么倒数第二个数字的长度小于 $j$；
  • 要么倒数第二个数字的长度为 $j$，此时该数字为 $num[i-2 \times j,i-j-1]$，此时一定满足 $num[i-j,\cdots,i - 1] > num[i-2 \times j,i-j-1]$；

因此我们可以得到如下递推公式:
$$
dp[i][j] = \sum_{k=0}^{j-1} dp[i-j][k] + dp[i-j][j] \quad if \quad num[i-j,\cdots,i - 1] \ge num[i-2 \times j,i-j-1]\
dp[i][j] = \sum_{k=0}^{j-1} dp[i-j][k] \quad if \quad num[i-j,\cdots,i - 1] < num[i-2 \times j,i-j-1]\
$$

此时我们只需要令 $sum[i][j] = \sum_{k=0}^{j} dp[i][k]$ 即可，则上述等式即转换为:
$$
dp[i][j] = sum[i-j][j-1] + dp[i-j][j] \quad (if \quad num[i-j,\cdots,i - 1] \ge num[i-2 \times j,i-j-1])\
dp[i][j] = sum[i-j][j-1] \quad (if \quad num[i-j,\cdots,i - 1] < num[i-2 \times j,i-j-1])\
$$

  1. 复杂度分析：
  • 时间复杂度：$O(n^2)$，其中 $n$ 表示给定的字符串的长度。
  • 空间复杂度：$O(n^2)$，其中 $n$ 表示给定的字符串的长度。

代码

const long long mod = 1e9 + 7;

class Solution {
public:
    int numberOfCombinations(string num) {
        int n = num.size();
        if (num[0] == '0') {
            return 0;
        }
        vector<vector<int>> lcp(n + 1, vector<int>(n + 1));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                if (num[i] == num[j]) {
                    lcp[i][j] = lcp[i + 1][j + 1] + 1;
                } else {
                    lcp[i][j] = 0;
                }
                lcp[j][i] = lcp[i][j];
            }
        }

        auto cmp = [&](int i, int j, int len) {
            if (j < 0) {
                return true;
            }
            int x = lcp[i][j];
            return x >= len || num[i + x] >= num[j + x];
        };
        
        vector<vector<long long>> dp(n + 1, vector<long long>(n + 1));
        vector<vector<long long>> sum(n + 1, vector<long long>(n + 1));
        sum[0] = vector<long long>(n + 1, 1L);
        sum[1] = vector<long long>(n + 1, 1L);
        sum[1][0] = 0;
        dp[0][0] = dp[1][1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (num[i - j] == '0') continue;
                if (cmp(i - j, i - 2 * j, j)) {
                    dp[i][j] = (dp[i][j] + sum[i - j][j]) % mod;
                } else {
                    dp[i][j] = (dp[i][j] + sum[i - j][j - 1]) % mod;
                }
            }
            for (int j = 1; j <= n; j++) {
                sum[i][j] = (sum[i][j - 1] + dp[i][j]) % mod;
            }
        }
        return sum[n][n];
    }
};

欢迎关注和打赏，感谢支持！

Tags: 力扣周赛
← 【build a computer】 project 9 leetcode contest 319 →

扫描二维码，分享此文章