分治法
相似动静布局
- 明确设定一条基线
- 依据这条基线能够不停的将问题合成,直到所有内容合乎基线规范
// 疾速排序
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
}