題目匯總
以下鏈接均為我博客內(nèi)對應(yīng)博文胯甩，有解題思路和代碼值纱，不定時更新補充。
目前范圍：Leetcode前150題
深度優(yōu)先/回溯法題目
輸入手機鍵盤的數(shù)字步做，組合所有可能的字母卡乾。
求一組不重復(fù)的數(shù)的全排列
求一組數(shù)的全排列（有重復(fù)數(shù)字），返回不重復(fù)的全排列
給定n信卡，生成n對括號隔缀，必須正常關(guān)閉所有符號
計算數(shù)獨，假設(shè)解唯一
給定一個無重復(fù)元素的數(shù)組 candidates 和一個目標數(shù) target 傍菇，找出 candidates 中所有可以使數(shù)字和為 target 的組合猾瘸。candidates 中的數(shù)字可以無限制重復(fù)被選取。
給定一個數(shù)組 candidates 和一個目標數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合牵触。candidates 中的每個數(shù)字在每個組合中只能使用一次淮悼。
經(jīng)典的八皇后問題
找出由[1,2,3…n]中所有數(shù)字組成的序列中第k大的。
求在1到n個數(shù)中挑選k個數(shù)的所有的組合類型荒吏。
給定一個由不同數(shù)字組成的集合敛惊，羅列出該集合的所有子集。
給定一個含有重復(fù)數(shù)字組成的集合绰更，羅列出該集合的所有子集瞧挤。
在一個二維矩陣中，每個元素都是一個字母儡湾，要判斷目標字符串能否由該矩陣中的元素連接而成特恬。所謂連接就是從矩陣中的某一個元素開始，向前后左右不斷前進徐钠，但不允許再次經(jīng)過走過的元素癌刽。
找出一個由純數(shù)字組成的序列能夠構(gòu)成的不同的IP地址。
將一個字符串分割成若干個子字符串尝丐，使得子字符串都是回文字符串显拜，要求列出所有的分割方案。
給定一個目標字符串和一組字符串爹袁，判斷目標字符串能否拆分成數(shù)個字符串远荠，這些字符串都在給定的那組字符串中。
給定一個目標字符串和一組單詞失息，將目標字符串進行拆分譬淳，要求拆分出的部分在那個單詞組中，拆分后的單詞用空格隔開盹兢，給出所有可能的拆分情況邻梆。
深度優(yōu)先總結(jié)
遞歸與迭代
二者相互關(guān)系
- 從計算機角度講，遞歸是迭代的特例绎秒。這個例子是兩種方式計算階乘的javascript代碼實現(xiàn)浦妄，可以在瀏覽器中，按F12調(diào)出控制臺见芹，在控制臺中進行實驗校辩。// 迭代，重復(fù)一定的算法辆童，達到想要的目的宜咒。數(shù)學(xué)上二分法，牛頓法是很好的迭代例子
function iteration(x){
var sum=1;
for(x; x>=1; x--){
sum = sum*x;
}
}
// 遞歸把鉴，自身調(diào)用自身的迭代就是遞歸故黑。
// 但是正式定義好像不是這么說的儿咱。這只是我個人理解
function recursion(x){
if(x>1){
return x*recursion(x-1);
}else{
return 1;
}
}
- 任何一個迭代的例子都有它的遞歸表示法，反之亦然场晶。比如請將下列冒泡排序（由大到谢觳骸）從迭代形式改寫為遞歸形式
：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)雅美觀角度講，遞歸的形式縮進會更少一些诗轻，顯得平整钳宪。
遞歸的劣勢
1.遞歸容易產(chǎn)生"棧溢出"錯誤（stack overflow）因為需要同時保存成千上百個調(diào)用記錄，所以遞歸非常耗費內(nèi)存扳炬。這也就是為什么會有『尾遞歸調(diào)用優(yōu)化』而迭代對于瀏覽器的影響頂多是由于計算量大而發(fā)生線程長時間占用的假死現(xiàn)象吏颖，不至于在運行時棧溢出而拋錯的問題『拚粒【備注：后來發(fā)現(xiàn) Chrome v61.0.3163.100 根本沒有做尾遞歸優(yōu)化處理半醉。】
2.效率方面劝术，遞歸可能存在冗余計算使用遞歸的方式會有冗余計算（比如最典型的是斐波那契數(shù)列缩多，計算第6個需要計算第4個和第5個，而計算第5個還需要計算第4個养晋，所處會重復(fù)）衬吆。迭代在這方面有絕對優(yōu)勢。但是這并不表明遞歸可以完全被取代绳泉。因為遞歸有更好的可讀性咆槽。
