6136. 算术三元组的数目

class Solution {
public:
    int arithmeticTriplets(vector<int>& a, int f) {
        int n = a.size();
        int ret=0;
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                for(int k = j+1;k<n;++k){
                    if( a[j]-a[i]==f && a[k]-a[j] ==f ){
                        ++ret;      
                    }
                }
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

class Solution {
public:
    int reachableNodes(int n, vector<vector<int>>& e, vector<int>& r) {
        vector<vector<int>> ne(n+1);
        unordered_map<int,int>m;
        
        for(int x:r){
            m[ x ] = 1;
        }
        
        for( auto&arr:e ){
            if( m[arr[0]]==0 && m[ arr[1] ]==0 ){
                ne[ arr[0] ].push_back(arr[1]);
                ne[ arr[1] ].push_back(arr[0]);
            }
        }
            
        int ret = 0;
        queue<int> q;
        q.push(0);
        unordered_map<int,int> v;
        while( !q.empty() ){
            int tp =q.front();
            q.pop();
            v[tp] = true;
            ++ret;
            for(int n:ne[tp]){
                if( v[n] == 0 ){
                    v[n]=1;
                    q.push(n);
                }
            }
        }
        return ret;
        
    }
};
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
33
34
35
36
37

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

class Solution {
public:
    bool validPartition(vector<int>& a) {
        
        int n = a.size();
        auto dp =  vector<bool>(n+1,false);
        dp[0] = true;
        if( a[1] == a[0] ){
            dp[2] = true;
        }
        
        for(int i=3;i<=n;++i){
            
            if(a[i-1] == a[i-2]){
                dp[i] = dp[i]||dp[i-2];
            }
            if( a[i-1] == a[i-2] && a[i-1] == a[i-3]){
                dp[i] = dp[i]||dp[i-3];
            }
            if( a[i-1] == a[i-2]+1 && a[i-2] == a[i-3]+1 ){
                dp[i] = dp[i]||dp[i-3];
            }
        }
        return dp[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

6138. 最长理想子序列

~思路
https://leetcode.cn/problems/longest-ideal-subsequence/solution/by-lfool-afr2/

class Solution {
public:
    int longestIdealString(string s, int k) {
        int n = s.size();
        vector<int> dp(26,0);
        for(int i=0;i<n;++i){
            int cur = s[i] - 'a';

            for(int j=1;j<=k;++j){

                if( cur-j>=0){
                    dp[cur] = std::max<int>(dp[cur],dp[cur-j]);
                }
                if( cur+j < 26){
                    dp[cur] = std::max<int>(dp[cur],dp[cur+j]);
                }
                  
            }
            ++dp[cur];
        }
        return *max_element(dp.begin(),dp.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23