范疇:遞歸
1驹饺、青蛙跳臺(tái)階
青蛙跳臺(tái)階算法,每次可以跳1級(jí)或兩級(jí)鱼炒,請(qǐng)問(wèn)有n級(jí)臺(tái)階蝌借,有多少種算法俐巴,遞歸和非遞歸如何寫(xiě)
-
遞歸:
public int JumpFloor(int n) { if (n < 0) return 0; int[] fibArry = { 0, 1, 2 }; if (n < 3) return fibArry[n]; return JumpFloor(n - 1) + JumpFloor(n - 2); }
-
非遞歸:
public int JumpFloor(int n) { if (n < 0) return 0; int[] fibArry = { 0, 1,2 }; if (n < 3) return fibArry[n]; long nReturn = 0L; long fibFirst=1L; long fibTow=2L; for (int i = 3; i <= n; i++) { nReturn = fibFirst + fibTow; fibFirst=fibTow ; fibTow = nReturn; } return nReturn; }
2、變態(tài)跳臺(tái)階 來(lái)自抛嚎模客網(wǎng)
一只青蛙一次可以跳上1級(jí)臺(tái)階劣光,也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法牲剃。
分析:
關(guān)于本題雄可,前提是n個(gè)臺(tái)階會(huì)有一次n階的跳法。分析如下:
f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2階一次跳2階的次數(shù)聪舒。
f(3) = f(3-1) + f(3-2) + f(3-3)
...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
說(shuō)明:
1)這里的f(n) 代表的是n個(gè)臺(tái)階有一次1,2,...n階的 跳法數(shù)虐急。
2)n = 1時(shí)止吁,只有1種跳法,f(1) = 1
3 ) n = 2時(shí)盼理,會(huì)有兩個(gè)跳得方式俄删,一次1階或者2階,這回歸到了問(wèn)題(1) 举哟,f(2) = f(2-1) + f(2-2)
4 ) n = 3時(shí)迅矛,會(huì)有三種跳得方式,1階壶硅、2階、3階椒舵,
那么就是第一次跳出1階后面剩下:f(3-1);第一次跳出2階约谈,剩下f(3-2);第一次3階泼橘,那么剩下f(3-3)
因此結(jié)論是f(3) = f(3-1)+f(3-2)+f(3-3)
5 ) n = n時(shí)迈勋,會(huì)有n種跳的方式,1階重归、2階...n階厦凤,得出結(jié)論:
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
由以上已經(jīng)是一種結(jié)論泳唠,但是為了簡(jiǎn)單,我們可以繼續(xù)簡(jiǎn)化:
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出:f(n) = 2f(n-1)
7 ) 最終結(jié)論 在n階臺(tái)階拓哺,一次有1脖母、2、...n階的跳的方式時(shí)烤礁,總得跳法為:
| 1 ,(n=0 )
f(n) = | 1 ,(n=1 )
| 2*f(n-1) ,(n>=2)
代碼:
public class Solution {
public int JumpFloorII(int target) {
if(target < 0){
return -1;
}else if(target == 0 || target == 1){
return 1;
}else{
return 2*JumpFloorII(target-1);
}
}
}
范疇:樹(shù)
題目:輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果脚仔,請(qǐng)重建出該二叉樹(shù)舆绎。
假設(shè)輸入的 前序遍歷 和 中序遍歷 的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}
和中序遍歷序列{4,7,2,1,5,3,8,6}
猎醇,則重建二叉樹(shù)并返回。
/**
*Definition for binary tree
*struct TreeNode {
*int val;
*TreeNode *left;
*TreeNode *right;
*TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
int inlen = in.size();
if(inlen == 0){
return NULL;
}
vector<int> left_pre,right_pre,left_in,right_in;
// 創(chuàng)建根節(jié)點(diǎn)阻问,根節(jié)點(diǎn)肯定是 前序遍歷 的第一個(gè)數(shù)
TreeNode* head = new TreeNode(pre[0]);
// 找到 中序遍歷 根節(jié)點(diǎn)所在位置称近,存在變量gen中
int gen = 0; // 從中序遍歷中找到的 根節(jié)點(diǎn)的坐標(biāo)
for(int i = 0; i < inlen; i++){
if(in[i] == pre[0]){
gen = i;
break;
}
}
// 接下來(lái)兩個(gè)for循環(huán)判斷:哪些元素屬于該根節(jié)點(diǎn)的左邊曹鸠,哪些屬于右邊
// 對(duì)于中序遍歷斥铺,根節(jié)點(diǎn)左邊的節(jié)點(diǎn)位于二叉樹(shù)的左邊晾蜘,根節(jié)點(diǎn)右邊節(jié)點(diǎn)位于二叉樹(shù)右邊
// 利用這一點(diǎn)對(duì)二叉樹(shù)進(jìn)行歸并,先判斷左邊的
for(int i = 0; i < gen; i++){
left_in.push_back(in[i]);
left_pre.push_back(pre[i+1]); //+1跳過(guò)前序的根節(jié)點(diǎn)
}
for(int i = gen+1; i < inlen; i++){
right_in.push_back(in[i]);
right_pre.push_back(pre[i]); //這里不用加1
}
// 和shell排序的思想類(lèi)似肆饶,取出前序和中序根節(jié)點(diǎn)左邊和右邊的子樹(shù)岖常,
// 也就是前面兩個(gè)for循環(huán)中保存起來(lái)的前序和中序的左右子樹(shù)數(shù)組
// 遞歸電泳該方法直到葉子節(jié)點(diǎn)
head->left = reConstructBinaryTree(left_pre,left_in);
head->right = reConstructBinaryTree(right_pre,right_in);
return head;
}
};