JZ6
問題描述：
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾亲桥，我們稱之為數(shù)組的旋轉(zhuǎn)轩娶。輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)魄缚，輸出旋轉(zhuǎn)數(shù)組的最小元素暗甥。
例如數(shù)組[3,4,5,1,2]為[1,2,3,4,5]的一個旋轉(zhuǎn)喜滨，該數(shù)組的最小值為1。NOTE：給出的所有元素都大于0撤防，若數(shù)組大小為0虽风，請返回0。
思路：
- 二分查找寄月，三個指針mid焰情、left、right
- 如果中間值大于數(shù)組尾部的值剥懒，則left = mid + 1
- 如果中間值小于尾部的值内舟，則right = mid
- 如果中間值等于尾部的值，則直接讓右指針自減
代碼：
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array == null || array.length == 0) return 0;
int n = array.length;
int l = 0, r = n - 1;
while(l < r) {
int m = (l + r) >> 1;
if(array[m] > array[r]) {
l = m + 1;
}else if(array[m] < array[r]){
r = m;
}else{ // 相等的時候初橘，避免最小值在（m和r之間）验游，所以這個時候只能讓r--
r--;
}
}
return array[l];
}
}
JZ7
問題描述：
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n保檐，請你輸出斐波那契數(shù)列的第n項（從0開始耕蝉，第0項為0，第1項是1）夜只。n<=39
思路：
- 動態(tài)規(guī)劃
代碼：
public class Solution {
public int Fibonacci(int n) {
if(n <= 1) return n;
int p1 = 0, p2 = 1, c = 0;
for(int i = 2; i <= n; i++) {
c = p1 + p2;
p1 = p2;
p2 = c;
}
return c;
}
}
JZ8
問題描述：
一只青蛙一次可以跳上1級臺階垒在，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結(jié)果）扔亥。
思路一：
- 動態(tài)規(guī)劃
- 第n階臺階可能的狀態(tài)為第n-1階的可能方案加上第n-2階的可能方案
代碼：
public class Solution {
public int JumpFloor(int target) {
if (target <= 1) return target;
int c0 = 1;
int c1 = 1;
int ans = 2;
for (int i = 2; i <= target; i++) {
ans = c0 + c1;
c0 = c1;
c1 = ans;
}
return ans;
}
}
JZ9
問題描述：
一只青蛙一次可以跳上1級臺階场躯，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法旅挤。
思路一：
- 動態(tài)規(guī)劃
- 第n階的可能方案為前面所有階層的方案累加和
代碼：
public class Solution {
public int JumpFloorII(int target) {
if(target == 1) return 1;
int[] dp = new int[target + 1];
dp[1] = 1;
for(int i = 2; i <= target; i++) {
for(int j = 1; j < i; j++) {
dp[i] += dp[j];
}
dp[i]++;
}
return dp[target];
}
}
JZ10
問題描述：
我們可以用2 * 1的小矩形橫著或者豎著去覆蓋更大的矩形踢关。請問用n個2 * 1的小矩形無重疊地覆蓋一個2 * n的大矩形，總共有多少種方法粘茄？
比如n = 3時签舞，2 * 3的矩形塊有3種覆蓋方法：
思路一：
- 這道題可以轉(zhuǎn)化一種思路：
- 你可以在1和2之間隨便取一個數(shù)，給定一個整數(shù)n柒瓣，你的目標(biāo)就是找出取出來的數(shù)累加和為n一共有多少種可能性儒搭！
- 例如：指定 n = 3, 可能的情況有
1 1 1,1 2,2 1; 所以一共有3種可能的情況 - 那么按照這個思路，一個dfs模板就可以解決問題了
代碼：
public class Solution {
int res = 0;
public int RectCover(int target) {
if(target <= 2)return target;
dfs(0, target);
return res;
}
private void dfs(int cur, int sum) {
if(cur > sum) return;
if(cur == sum) {
res++;
return;
}
dfs(cur + 1, sum);
dfs(cur + 2, sum);
}
}
