斐波那契数列
- 利用滚动数组的方法节省空间
class Solution { public: int Fibonacci(int n) { int a[3]; a[0]=1; a[1]=1; for(int i=2;i<n;i++) { a[i%3]=a[(i-1)%3]+a[(i-2)%3]; } return a[(n-1)%3]; } };
跳台阶
- 规律就是上一题的斐波那契数列,这回是用递归的方式写的
class Solution { public: int jumpFloor(int number) { if(number<=0) return 0; else if(number==1) return 1; else if(number==2) return 2; else return jumpFloor(number-1)+jumpFloor(number-2); } };
变态跳台阶
- 一共有n个台阶,第n个台阶必须跳上去,对于剩下的n-1个台阶可以选择跳或不跳,结果为2^(n-1)
class Solution { public: int jumpFloorII(int number) { return pow(2,number-1); } };
矩形覆盖
- 和之前的青蛙跳一摸一样....
class Solution { public: int rectCover(int number) { if(number<=0) return 0; else if(number==1) return 1; else if(number==2) return 2; else return rectCover(number-1)+rectCover(number-2);; } };
二进制中1的个数
-
要了解如何求一个数的补码,对于正数不变,对于负数,符号位不变,按位取反,末尾加1
class Solution { public: int NumberOf1(int n) { int ans=0; if(n>=0) { while(n) { if(n%2==1) ans++; n=n/2; } return ans; } else { int data = -n; int num[32]; memset(num,0,sizeof(num)); int k=0; while(data) { if(data%2==1) num[k]=1; data=data/2; k++; } for(int i=0;i<32;i++) { if(num[i]==1) num[i]=0; else num[i]=1; } num[31]=1; num[0]++; for(int i=0;i<32;i++) { if(num[i]==2) { num[i]=0; num[i+1]++; } } for(int i=0;i<31;i++) { if(num[i]==1) ans++; } return ans+1; } } };
数值的整数次幂
- 我的做法非常简单,没什么可说的
class Solution { public: double Power(double base, int exponent) { double ans=1.0; int flag=0; if(exponent<0) { flag=1; exponent=-exponent; } for(int i=0;i<exponent;i++) { ans=ans*base; } if(flag==1) return 1.0/ans; else return ans; } };