第356场周赛

content {:toc}

6900. 统计完全子数组的数目 - 力扣（LeetCode）

给你一个由正整数组成的数组 nums 。

如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：

子数组中不同元素的数目等于整个数组不同元素的数目。

返回数组中 完全子数组 的数目。

子数组 是数组中的一个连续非空序列。
1
2
3
输入：nums = [1,3,1,2,2]
输出：4
解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。

 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


class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        // 子数组问题
        int len = nums.size();
        unordered_map<int, int> mp, rem;
        
        for(auto n: nums){
            rem[n]++;
        }
        
        // auto rem = mp;
        
        int r = 0, l = 0;
        int res = 0;
        
        while(r< len){
            int n = nums[r++];
            mp[n]++;
            
            while(mp.size() == rem.size() && l< r){
                // 在左端点的情况下
                // 枚举右端点
                res += (len - r +1);
                int n = nums[l++];
               mp[n]--;

                if(mp[n] == 0){
                    mp.erase(n);
                }

            }
        }
        return res;        
    }
}

2801. 统计范围内的步进数字数目 - 力扣（LeetCode）

给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的 步进数字 数目。

如果一个整数相邻数位之间差的绝对值都恰好是 1 ，那么这个数字被称为 步进数字 。

请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。

由于答案可能很大，请你将它对 109 + 7 取余后返回。

**注意：**步进数字不能有前导 0 。
1
2
3
输入：low = "1", high = "11"
输出：10
解释：区间 [1,11] 内的步进数字为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 和 10 。总共有 10 个步进数字。所以输出为 10 。

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71


// 这一版代码好一点了, 虽然逻辑还是有点重复
class Solution {
    bool isper(string s){
        int len = s.size();
        for(int i =1; i<len; ++i){
            if(abs(s[i] - s[i-1] ) != 1){
                return false;
            }
            
        }
        return true;
    }
public:
    int countSteppingNumbers(string low, string high) {
        // 一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。
        // s.len <= 100
        int k = 1e9+7;
        
        // cur是 第几位数字, j 是 
        // limit 是该位置受不受限制
        unordered_map<int, int> mp;
        function<int (int, int, bool, string &)> dfs = [&](int cur, int lastnum, bool islimit,   string &s)-> int{
            // lastnum == -1 时代表着没有数字
            if(cur == s.size() ){
                return 1;
            }
            // cout<< "cur="<< cur<< "\tlastnum = "<< lastnum<< "\tislimit"<< islimit<< '\n'<< s<< '\n';
            int res = 0;

            // 都是前导零
            if(lastnum <0){
                res += dfs(cur+1, -1, false, s);
                res %= k;

                int up = islimit? s[cur] - '0': 9 ;
                for(int i = 1; i<= up; i++){
                    res += dfs(cur+1, i, islimit && i ==up , s );
                    res %= k;
                }
                
            }

            else{
                int flag = 1000 * lastnum + cur;
                if(!islimit && mp.count(flag)){
                    return mp[flag];
                }
                int up = islimit? s[cur] - '0': 9 ;
                for(int i  = lastnum <0? 1: 0; i<= up; ++i){
                    if(abs(i - lastnum) == 1){
                        res += dfs(cur+1, i, islimit&& i == up, s);
                        res %= k;
                    }
                }
                if(!islimit){
                    mp[flag] = res;
                }

            }
            



            return res;
        };
        int max = dfs(0, -1, true, high );
        mp.clear();
        return (max -  dfs(0, -1, true, low ) + isper(low) + k)%k;
        
    }
};

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94


// 极度让人恶心的代码
// 发现逻辑很多重复了

