On the shoulders of giants.

biweekly-contest-24

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

给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。

你需要从左到右遍历 nums 数组,并将 startValue 依次累加上 nums 数组中的值。

请你在确保累加和始终大于等于 1 的前提下,选出一个最小的 正数 作为 startValue 。

示例 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
题解

在不选定初始值的情况下,找出前缀和最小的值是多少。

如果该值小于等于 0 ,我们可以让初始值等于该值取反后加一;

如果该值大于等于 1,我们直接让初始值等于 1。

时间复杂度:\(O(n)\)

class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int lim = 1E9, sum = 0;
        for(auto x : nums) {
            sum += x;
            lim = min(lim, sum);
        }
        return lim <= 0 ? -lim + 1 : 1;
    }
};

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

给你数字 k ,请你返回和为 k 的斐波那契数字的最少数目,其中,每个斐波那契数字都可以被使用多次。

斐波那契数字定义为:

  • 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
题解

经典题,我们有结论:不会选取相同的两个数。

我们从最大小于目标值的 Fib 开始,构造出答案。

时间复杂度:\(O(44k)\)

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        int total = 0, x = k;
        while(x) {
            int a = 0, b = 1, c;
            while(b <= x) {
                c = a + b;
                a = b;
                b = c;
            }
            x -= a;
            total++;
        }
        return total;
    }
};

长度为 n 的开心字符串中字典序第 k 小的字符串

一个 「开心字符串」定义为:

  • 仅包含小写字母 ['a', 'b', 'c'].
  • 对所有在 1 到 s.length - 1 之间的 i ,满足 s[i] != s[i + 1] (字符串的下标从 1 开始)。

比方说,字符串 “abc”“ac”,”b” 和 “abcbabcbcb” 都是开心字符串,但是 “aa”“baa” 和 “ababbc” 都不是开心字符串。

给你两个整数 n 和 k ,你需要将长度为 n 的所有开心字符串按字典序排序。

请你返回排序后的第 k 个开心字符串,如果长度为 n 的开心字符串少于 k 个,那么请你返回 空字符串 。

示例 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
题解

回溯搜索出第 k 个合法字符串。

时间复杂度:\(O(3^n)\)

class Solution {
public:
    int total = 0, n, k; 
    bool check(string now) {
        int m = now.length();
        if(m <= 1) return true;
        return now[m - 1] != now[m - 2];
    }
    string search(string now) {
        if(n < now.length() || !check(now)) return "";
        if(now.length() == n) total++;
        if(total == k) return now;
        for(char c = 'a'; c <= 'c'; c++) {
            string ret = search(now + c);
            if(ret != "") return ret;
        }
        return "";
    }
    string getHappyString(int n, int k) {
        this->n = n;
        this->k = k;
        return search("");
    }
};

恢复数组

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串,我们所知道的信息只有:数组中所有整数都在 [1, k] 之间,且数组中的数字都没有前导 0 。

给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。

按照上述程序,请你返回所有可能输出字符串 s 的数组方案数。

由于数组方案数可能会很大,请你返回它对 10^9 + 7 取余 后的结果。

示例 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
题解

动态规划,设 \(dp_{x}\) 为前 x 字符的字符串恢复数组的方案数。

转移,我们可以枚举最后一个数组元素,然后用前面的状态转移。

时间复杂度:\(O(n\log k)\)

const int MOD = 1E9 + 7;
class Solution {
public:
    int numberOfArrays(string s, int k) {
        int n = s.length(), m = log10(k) + 1;
        vector<int> dp(n + 1);
        dp[0] = 1;
        for(int i = 1; i <= n; i++) {
            long long x = s[i - 1] - '0', p = 10;
            if(x && x <= k) dp[i] = dp[i - 1];
            for(int j = i - 1; x <= k && j && (i - j + 1) <= m; j--) {
                if(s[j - 1] != '0') {
                    x = (s[j - 1] - '0') * p + x;
                    if(x && x <= k) dp[i] = (dp[i] + dp[j - 1]) % MOD;
                }
                p *= 10;
            }
        }
        return dp[n];
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注