Welcome to Andy's Blog!
一念净心，花开遍世界-
剑指offer-数值的整数次方
题目描述 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
解体思路1
使用普通迭代求解幂次方
代码实现:(O(N))
public class Solution { public double Power(double base, int exponent) { boolean isNegative = false; double result = 1; if(exponent == 0) { return 1; } else if(exponent < 0){ exponent = - exponent; isNegative = true; } for(int i=1; i<=exponent; i++) { result *= base; } return isNegative ? 1/result : result; } }解体思路2
代码实现：(O(logN))
public class Solution { public double Power(double base, int exponent) { boolean isNegative = false; if(exponent == 0) return 1; if(exponent == 1) return base; if(exponent < 0) { exponent = - exponent; isNegative = true; } double pow = Power(base * base, exponent/2); if(exponent % 2 != 0) pow = pow * base; return isNegative ? 1/pow : pow; } }
-
剑指offer-矩形覆盖
题目描述 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解体思路
依旧是斐波那契数列 2n的大矩形，和n个21的小矩形 其中target*2为大矩阵的大小 有以下几种情形：
- ️target <= 0 大矩形为<= 2*0,直接return 1；
- ️target = 1大矩形为2*1，只有一种摆放方法，return1；
- ️target = 2 大矩形为2*2，有两种摆放方法，return2；
- ️target = n 分为两步考虑： 1) 第一次摆放一块 21的小矩阵，则摆放方法总共为f(target - 1) 2) 第一次摆放一块12的小矩阵，则摆放方法总共为f(target-2)
综上：f(n) = f(n-1) + f(n-2)
代码实现：
public class Solution { public int RectCover(int target) { if(target <= 2) return target; int[] fib = new int[target]; fib[0] = 1; fib[1] = 2; for(int i=2; i<target; i++) { fib[i] = fib[i-1] + fib[i-2]; } return fib[target - 1]; } }
-
剑指offer-变态跳台阶
题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解体思路1
对于本题,假设总跳法数量为f(n)，通过分析可以知道： f(n) = f(n-1) + f(n-2) + … +f(1) + 1 代码实现1(两层迭代):
public class Solution { public int JumpFloorII(int target) { if( target <= 2) return target; int[] fn = new int[target]; fn[0] = 1; fn[1] = 2; for(int i=2; i<target; i++) { for(int j=0; j<i; j++) { fn[i] += fn[j]; } fn[i]++; } return fn[target - 1]; } }解体思路2
因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级 跳1级，剩下n-1级，则剩下跳法是f(n-1) 跳2级，剩下n-2级，则剩下跳法是f(n-2) 所以f(n)=f(n-1)+f(n-2)+…+f(1) 因为f(n-1)=f(n-2)+f(n-3)+…+f(1) 所以f(n)=2*f(n-1)
代码实现1(递归）：
public class Solution { public int JumpFloorII(int target) { if(target <= 2) { return target; } else { return 2 * JumpFloorII(target - 1); } } }代码实现2：（位运算,速度更快）
public class Solution { public int JumpFloorII(int target) { int fn1 = 1; return fn1 << (target - 1); } }
-
剑指offer-跳台阶
题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。。
解体思路
对于本题,假设总跳法数量为f(n)
a.假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
c.由a, b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
e.可以发现最终得出的是一个斐波那契数列：
1, (n=1) f(n) = 2, (n=2) f(n-1)+f(n-2) ,(n>2,n为整数)实现代码1: (时间复杂度：O(n) 空间复杂度：O(n) ）
public class Solution { public int JumpFloor(int n) { if(n <= 2) { return n; } int[] fn = new int[n]; fn[0] = 1; fn[1] = 2; for(int i=2; i<n; i++) { fn[i] = fn[i-1] + fn[i-2]; } return fn[n-1]; } }实现代码2：(时间复杂度：O(n) 空间复杂度：O(1) ）
public class Solution { public int JumpFloor(int n) { if(n <= 2) return n; int prepre = 1; int pre = 2; int result = 0; for(int i=2; i<n; i++) { result = prepre + pre; prepre = pre; pre = result; } return result; } }
-
剑指offer-二进制中 1 的个数
题目描述 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解体思路
1.使用Integer.bitCount() 方法
public int NumberOf1(int n) { return Integer.bitCount(n); }2.n&(n-1) O(logM)时间复杂度，M表示1的个数 该位运算是去除n的位级表示的最低的以为
n :10110100 n-1 :10110011 n&(n-1) :10110000相关代码：
public class Solution { public int NumberOf1(int n) { int cnt = 0; while(n != 0) { cnt++; n &= (n - 1); } return cnt; } }
-
剑指offer-斐波那契数列
题目描述 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39
解体思路
1.使用递归求解
if(n <= 1) return n; } else { return Fibonacci(n-1) + Fibonacci(n-2); }2.使用迭代求解 下例是一个简单的动态规划，以一定的空间代价避免代价更大的重复计算的栈空间浪费,虽然看起来很蠢，空间浪费了sizeof(int)*(n-1)，但是对于那个超大n的测试用例应该是可以通过了，时间复杂度也达到了O(n)。
public int Fibonacci(int n) { if(n <= 1) { return n; } int[] fib = new int[n]; fib[0] = 1; fib[1] = 1; for(int i=2; i<n; i++) { fib[i] = fib[i-1] + fib[i-2]; } return fib[n-1]; }考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。
public int Fibonacci(int n) { if(n <= 1) return n; int pre2 = 0, pre1 = 1; int fib = 0; for(int i=2; i<=n; i++) { fib = pre2 + pre1; pre2 = pre1; pre1 = fib; } return fib; }由于待求解的 n 小于 40，因此可以将前 40 项的结果先进行计算，之后就能以 O(1) 时间复杂度得到第 n 项的值了。
public class Solution { private int[] fib = new int[40]; public Solution() { fib[1] = 1; for(int i=2; i<fib.length; i++) { fib[i] = fib[i-1] + fib[i-2]; } } public int Fibonacci(int n) { return fib[n]; } }