第 24 场双周赛

Posted on | In , | |
Words count in article: 422 | Reading time ≈ 2

5372. 逐步求和得到正数的最小值

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int curmin = INT_MAX;
        int sum = 0;
        for(auto num: nums) {
            sum += num;
            curmin = min(curmin, sum);
        }
        return curmin < 1 ? abs(curmin)+1: 1;
    }
};

5373. 和为 K 的最少斐波那契数字数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<long long> fib = {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170};
    
    int findMinFibonacciNumbers(int k) {
        int c = 0;
        int i = 0;
        for(i=0; i<45; i++) {
            if(fib[i] >= k) break;
        }
        for(; i>=0; ) {
            if(k <= 0) break;
            while(k < fib[i]) i--;
            c++;
            k -= fib[i];
        }
        return c;
    }
};

5374. 长度为 n 的开心字符串中字典序第 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
class Solution {
public:
    vector<string> res;
    void dfs(int n, string cur) {
        if(n == 0) {
            res.push_back(cur);
            return;
        }
        if(cur == "") {
            dfs(n-1, cur+'a');
            dfs(n-1, cur+'b');
            dfs(n-1, cur+'c');
            return;
        }
        int size = cur.size();
        if(cur[size-1] == 'a') {
            dfs(n-1, cur+'b');
            dfs(n-1, cur+'c');
        } else if (cur[size-1] == 'b') {
            dfs(n-1, cur+'a');
            dfs(n-1, cur+'c');
        } else if (cur[size-1] == 'c') {
            dfs(n-1, cur+'a');
            dfs(n-1, cur+'b');
        }
    }
    string getHappyString(int n, int k) {
        dfs(n, "");
        return k > res.size() ? "" : res[k-1];
    }
};

5375. 恢复数组

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:
    int numberOfArrays(string s, int k) {
        int mo = 1000000007;
        int n = s.size();
        vector <int> f(n + 5, 0);
        f[0] = 1;
        for (int i = 0; i < n; i++) {
            f[i + 1] = 0;
            long long now = 0, base = 1;
            for (int j = i; j >= 0 && j >= i - 15; j--) {
                now += base * (s[j] - '0');
                base *= 10;
                if (now > k) {
                    break;
                }
                if (s[j] != '0') {
                    (f[i + 1] += f[j]) %= mo;
                }
            }
        }
        return f[n];
    }
};
Donate? comment?