常見(jiàn)數(shù)據(jù)結(jié)構(gòu)與算法題

范疇:遞歸

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;
}
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末竭鞍,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子冯乘,更是在濱河造成了極大的恐慌晒夹,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異读跷,居然都是意外死亡舔亭,警方通過(guò)查閱死者的電腦和手機(jī)蟀俊,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)肢预,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)洼哎,“玉大人,你說(shuō)我怎么就攤上這事锭沟∈恫梗” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)切油。 經(jīng)常有香客問(wèn)我澎胡,道長(zhǎng),這世上最難降的妖魔是什么岛琼? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任槐瑞,我火速辦了婚禮阁苞,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘那槽。我一直安慰自己,他們只是感情好糟趾,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布义郑。 她就那樣靜靜地躺著,像睡著了一般交汤。 火紅的嫁衣襯著肌膚如雪劫笙。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,736評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音允华,去河邊找鬼。 笑死汉额,一個(gè)胖子當(dāng)著我的面吹牛曹仗,可吹牛的內(nèi)容都是我干的榨汤。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼怎茫,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼收壕!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起轨蛤,我...
    開(kāi)封第一講書(shū)人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤蜜宪,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后祥山,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體圃验,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年缝呕,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片供常。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡摊聋,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出栈暇,到底是詐尸還是另有隱情麻裁,我是刑警寧澤,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站煎源,受9級(jí)特大地震影響色迂,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜薪夕,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一脚草、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧原献,春花似錦馏慨、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至讲仰,卻和暖如春慕趴,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背鄙陡。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工冕房, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人趁矾。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓耙册,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親毫捣。 傳聞我的和親對(duì)象是個(gè)殘疾皇子详拙,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容