class Solution {
    bool isper(string s){
        int len = s.size();
        for(int i =1; i<len; ++i){
            if(abs(s[i] - s[i-1] ) != 1){
                return false;
            }
            
        }
        return true;
    }
public:
    int countSteppingNumbers(string low, string high) {
        // 一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。
        // s.len <= 100
        int k = 1e9+7;
        
        // cur是 第几位数字, j 是 
        // limit 是该位置受不受限制
        unordered_map<int, int> mp;
        function<int (int, int, bool, string &)> dfs = [&](int cur, int lastnum, bool islimit,   string &s)-> int{
            // lastnum == -1 时代表着没有数字
            if(cur == s.size() ){
                return 1;
            }
            // cout<< "cur="<< cur<< "\tlastnum = "<< lastnum<< "\tislimit"<< islimit<< '\n'<< s<< '\n';
            int res = 0;
            if(islimit ){
                if(lastnum <0){
                    int up = s[cur] - '0';
                    res += dfs(cur+1, -1, false, s);
                    res %= k;
                    for(int i = 1; i<= up; i++){
                        res += dfs(cur+1, i, islimit && i ==up , s );
                        res %= k;
                    }
                    
                }
                
                else{ // lastnum >= 0
                    int up = s[cur] - '0';
                    for(int i  = 0; i<= up; ++i){
                        if(abs(i - lastnum) == 1){
                            res += dfs(cur+1, i, islimit&& i == up, s);
                            res %= k;
                        }
                    }
                }
                
                

                
            }
            
            else{// !islimit
                int flag = cur + 1000 * lastnum;
                if(mp.count(flag)){
                    return mp[flag];
                }


                if(lastnum <0 ){
                    res += dfs(cur+1, -1, false, s);
                    res %=k;
                    for(int i = 1; i<= 9; i++){
                        res += dfs(cur+1, i, false , s );
                        res %= k;
                    }
                }
                
                else{// lastnum >=0 
                    if(lastnum +1 <=9)
                    res += dfs(cur+1, lastnum +1, false, s);
                    res%= k;
                    
                    if(lastnum-1 >=0)
                    res += dfs(cur+1, lastnum -1, false, s);
                    res %= k;
                }

                mp[flag] = res;
            }
            
            return res;
        };
        int max = dfs(0, -1, true, high );
        mp.clear();
        return (max -  dfs(0, -1, true, low ) + isper(low) + k)%k;
        
    }
};

2800. 包含三个字符串的最短字符串 - 力扣（LeetCode）

给你三个字符串 a ，b 和 c ，你的任务是找到长度最短的字符串，且这三个字符串都是它的 子字符串 。

如果有多个这样的字符串，请你返回 字典序最小 的一个。

请你返回满足题目要求的字符串。

注意：

两个长度相同的字符串 a 和 b ，如果在第一个不相同的字符处，a 的字母在字母表中比 b 的字母靠前，那么字符串 a 比字符串 b 字典序小 。

子字符串 是一个字符串中一段连续的字符序列。
1
2
3
输入：a = "abc", b = "bca", c = "aaa"
输出："aaabca"
解释：字符串 "aaabca" 包含所有三个字符串：a = ans[2...4] ，b = ans[3..5] ，c = ans[0..2] 。结果字符串的长度至少为 6 ，且"aaabca" 是字典序最小的一个。

 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
38


class Solution {
    string merge(const string &a, const string &b){
        // return a+ b
        
        // 注意是不等于 -1, 因为可能是 0
        // 不要写  if(a.find(b) )
        if(a.find(b) != -1){
            return a;
        }

        if(b.find(a) != -1){
            return b;
        }

        for(int i = min(a.size(), b.size()); i>-1; --i){
            if(a.substr(a.size( ) -i ) == b.substr(0, i) ){
                // cout<< a+ b.substr(i)<< '\n';
                return a+ b.substr(i);
            }
        }
        return "";
    }
public:
    string minimumString(string a, string b, string c) {
        string arr[] = {a, b, c};

        string ans = "";
        // 枚举 arr 的全排列
        int perm[][3] = {   {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
        for (const auto& p : perm) {
            string s = merge(merge(arr[p[0]], arr[p[1]]), arr[p[2]]);
            if (ans.empty() || s.length() < ans.length() || (s.length() == ans.length() && s < ans)) {
                ans = s;
            }
        }
        return ans;
    }
};