算法（分治法、贪心算法、动态规划） javascript前端

分治法 【算法（分治法、贪心算法、动态规划）】类似动态规划

明确设定一条基线
根据这条基线可以不停的将问题分解，直到所有内容符合基线标准

// 快速排序 const quickSort = fucntion(arr) { if (arr.length <= 1) { return arr }// 1、找到基线，并对基线左右做声明 // 中间值下标 let pivotIndex = Math.floot(arr.length / 2) // 中间值 let pivot = arr.splice(pivotIndex, 1)[0] let left = [] let right = []// 2、遍历当前的内容，按照基线去划分左右 for (let i = 0; i < arr.length; i++) { if (arr[i] < pivot) { left.push(arr[i]) } else { right.push(arr[i]) } } // 3. 递归处理，不断根据新的基线生成新内容，并进行连接 return quickSort(left).concat([pivot], quickSort(right)) }

示例

let arr = [6, 3, 2, 6, 44, 1, 8, 10, 43, 1] let res = quickSort(arr)result: [ 1, 1,2,3,6, 6, 8, 10, 43, 44 ]

贪心算法

利益最大化始终查找最大的项目，尽可能快满足需求
何时适用贪婪：需要查找最大项目等类型，同时满足利益最大化

// 给定一个整数数组inputArr，找到一个具有最大和的连续子数组（子数组必须包含一个元素），返回其最大和 const maxSubArray = function(inputArr) { // 判断传入值 if (inputArr.length <= 1) return inputArr let rtnArr = inputArr[0] let sum = 0 for (const num of inputArr) { // 最快效率找到的就直接找连续的正整数子集，所以遇到负数就重新开始 if (sum > 0) { sum += num } else { sum = num } rtnArr = Math.max(rtnArr, sum) } }

动态规划

动态规划(何时使用动态规划) - 将待求解的问题分解成若干子问题；子问题之间相互有联系

// 斐波那契数列 const fib = function(n) { // 传入校验 if (n < 2) return n // 1、确定分界 let pre = 0 let next = 0 let res = 1 // 2、遍历所有内容进行运算执行 for (let i = 2; i <= n; i++) { // 往前移一位 pre = next next = res // 计算出第三位的熟 res = pre + next } return res }