LeetCode 第 24 场双周赛（326/1898，前17.2%）

示例 1：
输入：nums = [-3,2,-3,4,2]
输出：5
解释：如果你选择 startValue = 4，在第三次累加时，和小于 1 。
                累加求和
                startValue = 4 | startValue = 5 | nums
                  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
                  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
                  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
                  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
                  (4 +2 ) = 6  | (5 +2 ) = 7    |   2
                  
示例 2：
输入：nums = [1,2]
输出：1
解释：最小的 startValue 需要是正数。

示例 3：
输入：nums = [1,-2,-3]
输出：5
 
提示：
1 <= nums.length <= 100
-100 <= nums[i] <= 100

class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int val=1, i, sum=0;
        for(i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            if(sum >= 1)
                continue;
            else
                val = max(val, 1-sum);
        }
        return val;
    }
};

斐波那契数字定义为：
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
数据保证对于给定的 k ，一定能找到可行解。

示例 1：
输入：k = 7
输出：2 
解释：斐波那契数字为：1，1，2，3，5，8，13，……
对于 k = 7 ，我们可以得到 2 + 5 = 7 。

示例 2：
输入：k = 10
输出：2 
解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。

示例 3：
输入：k = 19
输出：3 
解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。
 
提示：
1 <= k <= 10^9

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        set<int> s;
        s.insert(1);
        int a = 1, b =1, fn=1, end = 1000000000;
        while(fn <= end)
        {
            fn = a+b;
            a = b;
            b = fn;
            s.insert(fn);
        }
        int count = 0;
        while(k!=0)
        {
            auto it = s.upper_bound(k);
            k -= *(--it);
            count++;
        }
        return count;
    }
};

示例 1：
输入：n = 1, k = 3
输出："c"
解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。
按照字典序排序后第三个字符串为 "c" 。

示例 2：
输入：n = 1, k = 4
输出：""
解释：长度为 1 的开心字符串只有 3 个。

示例 3：
输入：n = 3, k = 9
输出："cab"
解释：长度为 3 的开心字符串总共有 12 个 
["aba", "abc", "aca", "acb", "bab", "bac", 
"bca", "bcb", "cab", "cac", "cba", "cbc"] 。
第 9 个字符串为 "cab"

示例 4：
输入：n = 2, k = 7
输出：""

示例 5：
输入：n = 10, k = 100
输出："abacbabacb"
 
提示：
1 <= n <= 10
1 <= k <= 100

class Solution {
    char ch[3] = {'a','b','c'};
    vector<string> ans;
    string s;
    int N, K;
public:
    string getHappyString(int n, int k) {
        N = n;
        K = k;
        dfs(s);
        if(k > ans.size())
            return "";
        return ans[k-1];
    }

    void dfs(string s)
    {
        if(ans.size()>=K)
            return;
        if(s.size()==N)
        {
            ans.push_back(s);
            return;
        }
        for(int i = 0; i < 3; ++i)
        {
            if(s.empty() || s.back()!=ch[i])
                dfs(s+ch[i]);
        }
    }
};

示例 1：
输入：s = "1000", k = 10000
输出：1
解释：唯一一种可能的数组方案是 [1000]

示例 2：
输入：s = "1000", k = 10
输出：0
解释：不存在任何数组方案满足所有整数都 >= 1 且 <= 10 同时输出结果为 s 。

示例 3：
输入：s = "1317", k = 2000
输出：8
解释：可行的数组方案为 [1317]，[131,7]，[13,17]，[1,317]，
[13,1,7]，[1,31,7]，[1,3,17]，[1,3,1,7]

示例 4：
输入：s = "2020", k = 30
输出：1
解释：唯一可能的数组方案是 [20,20] 。 [2020] 不是可行的数组方案，原因是 2020 > 30 。 
[2,020] 也不是可行的数组方案，因为 020 含有前导 0 。

示例 5：
输入：s = "1234567890", k = 90
输出：34
 
提示：
1 <= s.length <= 10^5.
s 只包含数字且不包含前导 0 。
1 <= k <= 10^9.