題目匯總

以下鏈接均為我博客內(nèi)對(duì)應(yīng)博文，有解題思路和代碼，不定時(shí)更新補(bǔ)充。

目前范圍：Leetcode前150題

深度優(yōu)先/回溯法題目

• Letter Combinations of a Phone Number/電話號(hào)碼的字母組合

輸入手機(jī)鍵盤的數(shù)字，組合所有可能的字母。

• Permutations/全排列

求一組不重復(fù)的數(shù)的全排列

• Permutations II/全排列 II

求一組數(shù)的全排列（有重復(fù)數(shù)字），返回不重復(fù)的全排列

• Generate Parentheses/括號(hào)生成

給定n，生成n對(duì)括號(hào)，必須正常關(guān)閉所有符號(hào)

• Sudoku Solver/解數(shù)獨(dú)

計(jì)算數(shù)獨(dú)，假設(shè)解唯一

• Combination Sum/組合總和

給定一個(gè)無重復(fù)元素的數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。candidates 中的數(shù)字可以無限制重復(fù)被選取。

• Combination Sum II/組合總和 II

給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。

• N-Queens/N-Queens II/N皇后/N皇后 II

經(jīng)典的八皇后問題

• Permutation Sequence/第k個(gè)排列

找出由[1,2,3…n]中所有數(shù)字組成的序列中第k大的。

• Combinations/組合

求在1到n個(gè)數(shù)中挑選k個(gè)數(shù)的所有的組合類型。

• Subsets/Subsets II/子集/子集 II

給定一個(gè)由不同數(shù)字組成的集合，羅列出該集合的所有子集。

給定一個(gè)含有重復(fù)數(shù)字組成的集合，羅列出該集合的所有子集。

• Word Search/單詞搜索

在一個(gè)二維矩陣中，每個(gè)元素都是一個(gè)字母，要判斷目標(biāo)字符串能否由該矩陣中的元素連接而成。所謂連接就是從矩陣中的某一個(gè)元素開始，向前后左右不斷前進(jìn)，但不允許再次經(jīng)過走過的元素。

• Restore IP Addresses/復(fù)原IP地址

找出一個(gè)由純數(shù)字組成的序列能夠構(gòu)成的不同的IP地址。

• Palindrome Partitioning/Palindrome Partitioning II/分割回文串/分割回文串II

將一個(gè)字符串分割成若干個(gè)子字符串，使得子字符串都是回文字符串，要求列出所有的分割方案。

• Word Break/Word Break II/單詞拆分/單詞拆分 II

給定一個(gè)目標(biāo)字符串和一組字符串，判斷目標(biāo)字符串能否拆分成數(shù)個(gè)字符串，這些字符串都在給定的那組字符串中。

給定一個(gè)目標(biāo)字符串和一組單詞，將目標(biāo)字符串進(jìn)行拆分，要求拆分出的部分在那個(gè)單詞組中，拆分后的單詞用空格隔開，給出所有可能的拆分情況。

深度優(yōu)先總結(jié)

遞歸與迭代

二者相互關(guān)系

1. 從計(jì)算機(jī)角度講，遞歸是迭代的特例。這個(gè)例子是兩種方式計(jì)算階乘的javascript代碼實(shí)現(xiàn)，可以在瀏覽器中，按F12調(diào)出控制臺(tái)，在控制臺(tái)中進(jìn)行實(shí)驗(yàn)。// 迭代，重復(fù)一定的算法，達(dá)到想要的目的。數(shù)學(xué)上二分法，牛頓法是很好的迭代例子

function iteration(x){
   var sum=1; 
   for(x; x>=1; x--){
       sum = sum*x;
   }
}

// 遞歸，自身調(diào)用自身的迭代就是遞歸。
// 但是正式定義好像不是這么說的。這只是我個(gè)人理解

function recursion(x){
   if(x>1){
       return x*recursion(x-1);
   }else{
       return 1;
   }
}

2. 任何一個(gè)迭代的例子都有它的遞歸表示法，反之亦然。比如請(qǐng)將下列冒泡排序（由大到小）從迭代形式改寫為遞歸形式

：function swap(array, i, j){
    const temp = array[i]
    array[i] = array[j]
    array[j] = temp
}
function bubble(array){
    let length = array.length
    for(let i = length-1; i>0; i--){
        for(let j=0; j<i; j++){
            if(array[j] < array[j+1]){
                swap(array, j, j+1)
            }
        }
    }
    return array
}
answer：function swap(array, i, j){
    const temp = array[i]
    array[i] = array[j]
    array[j] = temp
}
function bubble(array, i = array.length-1, j = 0){
    if(i===1){
        return array
    }
    if(j > i){
        j = 0
        i--
    }
    if(array[j] < array[j+1]){
        swap(array, j, j+1)
    }

    return bubble(array, i, j+1)
}

從代碼優(yōu)雅美觀角度講，遞歸的形式縮進(jìn)會(huì)更少一些，顯得平整。

遞歸的劣勢

1.遞歸容易產(chǎn)生"棧溢出"錯(cuò)誤（stack overflow）因?yàn)樾枰瑫r(shí)保存成千上百個(gè)調(diào)用記錄，所以遞歸非常耗費(fèi)內(nèi)存。這也就是為什么會(huì)有『尾遞歸調(diào)用優(yōu)化』而迭代對(duì)于瀏覽器的影響頂多是由于計(jì)算量大而發(fā)生線程長時(shí)間占用的假死現(xiàn)象，不至于在運(yùn)行時(shí)棧溢出而拋錯(cuò)的問題?！緜渥ⅲ汉髞戆l(fā)現(xiàn) Chrome v61.0.3163.100 根本沒有做尾遞歸優(yōu)化處理?！?/p>

2.效率方面，遞歸可能存在冗余計(jì)算使用遞歸的方式會(huì)有冗余計(jì)算（比如最典型的是斐波那契數(shù)列，計(jì)算第6個(gè)需要計(jì)算第4個(gè)和第5個(gè)，而計(jì)算第5個(gè)還需要計(jì)算第4個(gè)，所處會(huì)重復(fù)）。迭代在這方面有絕對(duì)優(yōu)勢。但是這并不表明遞歸可以完全被取代。因?yàn)檫f歸有更好的可讀性。