给你一个数N求最少需要多少步可以变为Fibonacci数
Fibonacci数列是这样定义的：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, …，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。
题目链接–https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=122&&tqId=33668
1，首先复习下，求第n个斐波那契数的方法
方法A—递归的方法
int fib(int n)
{
if (n <= 1)
return 0;
else if (n == 2 || n == 3)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = fib(n);
printf("%d\n", ret);
return 0;
}
方法B—平移法
int main()
{
int n = 0;
scanf("%d", &n);
int a = 0;
int b = 1;
int c = 0;
while (n > 3)
{
c = a + b;
a = b;
b = c;
n--;
}
if (n == 2||n==3)
c++;
printf("%d\n", c);
return 0;
}
显然用递归的方法会超出时间限制，所以用第二种方法----平移法
我只需要在平移的过程中找到a<n<b 然后算出三者中的两者差值最小的数即可
#include<stdio.h>
int main()
{
int n=0;
scanf("%d",&n);
int a=0;
int b=1;
int c=0;
while(1)
{
if(n==b||n==0)
{
printf("%d",0);
break;
}
else if(n>a&&n<b)
{
if(abs(n-a)<abs(n-b))
{
printf("%d\n",abs(n-a));
break;
}
else
{
printf("%d\n",abs(n-b));
break;
}
}
c=a+b;
a=b;
b=c;
}
return 0;
}
题目2-----替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy
题目链接----https://www.nowcoder.com/questionTerminal/4060ac7e3e404ad1a894ef3e17650423
void replaceSpace(char *str,int length)
{
char* ret=str;
int count=0;
while(*ret)
{
if(*ret==' ')
count++;
ret++;
}
int newlength=length+count*2;
int end1=length;
int end2=newlength;
while(end1!=end2)
{
if(str[end1]!=' ')
{
str[end2]=str[end1];
end2--;
end1--;
}
else
{
str[end2]='0';
end2--;
str[end2]='2';
end2--;
str[end2]='%';
end2--;
end1--;
}
}
}
思维:
1先找出数组中有多少个空格，然后增加字符串的长度，空格数*2即可。（不需要增加扩容）
2然后从新长度那里开始填字符，遇到空格填依次填入‘0’，‘2’，‘%’即可。
题目三—错误的集合
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/set-mismatch/
解题思路：
1 先用qsort排序
2然后遍历数组，找到重复的数字填入错误的结合下标0.
3然后再找第二个，肯定是数组前后两个元素中差值大于1，只需要将那个小的数加1填入错误的集合下标1即可.
4但是有一中特殊的情况，万一丢失的数字是n，就要另外考虑了
int cmp_int(const void* e1,const void* e2)
{
return *(int*)e1-*(int*)e2;
}
int* findErrorNums(int* nums, int numsSize, int* returnSize)
{
int* arr=(int*)malloc(8);
*returnSize=2;
qsort(nums,numsSize,sizeof(nums[0]),cmp_int);
int cur=0;
int pre=0;
int i=0;
for(i=0;i<numsSize;i++)
{
cur=nums[i];
if(cur==pre)
{
arr[0]=cur;
}
else if(cur-pre>1)
{
arr[1]=pre+1;
}
pre=cur;
}
if(nums[numsSize-1]!=numsSize)
arr[1]=numsSize;
return arr;
}
|