2020-09-24

算法模板

写在前面

  • 常见算法模板（自己总结，非官方）

数据结构

数组

链表

栈

队列

Hash

滑动窗口

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
function(s, t) {
  let need = new Map; // 需要凑齐的字符数
  let window = new Map; // 窗口中的字符数
  for (let i of t) {
    if (need.has(i)) need.set(i, need.get(i) + 1);
    else need.set(i, 1);
  }
  
  let left = 0, right = 0;
  let valid = 0; // 窗口中满足 need 条件的字符个数

  // 判断左侧窗口是否要收缩
  while (right < s.length) {
    let c = s[right]; // 即将移入窗口的字符
    right ++; // 右移窗口
    // 进行窗口内数据的一系列更新
    // ... some code

    // debug here ...

    // 判断左侧窗口是否要收缩
    while (valid === need.size) {
      let d = s[left]; // 即将移出窗口的字符
      left ++; // 左移窗口
      // 进行窗口内数据的一系列更新
      // ... some code
    }
  }
  return ...
};

树

前缀和

单调栈

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
// 84. 柱状图中最大的矩形
// 单调栈
var largestRectangleArea = function(heights) {
  let area = 0;
  let stack = [];
  let current = 0;
  heights = [0, ...heights, 0];
  while (current < heights.length) {
    // 栈不为空 且 当前元素 要 大于 栈顶元素
    // 才能被框住
    while(stack.length && heights[current] < heights[stack[stack.length - 1]]) {
      let h = heights[stack[stack.length - 1]];
      stack.pop();
      if (!stack.length) break;
      area = Math.max(area, (current - stack[stack.length - 1] - 1) * h)
    }
    stack.push(current);
    current ++;
  }
  return area;
};



let stack = [];
let current = 0;
while(current < nums.length) {
    // 这是单调递增栈，视情况而定，当前元素是否大于栈顶元素
    while(stack.length && nums[current] < nums[stack[stack.length -1]]) {
        let base = nums[stack[stack.length -1]];
        stack.pop();
        if (!stack.length) break;
        // some code ...
    }
    stack.push(current);
    current ++;
}

双指针

1
2
3
4
5
6
7
8
9
10
let max = 0;
for (let i = 0, j = nums.length - 1; i !== j; ) {
    max = Math.max(max, Math.min(nums[i], nums[j]) * (j - i)) ;
    if (nums[i] < nums[j]) {
        i ++;
    } else {
        j --;
    }
}
return max;

双指针暴力

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
39
40
var largestRectangleArea = function(heights) {
    if (!heights.length) return 0;
    let area = 0;
    for (let i = 0; i < heights.length; i ++) {
      let leftIndex = i;
      let rightIndex = i;
      let h = heights[i]; // 基准点，往前往后遍历求解
      while(heights[leftIndex - 1] >= h) {
        leftIndex --;
      }
      while(heights[rightIndex + 1] >= h) {
        rightIndex ++;
      }
      let distance = rightIndex - leftIndex + 1;
      area = Math.max(area, distance * h);
    }
    return area;
};


