简单算法
斐波那契数列
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1, F(N) = F(N - 1) + F(N - 2), 其中 N > 1，给定 N，计算 F(N)。
function fib(N) {
// 若 N <= 1，则返回 N
if (N <= 1) {
return N;
}
// 若 N == 2，则返回 fib(2-1) + fib(2-2) = 1
if (N == 2) {
return 1;
}
// 至少需要三个变量存储 fib(N), fib(N-1) 和 fib(N-2)。
let current = 0;
// 代表 fib(N)
let prev1 = 1;
// 代表fib(N-1)
let prev2 = 1;
// 代表 fib(N-2)for (let i = 3;
i <= N;
i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
时间复杂度：O(N)。
空间复杂度：O(1)，仅仅使用了 current，prev1，prev2。
冒泡排序 基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
每一趟遍历，将一个最大的数移到序列末尾（比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换）。
文章图片
function bubbleSort(arr) {
if (!arr || !arr.length) {
return []
}
// 外部的循环控制所有回合
for (let i = 0;
i < arr.length - 1;
i++) {
// 内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换
for (let j = 0;
j < arr.length - i - 1;
j++) {
if (arr[j] > arr[j+1]) {
const temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
}
}
}
}
优化版本：
/*
* 如果有 100 个数的数组，仅前面 10 个无序，后面 90 个都已排好序且都大于前面 10 个数字，那么在第一趟遍历后，
* 最后发生交换的位置必定小于 10，且这个位置之后的数据必定已经有序了，
* 记录下这个位置，第二次只要从数组头部遍历到这个位置就可以了
*/
function bubbleSort(arr) {
if (!arr || !arr.length) {
return []
}
let flag = arr.length
while(flag) {
let n = flag
flag = 0
for (let i = 1;
i < n;
i++) {
if (arr[i - 1] > arr[i]) {
let temp = arr[i]
arr[i] = arr[i - 1]
arr[i - 1] = temp
flag = i
}
}
}
}
插入排序 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
文章图片
function insertSort(arr) {
// let len = arr.length;
for (let i = 1;
i < arr.length;
i++) {
// 将 arr[i] 插入到有序队列（arr[0] —— arr[i-1]）中
for (let j = i - 1;
j >= 0 && arr[j] > arr[j + 1];
j--) {
let temp = arr[j + 1]
arr[j + 1] = arr[j]
arr[j] = temp
}
}
return arr;
}
快速排序 快速排序每一趟排序，都会寻找一个基准元素，有的采用第一个元素，有的会随机生成一个，但是基本思想是不变的，一趟排序结束，会形成以基准元素为分界点的两部分，其中左边比基准元素小（假设从小到大排序），右边比基准元素大。然后再以相同的方法处理左边和右边两部分，即递归。
文章图片
function quickSort(arr, left, right) {
left = typeof left === 'number' ? left : 0
right = typeof right === 'number' ? right : arr.length - 1if (left < right) {
const partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex - 1)
quickSort(arr, partitionIndex + 1, right)
}return arr
}
// 分区操作，设定基准值（pivot）
function partition(arr, left, right) {
let pivot = left
let index = pivot + 1
for (let i = index;
i <= right;
i++) {
if (arr[i] < arr[pivot]) {
[ arr[i], arr[index] ] = [ arr[index], arr[i] ]
index++
}
}
[ arr[pivot], arr[index - 1] ] = [ arr[index - 1], arr[pivot] ]
return index - 1
}
归并排序（Merge Sort） 分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
文章图片
function mergeSort(arr) {
const len = arr.length;
if (len < 2) {
return arr;
}
const middle = Math.floor(len / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return mergeArr(mergeSort(left), mergeSort(right));
}function mergeArr(left, right) {
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}while (left.length) {
result.push(left.shift());
}while (right.length) {
result.push(right.shift());
}return result;
}
打乱数组 打乱一个没有重复元素的数组
洗牌算法：从最后一个元素开始，从数组中随机选出一个位置，交换，直到第一个元素。
class Disorder {
constructor(arr) {
this.originArr = [ ...arr ]
}reset() {
return this.originArr
}shuffle() {
const shuffleArr = [ ...this.originArr ]
let curLen = shuffleArr.length - 1
while (curLen > -1) {
// 生成一个范围在当前下标到数组末尾元素下标之间的随机整数
const random = Math.floor(shuffleArr.length * Math.random())
console.log(random);
// 将当前元素和随机选出的下标所指的元素互相交换
[ shuffleArr[curLen], shuffleArr[random] ] = [ shuffleArr[random], shuffleArr[curLen] ]
curLen--
}
return shuffleArr
}
}var obj = new Disorder([ 1, 4, 8, 9 ])
console.log(obj.shuffle());
console.log(obj.reset());
二叉树的最大深度 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
function TreeDepth(pRoot) {
if (!pRoot) {
return 0;
}
let left = TreeDepth(pRoot.left);
let right = TreeDepth(pRoot.right);
return Math.max(left, right) + 1;
}
二叉树的镜像 操作给定的二叉树，将其变换为源二叉树的镜像。
function Mirror(pRoot) {
if (!pRoot) {
return null
}
let temp = pRoot.left
pRoot.left = pRoot.right
pRoot.left = tempMirror(pRoot.left)
Mirror(pRoot.right)return pRoot
}
树的子结构 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
// 比较两棵树是否相同
function compTree(root1, root2) {
if (!root2) {
return true
}
if (!root1) {
return false
}
if (root1.val !== root2.val) {
return false
}
return compTree(root1.left, root2.left) && compTree(root1.right, root2.right)
}// 判断是否子结构
function HasSubtree(pRoot1, pRoot2) {
if (!pRoot1 || !pRoot2) {
return false
}
if (!compTree(pRoot1, pRoot2)) {
return HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2)
}
return true
}
给一个嵌套对象，返回展平对象（属性为 a.b.c）
const obj = {
a: 'a',
b: [1, 2],
c: true,
d: function() { console.log('d') },
e:{
a: 'a-e',
b: [1, 2, 3],
c: false,
d: function() { console.log('e-d') },
f:{
a: 'a-f',
b: [1, 2, 4],
c: true,
d: function() { console.log('f-d') },
}
}
}function flatObj (data) {
if (!data || data.constructor !== Object) {
return {}
}
const obj = {}
function flat(data, baseKey) {
// for...in 会遍历原型链上所有属性，不推荐使用
Object.keys(data).forEach(key => {
const value = https://www.it610.com/article/data[key];
const finalKey = baseKey ? `${baseKey}.${key}` : key;
if (value.constructor === Object) {
flat(value, finalKey);
} else {
obj[finalKey] = value;
}
})
return obj
}
return flat(data);
}const data = flatObj(obj)
data.d()
data['e.d']()
data['e.f.d']()
计算一个有序数组中，某个数字出现的次数
- 方法1：用两个循环，一个从头找一个从尾找，找到第一次出现的位置和最后一次出现的位置。再相减即可。
function GetNumberOfK(data, k) {
var start = -1
var end = -1
for (var i = 0;
i < data.length;
i++) {
if (data[i] == k) {
start = i;
break
}
}
for (var j = data.length - 1;
j > -1;
j--) {
if (data[j] == k) {
end = j
break
}
}
if (start != -1 && end != -1) {
return end - start + 1;
} else {
return 0
}
}
- 方法2：
二分法，找到数字出现的第一次和最后一次。
function GetNumberOfK(data, k) {
if (data.length == 0) {
return 0;
}
var first = theFirst(data, 0, data.length - 1, k)
var last = theLast(data, first - 1, data.length - 1, k)
if (first != -1 && last != -1) {
return last - first + 1;
} else {
return 0;
}
}
// 找到第一次出现K的位置
function theFirst(data, start, end, k) {
if (start > end) {
return -1;
}
var mid = parseInt((start + end) / 2)
if (data[mid] > k) {
end = mid - 1;
return theFirst(data, start, end, k)
} else if (data[mid] < k) {
start = mid + 1
return theFirst(data, start, end, k)
}
// 还要多加一个判断如果mid-1也为k的话，说明第一次出现的位置还更小。
else if ((mid - 1 >= 0) && (data[mid - 1] == k)) {
return theFirst(data, start, mid - 1, k)
} else {
return mid;
}
}
// 找到最后一次出现K的位置
function theLast(data, start, end, k) {
if (start > end) {
return -1;
}
var mid = parseInt((start + end) / 2)
if (data[mid] > k) {
end = mid - 1;
return theLast(data, start, end, k)
} else if (data[mid] < k) {
start = mid + 1
return theLast(data, start, end, k)
}
// 还要多加一个判断如果mid+1也为k的话，说明最后一次出现的位置还更大。
else if ((mid + 1 < data.length) && (data[mid + 1] == k)) {
return theLast(data, mid + 1, end, k)
} else {
return mid;
}
}
其他排序见1
【简单算法】其他排序见2
其他算法见
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- 科学养胃，别被忽悠，其实真的很简单
- Guava|Guava RateLimiter与限流算法
- opencv|opencv C++模板匹配的简单实现
- Python基础|Python基础 - 练习1
- 松软可口易消化，无需烤箱超简单，新手麻麻也能轻松成功~
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 简单心理2019春A期+32+张荣
- 《算法》-图[有向图]