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

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(n*k)
空间复杂度:O(e),e表示字符集数量,这里是26

最后修改:2022 年 09 月 01 日
如果觉得我的文章对你有用,请随意赞赏