// let max = 0;
let leftMax = 0;
let rightMax = 0;
for (let i = 0, j = nums.length - 1; i !== j; ) {
    if (nums[i] < nums[j]) {
        if (leftMax < nums[i]) {
            leftMax = nums[i];
        } else {
            // some code ...
        }
        i ++;
    } else {
        if (rightMax < nums[j]) {
            rightMax = nums[j];
        } else {
            // some code ...
        }
        j --;
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function recursion(level, param1, param2, ...) {
	// recursion terminator
	if (level > MAX_LEVEL) {
		procrss_result;
		return ;
	}
	
	// process logic in current level
	process(level, data ... );
	
	// drill down
	recursion(level + 1, new param1, new param2, ... );
	
	// reverse the current level status if needed
}

分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function divideConquer(problem, param1, param2, ... ) {
	// recursion terminator
	if (!problem) {
		print_result;
		return ;
	}
	
	// prepare data
	data = prepareData(problem);
	subProblems = splitProblem(problem, data);
	
	// conquer subProblems
	subResult1 = divideConquer(subProblems[0], newParam1, new Param2, ... );
	subResult2 = divideConquer(subProblems[1], newParam1, new Param2, ... );
	subResult3 = divideConquer(subProblems[2], newParam1, new Param2, ... );
	...
	
	// process and generate the final result
	result = processResult(subResult1, subResult2, subResult3, ... );
	
	// revert the current level status
}

DFS + 回溯

tips: 基础类型不能代入到参数列表中，不会被改变

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function dfs(node) {
	if (node in visited) {
		// already visited
		return ;
	}
	
	visited.add(node);
	
	// process current node
	// ...
	// logic here
	
	dfs(node.left);
	dfs(node.right);
}

DFS 代码 - 递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const visited = new Set;

function dfs(node, visited) {
	if (node in visited) {
		// already visited
		return ;
	}	
	
	visited.add(node);
	
	// process current  node here
	...
	for (nextNode in node.children) {
		if (!nextNode in visited) {
			dfs(nextNode, visited);
		}
	}
}

DFS 代码 - 非递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function dfs(root) {
	if (!root) return [];
	const visited = new Set;
	const stack = [root];
	
	while (stack.length) {
		let node = stack.pop();
		visited.add(node);
		
		process(node);
		nodes = generateRelatedNodes(node);
		stack.push(nodes);
	}
	
	// other processing work
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function BFS(graph, start, end) {
	const queue = [];
	queue.push([start]);
	const visited = new Set;
	visited.add(start);
	
	while (queue.length) {
		let node = queue.shift();
		visited.add(node);
		
		process(node);
		nodes = generateRelatedNodes(node);
		queue.push(nodes);
	}
	
	// other processing work
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
let left = 0, right = arr.length - 1;

while (left < = right) {
	let mid = (left + right) / 2;
	if (arr[mid] === target) {
		// find the target
		break or return result;
	} else if (arr[mid] < target) {
		left = mid + 1;
	} else {
		right = mid - 1;
	}
}

组合

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
var combine = function (n, k) {
	let res = [];
	let start = 1, path = [];
	combineHelper(n, k, start, res, path);
	return res;
}
/**
 * 
 * @param {*} n 1 ... n 数组 1 ~ n
 * @param {*} k 取 k 个数
 * @param {*} start 从哪个开始取（不从数组下标0开始）
 * @param {*} res 结果集
 * @param {*} path 单个结果
 */
var combineHelper = function (n, k, start, res, path) {
	// recursion terminator
	if (path.length === k) {
		res.push(path.slice()); // 备份一份
	}
	
	// logic process
	for (let i = start; i <= n; i ++) { // 数组为 1 ～ n，所以终止条件 i <= n;（视情况而定）
		path.push(i); // 选
		// drill down
		combineHelper(n. k, i + 1, res, path);
		path.pop(); // 不选
	}
}

排列

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
39
40
var permute = function(nums) {
	let res = [];
	let path =[];
	let usedNum = {};
	permuteHelper(nums, res, path, usedNum);
	return res;
};

/**
 * 
 * @param {*} nums 用于排列的数组
 * @param {*} res 结果集
 * @param {*} path 单个结果
 * @param {*} usedNum 使用过的数字
 */
 
 

var permuteHelper = function(nums, res, path, usedNum) {
	// recursion terminator
	if (path.length === nums.length) {
    // 变量 path 所指向的列表 在深度优先遍历的过程中只有一份 ，深度优先遍历完成以后，回到了根结点，成为空列表。
		res.push(path.slice());
	}
	
	// current level logic 
	for (let i = 0; i < nums.length; i ++) {
		if (usedNum[nums[i]] !== void 0) {
			continue;
		}
		path.push(nums[i]); // 选中
		usedNum[nums[i]] = truel;
		
		// drill down
		permuteHelper(nums, res, path, usedNum);
		
		path.pop(); // 未选中
		usedNum[nums[i]] = false; // 撤销使用记录
	}
};
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
39
40
41
42

var permuteUnique = function(nums) {
  let res = [];
  let defaultNum = {};
  // 统计字符出现个数
  for (let i = 0; i < nums.length; i ++) {
    defaultNum[nums[i]] ? defaultNum[nums[i]] ++ : defaultNum[nums[i]] = 1;
  }
  let usedNum = {... defaultNum};
  nums = nums.sort();
  permuteUniqueHelper(nums, res, [], usedNum);
  return res;
};
/**
 * 
 * @param {*} nums 传入的可使用数组
 * @param {*} res 结果
 * @param {*} path 当前层结果
 * @param {*} usedNum 使用过的map
 */
var permuteUniqueHelper = function(nums, res, path, usedNum) {
  // recursion terminator
  if (path.length === nums.length) {
    res.push(path.slice());
    return ;
  }
  // current level logic
  for (let i = 0; i < nums.length; i ++) {
    if (nums[i - 1] == nums[i] && i - 1 >= 0 && usedNum[nums[i]]) { // 避免产生重复的排列
      continue;
    }
    if (usedNum[nums[i]] !== void 0 && usedNum[nums[i]] === 0) continue;
    usedNum[nums[i]] --; // 使用次数减一
    path.push(nums[i]);
    
    // drill down
    permuteUniqueHelper(nums, res, path, usedNum);
    
    path.pop();
    usedNum[nums[i]] ++; // 撤销使用记录 
  }
};

动态规划

博弈论

写在后面

  • 最新更新 2020-12-29
EllePeng

EllePeng

stay awesome.