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：

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

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

题意

哈希表 + 双指针

思路

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

时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
空间复杂度：$O(1)$。

代码

直接遍历

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;
    }
};

双指针解法：

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：

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

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

题意

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

思路

感觉这个题目可以算是一个简单题目，直接BFS即可，非常简单的题目。我们直接从 0 点开始遍历，遇到不可达的点则返回。
复杂度分析：

时间复杂度：时间复杂度为 $O(n)$，$n$ 表示节点的数目。
空间复杂度：$O(n)$，$n$ 表示节点的数目。

代码

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：

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

示例 2：

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

题意

动态规划

思路

感觉就是非常非常常规的简单动态规划就可以搞定，设 $dp[i]$ 表示前 $i$ 个元素是否可以等效划分，则递推公式如下:
$$
dp[i] = dp[i] | dp[i-2] \qquad if (nums[i] = nums[i-1]) \
dp[i] = dp[i] | dp[i-3] \qquad if (nums[i] = nums[i-1], nums[i-1] = nums[i-2]) \
dp[i] = dp[i] | dp[i-2] \qquad if (nums[i] = nums[i-1] + 1, nums[i-1] = nums[i-2] + 1) \
$$
根据以上递推公式，直接进行动态规划求解即可。
复杂度分析：

时间复杂度：时间复杂度为 $O(n)$，其中 $n$ 表示数组的长度。
空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 表示数组的长度。

代码

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：

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

示例 2：

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

提示：

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

地址

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

题意

动态规划

思路

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

时间复杂度：$O(n |\Sigma|)$，$n$ 表示字符串的长度，$|\Sigma|$ 表示字符集，在这里 $|\Sigma| = 26$。
空间复杂度：$O(n |\Sigma|)$，$n$ 表示字符串的长度，$|\Sigma|$ 表示字符集，在这里 $|\Sigma| = 26$。

代码

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());
    }
};

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

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode biweekly contest 85 leetcode biweekly conttest 84 →

扫描二维码，分享此文章