关于力扣305周周赛的算法代码（动态规划周），解析后续会进行补充_给你一个下标从 0 开始、严格递增 的整数数组 a 和一个正整数 tar 。如果满足下述

力扣305周周赛算法完整代码，有参考各方大佬和自己的想法总结如下，也是第一次参加力扣周赛深有体会，后续可能持续更新力扣竞赛，解析还在编辑后续会 贴出来

6136. 算术三元组的数目

难度简单2收藏分享切换为英文接收动态反馈

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

来自 <力扣>

    //1.hash表写法
 
    int arithmeticTriplets(vector<int>& nums, int diff) {
 
        unordered_set<int> set;
 
        int pre=0,count=1,res=0;
 
        for(auto i:nums){
 
            set.insert(i);
 
        }
 
        for(int i=0;i<nums.size();++i){
 
            count=1;
 
            pre=nums[i];
 
            while(true){
 
                if(set.find(pre+diff)!=set.end()){
 
                    count++;
 
                    pre+=diff;
 
                }
 
                else break;
 
                if(count==3){ 
 
                    res++;
 
                    break;
 
                }
 
            }
 
        }
 
        return res;
 
    }

    //2.三指正

    int arithmeticTriplets(vector<int>& nums,int diff){
 
        int n=nums.size(),res=0;
 
        for(int i=0,j=i+1,k=j+1;i<n;++i){
 
            while(j+1<n&&nums[j]<nums[i]+diff) ++j;
 
            k=max(k,j+1);
 
            while(k<n&&nums[k]-nums[j]<diff) ++k;
 
            if(k<n&&nums[k]-nums[j]==diff&&nums[j]-nums[i]==diff) ++res;
 
        }
 
        return res;
 
    }

 

6139. 受限条件下可到达节点的数目（DFS/BFS/并查集）

来自 <力扣>

    vector<vector<int>> e;
 
    vector<bool> ban;
 
    int res=0;
 
    int reachableNodes(int n,vector<vector<int>>& edges,vector<int>& restricted){
 
        e.resize(n);
 
        ban.resize(n);
 
        for(auto i:edges){
 
            e[i[0]].push_back(i[1]);
 
            e[i[1]].push_back(i[0]);
 
        }
 
        for(auto i:restricted){
 
            ban[i]=true;
 
        }
 
        dfs(0,-1);
 
        return res;
 
    }
 
    void dfs(int cur,int pre){
 
        res++;
 
        for(int i:e[cur]){
 
            if(!ban[i]&&pre!=i){
 
                dfs(i,cur);
 
            }
 
        }
 
    }

6137. 检查数组是否存在有效划分（动态规划）

来自 <力扣>

    bool validPartition(vector<int>& nums) {
 
        vector<bool> dp(nums.size()+1,false);
 
        dp[0]=true;
 
        for(int i=1;i<nums.size();++i){
 
            int temp=nums[i];
 
            if(dp[i-1]&&temp==nums[i-1]) dp[i+1]=true;
 
            if(i>1&&dp[i-2]){
 
                if(nums[i-1]==nums[i-2]&&nums[i-1]==temp) dp[i+1]=true;
 
                if(nums[i-2]+1==nums[i-1]&&nums[i-1]+1==temp) dp[i+1]=true;
 
            }
 
        }
 
        return dp[nums.size()];
 
    }

6138. 最长理想子序列（动态规划）

来自 <力扣>

    int longestIdealString(string s, int k) {
 
        //确定dp数组
 
        vector<int> dp(26);
 
        int res=0;
 
        //遍历条件
 
        for (char c : s) {
 
            int x = c - 'a';
 
            int t = 0;
 
            for (int y = 0; y < 26; y++) if (abs(x - y) <= k) t = max(t, dp[y] + 1);
 
            dp[x] = max(dp[x], t);
 
            res=max(res,dp[x]);
 
        }
 
        return res;
 
    }