LeetCode 第24场夜喵双周赛题解

题目来源LeetCode

第1题来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-value-to-get-positive-step-by-step-sum

第2题来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k

第3题来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n

第4题来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-the-array/

第1题：逐步求和得到正数的最小值

给你一个整数数组 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

题目分析：

也就是求一个最小的数，使得每次前n个数字相加，都是大于0的
可以这样思考，选取数据，然后循环计算，当不满足条件的时候，自增，使其满足条件之后继续执行。此方法需要判断和数据自增多次。
另外一个方法，通样的方法，但是只判断一次，直接增加 - sum + 1 即可

代码演示

public class _2020_04_18_01_MinPositiveNumber {

    public static void main(String[] args) {
        int[] nums = {-3, 2, -3, 4, 2};
//        int[] nums = {1, -2, -3};
        int res = minStartValue(nums);
        System.out.println(res);
        System.out.println(minStartValue2(nums));

    }

    public static int minStartValue2(int[] nums) {
        int result = 1;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum < 0) {
                result = Math.max(result, -sum + 1);
            }
        }
        return result;
    }

    public static int minStartValue(int[] nums) {
        int result = 0;
        int temp = 0;
        for (int i = 0; i < nums.length; i++) {
            temp += nums[i];
            while (temp <= 0) {
                result++;
                temp++;
            }
        }
        if (result == 0) {
            return 1;
        }
        return result;
    }
}

第2题：和为 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

题目分析：

因为给了提示 1 <= k <= 10^9 所以，斐波那契数列的具体数组大小即可求出
因为求最小的几个可以完成，所以在求出斐波那契数列之后，在进行从大到小遍历即可

代码演示

public class _2020_04_18_02_Fibonacci {
    public static void main(String[] args) {
        System.out.println(findMinFibonacciNumbers(645157245));
    }

    public static int findMinFibonacciNumbers(int k) {
        int[] fibonacci = fibonacci();
        int count = 0;
        for (int index = fibonacci.length - 1; index >= 0; index--) {
            if (k >= fibonacci[index]) {
                k -= fibonacci[index];
                count++;
                if (k==0){
                    break;
                }
            }
        }
        return count;
    }

    public static int[] fibonacci() {
        int[] result = new int[45];
        result[0] = result[1] = 1;
        for (int i = 2; i < result.length; ++i) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result;
    }
}

第3题：长度为 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

题目分析

回溯过程中，每次添加一个字符(a, b, c)，并使得添加的字符与前一个字符不同，当添加的字符数为n时，则找到长度为n的开心字符串。
对回溯过程得到的所有的开心字符串进行排序，返回第k个开心字符串。

作者：mufanlee
链接：https://leetcode-cn.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/solution/hui-su-by-mufanlee/
来源：力扣（LeetCode）

代码演示

public class _2020_04_18_03_LastHappyString {
    public static void main(String[] args) {
        String happyString = getHappyString(3, 9);
        System.out.println(happyString);
    }

    public static String getHappyString(int n, int k) {
        List<String> res = new ArrayList<>();
        backtracking("a", n - 1, res);
        backtracking("b", n - 1, res);
        backtracking("c", n - 1, res);

        if (res.size() < k) {
            return "";
        }

        Collections.sort(res);
        return res.get(k - 1);
    }

    public static void backtracking(String s, int k, List<String> res) {
        if (k < 0 || (s.length() > 1 && s.charAt(s.length() - 1) == s.charAt(s.length() - 2))) {
            return;
        }

        if (k == 0) {
            res.add(s);
            return;
        }

        backtracking(s + 'a', k - 1, res);
        backtracking(s + 'b', k - 1, res);
        backtracking(s + 'c', k - 1, res);
    }

}

第4题：恢复数组

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [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[i]表示前i 位组成若干个合法数字的方案数动态转移方程dp[i] +=dp[j-1],其中s[j:i]表明从j到i-1是一个合法字符串，即该处数字小于k

代码实现

public class _2020_04_18_04_RestoreTheArray {

    public static void main(String[] args) {
        System.out.println(numberOfArrays("1234567890", 90));
    }

    public static int numberOfArrays(String s, int k) {
        int mod = 1000000007;
        if (s.length() < 1) {
            return 1;
        }
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            //i-j小于10的情况是因为k的最大值为10^9 所以超过10位的数字不用考虑
            for (int j = i; j > 0 && i - j < 10; j--) {
                String str = s.substring(j - 1, i);
                //前导0的情况直接跳过
                if (str.charAt(0) == '0'){
                    continue;
                }
                long num = Long.parseLong(str);
                //如果j出的数字比k大了，那说明再往前添加字符，一定只会更大，直接break
                if (num > k){
                    break;
                }
                dp[i] = (dp[i] + dp[j - 1]) % mod;
            }
        }
        return dp[s.length()];
    }
}

LeetCode 第24场夜喵双周赛 题解

题目来源LeetCode

第1题：逐步求和得到正数的最小值

示例 1：

示例 2：

示例 3

提示：

题目分析：

第2题：和为 K 的最少斐波那契数字数目

示例 1：

示例 2：

示例 3：

提示：

题目分析：

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

示例 1：

示例 2：

示例 3：

示例 4：

示例 5：

提示：

题目分析

第4题：恢复数组

示例 1：

示例 2：

示例 3：

示例 4：

示例 5：

提示：

题目解析

LeetCode 第24场夜喵双周赛题解