leetcode conttest 305

leetcode conttest 305

上午在医院看病，赛后打卡补题，感觉确实比较简单的题目。感觉最近状态越来越差，越来越没有时间参加比赛。并且感觉题目质量确实也越来越差，没有多少高质量的题目，感觉还算CF 或者 atcoder 的题目质量高很多。

6136. 算术三元组的数目

题目

给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件，则三元组 (i, j, k) 就是一个 算术三元组 ：

  • i < j < k ，
  • nums[j] - nums[i] == diff 且
  • nums[k] - nums[j] == diff
    返回不同 算术三元组 的数目。

示例 1：

1
2
3
4
5
输入：nums = [0,1,4,6,7,10], diff = 3
输出：2
解释：
(1, 2, 4) 是算术三元组：7 - 4 == 3 且 4 - 1 == 3 。
(2, 4, 5) 是算术三元组：10 - 7 == 3 且 7 - 4 == 3 。

示例 2：
1
2
3
4
5
输入：nums = [4,5,6,7,8,9], diff = 2
输出：2
解释：
(0, 2, 4) 是算术三元组：8 - 6 == 2 且 6 - 4 == 2 。
(1, 3, 5) 是算术三元组：9 - 7 == 2 且 7 - 5 == 2 。

提示：

  • 3 <= nums.length <= 200
  • 0 <= nums[i] <= 200
  • 1 <= diff <= 50
  • nums 严格 递增

地址

https://leetcode.cn/problems/number-of-arithmetic-triplets/

题意

哈希表 + 双指针

思路

  1. 简单题目，遍历每个一个 $x$, 由于数组 $nums$ 中每个元素都不相等，因此我们可以利用哈希表检测， $x + diff$ 与 $x + 2 \times diff$ 是否同时存在于数组中。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(1)$。

    代码

  • 直接遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int arithmeticTriplets(vector<int>& nums, int diff) {
            unordered_set<int> cnt;
            for (auto v : nums) {
                cnt.emplace(v);
            }
            int ans = 0;
            for (int i = 0; i < nums.size(); i++) {
                if (cnt.count(nums[i] + diff) && cnt.count(nums[i] + 2 * diff)) {
                    ans++;
                }
            }
            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
    class Solution {
    public:
        int arithmeticTriplets(vector<int>& nums, int diff) {
            int ans = 0;
            int i = 0, j = 1;
            for (auto x : nums) {
                while(nums[i] + 2 * diff < x) {
                    i++;
                }
                if (nums[i] + 2 * diff > x) {
                    continue;
                }
                while (nums[j] + diff < x) {
                    j++;
                }
                if (nums[j] + diff > x) {
                    continue;
                }
                if (nums[j] + diff == x) {
                    ans++;
                }
            }
            return ans;
        }
    };

6139. 受限条件下可到达节点的数目

题目

现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。

给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restricted 表示 受限 节点。

在不访问受限节点的前提下，返回你可以从节点 0 到达的 最多 节点数目。

注意，节点 0 不 会标记为受限节点。

示例 1：

1
2
3
4
输入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
输出：4
解释：上图所示正是这棵树。
在不访问受限节点的前提下，只有节点 [0,1,2,3] 可以从节点 0 到达。

示例 2：
1
2
3
4
输入：n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
输出：3
解释：上图所示正是这棵树。
在不访问受限节点的前提下，只有节点 [0,5,6] 可以从节点 0 到达。

提示：

  • 2 <= n <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges 表示一棵有效的树
  • 1 <= restricted.length < n
  • 1 <= restricted[i] < n
  • restricted 中的所有值 互不相同

地址

https://leetcode.cn/problems/reachable-nodes-with-restrictions

题意

广度有限搜索或者深度有限搜索

思路

  1. 感觉这个题目可以算是一个简单题目，直接BFS即可，非常简单的题目。我们直接从 0 点开始遍历，遇到不可达的点则返回。
  2. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n)$，$n$ 表示节点的数目。
  • 空间复杂度：$O(n)$，$n$ 表示节点的数目。

    代码

    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:
        int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
            queue<int> qu;
            unordered_set<int> cnt;
            vector<vector<int>> adj(n);
            for (auto v : restricted) {
                cnt.emplace(v);
            }
            for (auto &v : edges) {
                adj[v[0]].emplace_back(v[1]);
                adj[v[1]].emplace_back(v[0]);
            }
            int ans = 0;
            qu.emplace(0);
            vector<bool> visit(n, false);
            visit[0] =true;
            while (!qu.empty()) {
                int curr = qu.front();
                qu.pop();
                ans++;
                for (auto v : adj[curr]) {
                    if (visit[v]) continue;
                    if (cnt.count(v)) continue;
                    visit[v] = true;
                    qu.emplace(v);
                }
            }
            
            return ans;
        }
    };

