【力扣周赛第305场】全题题解

这次周赛四题都出的比较简单，分为一道构建与遍历图和三道线性动规的题。 题目链接

1. 算术三元组的数目

给你一个下标从 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 严格 递增

思路

用的线性dp来解： 如果在数组中num, num - diff, num - 2diff三个数同时存在，那这三个数就可以组成一个三元组。查找的思路是： 因为数据范围很小，可以先把所有数计数排序一下放入arr，如果arr[i]大于0，说明 i 存在，然后如果arr[i]、arr[i-diff]、arr[i-2*diff]三个数都存在，那这三个数就能组一个三元组，那我们就从arr[diff*2]开始向后遍历查找即可。

代码

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        int arr[201] = {0};
        int ret = 0;
        for(int i = 0;i < nums.size();i++){
            arr[nums[i]]++;
        }
        for(int i = diff*2;i <= 200;i++){
            if(arr[i] && arr[i - diff] && arr[i-diff-diff])ret++;
        }

        return ret;
    }
};

时间复杂度:O(n+k),k表示数值范围 空间复杂度:O(k)

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

现有一棵由 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 中的所有值 互不相同

思路

首先用edges构建一个邻接表，然后因为受限结点不能访问，所以构建邻接表时如果边有一端是受限结点，则不连该边。 最后就是根据邻接表从0结点开始访问所有结点并统计个数即可。

代码

class Solution {
    vector<int> es[100005];     //边表
    int seen[100005] = {0};     //结点是否访问过
public:
    int getMaxn(int root){
        seen[root] = 1;
        int maxn = 1;
        for(int &e : es[root]){
            if(seen[e])continue;
            maxn += getMaxn(e);
        }
        return maxn;
    }

    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        set<int> res;       //给restricted换成set容器存储
        for(int &re : restricted)res.insert(re);
        int a, b, maxn = 0;
        for(int i = 0;i < edges.size();i++){
            a = edges[i][0], b = edges[i][1];
            if(res.find(b) == res.end() && res.find(a) == res.end()){
                es[a].push_back(b);
                es[b].push_back(a);
            }
        }
        maxn = getMaxn(0);

        return maxn;
    }

};

时间复杂度:O(n+e),n表示结点数，e表示边数 空间复杂度:O(n+e)

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

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

思路

用线性动规来解： 从整体上看可能不好判断nums是否能被有效划分，但我们可以把这个大问题拆解成小问题，设arr是nums前i个数组成的子数组,如果arr末尾的两个或三个数字能组成有效划分，且arr数组减去末尾能有效划分的数后的子数组arr[0~i-3]也能有效划分,说明arr就能有效划分。 而arr[0~i-3]也是用同样的方式继续缩小问题规模，直到arr数的个数为nums的前两个数，直接判断这两个数是否相同，就知道arr[0~2]是否可以有效划分的了。 看代码可能更好理解：

代码

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        bool dp[100005] = {false};      //前i个数的子数组是否能划分
        dp[0] = true;
        if(nums[0] == nums[1])dp[2] = true;     //如果前两个数相同，说明子数组arr[0,1]能被有效划分
        for(int i = 3;i <= nums.size();i++){
            int ni = i - 1;
            if(nums[ni] == nums[ni-1] && dp[i-2])dp[i] = true;
            else if(nums[ni] == nums[ni-1] && nums[ni] == nums[ni-2] && dp[i-3])dp[i] = true;
            else if(nums[ni] - 1 == nums[ni-1] && nums[ni-1] - 1 == nums[ni-2] && dp[i-3])dp[i] = true;
        }

        return dp[nums.size()];
    }
};

时间复杂度:O(n) 空间复杂度:O(n)

4. 最长理想子序列

给你一个由小写字母组成的字符串 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 由小写英文字母组成

思路

也是线性dp来解： 设s前i个字符组成的子串ss中，最后一个字母是w，那么以w结尾的理想子串t，前一个字母只能取w-k~w+k之间的字母，那么t的最长长度就是前面以w-k~w+k这些字母为结尾的理想子串中最长的一条再+1（+w）。 最长的理想子串就是最后遍历以a-z结尾的理想子串长度中最长的一个。

代码

class Solution {
public:
    int longestIdealString(string s, int k) {
        int dp[200] = {0};       //以字母结尾的最长长度,也可以开26大小，我开200是为了减少i-'a'的计算
        int maxn = 0;
        for(int i = 0;i < s.length();i++){
            int tdp = 1;
            for(int ki = s[i] - k < 'a' ? 'a' : s[i] - k;ki <= s[i] + k;ki++)
                tdp = max(tdp, dp[ki] + 1);
            dp[s[i]] = tdp;
        }
        for(int i = 'a';i < 'a'+26;i++)maxn = max(maxn, dp[i]);

        return maxn;
    }
};

*时间复杂度：O(nk) 空间复杂度：O(e)**,e表示字符集数量，这里是26