70. 爬楼梯
70. 爬楼梯
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
思路
这和数组有什么关系呢？
其实是一道动态规划问题，但是也不难。理解一下
到达第i个台阶是不是有两种方式？
一种是从第i－2阶蹦上来。
一种是从第i阶蹦上来
这就是传说中的状态转移。我们初始化第一阶和第二阶方法，其他的按照上面说的生成就好了。
int climbStairs(int n){ if(!n) return 0; else if(n == 1) return 1; else if(n == 2) return 2;//直接返回 int ans[n]; ans[0] = 1;//初始化为第一阶的方法数 ans[1] = 2;//初始化为第二阶的方法数 for(int i = 2;i<n;i++) ans[i] = ans[i-1]+ans[i-2];//从前到后生成 return ans[n-1];//返回第n阶的方法数 }
509. 斐波那契数
509. 斐波那契数
题目描述
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你n，请计算F(n)。
思路
这个昨天写过，思路确实是用到数组保存求过的值。然后从前往后求就好啦0.0
int Fib[31]; int fib(int n){ Fib[0] = 0; Fib[1] = 1; for(int i = 2;i <= n;i++) Fib[i] = Fib[i-1] + Fib[i-2]; return Fib[n]; }
1137. 第 N 个泰波那契数
1137. 第 N 个泰波那契数
题目描述
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
思路
和上面的思路非常类似，直接看代码吧0.0
int a[38]; int tribonacci(int n){ a[0] = 0;a[1] = 1;a[2] = 1; for(int i =3;i <= n;i++ ) a[i] = a[i-1] + a[i-2] + a[i-3]; return a[n]; }
2006. 差的绝对值为 K 的数对数目
2006. 差的绝对值为 K 的数对数目
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。
|x| 的值定义为：
如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为 -x 。
思路
因为只要求数量，不要求具体的哪个数，所以可以先排序
主要的思路
从小到大排序
利用快慢指针来寻找满足条件的两个值。
找到后ans+=对应的成立数量。
注释：high-a是high满足条件的值。temp是满足上一次算的满足条件的值，如果这次low的值和上次的一样，直接加就好了。
int a[38]; int tribonacci(int n){ a[0] = 0;a[1] = 1;a[2] = 1; for(int i =3;i <= n;i++ ) a[i] = a[i-1] + a[i-2] + a[i-3]; return a[n]; }int cmp(int *a,int *b){return *a > *b;} int countKDifference(int* nums, int numsSize, int k){ int ans = 0,temp = 0; qsort(nums,numsSize,sizeof(int),cmp); int low = 0,high = 0; while(high < numsSize || (low && low <numsSize && nums[low] == nums[low - 1])){ while(high < numsSize && nums[high] - nums[low] < k ) high++; int a = high;//第一个可能成立的点 while(high < numsSize && nums[high] - nums[low] == k) high++;//第一个不成立的点 if(low && nums[low] == nums[low - 1]) ans+=temp;//与上次的low相同直接加就好了 else ans+=high - a,temp = high - a; low ++; } return ans; }
LCP 01. 猜数字
LCP 01. 猜数字
题目描述
小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？
输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。
思路
这意思就是数组1和数组2对应元素相等就统计一次呗？
int game(int* guess, int guessSize, int* answer, int answerSize){ int ans = 0; for(int i = 0;i < guessSize;i++) if(guess[i] == answer[i]) ans++; return ans; }
LCP 06. 拿硬币
LCP 06. 拿硬币
题目描述
桌上有n堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数
思路
看起来花里胡哨，翻译一下就是每一个数如果是偶数就/2，奇数就+1/2最终和是多少？这不是就简单了对不对？
int minCount(int* coins, int coinsSize){ int ans = 0; for(int i = 0;i < coinsSize;i++) ans += coins[i] & 1 ? ((coins[i]+1)/2) : coins[i]/2; return ans; }
