【手撕代码6】常考

快排

• 快排思想：在数据集之中，选择一个元素作为"基准"（pivot）。
  所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
  对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
• 如何选枢纽：

1. 在当前数组中随机一个

2. 在当前数组的第一个元素，中间的元素，最后的元素中挑大小居中的那一个。

这样就可以有效避免每次都挑一个最小（大）的元素了

var quickSort = function(arr) {

　　if (arr.length <= 1) { return arr; }

　　var pivotIndex = Math.floor(arr.length / 2);

　　var pivot = arr.splice(pivotIndex, 1)[0];

　　var left = [];

　　var right = [];

　　for (var i = 0; i < arr.length; i++){

　　　　if (arr[i] < pivot) {

　　　　　　left.push(arr[i]);

　　　　} else {

　　　　　　right.push(arr[i]);

　　　　}

　　}

　　return quickSort(left).concat([pivot], quickSort(right));

};

回文串判断

• 如果一个字符串忽略标点符号、大小写和空格，正着读和反着读一模一样，那么这个字符串就是palindrome(回文)

function palindrome(str){
  var reg = /[W_]/g;
  var lowerStr=str.toLowerCase().replace(reg,function(res){
    return "";
  });
  if(lowerStr.length===0){
    return true;
  }
  if(lowerStr[0]!==lowerStr[lowerStr.length-1]){
    return false;
  }else{
    return palindrome(lowerStr.slice(1,lowerStr.length-1));
  }
  
}
var str="aabbAA";
console.log(palindrome(str));

翻转字符串算法

function reverseString(str){
  var tmp="";
  for(var i=str.length-1;i>=0;i--){
    tmp+=str.charAt(i);
  }
  return tmp;
}
var str="aaahhhgggss";
console.log(reverseString(str));

展平数组

• es10 flat（1）展开一层，flat（2）展开两层

[1,[2,3,[4,5]],[3,4,[4,5,[3,4]]]].flat(2)

• es6（some+...)

function faltten(arr){
  while(arr.some(item=>Array.isArray(item))){
    arr=[].concat(...arr);
  }
  return arr;
}
console.log(faltten([2,3,[3,4,[5,5,5]]]));

• ...展开一层

[].concat(...[2,3,[3,4,[5,5,5]],[2,[3,4,[5,6]]]]

• reduce+concat

function faltten(arr){
 return arr.reduce((pre,now)=>{
   return pre.concat(Array.isArray(now)?faltten(now):now);
 },[])
}

reduce实现map

• map() 方法返回一个新数组，数组中的元素为原始数组元素调用函数处理后的值。

  • map() 方法按照原始数组元素顺序依次处理元素。

  • 注意： map() 不会对空数组进行检测。

  • 注意： map() 不会改变原始数组。

  • array.map(function(currentValue,index,arr), thisValue)

  • thisValue：对象作为该执行回调时使用，传递给函数，用作 "this" 的值。如果省略了 thisValue，或者传入 null、undefined，那么回调函数的 this 为全局对象。（如果用箭头函数则绑定无效）

• array.reduce(function(total, currentValue, currentIndex, arr), initialValue)

Array.prototype.fakeMap=function(fn,context){
  if(typeof fn!=="function"){
    throw new TypeError( fn+"is not a function");
  }
  let arr = this;
  if(!Array.isArray(arr)){
    throw new TypeError('list must be a Array');
  }
  if(arr.length==0){
    return [];
  }
  return arr.reduce((total,value,index)=>{
    total.push(fn.call(context,value,index,arr));
    return total;
  },[])
}
let arr = [1,2,3];
let obj={a:1}
// let newarr=arr.fakeMap((item, index, arr) => item+1);
let mya=arr.fakeMap(function(){
  console.log(this.a)
},obj);
// console.log(newarr);

字符串中出现最多次的字符

var str="asjfhsdhdkghdnmjhsafjhsf";
function findMaxCount(str){
  var obj={};
  for(let i=0;i<str.length;i++){
    if(obj[str.charAt(i)]){
      obj[str.charAt(i)]++;
    }else{
      obj[str.charAt(i)]=1;
    }
  }
  let num=0;
  let char="";
  for(var key in obj){
    if(obj[key]>num){
      num=obj[key];
      char=key;
    }
  }
  console.log("出现最多次数的是:"+char+",出现了:"+num+"次")
}
findMaxCount(str);

有多个is，怎么把is只剩一个

var str="hhishhisisishhh";
function deleteIs(str){
  var flag=true;
  tmp=str.replace(/is/g,function(item){
    if(flag){
      flag=false;
      return item;
    }else{
      return "";
    }
  })
  console.log(tmp);
}
deleteIs(str);