目录

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

给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。
你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums 数组中的值。
请你在确保累加和始终大于等于 1 的前提下，选出一个最小的 正数 作为 startValue 。

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

示例

输入：nums = [-3,2,-3,4,2]
输出：5
解释：如果你选择 startValue = 4，在第三次累加时，和小于 1 。

我的思路

首先题目应该求 最小的”正整数“。
从左到右遍历nums执行累加过程，记录下该过程中累加和所能达到的最小值 tmp。
所求即 1和 tmp 的差值。
这里最初不小心被罚时了，未考虑 tmp 为正的情况。

我的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        tmp = float('inf')
        cur = 0
        for num in nums:
            cur += num
            if tmp > cur:
                tmp = cur
        tmp = min(tmp, 0)
        return 1 - tmp

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

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

  • $F_{1}$ = 1
  • $F_{2}$ = 1
  • $F_{n}$ = $F_{n-1}$ + $F_{n-2}$ ， 其中 n > 2 。 数据保证对于给定的 k ，一定能找到可行解。

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

示例

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

输入：k = 19
输出：3
解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。

我的思路

用DP求斐波那契数列，直到求到第一个比 k 大的斐波那契数 cur。若在此过程中有与 k 相等的斐波那契数，即只用一个斐波那契数即可加到 k ，则直接返回 1 即可。
cur 前的斐波那契数列 dp 可用于累加得 k。
这里涉及 贪心 。用 二分查找 从数列 dp 中找第一个小于等于 k 的数的下标索引，k 减去该数得到残余待累加部分。while循环重复此过程直到残余部分在 dp 中或残余部分为0。

我的代码

 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

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        dp = []
        dp.append(1)
        dp.append(1)
        
        while True:
            cur = dp[-1] + dp[-2]
            if cur == k:
                return 1
            if cur > k:
                break
            dp.append(cur)
        
        def biSearch(target, arr):
            """
            在升序序列arr中找到第一个小于等于target的数的下标
            """
            left, right = 0, len(arr) - 1
            ind = -1
            while left <= right:
                mid = left + (right - left) // 2
                if arr[mid] == target:
                    return mid
                if arr[mid] < target:
                    ind = mid
                    left = mid + 1           
                else:
                    right = mid - 1
            return ind
        
        k -= dp[-1]
        res = 1
        while k > 0:
            try:
                if dp.index(k) >= 0:
                    return res + 1
            except:
                ind = biSearch(k, dp)
                res += 1
                k -= dp[ind]  
        
        return res

长度为 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 个，那么请你返回 空字符串 。

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

示例

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

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

别人的思路

DFS回溯。
先搜索出的字符串 cur 长度满足要求的所有开心字符串。
如果 cur 长度未满足要求则从 字母表[‘a’, ‘b’, ‘c’] 中选。这里要注意有两个判断条件。一个是 cur 长度为0时，直接按字典序加上字母表中的字符进行DFS，另一个是 当前新加字符不能与 cur 的最后一个字符相同。

别人的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def getHappyString(self, n: int, k: int) -> str:

        self.res = [] # 存储开心字符串

        def dfs(cur):
            """
            cur: 当前字符串
            """
            if len(cur) == n:
                self.res.append(cur)
                return
                                
            for ch in ['a', 'b', 'c']:
                if len(cur) == 0:
                    dfs(cur + ch)
                elif ch != cur[-1]:
                    dfs(cur + ch)

        dfs("")
        if k > len(self.res):
            return ""
        return self.res[k - 1]

恢复数组

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

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

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

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

1 <= s.length <= 10^5
s 只包含数字且不包含前导 0
1 <= k <= 10^9.

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

示例

输入：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]

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

别人的思路

自底向上的DP。
dp[i]表示从 s 下标索引为 i 的字符开始到 s 最后一个字符结束的字符串的拆分方案数。 例如求对字符串“1234567890”的子串“7890”，k = 100时，其拆分方案数为dp[6]：

  • 求拆分“7”与“890"的拆分方案数，即为”890“的拆分方案数dp[7]
  • 求拆分”78“与”90“的拆分方案数，即为”90“的拆分方案数dp[8]
  • 求拆分”789“与”0“的拆分方案数，由于789大于k，同时0不能做前导，故dp[9] = 0
  • 最后dp[6] = dp[7] + dp[8] + dp[9] + dp[10]

可以看到转移方程为 dp[i] = $\sum\limits_{j=1}^{n-i}dp[j]$。
其中的约束条件说明：

  • j $\in$ [1, n - i], 因为子串只取到 s 的末尾
  • j <= 10，因为1 <= k <= 10^9，故子串长度不能超过10
  • 子串数字 int(cur) 不能超过 k

至于边界dp[10]为何要取1，暂时还想不到好的解释来说明。

别人的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        n = len(s)
        # 开多一个位置，将末位设为1，避免额外的边界判断
        dp = [0] * (n + 1) 
        dp[-1] = 1
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                # 前导0是不允许的
                dp[i] = 0
                continue
            j = 1
            while i + j <= n and j <= 10:
                cur = s[i:i+j]
                if int(cur) > k:
                    # 若大于k，则再加数必然更大，故跳出while循环
                    break
                # 在运行过程中取模，避免dp中保存过大的数造成较大的时间和空间损失
                dp[i] = (dp[i] + dp[i + j]) % (10**9 + 7)
                j += 1
        return dp[0]

总结

仅AC前两道题，排位956/1898。
还是死在第三题 5374. 长度为 n 的开心字符串中字典序第 k 小的字符串 的DFS回溯和第四题 5375. 恢复数组 的DP。