第 183 场周赛

Posted on | In , | |
Words count in article: 525 | Reading time ≈ 3

非递增顺序的最小子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for(auto i: nums) sum += i;
        int tsum = 0;
        vector<int> ret;
        for(int i=nums.size()-1; i>=0; i-- ){
            tsum += nums[i];
            sum -= nums[i];
            ret.push_back(nums[i]);
            if(tsum > sum) break;
        }
        return ret;
    }
};

5377. 将二进制表示减到 1 的步骤数

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
class Solution {
public:
    int numSteps(string s) {
        int ans = 0;
        while (s.size() != 1) {
            string news;
            if (s.back() == '0') {
                news = s.substr(0, s.size() - 1);
                s = news;
            } else {
                bool all1 = true;
                int last = -1;
                for (int i = s.size() - 1; i >= 0; i--) {
                    if (s[i] != '1') {
                        all1 = false;
                        last = i;
                        break;
                    }
                }
                if (all1) {
                    return ans + 1 + s.size();
                } else {
                    s[last] = '1';
                    for (int i = last + 1; i < s.size(); i++) {
                        s[i] = '0';
                    }
                }
            }
            ans++;
        }
        return ans;
    }
};

最长快乐字符串

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
class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        string ans;
        while(true){
            if(a==0&&b==0&&c==0) break;
            if(ans.size()>=2&&ans.back()=='a'&&ans[ans.size()-2]=='a'){
                if(b==0&&c==0) break;
                if(b>=c){
                    ans.push_back('b');
                    b--;
                }else{
                    ans.push_back('c');
                    c--;
                }
                continue;
            }
            
            if(ans.size()>=2&&ans.back()=='b'&&ans[ans.size()-2]=='b'){
                if(a==0&&c==0) break;
                if(a>=c){
                    ans.push_back('a');
                    a--;
                }else{
                    ans.push_back('c');
                    c--;
                }
                continue;
            }
            
            if(ans.size()>=2&&ans.back()=='c'&&ans[ans.size()-2]=='c'){
                if(a==0&&b==0) break;
                if(a>=b){
                    ans.push_back('a');
                    a--;
                }else{
                    ans.push_back('b');
                    b--;
                }
                continue;
            }
            
            if(a>=b&&a>=c){
                ans.push_back('a');
                a--;
                continue;
            }
            
            if(b>=a&&b>=c){
                ans.push_back('b');
                b--;
                continue;
            }
            
            if(c>=a&&c>=b){
                ans.push_back('c');
                c--;
                continue;
            }
        }
        return ans;
    }
};

石子游戏 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string stoneGameIII(vector<int>& a) {
        int n = a.size();
        vector <int> f;
        f.resize(n + 1);
        f[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            f[i] = -1e9;
            int s = 0;
            for (int j = i; j < n && j < i + 3; j++) {
                s += a[j];
                f[i] = max(f[i], s - f[j + 1]);
            }
        }
        if (f[0] > 0) {
            return "Alice";
        } else if (f[0] == 0) {
            return "Tie";
        } else {
            return "Bob";
        }
    }
};s
Donate? comment?