常用算法整理
- 劍指Offer http://itmyhome.com/sword-means-offer/sword-means-offer.pdf
- 算法可視化界? https://github.com/algorithm-visualizer/algorithm-visualizer
位運(yùn)算
- ?進(jìn)制、二進(jìn)制相互轉(zhuǎn)換
- 十進(jìn)制
33可以看成是32 + 1，并且33應(yīng)該是六位二進(jìn)制的（因?yàn)?33近似32吗货，而32是 2 的五次方，所以是六位）瓷产，那么 十進(jìn)制33就是100001涌矢，只要是 2 的次方摆出，那么就是 1否則都為 0 - 那么二進(jìn)制
100001同理朗徊，首位是2^5，末位是2^0偎漫，相加得出 33
左移 <<
10 << 1 // -> 20
左移就是將二進(jìn)制全部往左移動(dòng)爷恳，10 在二進(jìn)制中表示為 1010 ，左移一位后變成 10100 象踊，轉(zhuǎn)換為十進(jìn)制也就是 20温亲，所以基本可以把左移看成以下公式 a * (2 ^ b)
算數(shù)右移 >>
10 >> 1 // -> 5
算數(shù)右移就是將二進(jìn)制全部往右移動(dòng)并去除多余的右邊，10 在二進(jìn)制中表示為 1010 杯矩，右移一位后變成 101 栈虚，轉(zhuǎn)換為十進(jìn)制也就是 5，所以基本可以把右移看成以下公式 int v = a / (2 ^ b)
右移很好用史隆，比如可以用在二分算法中取中間值
13 >> 1 // -> 6
按位操作
按位與
每一位都為 1魂务，結(jié)果才為 1
8 & 7 // -> 0
// 1000 & 0111 -> 0000 -> 0
按位或
其中一位為 1，結(jié)果就是 1
8 | 7 // -> 15
// 1000 | 0111 -> 1111 -> 15
按位異或
每一位都不同泌射，結(jié)果才為 1
8 ^ 7 // -> 15
8 ^ 8 // -> 0
// 1000 ^ 0111 -> 1111 -> 15
// 1000 ^ 1000 -> 0000 -> 0
從以上代碼中可以發(fā)現(xiàn)按位異或就是不進(jìn)位加法
面試題：兩個(gè)數(shù)不使用四則運(yùn)算得出和
這道題中可以按位異或粘姜，因?yàn)榘次划惢蚓褪遣贿M(jìn)位加法，8 ^ 8 = 0 如果進(jìn)位了熔酷，就是 16 了孤紧，所以我們只需要將兩個(gè)數(shù)進(jìn)行異或操作，然后進(jìn)位纯陨。那么也就是說兩個(gè)二進(jìn)制都是 1 的位置，左邊應(yīng)該有一個(gè)進(jìn)位 1留储，所以可以得出以下公式 a + b = (a ^ b) + ((a & b) << 1) 翼抠，然后通過迭代的方式模擬加法
function sum(a, b) {
if (a == 0) return b
if (b == 0) return a
let newA = a ^ b
let newB = (a & b) << 1
return sum(newA, newB)
}
排序
以下兩個(gè)函數(shù)是排序中會(huì)用到的通用函數(shù)，就不一一寫了
function checkArray(array) {
if (!array) return
}
function swap(array, left, right) {
let rightValue = array[right]
array[right] = array[left]
array[left] = rightValue
}
冒泡排序
冒泡排序的原理如下获讳，從第一個(gè)元素開始阴颖，把當(dāng)前元素和下一個(gè)索引元素進(jìn)行比較。如果當(dāng)前元素大丐膝，那么就交換位置量愧，重復(fù)操作直到比較到最后一個(gè)元素钾菊，那么此時(shí)最后一個(gè)元素就是該數(shù)組中最大的數(shù)。下一輪重復(fù)以上操作偎肃，但是此時(shí)最后一個(gè)元素已經(jīng)是最大數(shù)了煞烫，所以不需要再比較最后一個(gè)元素，只需要比較到 length - 2 的位置累颂。
https://user-gold-cdn.xitu.io/2018/4/12/162b895b452b306c?w=670&h=508&f=gif&s=282307
以下是實(shí)現(xiàn)該算法的代碼
function bubble(array) {
checkArray(array);
for (let i = array.length - 1; i > 0; i--) {
// 從 0 到 `length - 1` 遍歷
for (let j = 0; j < i; j++) {
if (array[j] > array[j + 1]) swap(array, j, j + 1)
}
}
return array;
}
該算法的操作次數(shù)是一個(gè)等差數(shù)列 n + (n - 1) + (n - 2) + 1 滞详，去掉常數(shù)項(xiàng)以后得出時(shí)間復(fù)雜度是 O(n * n)
插入排序
插入排序的原理如下。第一個(gè)元素默認(rèn)是已排序元素紊馏，取出下一個(gè)元素和當(dāng)前元素比較料饥，如果當(dāng)前元素大就交換位置。那么此時(shí)第一個(gè)元素就是當(dāng)前的最小數(shù)朱监，所以下次取出操作從第三個(gè)元素開始岸啡，向前對(duì)比，重復(fù)之前的操作赫编。
https://user-gold-cdn.xitu.io/2018/4/12/162b895c7e59dcd1?w=670&h=508&f=gif&s=609549
以下是實(shí)現(xiàn)該算法的代碼
function insertion(array) {
checkArray(array);
for (let i = 1; i < array.length; i++) {
for (let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--)
swap(array, j, j + 1);
}
return array;
}
該算法的操作次數(shù)是一個(gè)等差數(shù)列 n + (n - 1) + (n - 2) + 1 巡蘸，去掉常數(shù)項(xiàng)以后得出時(shí)間復(fù)雜度是 O(n * n)
選擇排序
選擇排序的原理如下。遍歷數(shù)組沛慢，設(shè)置最小值的索引為 0赡若，如果取出的值比當(dāng)前最小值小，就替換最小值索引团甲，遍歷完成后逾冬，將第一個(gè)元素和最小值索引上的值交換。如上操作后躺苦，第一個(gè)元素就是數(shù)組中的最小值身腻，下次遍歷就可以從索引 1 開始重復(fù)上述操作。
https://user-gold-cdn.xitu.io/2018/4/13/162bc8ea14567e2e?w=670&h=508&f=gif&s=965636
以下是實(shí)現(xiàn)該算法的代碼
function selection(array) {
checkArray(array);
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
minIndex = array[j] < array[minIndex] ? j : minIndex;
}
swap(array, i, minIndex);
}
return array;
}
該算法的操作次數(shù)是一個(gè)等差數(shù)列 n + (n - 1) + (n - 2) + 1 匹厘，去掉常數(shù)項(xiàng)以后得出時(shí)間復(fù)雜度是 O(n * n)
歸并排序
歸并排序的原理如下嘀趟。遞歸的將數(shù)組兩兩分開直到最多包含兩個(gè)元素，然后將數(shù)組排序合并愈诚，最終合并為排序好的數(shù)組她按。假設(shè)我有一組數(shù)組 [3, 1, 2, 8, 9, 7, 6]，中間數(shù)索引是 3炕柔，先排序數(shù)組 [3, 1, 2, 8] 酌泰。在這個(gè)左邊數(shù)組上，繼續(xù)拆分直到變成數(shù)組包含兩個(gè)元素（如果數(shù)組長(zhǎng)度是奇數(shù)的話匕累，會(huì)有一個(gè)拆分?jǐn)?shù)組只包含一個(gè)元素）陵刹。然后排序數(shù)組 [3, 1] 和 [2, 8] ，然后再排序數(shù)組 [1, 3, 2, 8] 欢嘿，這樣左邊數(shù)組就排序完成衰琐，然后按照以上思路排序右邊數(shù)組也糊，最后將數(shù)組 [1, 2, 3, 8] 和 [6, 7, 9] 排序。
https://user-gold-cdn.xitu.io/2018/4/13/162be13c7e30bd86?w=896&h=1008&f=gif&s=937952
以下是實(shí)現(xiàn)該算法的代碼
function sort(array) {
checkArray(array);
mergeSort(array, 0, array.length - 1);
return array;
}
function mergeSort(array, left, right) {
// 左右索引相同說明已經(jīng)只有一個(gè)數(shù)
if (left === right) return;
// 等同于 `left + (right - left) / 2`
// 相比 `(left + right) / 2` 來說更加安全羡宙，不會(huì)溢出
// 使用位運(yùn)算是因?yàn)槲贿\(yùn)算比四則運(yùn)算快
let mid = parseInt(left + ((right - left) >> 1));
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
let help = [];
let i = 0;
let p1 = left;
let p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
while (p1 <= mid) {
help[i++] = array[p1++];
}
while (p2 <= right) {
help[i++] = array[p2++];
}
for (let i = 0; i < help.length; i++) {
array[left + i] = help[i];
}
return array;
}
以上算法使用了遞歸的思想狸剃。遞歸的本質(zhì)就是壓棧，每遞歸執(zhí)行一次函數(shù)辛辨，就將該函數(shù)的信息（比如參數(shù)捕捂，內(nèi)部的變量，執(zhí)行到的行數(shù)）壓棧斗搞，直到遇到終止條件指攒，然后出棧并繼續(xù)執(zhí)行函數(shù)。對(duì)于以上遞歸函數(shù)的調(diào)用軌跡如下
mergeSort(data, 0, 6) // mid = 3
mergeSort(data, 0, 3) // mid = 1
mergeSort(data, 0, 1) // mid = 0
mergeSort(data, 0, 0) // 遇到終止僻焚，回退到上一步
mergeSort(data, 1, 1) // 遇到終止允悦，回退到上一步
// 排序 p1 = 0, p2 = mid + 1 = 1
// 回退到 `mergeSort(data, 0, 3)` 執(zhí)行下一個(gè)遞歸
mergeSort(2, 3) // mid = 2
mergeSort(3, 3) // 遇到終止，回退到上一步
// 排序 p1 = 2, p2 = mid + 1 = 3
// 回退到 `mergeSort(data, 0, 3)` 執(zhí)行合并邏輯
// 排序 p1 = 0, p2 = mid + 1 = 2
// 執(zhí)行完畢回退
// 左邊數(shù)組排序完畢虑啤，右邊也是如上軌跡
該算法的操作次數(shù)是可以這樣計(jì)算：遞歸了兩次隙弛，每次數(shù)據(jù)量是數(shù)組的一半，并且最后把整個(gè)數(shù)組迭代了一次狞山，所以得出表達(dá)式 2T(N / 2) + T(N) （T 代表時(shí)間全闷，N 代表數(shù)據(jù)量）。根據(jù)該表達(dá)式可以套用 該公式 得出時(shí)間復(fù)雜度為 O(N * logN)
快排
快排的原理如下萍启。隨機(jī)選取一個(gè)數(shù)組中的值作為基準(zhǔn)值总珠，從左至右取值與基準(zhǔn)值對(duì)比大小。比基準(zhǔn)值小的放數(shù)組左邊勘纯，大的放右邊局服，對(duì)比完成后將基準(zhǔn)值和第一個(gè)比基準(zhǔn)值大的值交換位置。然后將數(shù)組以基準(zhǔn)值的位置分為兩部分驳遵，繼續(xù)遞歸以上操作淫奔。
https://user-gold-cdn.xitu.io/2018/4/16/162cd23e69ca9ea3?w=824&h=506&f=gif&s=867744
以下是實(shí)現(xiàn)該算法的代碼
function sort(array) {
checkArray(array);
quickSort(array, 0, array.length - 1);
return array;
}
function quickSort(array, left, right) {
if (left < right) {
swap(array, , right)
// 隨機(jī)取值，然后和末尾交換堤结，這樣做比固定取一個(gè)位置的復(fù)雜度略低
let indexs = part(array, parseInt(Math.random() * (right - left + 1)) + left, right);
quickSort(array, left, indexs[0]);
quickSort(array, indexs[1] + 1, right);
}
}
function part(array, left, right) {
let less = left - 1;
let more = right;
while (left < more) {
if (array[left] < array[right]) {
// 當(dāng)前值比基準(zhǔn)值小唆迁，`less` 和 `left` 都加一
++less;
++left;
} else if (array[left] > array[right]) {
// 當(dāng)前值比基準(zhǔn)值大，將當(dāng)前值和右邊的值交換
// 并且不改變 `left`竞穷，因?yàn)楫?dāng)前換過來的值還沒有判斷過大小
swap(array, --more, left);
} else {
// 和基準(zhǔn)值相同唐责，只移動(dòng)下標(biāo)
left++;
}
}
// 將基準(zhǔn)值和比基準(zhǔn)值大的第一個(gè)值交換位置
// 這樣數(shù)組就變成 `[比基準(zhǔn)值小, 基準(zhǔn)值, 比基準(zhǔn)值大]`
swap(array, right, more);
return [less, more];
}
該算法的復(fù)雜度和歸并排序是相同的，但是額外空間復(fù)雜度比歸并排序少来庭，只需 O(logN)妒蔚，并且相比歸并排序來說穿挨，所需的常數(shù)時(shí)間也更少月弛。
面試題
Sort Colors：該題目來自 LeetCode肴盏，題目需要我們將 [2,0,2,1,1,0] 排序成 [0,0,1,1,2,2] ，這個(gè)問題就可以使用三路快排的思想帽衙。
以下是代碼實(shí)現(xiàn)
var sortColors = function(nums) {
let left = -1;
let right = nums.length;
let i = 0;
// 下標(biāo)如果遇到 right菜皂，說明已經(jīng)排序完成
while (i < right) {
if (nums[i] == 0) {
swap(nums, i++, ++left);
} else if (nums[i] == 1) {
i++;
} else {
swap(nums, i, --right);
}
}
};
Kth Largest Element in an Array：該題目來自 LeetCode，題目需要找出數(shù)組中第 K 大的元素厉萝，這問題也可以使用快排的思路恍飘。并且因?yàn)槭钦页龅?K 大元素，所以在分離數(shù)組的過程中谴垫，可以找出需要的元素在哪邊章母，然后只需要排序相應(yīng)的一邊數(shù)組就好。
以下是代碼實(shí)現(xiàn)
var findKthLargest = function(nums, k) {
let l = 0
let r = nums.length - 1
// 得出第 K 大元素的索引位置
k = nums.length - k
while (l < r) {
// 分離數(shù)組后獲得比基準(zhǔn)樹大的第一個(gè)元素索引
let index = part(nums, l, r)
// 判斷該索引和 k 的大小
if (index < k) {
l = index + 1
} else if (index > k) {
r = index - 1
} else {
break
}
}
return nums[k]
};
function part(array, left, right) {
let less = left - 1;
let more = right;
while (left < more) {
if (array[left] < array[right]) {
++less;
++left;
} else if (array[left] > array[right]) {
swap(array, --more, left);
} else {
left++;
}
}
swap(array, right, more);
return more;
}
堆排序
堆排序利用了二叉堆的特性來做翩剪，二叉堆通常用數(shù)組表示乳怎，并且二叉堆是一顆完全二叉樹（所有葉節(jié)點(diǎn)（最底層的節(jié)點(diǎn)）都是從左往右順序排序，并且其他層的節(jié)點(diǎn)都是滿的）前弯。二叉堆又分為大根堆與小根堆蚪缀。
- 大根堆是某個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)的值都比他小
- 小根堆是某個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)的值都比他大
堆排序的原理就是組成一個(gè)大根堆或者小根堆。以小根堆為例恕出，某個(gè)節(jié)點(diǎn)的左邊子節(jié)點(diǎn)索引是 i * 2 + 1询枚，右邊是 i * 2 + 2，父節(jié)點(diǎn)是 (i - 1) /2浙巫。
- 首先遍歷數(shù)組金蜀，判斷該節(jié)點(diǎn)的父節(jié)點(diǎn)是否比他小，如果小就交換位置并繼續(xù)判斷狈醉，直到他的父節(jié)點(diǎn)比他大
- 重新以上操作 1廉油，直到數(shù)組首位是最大值
- 然后將首位和末尾交換位置并將數(shù)組長(zhǎng)度減一，表示數(shù)組末尾已是最大值苗傅，不需要再比較大小
- 對(duì)比左右節(jié)點(diǎn)哪個(gè)大抒线，然后記住大的節(jié)點(diǎn)的索引并且和父節(jié)點(diǎn)對(duì)比大小，如果子節(jié)點(diǎn)大就交換位置
- 重復(fù)以上操作 3 - 4 直到整個(gè)數(shù)組都是大根堆渣慕。
https://user-gold-cdn.xitu.io/2018/4/17/162d2a9ff258dfe1?w=1372&h=394&f=gif&s=1018181
以下是實(shí)現(xiàn)該算法的代碼
function heap(array) {
checkArray(array);
// 將最大值交換到首位
for (let i = 0; i < array.length; i++) {
heapInsert(array, i);
}
let size = array.length;
// 交換首位和末尾
swap(array, 0, --size);
while (size > 0) {
heapify(array, 0, size);
swap(array, 0, --size);
}
return array;
}
function heapInsert(array, index) {
// 如果當(dāng)前節(jié)點(diǎn)比父節(jié)點(diǎn)大嘶炭，就交換
while (array[index] > array[parseInt((index - 1) / 2)]) {
swap(array, index, parseInt((index - 1) / 2));
// 將索引變成父節(jié)點(diǎn)
index = parseInt((index - 1) / 2);
}
}
function heapify(array, index, size) {
let left = index * 2 + 1;
while (left < size) {
// 判斷左右節(jié)點(diǎn)大小
let largest =
left + 1 < size && array[left] < array[left + 1] ? left + 1 : left;
// 判斷子節(jié)點(diǎn)和父節(jié)點(diǎn)大小
largest = array[index] < array[largest] ? largest : index;
if (largest === index) break;
swap(array, index, largest);
index = largest;
left = index * 2 + 1;
}
}
以上代碼實(shí)現(xiàn)了小根堆，如果需要實(shí)現(xiàn)大根堆逊桦，只需要把節(jié)點(diǎn)對(duì)比反一下就好眨猎。
該算法的復(fù)雜度是 O(logN)
系統(tǒng)自帶排序?qū)崿F(xiàn)
每個(gè)語言的排序內(nèi)部實(shí)現(xiàn)都是不同的。
對(duì)于 JS 來說强经，數(shù)組長(zhǎng)度大于 10 會(huì)采用快排睡陪，否則使用插入排序 源碼實(shí)現(xiàn) 。選擇插入排序是因?yàn)殡m然時(shí)間復(fù)雜度很差，但是在數(shù)據(jù)量很小的情況下和 O(N * logN)相差無幾兰迫，然而插入排序需要的常數(shù)時(shí)間很小信殊，所以相對(duì)別的排序來說更快。
對(duì)于 Java 來說汁果，還會(huì)考慮內(nèi)部的元素的類型涡拘。對(duì)于存儲(chǔ)對(duì)象的數(shù)組來說，會(huì)采用穩(wěn)定性好的算法据德。穩(wěn)定性的意思就是對(duì)于相同值來說鳄乏，相對(duì)順序不能改變。
https://user-gold-cdn.xitu.io/2018/4/18/162d7df247dcda00?w=440&h=727&f=png&s=38002
鏈表
反轉(zhuǎn)單向鏈表
該題目來自 LeetCode棘利，題目需要將一個(gè)單向鏈表反轉(zhuǎn)橱野。思路很簡(jiǎn)單，使用三個(gè)變量分別表示當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的前后節(jié)點(diǎn)善玫，雖然這題很簡(jiǎn)單仲吏，但是卻是一道面試常考題
以下是實(shí)現(xiàn)該算法的代碼
var reverseList = function(head) {
// 判斷下變量邊界問題
if (!head || !head.next) return head
// 初始設(shè)置為空蝌焚，因?yàn)榈谝粋€(gè)節(jié)點(diǎn)反轉(zhuǎn)后就是尾部裹唆，尾部節(jié)點(diǎn)指向 null
let pre = null
let current = head
let next
// 判斷當(dāng)前節(jié)點(diǎn)是否為空
// 不為空就先獲取當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)
// 然后把當(dāng)前節(jié)點(diǎn)的 next 設(shè)為上一個(gè)節(jié)點(diǎn)
// 然后把 current 設(shè)為下一個(gè)節(jié)點(diǎn)，pre 設(shè)為當(dāng)前節(jié)點(diǎn)
while(current) {
next = current.next
current.next = pre
pre = current
current = next
}
return pre
};
樹
二叉樹的先序只洒，中序许帐，后序遍歷
先序遍歷表示先訪問根節(jié)點(diǎn)，然后訪問左節(jié)點(diǎn)毕谴，最后訪問右節(jié)點(diǎn)成畦。
中序遍歷表示先訪問左節(jié)點(diǎn)，然后訪問根節(jié)點(diǎn)涝开，最后訪問右節(jié)點(diǎn)循帐。
后序遍歷表示先訪問左節(jié)點(diǎn)，然后訪問右節(jié)點(diǎn)舀武，最后訪問根節(jié)點(diǎn)拄养。
遞歸實(shí)現(xiàn)
遞歸實(shí)現(xiàn)相當(dāng)簡(jiǎn)單，代碼如下
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var traversal = function(root) {
if (root) {
// 先序
console.log(root);
traversal(root.left);
// 中序
// console.log(root);
traversal(root.right);
// 后序
// console.log(root);
}
};
對(duì)于遞歸的實(shí)現(xiàn)來說银舱，只需要理解每個(gè)節(jié)點(diǎn)都會(huì)被訪問三次就明白為什么這樣實(shí)現(xiàn)了瘪匿。
非遞歸實(shí)現(xiàn)
非遞歸實(shí)現(xiàn)使用了棧的結(jié)構(gòu)，通過棧的先進(jìn)后出模擬遞歸實(shí)現(xiàn)寻馏。
以下是先序遍歷代碼實(shí)現(xiàn)
function pre(root) {
if (root) {
let stack = [];
// 先將根節(jié)點(diǎn) push
stack.push(root);
// 判斷棧中是否為空
while (stack.length > 0) {
// 彈出棧頂元素
root = stack.pop();
console.log(root);
// 因?yàn)橄刃虮闅v是先左后右棋弥，棧是先進(jìn)后出結(jié)構(gòu)
// 所以先 push 右邊再 push 左邊
if (root.right) {
stack.push(root.right);
}
if (root.left) {
stack.push(root.left);
}
}
}
}
以下是中序遍歷代碼實(shí)現(xiàn)
function mid(root) {
if (root) {
let stack = [];
// 中序遍歷是先左再根最后右
// 所以首先應(yīng)該先把最左邊節(jié)點(diǎn)遍歷到底依次 push 進(jìn)棧
// 當(dāng)左邊沒有節(jié)點(diǎn)時(shí)，就打印棧頂元素诚欠，然后尋找右節(jié)點(diǎn)
// 對(duì)于最左邊的葉節(jié)點(diǎn)來說顽染，可以把它看成是兩個(gè) null 節(jié)點(diǎn)的父節(jié)點(diǎn)
// 左邊打印不出東西就把父節(jié)點(diǎn)拿出來打印漾岳，然后再看右節(jié)點(diǎn)
while (stack.length > 0 || root) {
if (root) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
console.log(root);
root = root.right;
}
}
}
}
以下是后序遍歷代碼實(shí)現(xiàn)，該代碼使用了兩個(gè)棧來實(shí)現(xiàn)遍歷粉寞，相比一個(gè)棧的遍歷來說要容易理解很多
function pos(root) {
if (root) {
let stack1 = [];
let stack2 = [];
// 后序遍歷是先左再右最后根
// 所以對(duì)于一個(gè)棧來說蝗羊，應(yīng)該先 push 根節(jié)點(diǎn)
// 然后 push 右節(jié)點(diǎn)，最后 push 左節(jié)點(diǎn)
stack1.push(root);
while (stack1.length > 0) {
root = stack1.pop();
stack2.push(root);
if (root.left) {
stack1.push(root.left);
}
if (root.right) {
stack1.push(root.right);
}
}
while (stack2.length > 0) {
console.log(s2.pop());
}
}
}
中序遍歷的前驅(qū)后繼節(jié)點(diǎn)
實(shí)現(xiàn)這個(gè)算法的前提是節(jié)點(diǎn)有一個(gè) parent 的指針指向父節(jié)點(diǎn)仁锯，根節(jié)點(diǎn)指向 null 。
https://user-gold-cdn.xitu.io/2018/4/24/162f61ad8e8588b7?w=682&h=486&f=png&s=41027
如圖所示翔悠，該樹的中序遍歷結(jié)果是 4, 2, 5, 1, 6, 3, 7
前驅(qū)節(jié)點(diǎn)
對(duì)于節(jié)點(diǎn) 2 來說业崖，他的前驅(qū)節(jié)點(diǎn)就是 4 ，按照中序遍歷原則蓄愁，可以得出以下結(jié)論
- 如果選取的節(jié)點(diǎn)的左節(jié)點(diǎn)不為空双炕，就找該左節(jié)點(diǎn)最右的節(jié)點(diǎn)。對(duì)于節(jié)點(diǎn)
1來說撮抓，他有左節(jié)點(diǎn)2妇斤，那么節(jié)點(diǎn)2的最右節(jié)點(diǎn)就是5 - 如果左節(jié)點(diǎn)為空，且目標(biāo)節(jié)點(diǎn)是父節(jié)點(diǎn)的右節(jié)點(diǎn)丹拯，那么前驅(qū)節(jié)點(diǎn)為父節(jié)點(diǎn)站超。對(duì)于節(jié)點(diǎn)
5來說，沒有左節(jié)點(diǎn)乖酬，且是節(jié)點(diǎn)2的右節(jié)點(diǎn)死相，所以節(jié)點(diǎn)2是前驅(qū)節(jié)點(diǎn) - 如果左節(jié)點(diǎn)為空，且目標(biāo)節(jié)點(diǎn)是父節(jié)點(diǎn)的左節(jié)點(diǎn)咬像，向上尋找到第一個(gè)是父節(jié)點(diǎn)的右節(jié)點(diǎn)的節(jié)點(diǎn)算撮。對(duì)于節(jié)點(diǎn)
6來說，沒有左節(jié)點(diǎn)县昂，且是節(jié)點(diǎn)3的左節(jié)點(diǎn)，所以向上尋找到節(jié)點(diǎn)1，發(fā)現(xiàn)節(jié)點(diǎn)3是節(jié)點(diǎn)1的右節(jié)點(diǎn)槽驶，所以節(jié)點(diǎn)1是節(jié)點(diǎn)6的前驅(qū)節(jié)點(diǎn)
以下是算法實(shí)現(xiàn)
function predecessor(node) {
if (!node) return
// 結(jié)論 1
if (node.left) {
return getRight(node.left)
} else {
let parent = node.parent
// 結(jié)論 2 3 的判斷
while(parent && parent.right === node) {
node = parent
parent = node.parent
}
return parent
}
}
function getRight(node) {
if (!node) return
node = node.right
while(node) node = node.right
return node
}
后繼節(jié)點(diǎn)
對(duì)于節(jié)點(diǎn) 2 來說呼畸，他的后繼節(jié)點(diǎn)就是 5 ，按照中序遍歷原則待讳，可以得出以下結(jié)論
- 如果有右節(jié)點(diǎn)预明，就找到該右節(jié)點(diǎn)的最左節(jié)點(diǎn)。對(duì)于節(jié)點(diǎn)
1來說耙箍，他有右節(jié)點(diǎn)3撰糠，那么節(jié)點(diǎn)3的最左節(jié)點(diǎn)就是6 - 如果沒有右節(jié)點(diǎn)，就向上遍歷直到找到一個(gè)節(jié)點(diǎn)是父節(jié)點(diǎn)的左節(jié)點(diǎn)辩昆。對(duì)于節(jié)點(diǎn)
5來說阅酪，沒有右節(jié)點(diǎn)，就向上尋找到節(jié)點(diǎn)2，該節(jié)點(diǎn)是父節(jié)點(diǎn)1的左節(jié)點(diǎn)术辐，所以節(jié)點(diǎn)1是后繼節(jié)點(diǎn)
以下是算法實(shí)現(xiàn)
function successor(node) {
if (!node) return
// 結(jié)論 1
if (node.right) {
return getLeft(node.right)
} else {
// 結(jié)論 2
let parent = node.parent
// 判斷 parent 為空
while(parent && parent.left === node) {
node = parent
parent = node.parent
}
return parent
}
}
function getLeft(node) {
if (!node) return
node = node.left
while(node) node = node.left
return node
}
樹的深度
樹的最大深度：該題目來自 Leetcode砚尽，題目需要求出一顆二叉樹的最大深度
以下是算法實(shí)現(xiàn)
var maxDepth = function(root) {
if (!root) return 0
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};
對(duì)于該遞歸函數(shù)可以這樣理解：一旦沒有找到節(jié)點(diǎn)就會(huì)返回 0，每彈出一次遞歸函數(shù)就會(huì)加一辉词，樹有三層就會(huì)得到3必孤。
動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃背后的基本思想非常簡(jiǎn)單。就是將一個(gè)問題拆分為子問題瑞躺，一般來說這些子問題都是非常相似的敷搪，那么我們可以通過只解決一次每個(gè)子問題來達(dá)到減少計(jì)算量的目的。
一旦得出每個(gè)子問題的解幢哨，就存儲(chǔ)該結(jié)果以便下次使用赡勘。
斐波那契數(shù)列
斐波那契數(shù)列就是從 0 和 1 開始，后面的數(shù)都是前兩個(gè)數(shù)之和
0捞镰，1闸与，1，2岸售，3践樱，5，8凸丸，13映胁，21，34甲雅，55解孙，89....
那么顯然易見，我們可以通過遞歸的方式來完成求解斐波那契數(shù)列
function fib(n) {
if (n < 2 && n >= 0) return n
return fib(n - 1) + fib(n - 2)
}
fib(10)
以上代碼已經(jīng)可以完美的解決問題抛人。但是以上解法卻存在很嚴(yán)重的性能問題弛姜，當(dāng) n 越大的時(shí)候，需要的時(shí)間是指數(shù)增長(zhǎng)的妖枚，這時(shí)候就可以通過動(dòng)態(tài)規(guī)劃來解決這個(gè)問題廷臼。
動(dòng)態(tài)規(guī)劃的本質(zhì)其實(shí)就是兩點(diǎn)
- 自底向上分解子問題
- 通過變量存儲(chǔ)已經(jīng)計(jì)算過的解
根據(jù)上面兩點(diǎn)，我們的斐波那契數(shù)列的動(dòng)態(tài)規(guī)劃思路也就出來了
- 斐波那契數(shù)列從 0 和 1 開始绝页，那么這就是這個(gè)子問題的最底層
- 通過數(shù)組來存儲(chǔ)每一位所對(duì)應(yīng)的斐波那契數(shù)列的值
function fib(n) {
let array = new Array(n + 1).fill(null)
array[0] = 0
array[1] = 1
for (let i = 2; i <= n; i++) {
array[i] = array[i - 1] + array[i - 2]
}
return array[n]
}
fib(10)
0 - 1背包問題
該問題可以描述為：給定一組物品荠商，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)续誉，我們?nèi)绾芜x擇莱没，才能使得物品的總價(jià)格最高。每個(gè)問題只能放入至多一次酷鸦。
假設(shè)我們有以下物品
| 物品 ID / 重量 | 價(jià)值 |
|---|---|
| 1 | 3 |
| 2 | 7 |
| 3 | 12 |
對(duì)于一個(gè)總?cè)萘繛?5 的背包來說饰躲，我們可以放入重量 2 和 3 的物品來達(dá)到背包內(nèi)的物品總價(jià)值最高牙咏。
對(duì)于這個(gè)問題來說，子問題就兩個(gè)嘹裂，分別是放物品和不放物品妄壶，可以通過以下表格來理解子問題
| 物品 ID / 剩余容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 1 | 0 | 3 | 3 | 3 | 3 | 3 |
| 2 | 0 | 3 | 7 | 10 | 10 | 10 |
| 3 | 0 | 3 | 7 | 12 | 15 | 19 |
直接來分析能放三種物品的情況，也就是最后一行
- 當(dāng)容量少于 3 時(shí)寄狼，只取上一行對(duì)應(yīng)的數(shù)據(jù)丁寄，因?yàn)楫?dāng)前容量不能容納物品 3
- 當(dāng)容量 為 3 時(shí)，考慮兩種情況泊愧，分別為放入物品 3 和不放物品 3
- 不放物品 3 的情況下伊磺，總價(jià)值為 10
- 放入物品 3 的情況下，總價(jià)值為 12拼卵，所以應(yīng)該放入物品 3
- 當(dāng)容量 為 4 時(shí)，考慮兩種情況蛮艰，分別為放入物品 3 和不放物品 3
- 不放物品 3 的情況下腋腮，總價(jià)值為 10
- 放入物品 3 的情況下，和放入物品 1 的價(jià)值相加壤蚜，得出總價(jià)值為 15即寡，所以應(yīng)該放入物品 3
- 當(dāng)容量 為 5 時(shí)，考慮兩種情況袜刷，分別為放入物品 3 和不放物品 3
- 不放物品 3 的情況下聪富，總價(jià)值為 10
- 放入物品 3 的情況下，和放入物品 2 的價(jià)值相加著蟹，得出總價(jià)值為 19墩蔓，所以應(yīng)該放入物品 3
以下代碼對(duì)照上表更容易理解
/**
* @param {*} w 物品重量
* @param {*} v 物品價(jià)值
* @param {*} C 總?cè)萘? * @returns
*/
function knapsack(w, v, C) {
let length = w.length
if (length === 0) return 0
// 對(duì)照表格，生成的二維數(shù)組萧豆，第一維代表物品奸披，第二維代表背包剩余容量
// 第二維中的元素代表背包物品總價(jià)值
let array = new Array(length).fill(new Array(C + 1).fill(null))
// 完成底部子問題的解
for (let i = 0; i <= C; i++) {
// 對(duì)照表格第一行， array[0] 代表物品 1
// i 代表剩余總?cè)萘? // 當(dāng)剩余總?cè)萘看笥谖锲?1 的重量時(shí)涮雷，記錄下背包物品總價(jià)值阵面，否則價(jià)值為 0
array[0][i] = i >= w[0] ? v[0] : 0
}
// 自底向上開始解決子問題，從物品 2 開始
for (let i = 1; i < length; i++) {
for (let j = 0; j <= C; j++) {
// 這里求解子問題洪鸭，分別為不放當(dāng)前物品和放當(dāng)前物品
// 先求不放當(dāng)前物品的背包總價(jià)值样刷，這里的值也就是對(duì)應(yīng)表格中上一行對(duì)應(yīng)的值
array[i][j] = array[i - 1][j]
// 判斷當(dāng)前剩余容量是否可以放入當(dāng)前物品
if (j >= w[i]) {
// 可以放入的話，就比大小
// 放入當(dāng)前物品和不放入當(dāng)前物品览爵，哪個(gè)背包總價(jià)值大
array[i][j] = Math.max(array[i][j], v[i] + array[i - 1][j - w[i]])
}
}
}
return array[length - 1][C]
}
最長(zhǎng)遞增子序列
最長(zhǎng)遞增子序列意思是在一組數(shù)字中置鼻，找出最長(zhǎng)一串遞增的數(shù)字，比如
0, 3, 4, 17, 2, 8, 6, 10
對(duì)于以上這串?dāng)?shù)字來說蜓竹，最長(zhǎng)遞增子序列就是 0, 3, 4, 8, 10沃疮，可以通過以下表格更清晰的理解
| 數(shù)字 | 0 | 3 | 4 | 17 | 2 | 8 | 6 | 10 |
|---|---|---|---|---|---|---|---|---|
| 長(zhǎng)度 | 1 | 2 | 3 | 4 | 2 | 4 | 4 | 5 |
通過以上表格可以很清晰的發(fā)現(xiàn)一個(gè)規(guī)律盒让，找出剛好比當(dāng)前數(shù)字小的數(shù)，并且在小的數(shù)組成的長(zhǎng)度基礎(chǔ)上加一司蔬。
這個(gè)問題的動(dòng)態(tài)思路解法很簡(jiǎn)單邑茄，直接上代碼
function lis(n) {
if (n.length === 0) return 0
// 創(chuàng)建一個(gè)和參數(shù)相同大小的數(shù)組，并填充值為 1
let array = new Array(n.length).fill(1)
// 從索引 1 開始遍歷俊啼，因?yàn)閿?shù)組已經(jīng)所有都填充為 1 了
for (let i = 1; i < n.length; i++) {
// 從索引 0 遍歷到 i
// 判斷索引 i 上的值是否大于之前的值
for (let j = 0; j < i; j++) {
if (n[i] > n[j]) {
array[i] = Math.max(array[i], 1 + array[j])
}
}
}
let res = 1
for (let i = 0; i < array.length; i++) {
res = Math.max(res, array[i])
}
return res
}
