4. 最长公共子序列(LCS动态规划)
// dp[i][j] 计算去最大长度，记住口诀：相等左上角加一，不等取上或左最大值function LCS(str1, str2){ var rows = str1.split("") rows.unshift("") var cols = str2.split("") cols.unshift("") var m = rows.length var n = cols.length var dp = [] for(var i = 0; i < m; i++){ dp[i] = [] for(var j = 0; j < n; j++){ if(i === 0 || j === 0){ dp[i][j] = 0 continue } if(rows[i] === cols[j]){ dp[i][j] = dp[i-1][j-1] + 1 //对角＋1 }else{ dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) //对左边，上边取最大 } } console.log(dp[i].join(""))//调试 } return dp[i-1][j-1] }//!!!如果它来自左上角加一，则是子序列，否则向左或上回退。//findValue过程，其实就是和 就是把T[i][j]的计算反过来。// 求最长子序列function findValue(input1,input2,n1,n2,T){ var i = n1-1,j=n2-1; var result = [];//结果保存在数组中 console.log(i); console.log(j); while(i>0 && j>0){ if(input1[i] == input2[j]){ result.unshift(input1[i]); i--; j--; }else{ //向左或向上回退 if(T[i-1][j]>T[i][j-1]){ //向上回退 i--; }else{ //向左回退 j--; } } } console.log(result);}5. 数组去重，多种方法
双for循环, splice剔除并i--回退
indexOf等于index
filter indexOf === index
新数组indexOf === index
使用空对象等
6. 实现一个函数功能：sum(1,2,3,4..n)转化为 sum(1)(2)(3)(4)…(n)
// 使用柯里化 + 递归function curry ( fn ) { var c = (...arg) => (fn.length === arg.length) ? fn (...arg) : (...arg1) => c(...arg, ...arg1) return c}7. 反转二叉树
var invertTree = function (root) { if (root !== null) { [root.left, root.right] = [root.right, root.left] invertTree(root.left) invertTree(root.right) } return root}8. 贪心算法解决背包问题
var items = [\'A\',\'B\',\'C\',\'D\']var values = [50,220,60,60]var weights = [5,20,10,12]var capacity = 32 //背包容积 greedy(values, weights, capacity) // 320 function greedy(values, weights, capacity) { var result = 0 var rest = capacity var sortArray = [] var num = 0 values.forEach((v, i) => { sortArray.push({ value: v, weight: weights[i], ratio: v / weights[i] }) }) sortArray.sort((a, b) => b.ratio - a.ratio) sortArray.forEach((v, i) => { num = parseInt(rest / v.weight) rest -= num * v.weight result += num * v.value }) return result }9. 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
function FindNumbersWithSum(array, sum){ var index = 0 for (var i = 0; i < array.length - 1 && array[i] < sum / 2; i++) { for (var j = i + 1; j < array.length; j++) { if (array[i] + array[j] === sum) return [array[i], array[j]] } //index = array.indexOf(sum - array[i], i + 1) // if (index !== -1) { // return [array[i], array[index]] //} } return []10. 二叉树各种(层序)遍历
深度广度遍历
// 根据前序和中序重建二叉树/* function TreeNode(x) { this.val = x; this.left = null; this.right = null;} */function reConstructBinaryTree(pre, vin){ var result = null if (pre.length === 1) { result = { val: pre[0], left: null, right: null } } else if (pre.length > 1) { var root = pre[0] var vinRootIndex = vin.indexOf(root) var vinLeft = vin.slice(0, vinRootIndex) var vinRight = vin.slice(vinRootIndex + 1, vin.length) pre.shift() var preLeft = pre.slice(0, vinLeft.length) var preRight = pre.slice(vinLeft.length, pre.length) result = { val: root, left: reConstructBinaryTree(preLeft, vinLeft), right: reConstructBinaryTree(preRight, vinRight) } } return result} // 递归// 前序遍历function prevTraverse (node) { if (node === null) return; console.log(node.data); prevTraverse(node.left); prevTraverse(node.right);} // 中序遍历function middleTraverse (node) { if (node === null) return; middleTraverse(node.left); console.log(node.data); middleTraverse(node.right);} // 后序遍历function lastTraverse (node) { if (node === null) return; lastTraverse(node.left); lastTraverse(node.right); console.log(node.data);} // 非递归// 前序遍历function preTraverse(tree) { var arr = [], node = null arr.unshift(tree) while (arr.length) { node = arr.shift() console.log(node.root) if (node.right) arr.unshift(node.right) if (node.left) arr.unshift(node.left) } } // 中序遍历function middleTraverseUnRecursion (root) { let arr = [], node = root; while (arr.length !== 0 || node !== null) { if (node === null) { node = arr.shift(); console.log(node.data); node = node.right; } else { arr.unshift(node); node = node.left; } } } // 广度优先-层序遍历// 递归var result = []var stack = [tree]var count = 0var bfs = function () { var node = stack[count] if (node) { result.push(node.value) if (node.left) stack.push(node.left) if (node.right) stack.push(node.right) count++ bfs() }}bfs()console.log(result)// 非递归function bfs (node) { var result = [] var queue = [] queue.push(node) while (queue.length) { node = queue.shift() result.push(node.value) node.left && queue.push(node.left) node.right && queue.push(node.right) } return result}