月度存档: 二月 2019

五种常见的算法模版

//循环
function loop(a, b, c) {
	// 终止条件
	if(a===xxx){
		return
	}

	doSomething(a, b, c);

	loop(a+1, b, c);

	reverse_state(a, b, c) //还原状态
}

//深度优先搜索
const visited = new Set();   //利用visited记忆化,防止重复计算
function DFS(node, a, b) {
	visited.add(node);
	doSomething(node, b, c);

	for(let i = 0; i<node.children.length; i++) {
		if(!visited.has(node.children[i])){
			DFS(node.children[i], a, b)
		}
	}

	reverse_state(node, b, c) //还原状态
}

//广度优先搜索
function BFS(root, a, b) {
	// 设置缓存队列
	const quene = [];
	quene.push(root);

	while(queue.length>0){
		let node = queue.pop();
		doSomething(_node, b, c);

		for(let i = 0; i<node.children.length; i++) {
			quene.push(node.children[i]);
		}
	}
}

//二分搜索
function binarySearch(array, target) {
		let left = 0;
		let right = array.length-1;

		while(left<=right){
			let mid = Math.floor((right + left)/2);
			if(array[mid] === target){
				//找到了
				return xx;
			}else if(target<array[mid]){
				right = mid-1; //左右边界调整
			}else{
				left = mid+1;
			}
		}

		return -1;
}

//DP
function DP(a, b, c){
	//定义DP[i]的含义,这里有可能是多维数组
	let DP = [];

	//设置DP[0]的值
	DP[0] = xxx;

	//这里可能是多重循环
	for(let i = 1; i<something; i++) {
		DP[i] = doSomething(DP[i-$])  //按照实际情况写出递推公式
	}

	return DP[i] //结果一般存在最后一个数组或第一个
}