关于javascript:算法分治法贪心算法动态规划

分治法

相似动静布局

1. 明确设定一条基线
2. 依据这条基线能够不停的将问题合成，直到所有内容合乎基线规范

// 疾速排序
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
]

贪婪算法

1. 利益最大化 始终查找最大的我的项目，尽可能快满足需要
2. 何时实用贪心：须要查找最大我的项目等类型，同时满足利益最大化

// 给定一个整数数组 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
}