计算题目
9. 斐波那契数列
描述
输出斐波那契数列的第n项（从0开始，第0项为0）。
公式:
f(n) = n, n <= 1
f(n) = f(n-1) + f(n-2), n > 1
思路：采用自底向上方法来保存了先前计算的值，为后面的调用服务。
public int Fibonacci(int n) {
if(n<=1)
return n;
int f1 = 0;
int f2 = 1;
for(int i=2;i<=n;i++) {
f2 = f1+f2;
f1 = f2-f1;
}
return f2;
}
青蛙跳台阶
描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路
基于斐波那契
public int numWays(int n) {
int f1 = 1;
int f2 = 1;
int result = 0;
for(int i=0;i< n;i++){
result = (f1 + f2)%1000000007;
f1 = f2;
f2 = result;
}
return f1;
}
变态青蛙跳
描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路
在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：
| 1 ,(n=0 )
f(n) = | 1 ,(n=1 )
| 2*f(n-1),(n>=2)
public int JumpFloorII(int target) {
if (target <= 0) {
return -1;
} else if (target == 1) {
return 1;
} else {
return 2 * JumpFloorII(target - 1);
}
}
10. 位运算
描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {
count++;
n = (n - 1) & n;
}
return count;
}
11. 整数的N次方
描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路
-
指数为负时，可以先对指数求绝对值，算出次方的结果后再取倒数
-
当底数为0，指数为负时，会出现对0求倒数情况，要特殊处理
-
0的0次方在数学上没有意义，因此无论输出0还是1都是可以接受的
-
在计算次方的时候，除了简单的遍历，我们可以使用递归的思想，如下公式，来减少计算量：
public double Power(double base, int exponent) {
int n = exponent;
if(exponent==0){
// 当指数为0底数为0时，没有意义，返回0或者返回1都可以
return 1;
}else if(exponent < 0){
if(base == 0){
throw new RuntimeException("分母不能为0");
}
n = -exponent;
}
double res = PowerUnsignedExponent(base, n);
return exponent < 0? 1/res: res;
}
public double PowerUnsignedExponent(double base, int n){
if(n == 0)
return 1;
if(n == 1)
return base;
//递归
double res = PowerUnsignedExponent(base, n>>1);
res *= res;
if((n & 0x1) == 1)
res *= base;
return res;
}
32. 整数中1出现的次数
描述
思路
public int NumberOf1Between1AndN_Solution(int n) {
if (n <= 0)
return 0;
int count = 0;
for (long i = 1; i <= n; i *= 10) {
long diviver = i * 10;
count += (n / diviver) * i + Math.min(Math.max(n % diviver - i + 1, 0), i);
}
return count;
}
34. 丑数
描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路
- 只求丑数，不要去管非丑数。
- 每个丑数必然是由小于它的某个丑数乘以2，3或5得到的，我们把求得的丑数都保存下来，用之前的丑数分别乘以2，3，5，找出这三这种最小的并且大于当前最大丑数的值，即为下一个我们要求的丑数。
- 这种方法用空间换时间，时间复杂度为O(n)。
public int GetUglyNumber_Solution(int index) {
if (index <= 0)
return 0;
if (index == 1)
return 1;
int[] reslut = new int[index];
int t2 = 0, t3 = 0, t5 = 0;
reslut[0] = 1;
for (int i = 1; i < index; i++) {
reslut[i] = Min(reslut[t2] * 2, reslut[t3] * 3, reslut[t5] * 5);
if (reslut[i] == reslut[t2] * 2)
t2++;
if (reslut[i] == reslut[t3] * 3)
t3++;
if (reslut[i] == reslut[t5] * 5)
t5++;
}
return reslut[index - 1];
}
46. 1+ 2 +...+n
描述
思路
1.需利用逻辑与的短路特性实现递归终止。
2.当n==0时，(n>0)&&((sum+=Sum_Solution(n-1))>0)只执行前面的判断，为false，然后直接返回0；
3.当n>0时，执行sum+=Sum_Solution(n-1)，实现递归计算Sum_Solution(n)。
public int Sum_Solution(int n){
int sum=n;
boolean ans=(n>0)&&((sum+=Sum_Solution(n-1))>0);
return sum;
}
不用加减乘除做加法
思路
首先看十进制是如何做的： 5+7=12，三步走
第一步：相加各位的值，不算进位，得到2。
第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。 同样我们
可以用三步走的方式计算二进制值相加： 5-101，7-111
第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。
第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
public int Add(int num1,int num2) {
int sum,carry;
while(num2!=0){
sum = num1^num2;
carry = (num1&num2)<<1;
num1 = sum;
num2 = carry;
}
return num1;
}
