js常用算法
2020-01-08 本文已影响0人
Viker_bar
算法基础知识
一 ：排序
//冒泡排序
function sort(arr){
if(arr.length <=1) return arrr;
for(var i=0;i<arrr.length;i++){
for(var j=0;j<arr.length;j++){
if(arr[i]>arr[j]){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
//快速排序
function quickSort(arr){
if(arr.length<=1) return arr;
var mid = ~~(arr.length/2),midVal = arr.splice(mid,1)[0],left = [],right = [];
arr.forEach(function(item){
item>midVal ? right.push(item) : left.push(item);
})
return quickSort(left).concat(midVal,quickSort(right));
}
二 ：去重
//去重
function dedupe(arr){
var obj = {},
result = [],
len = arr.length,
i=0;
for(;i<arr.length;i++){
if(!obj[arr[i]]){
obj[arr[i]] = 1;
result.push(arr[i]);
}
}
return result;
}
//去重
function dedupe(arr){
return Array.from(new Set(arr));
}
三：查找某项在数组中的索引值（二分查找）
function binary_search(arr, key) {
var low = 0, high = arr.length - 1;
while(low <= high){
var mid = parseInt(low + (high - low) / 2);
if(key === arr[mid]){
return mid;
} else if (key > arr[mid]){
low = mid + 1;
} else if (key < arr[mid]){
high = mid -1;
} else {
return -1;
}
}
};
var arr = [5,13,19,21,37,56,64,75,80,88,92];
var result = binary_search(arr, 21);
console.log(result);
四 ：广度与深度优先遍历
操作树型数据结构 链接
/*** 广度优先遍历 ***/
function findPathBFS(source, goal) {
// 深拷贝原始数据
var dataSource = JSON.parse(JSON.stringify(source))
var res = []
// 每一层的数据都 push 进 res
res.push(...dataSource)
// res 动态增加长度
for (var i = 0; i < res.length; i++) {
var curData = res[i]
// 匹配成功
if (curData.value === goal) {
var result = []
// 返回当前对象及其父节点所组成的结果
return (function findParent(data) {
result.unshift(data.key)
if (data.parent) return findParent(data.parent)
return result
})(curData)
}
// 如果有 children 则 push 进 res 中待搜索
if (curData.children) {
res.push(...curData.children.map(d => {
// 在每一个数据中增加 parent，为了记录路径使用
d.parent = curData
return d
}))
}
}
// 没有搜索到结果，默认返回空数组
return []
}
/*** 深度优先遍历 ***/
function findPathDFS(source, goal) {
// 因为会改变原数据，因此做深拷贝处理
var dataSource = JSON.parse(JSON.stringify(source))
var res = []
return (function dfs(data) {
res.push(data)
// 深度搜索一条数据，存取在数组 res 中
if (data.children) return dfs(data.children[0])
// 匹配成功
if (res[res.length - 1].value === goal) {
return res.map(r => r.key)
}
// 匹配失败则删掉当前比对的节点
res.pop()
// 没有匹配到任何值则 return，如果源数据有值则再次深度搜索
if (!res.length) return !!dataSource.length ? dfs(dataSource.shift()) : res
// 取得最后一个节点，待做再次匹配
var lastNode = res[res.length - 1]
// 删除已经匹配失败的节点（即为上面 res.pop() 的内容）
lastNode.children.shift()
// 没有 children 时
if (!lastNode.children.length) {
// 删除空 children，且此时需要深度搜索的为 res 的最后一个值
delete lastNode.children
return dfs(res.pop())
}
return dfs(lastNode.children[0])
})(dataSource.shift())
}
五 ：其它
//统计一个字符串出现最多的字母
function countChar(str){
return Array.prototype.reduce.call(str,function(pre,current){
if(pre[current]){
pre[current] ++;
}else{
pre[current ] = 1;
}
return pre;
},{});
}
function findMax(str){
let chars = countChar(str);
let max = 0;
let char = null;
for(let c in chars){
if(chars[c] > max){
max = chars[c];
char = c;
}
}
return {
"char" : char, //字母
"num" : max //出现的次数
};
}
//深拷贝
function deepClone(origin,target) { //origin是被克隆对象，target是目标对象
var target = target || {};
for(var key in origin) {
if(origin.hasOwnProperty(key)) {
if(Array.isArray(origin[key])) { //如果是数组
target[key] = [];
deepClone(origin[key],target[key])
} else if (typeof origin[key] === 'object' && origin[key] !== null) {
target[key] = {};
deepClone(origin[key],target[key])
} else {
target[key] = origin[key];
}
}
}
return target;
}
//Es6
function deepClone(val) {
return Array.isArray(val) ? Array.from(val, deepClone) : val;
}
//阶乘
function factorialize(n){
if(n <= 1 && n>0) return 1;
return n * factorialize(n-1)
}
/* 不借助临时变量，进行两个整数的交换*/
//方法一 ES6
var a = 1, b = 2;
[a,b] = [b,a];
console.log(a,b)
//方法二 算术运算
function swap(x , y) {
x=x+y; //x暂存两数之和
y=x-y; //y为两数之和减去y，即原来的x
x=x-y;
return [x,y];
}
//反转字符串
function reverseString(str){
return str.split("").reverse().join("");
}
//实现斐波那契数列
function fib(n){
return n < 2 ? 1 : (fib(n-1) + fib(n-2));
}
//速度创建1-100的数组
//Es5
var a = Array.prototype.map.call(Array(101).join('0').split(''), function() {
return arguments[1] + 1;
});
//Es6
let arr = Array.from(Array(100), (value, index) => index + 1);//from会将空位转成undefined
let arr = Array.from({length: 100}, (value, index) => index + 1);
//洗牌算法 and 打乱数组算法
function shuffle(arr){
let n = arr.length, random;
while(0!=n){
random = (Math.random() * n--) >>> 0; // 无符号右移位运算符向下取整
[arr[n], arr[random]] = [arr[random], arr[n]] // ES6的结构赋值实现变量互换
}
return arr;
}
//判断是否是回文
//回文( Palindromes )，在中文文当中是指倒着念和顺着念都是相同的，前后对称，
//例如“上海自来水来自海上”；
//在英文文当中是指正着看和反着看都相同的单词，例如“madam”；
//而对于数字，又称之为回文数，是指一个像“16461”这样的对称的数，
//即这个数的数字按相反的顺序重新排列后得到的数和原来的数一样
function palindRome(str){
var len = str.length;
var str1 = "";
for(var i=len-1; i>=0;i--){
str1+=str[i];
}
console.log(str1 == str)
};
//String indexOf的实现
function arrindexOf(a,b,n){
let arr1=Array.from(a);
let arr2=Array.from(b);
let i=n||0;
if(arr1.length>(arr2.length-n)){
return -1;
}
for(i;i<arr2.length;i++){
if(arr2[i]===arr1[0]){
for(let j=0;j<arr1.length;j++){
if(arr1[j]!==arr2[i+j]){
//这里当不匹配的时候需要重新从当前位置再次往后查找
arrindexOf.call(this,a,b,i+j);
}else if(j===arr1.length-1){
return i;
}
}
}
}
}
//Array indexOf的实现
function ArrayIndexOf(arr, value, n) {
var i = isNaN(n) ? 0 : n; //有第三参时
i = (i < 0) ? arr.length + i: i; //第三参为负数时
for (i; i < arr.length; i++) {
if (arr[i] === value) {
return i;
}
}
return - 1;
}
//实现抽奖功能？
//调用jqueryRotate.js插件来转动轮盘
//过程（https://juejin.im/post/5cf0804f518825332a1eff85）
1：生成一个权重相同的新数组
2：打乱数组
3：random随机数
