algorithm
Adrian Yang
Front End Engineer算法
两数之和
var nums = [2, 7, 11, 15];var target = 26;var twoSum = function (nums, target) { var box = new Map(); for (var i =0; i < nums.length; i++){ if(box[target - nums[i]] >= 0){ return [box[target - nums[i]], i] } box[nums[i]] = i; }}递归
1-10的和
function sum(n){ if(n > 10) return 0 return n+sum(n+1);}
let total = sum(1);console.log(total);细胞分裂
一个细胞 一个小时分裂一次 生命周期是三个小时 求 n小时后容器内 有多少个细胞?
// 黄色细胞由绿色细胞决定 绿色细胞由白色细胞决定// 最新的白色细胞 可能由 白色 绿色 黄色来决定.function total(n){ var yellow = function(n){ if(n === 0 || n === 1){return 0}; return green(n - 1); } var green = function(n){ if(n === 0){return 0}; return white(n - 1); } var white = function(n){ if(n === 0){return 1}; return white(n - 1) + green(n - 1) + yellow(n - 1); } return yellow(n) + green(n) + white(n);}排序算法
数组常用的api
spliece 实现数组增删改@params spliece.(n,m) 从索引n 开始删除m个元素, 若m 不写 是直接删除到末尾@return 返回删除的部分
push 向末尾追加popunshift 向开头追加concat 数组拼接sort 数组排序 return a-b 进行升序排序冒泡排序 Bubble
数组的当前项 与 后一项进行比较, 若后一项大 则交换位置一共比较 length-1 轮, 每一次都可以有一个最大数放到末尾 最多比较次数一共为 两者交换 解构赋值 [a,b] = [b,a]
function bubble(arr) { let temp = null; //外层循环控制比较轮数 for (var i = 0; i < arr.length-1; i++) { for (var j = 0; j < arr.length-i-1; i++) { // 里层循环控制每一轮比较次数 if (arr[j] > arr[j+1]) { temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] =temp; //[arr[j],arr[j+1]] = [arr[j+1],arr[j]] } } } return arr;}// O(n^2)插入排序
// 准备一个新数组, 用来存储抓到手里的牌, 开始先抓一张牌 let handel = []; handle.push(arr[0]);
// 从第二项开始一次抓牌, 直到把台面上的牌都抓光 for(let i =1; i < arr.length; i++){ //A 是新抓的牌 let A = arr[i]; // 和 HANDLE 中的牌依次比较 for(let j = handle.length-1; j>=0; j--){ // 每一次比较手中的牌 let B = handle[j]; // 如果当前 新牌A 比 被比较的牌B大了 将A 放到B 的后面 if(A > B){ handle,splice(j+1,0,A) break; } if(j === 0){ handel.unshift(A); // 已经比到第一项, 我们把新牌放到手中最前面即可. } } } return handle;}// O(n^2)快速排序 quick
找到中间项, 将它从运来的数组中移除, 同时获得这一项的结果让每一项 与 中间项比较, 比它小的放在左边 大的放在右边function quick(arr){ //结束递归 当 arr 小于等于 一项,则不用处理 if(ary.length <= 1){ return arr; } // 1. 找到数组的中间项,在原有的数组中把它移除 let middleIndex = Math.floor(arr.length/2); let middleValue = arr.splice(middleIndex,1)[0];
// 2. 准备左右两个数组,循环剩下数组中的每一项,比当前小的放在左边数组中,反之放到右边的数组中 let arrLeft = []; arrRight = []; for(let i=0; i < arr.length; i++){ let item = arr[i]; item < middleValue ? arrLeft.push(item) : arrRight.push(item); } // 3. 递归的方式让左右两边的数组持续这样处理, 一直到左右两边都排好序为止。 最后进行 左边 + 中间 +右边 拼接成最后结果 return quick(arrLeft).concat(middleValue,quick(arrRight))}//O(nlogn)选择排序
O(n²)
归并排序
O(nlogn)
希尔排序
O(nlogn)
堆排序
O(nlogn)
计数排序
O(n+k)
桶排序
基数排序
O(N*M)
数组去重
unserscore 库 中的 _.uniq()
直接使用set
var result = [... new Set(arr)]之前没有的元素 push 进新数组
var arr = [1,1,2,3]function unique(arr) function unique(arr) { if (!Array.isArray(arr)) { console.log('type error!') return } var array =[]; for(var i = 0; i < arr.length; i++) { if( !array.includes( arr[i]) ) {//includes 检测数组是否有某个值 array.push(arr[i]); } } return array or arr.foreach(item=>{ if(result.indexOf(item) === -1) return array.push(item) })
}使用filter
function unique(arr) { return arr.filter(function(item, index, arr) {//indexOf()方法返回在数组中可以找到一个给定元素的第一个索引,如果不存在,则返回-1。 //当前元素,在原始数组中的第一个索引==当前索引值,否则返回当前元素 return arr.indexOf(item, 0) === index; });
使用 reduce
function unique(arr) { var result = arr.reduce((pre,item)=>{ return pre.includes(item) ? pre : [...pre,item] }) });
利用属性的唯一值
function getUniqueArray(){ var result = {}
arr.foreach((item,index)=>{ result[arr[index]] = 'sss'; })
result = Objects.keys(result).map(item => ~~item) //字符串转换成数字 console.log(result);}使用双重循环
function unique(arr){ for(var i=0; i<arr.length; i++){ for(var j=i+1; j<arr.length; j++){ if(arr[i]==arr[j]){ arr.splice(j,1); j--; } } }return arr;}sort 进行排序 比较相邻两个数的数值
function getUniqueArray(){ var result = [] var temp = arr.sort(); for (var i = 0 ; i < temp.length; i--) { if(temp[i] !=== temp[i+1]){ result.push(arr[i]) } }}随机交换数组内的元素(洗牌法)
function randomsort(arr){ var temp, leng = arr.length, tempindex; for(var i = 0; i < leng; i++){ tempindex = Math.floor(Math.random()*(leng - i) + i); temp = arr[i]; arr[i] = arr[tempindex]; arr[tempindex] = temp; } return arr;}