0%

leetcode 第24场双周赛

哎 每次都只能做出来前前前前面三道,左后一道永远卡住,永远排名几百

upload successful

思路:签到题暴力即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int minStartValue(vector<int>& nums) {
int n = nums.size();
for(int i=1;i<10000;i++){
int sum = i;
bool flag=1;
for(int j=0;j<n;j++){
sum+=nums[j];
if(sum<1){
flag=0;
break;
}
}
if(flag)return i;
}
return 0;
}
};

upload successful

思路:看到题的第一反应就是完全背包模型,但是k非常大,抱着侥幸心理交了一发,果然超时了,后面想到其实可以用贪心的思路解,每次用不超过k的斐波那契数去凑k,然后k减去这个数,一直持续到k为0即可。

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 {
public:
int findMinFibonacciNumbers(int k) {
vector<int>num(46);
int res=0;
num[1]=1;
num[0]=1;
for(int i=2;i<46;i++){
num[i]=num[i-1]+num[i-2];
}
while(k){
res++;
int l = 0,r=45;
while(l<r){
int mid = (l + r + 1) >> 1;
if(num[mid]<=k)l = mid;
else r = mid-1;
}
k-=num[r];
}
return res;
}
};

upload successful

思路:看到题第一反应就是找规律,先是个数,长度为1的开心串有3个,长度为2的开心串有6个,长度为3的开心串有12个,所以显然长度为k的开心串个数是长度为k-1的开心串的个数的两倍。然后题目要求按字典序找到长度为n的第k个开心串,显然是递推的过程,长度为1时,有 a, b, c三种,长度为2时是在长度为1的基础上增加的,对于a来说可以加两个字母 b,c,对b来说可以加两个字母 a,c,对c来说可以加a,b所以长度为2时有6种按字典序分别为
ab,ac,ba,bc,ca,cb,长度为3时,是在长度为2的基础上加的,构造过程相同,只需要判断上一个长度(当前长度为3时上个长度为2)的字符串的最后一位是什么就能判断要在上个长度字符串的后面加什么字符构造长度加1的开心串。要注意无解的情况

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
class Solution {
public:
string getHappyString(int n, int k) {
vector<int>dp(11),sum(11);
dp[1]=3;
vector<string>res;
for(int i=2;i<=10;i++)dp[i] = dp[i-1]*2;//记录长度为i的开心串个数
for(int i=1;i<11;i++)sum[i] = sum[i-1] + dp[i];
if(k>dp[n])return "";
res.push_back("a");
res.push_back("b");
res.push_back("c");
int cnt=0;
for(int i=2;i<12;i++){
while(cnt<sum[i-1]){
if(res[cnt][i-2] == 'a'){
res.push_back(res[cnt] + 'b');
res.push_back(res[cnt] + 'c');
}else if(res[cnt][i-2] == 'b'){
res.push_back(res[cnt] + 'a');
res.push_back(res[cnt] + 'c');
}else{
res.push_back(res[cnt] + 'a');
res.push_back(res[cnt] + 'b');
}
cnt++;
}
}
return res[sum[n-1]+k-1];
}
};