目录
零、写在前面
一、主要知识点
1.找到递推式
二、课后习题
509. 斐波那契数
1137. 第 N 个泰波那契数(看上面那题)
119. 杨辉三角 II
70. 爬楼梯
剑指 Offer 62. 圆圈中最后剩下的数字
剑指 Offer II 092. 翻转字符
写在最后
零、写在前面
今天是打卡的第28天，今天好累，不过好多题都是之前做过的，下午没课我能睡一小会了，老规矩，知识点在：
《算法零基础100讲》(第28讲) 递推问题https://blog.csdn.net/WhereIsHeroFrom/article/details/121367086
https://blog.csdn.net/WhereIsHeroFrom/article/details/121367086
一、主要知识点
1.找到递推式
其实参考代码没啥用，主要是要找到递推式，才能更好的解题。学好数学-.-
long long getACM(int n) { long long g[40]; g[1] = 3, g[2] = 8; for(i = 3; i <= n; i++) { g[i] = 2 * (g[i-1] + g[i-2]); } return g[n]; }
二、课后习题
509. 斐波那契数
509. 斐波那契数
https://leetcode-cn.com/problems/fibonacci-number/
题目描述
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
思路
这个我写过，但是我找不到了，，，其实就是利用空间来更新数组 得到最终的结果就好了。
int fib(int n){ if(!n) return 0; int F[n + 1];//创建数组保存计算过的数字 F[0] = 0;//初始值 F[1] = 1; for(int i =2;i <= n;i++){ F[i] = F[i-1] + F[i-2]; } return F[n]; }
1137. 第 N 个泰波那契数(看上面那题)
1137. 第 N 个泰波那契数
https://leetcode-cn.com/problems/n-th-tribonacci-number/
119. 杨辉三角 II
119. 杨辉三角 II
https://leetcode-cn.com/problems/pascals-triangle-ii/
题目描述
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
思路
按照规则计算就好了，但是注意到F[n][i]= F[n-1][i-1]+F[n-1][i]
可以考虑一个问题就是节约空间的话 从后往前更新就好了？
我就记得我写过，在这里，，，之前写的实在排版脑子疼。。。凑合看 有时间我翻修一下
[题解]《算法零基础100讲》(第4讲) 组合数(c语言描述)https://bbs.csdn.net/topics/602771428
70. 爬楼梯
70. 爬楼梯
https://leetcode-cn.com/problems/climbing-stairs/
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
思路
很容易想到 F[n] = F[n-1]+F[n-2]，也就是走到第n阶有两种方式 一种是从n-1走一阶到，另外一种从n-2阶梯走2台阶。直接写代码就完事了。
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];//返回最大值 }
剑指 Offer 62. 圆圈中最后剩下的数字
剑指 Offer 62. 圆圈中最后剩下的数字
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
题目描述
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
思路
如果删掉一个元素是不是就只剩n-1一个元素了？
然后根据递归就好了 其实就是F(n,m)=(m%n+F(n-1,m))%n = (m+F(n-1,m)%10;
做了个小视频，大家直接看就好了。官方的题解给动画是错的！
int lastRemaining(int n, int m){ int x = 0; for (int i = 2; i != n + 1; ++i) { x = (m + x) % i; //根据递推式进行计算就好了 } return x; }
剑指 Offer II 092. 翻转字符
剑指 Offer II 092. 翻转字符
https://leetcode-cn.com/problems/cyJERH/
题目描述
如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。
我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。
思路
遍历每个跳变点看在哪个跳变点的时候反转次数最少。
一开始计数count为所有的0的个数。表示在最开始就反转。
往后移动一个位置的时候 如果这个位置是0 那么翻转的次数减少一次 如果是1增加一次
int minFlipsMonoIncr(char * s){ if(strlen(s) == 1) return 0; int count = 0,min = 0; for(int i = 0;s[i];i++) if(s[i] == '0') count++;//统计在最前面反转的次数 min = count; //min初始值 for(int i = 0;s[i];i++){ if(s[i] == '0') count--; else count++; //更新count min = min>count?count:min;//更新min } return min; }
写在最后
挺好，很多之前的东西不够精致，得慢慢的改一改，回头看看之前真的写的好垃圾。。
