【算法篇】树、动态规划及字符串相关

非递归实现中先序、中序、后续遍历

非递归实现使用了栈的结构,通过栈的先进后出模拟递归实现。

以下是先序遍历代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function pre(root) {
if(root){
let stack = [];
// 先将根节点 push
stack.push(root);
// 判断栈中是否为空
while(stack.length > 0){
// 弹出栈顶元素
root = stack.pop();
console.log(root);
// 因为先序遍历是先左后右,栈是先进后出结构
// 所以先push右边再push左边
if(root.right){
stack.push(root.right);
}
if(root.left){
stack.push(root.left);
}
}
}
}

以下是中序遍历代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function mid(root) {
if(root){
let stack = [];
// 中序遍历是先左再根最后右
// 所以首先应该先把最左边节点遍历到底依次push进栈
// 当左边没有节点时,就打印栈顶元素,然后寻找右节点
// 对于最左边的叶节点来说,可以把它看成是两个 null 节点的父节点
// 左边打印不出东西就把父节点拿出来打印,然后再看右节点
while(stack.length > 0 || root){
if(root) {
stack.push(root);
root = root.left;
}else{
root = stack.pop();
console.log(root);
root = root.right;
}
}
}
}

以下是后续遍历代码实现,该代码使用了两个栈来实现遍历,相比一个栈的遍历来说要容易理解得多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function pos(root) {
if(root){
let stack1 = [];
let stack2 = [];

// 后续遍历是先左再右最后根
// 所以对于一个栈来说,应该先push根节点
// 然后push右节点,最后push左节点
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(stack2.pop());
}
}
}

中序遍历的前驱后续节点

实现这个算法的前提是节点有一个parent的指针指向父节点,根节点指向null

https://user-gold-cdn.xitu.io/2018/4/24/162f61ad8e8588b7?w=682&h=486&f=png&s=41027

如果所示,该树的中序遍历结果是4,2,5,1,6,3,7

前驱节点

对于节点2来说,他的前驱节点就是4,按照中序遍历规则(左、根、右),可以得出以下结论

  1. 如果选取的节点的左节点不为空,就找该左节点最右的节点。对于节点1来说,他有左节点2,那么节点2的最右节点就是5
  2. 如果左节点为空,且目标节点是父节点的右节点,那么前驱节点为父节点。对于节点5来说,没有左节点,且是节点2的右节点,所以节点2是前驱节点
  3. 如果左节点为空,且目标节点是父节点的左节点,向上寻找到第一个是父节点的右节点的节点。对于节点6来说,没有左节点,且是节点3的左节点,所以向上寻找到节点1,发现节点3是节点1的右节点,所以节点1是节点6的前驱节点

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function predecessor(node){
if(!node) rteurn;
// 结论1
if(node.left){
return getRight(node.left);
}else{
let parent = node.parent;
// 结论23的判断
while(parent && parent.right === node){
node = parent;
parent = node.parent;
}
retrn parent;
}
}

function getRight(node){
if(!node) return;
node = node.right;
while(node) node = node.right;
return node;
}

后继节点

对于节点2来说,他的后继节点就是5,按照中序遍历原则,可以得出以下结论

  1. 如果有右节点,就找到该右节点的最左节点。对于节点1来说,他有右节点3,那么节点3的最左节点就是6
  2. 如果没有右节点,就向上遍历直到找到一个节点是父节点的左节点。对于节点5来说,没有右节点,就向上寻找到节点2,该节点是父节点1的左节点,所以节点1是后继节点

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function successor(node){
if(!node) return;
// 结论1
if(node.right){
return getLeft(node.right);
}else{
// 结论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;
}


动态规划

动态规划背后的基本思想非常简单,就是将一个问题拆分为子问题,一般来说这些子问题都是非常相似的,那么我们可以通过只解决一次每个子问题来达到减少计算量的目的。

一旦得出每个子问题的解,就存储该结果以便下次使用。

斐波那契数列

斐波那契数列就是从0和1开始,后面的数都是前两个数之和。
那么显而易见,我们可以通过递归的方式来完成求解斐波那契数列

1
2
3
4
5
function fib(n) {
if(n < 2 && n >= 0) return n;
return fib(n - 1) + fib(n - 2);
}
fib(10);

以上代码已经可以完美的解决问题,但是以上解法却存在很严重的性能问题,当n越大的时候,需要的时间是指数增长的,这时候就可以通过动态规划来解决这个问题。

动态规划的本质其实就两点

  1. 自底向上分解子问题
  2. 通过变量存储已经计算过的解

根据上面两点,斐波那契数列的动态规划思路也就出来了

  1. 斐波那契数列从0和1开始,那么这就是这个子问题的最底层
  2. 通过数组来存储每一位所对应的斐波那契数列的值
1
2
3
4
5
6
7
8
9
10
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 背包问题

该问题可以描述为:给定一组物品,没种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。每个问题只能放入至多一次。

假设我们有以下物品

物品ID/重量 价值
1 3
2 7
3 12

对于一个总容量为5的背包来说,我们可以放入重量2和3的物品来达到背包被的物品总价值最高。
对于这个问题来说,子问题就两个,分别是放物品和不放物品,可以通过以下表格来理解子问题

物品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

直接来分析能放三种物品的情况,也就是最后一行

  • 当容量少于3时,只取上一行对应的数据,因为当前容量不能容纳物品3
  • 当容量为3时,考虑两种情况,分别为放入物品3和不放物品3
    • 不放物品3的情况下,总价值为10
    • 放入物品3的情况下,总价值为12,所以应该放入物品3
  • 当容量为4时,考虑两种情况,分别为放入物品3和不放物品3
    • 不放物品3的情况下,总价值为10
    • 放入物品3的情况下,和放入物品1的价值相加,得出总价值为15,所以应该放入物品3
  • 当容量为5时,考虑两种情况,分别为放入物品3和不放物品3
    • 不放物品3的情况下,总价值为10
    • 放入物品3的情况下,和放入物品2的价值相加,得出总价值为19,所以应该放入物品3

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @param {*} w 物品重量
* @param {*} v 物品价值
* @param {*} c 总容量
* @returns
*/
function knapsack(w,v,c){
let length = w.length;
if(length === 0) return 0;

// 对照表格,生成的二维数组,第一维代表物品,第二维代表背包剩余容量
// 第二维中的元素代表背包物品总价值
let array = new Array(length).fill(new Array(c + 1).fill(null));

// 完成底部子问题的解
for(let i = 0; i <= c; i++){
// 对照表格第一行,array[0]代表物品1
// i代表剩余总容量
// 当剩余总容量大于物品1的重量时,记录下背包物品总价值,否则价值为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++){
// 这里求解子问题,分别为不放当前物品和放当前物品
// 先求不放当前物品的背包总价值,这里的值也就是对应表格中上一行对应的值
array[i][j] = array[i - 1][j];
// 判断当前剩余容量是否可以放入当前物品
if(j >= w[i]){
// 可以放入的话,就比大小
// 放入当前物品和不放入当前物品,哪个背包总价值大
array[i][j] = Math.max(array[i][j], v[i] + array[i -1][j - w[i]])
}
}
}
return array[length - 1][c];
}

最长递增子序列

这个问题的动态思路解法很简单,直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function lis(n) {
if(n.length === 0) return 0;
let array = new Array(n.length).fill(1);
for(let i = 1; i < n.length; 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;
}


字符串相关

在字符串相关的算法中,Trie树可以解决很多问题,同时又具备良好的空间和时间复杂度,比如以下问题

  • 词频统计
  • 前缀匹配
坚持原创技术分享,您的支持将鼓励我继续创作!