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;
}
网友评论