2369. 检查数组是否存在有效划分

题目

给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。

如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：

  • 子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
  • 子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
  • 子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。
    如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。

示例 1：

1
2
3
4
输入：nums = [4,4,4,5,6]
输出：true
解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。
这是一种有效划分，所以返回 true 。

示例 2：
1
2
3
输入：nums = [1,1,1,2]
输出：false
解释：该数组不存在有效划分。

提示：

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 106

地址

https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array

题意

动态规划

思路

  1. 感觉就是非常非常常规的简单动态规划就可以搞定，设 $dp[i]$ 表示前 $i$ 个元素是否可以等效划分，则递推公式如下:根据以上递推公式，直接进行动态规划求解即可。
  2. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n)$，其中 $n$ 表示数组的长度。
  • 空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 表示数组的长度。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
        bool validPartition(vector<int>& nums) {
            int n = nums.size();
            vector<bool> dp(n + 1, false);
            dp[0] = true;
            dp[1] = false;
            for (int i = 2; i <= n; i++) {
                /* two */
                if (nums[i - 1] == nums[i - 2]) {
                    dp[i] = dp[i] | dp[i - 2];
                }
                /* tree */
                if (i >= 3 && nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) {
                    dp[i] = dp[i] | dp[i-3];
                }
                /* tree */
                if (i >= 3 && nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1) {
                    dp[i] = dp[i] | dp[i-3];
                }
            }
            return dp[n];
        }
    };

2370. 最长理想子序列

题目

给你一个由小写字母组成的字符串 s ，和一个整数 k 。如果满足下述条件，则可以将字符串 t 视作是 理想字符串 ：

  • t 是字符串 s 的一个子序列。
  • t 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 k。
    返回 最长 理想字符串的长度。

字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。

注意：字母表顺序不会循环。例如，'a' 和 'z' 在字母表中位次的绝对差值是 25 ，而不是 1 。

示例 1：

1
2
3
4
输入：s = "acfgbd", k = 2
输出：4
解释：最长理想字符串是 "acbd" 。该字符串长度为 4 ，所以返回 4 。
注意 "acfgbd" 不是理想字符串，因为 'c' 和 'f' 的字母表位次差值为 3 。

示例 2：
1
2
3
输入：s = "abcd", k = 3
输出：4
解释：最长理想字符串是 "abcd" ，该字符串长度为 4 ，所以返回 4 。

提示：

  • 1 <= s.length <= 105
  • 0 <= k <= 25
  • s 由小写英文字母组成

地址

https://leetcode.cn/problems/longest-ideal-subsequence

题意

动态规划

思路

  1. 感觉只能算是中等题目吧，设 $dp[i][j]$ 表示前 $i$ 个字母中且以字母 $j$ 为结尾最长理想字符串的长度，此时我们可以知道如下递推公式:且满足 $|j-k| \le k$ 满足即可。非常简单的动态规划。
  2. 复杂度分析：
  • 时间复杂度：$O(n |\Sigma|)$，$n$ 表示字符串的长度，$|\Sigma|$ 表示字符集，在这里 $|\Sigma| = 26$。
  • 空间复杂度：$O(n |\Sigma|)$，$n$ 表示字符串的长度，$|\Sigma|$ 表示字符集，在这里 $|\Sigma| = 26$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestIdealString(string s, int k) {
        int n = s.size();
        int ans = 0;
        vector<vector<int>> dp(n + 1, vector<int>(26));
        for (int i = 1; i <= n; i++) {
            int x = s[i - 1] - 'a';
            dp[i] = dp[i-1];
            for (int j = 0; j < 26; j++) {
                int d = abs(x - j);
                if (d <= k) {
                    dp[i][x] = max(dp[i][x], dp[i - 1][j] + 1);
                }
            }
        }
        return *max_element(dp[n].begin(), dp[n].end());
    }
};

#

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

力扣周赛
#力扣周赛
leetcode conttest 305
http://example.com/2022/11/01/力扣周赛题解/23/
Author
Mike Meng
Posted on
November 1, 2022
Updated on
September 8, 2026
Licensed under