苏州网站建设制作,查看网站服务器信息,站点和网页的关系,区域网站设计文章目录1. 比赛结果2. 题目1. LeetCode 5372. 逐步求和得到正数的最小值 easy2. LeetCode 5373. 和为 K 的最少斐波那契数字数目 medium3. LeetCode 5374. 长度为 n 的开心字符串中字典序第 k 小的字符串 medium4. LeetCode 5375. 恢复数组 hard1. 比赛结果
做出来了 1、2、3…
文章目录1. 比赛结果2. 题目1. LeetCode 5372. 逐步求和得到正数的最小值 easy2. LeetCode 5373. 和为 K 的最少斐波那契数字数目 medium3. LeetCode 5374. 长度为 n 的开心字符串中字典序第 k 小的字符串 medium4. LeetCode 5375. 恢复数组 hard1. 比赛结果
做出来了 1、2、3 题32分钟做出来3题感觉有点蒙过来。第4题实在没思路继续加油
全国排名326 / 189817.2%全球排名1218 / 772915.8%
2. 题目
1. LeetCode 5372. 逐步求和得到正数的最小值 easy
题目链接 给你一个整数数组 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解答
一直加自己的不够就补取最大的
class Solution {
public:int minStartValue(vectorint nums) {int val1, i, sum0;for(i 0; i nums.size(); i){sum nums[i];if(sum 1)continue;elseval max(val, 1-sum);}return val;}
};2. LeetCode 5373. 和为 K 的最少斐波那契数字数目 medium
题目链接 给你数字 k 请你返回和为 k 的斐波那契数字的最少数目其中每个斐波那契数字都可以被使用多次。
斐波那契数字定义为
F1 1
F2 1
Fn Fn-1 Fn-2 其中 n 2 。
数据保证对于给定的 k 一定能找到可行解。示例 1
输入k 7
输出2
解释斐波那契数字为11235813……
对于 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解题
先生成斐波那契数列插入set贪心在set中找小于k的最大数
class Solution {
public:int findMinFibonacciNumbers(int k) {setint s;s.insert(1);int a 1, b 1, fn1, end 1000000000;while(fn end){fn ab;a b;b fn;s.insert(fn);}int count 0;while(k!0){auto it s.upper_bound(k);k - *(--it);count;}return count;}
};16 ms 8 MB
3. LeetCode 5374. 长度为 n 的开心字符串中字典序第 k 小的字符串 medium
题目链接 一个 「开心字符串」定义为
仅包含小写字母 [‘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解题
dfs搜索即可且是按字典序排列的
class Solution {char ch[3] {a,b,c};vectorstring 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(sch[i]);}}
};20 ms 8 MB
4. LeetCode 5375. 恢复数组 hard
题目链接
某个程序本来应该输出一个整数数组。 但是这个程序忘记输出空格了以致输出了一个数字字符串 我们所知道的信息只有数组中所有整数都在 [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做不出来参考评论区Zakl 的解答
