讨论/题目交流/🐱 第 24 场夜喵双周赛/
🐱 第 24 场夜喵双周赛
展开讨论
力扣 (LeetCode)发起于 2020-04-18
最近编辑于 2020-04-18

占坑。

估计打了下午的比赛感觉晚上的简单好多了。

T1. 逐步求和得到正数的最小值
按照题意扫一遍找到所有前缀和的最小值 vv. 然后ans=max(1,1v)ans = max(1, 1 - v).

T2. 和为 K 的最少斐波那契数字数目
因为fibonacci数列增长的很快, 我们直接将小于1e9的所有项列出来就行。 然后贪心的从大往小减就行。

至于为什么这么做是对的。

因为fib数列中, 2an=an+1+an22a_n = a_{n+1} + a_{n-2}. 因此, 先取大的一定不会让小的取2次以上更优。

T3.长度为 n 的开心字符串中字典序第 k 小的字符串
因为n非常小, 直接生成出所有的“开心字符串”就行, 最后排序取字典序第k个即可。
这道题n最大为10, 可以求出最多有 3 * 2^9 = 1536个字符串, 完全可以暴力求解。

时间复杂度 O(n3n)O(n3^n)
空间复杂度 O(3n)O(3^n)

T4. 恢复数组
显然是一个很简单的dp

设f(i)为前i位可能存在的方案数, 我们有:
f(i)=j=0i1f(j)s[j...i1]<=kf(i) = \sum_{j = 0}^{i - 1} {f(j) | s[j...i-1] <= k}

因为这里k最多为1e9, 所以我们只需要搜前面9位就可以了。

时间复杂度 O(nlogk)O(nlogk)
空间复杂度 O(n)O(n)

1
展开全部 32 讨论