编程题

JS实现千分分隔符

方法1：自带函数 toLocaleString

方法2：正则

function numFormat(num){
    var res=num.toString().replace(/\d+/, function(n){ // 先提取整数部分
         return n.replace(/(\d)(?=(\d{3})+$)/g,function($1){
             console.log($1)
            return $1+",";
          });
    })
    return res;
  }
  
  var a=1234567894532;
  var b=673439.4542;
  console.log(numFormat(a)); // "1,234,567,894,532"

冒泡排序 n2 稳定

function bubbleSort(arr) {
    var len = arr.length;
    for(var i = 0;i < len;i++) {
        for(var j = 0;j < len-1-i;j++) {
            if(arr[j] > arr[j+1]) {// 相邻元素两两比较
                var temp = arr[j+1];// 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

快速排序 nlog2n 不稳定

主要思想：

找个中间数，将各个元素与之比较，小的放前面，大的放后面

对小的部分和大的部分重复上面步骤（递归）

function quick(arr){
    if(arr.length<=1){
        return arr
    }
    var midIndex=parseInt(arr.length/2)
    var mid=arr.splice(midIndex,1)[0]
    var left=[]
    var right=[]
    for(var i=0;i<arr.length;i++){
        if(arr[i]<=mid){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    return quick(left).concat(mid,quick(right))
}

插入排序 n2 稳定

每次将一个待排序的数字按其关键码的大小插入到一个已排好的有序序列中，直到全部数字排好序。

let arr =[12,8,25,16,1]
function bubble(arr){  
    arr2=[];
    arr2.push(arr[0])
    for(var i=1;i<arr.length;i++){
        let A=arr[i];
        for(var j=arr2.length;j>=0;j--){
            let B=arr2[j]
            if(A>B){
                arr2.splice(j+1,0,A)
                break;
            }
            if(j===0){
                arr2.unshift(A)
                // break;
            }
        }
    }
    return arr2
}

选择排序 n2 不稳定

其基本思想是：首先在待排序序列中选出最小值，存放在排序序列起始位置，然后再从剩余未排序元素中继续寻找最小元素，放到已排序序列末尾。以此类推，直到所有元素均排序完毕。

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for(var i = 0; i< len-1;i++){
        minIndex = i;
        for(var j = i+1;j<len;j++) {
            if(arr[j] < arr[minIndex]) {// 寻找最小的数
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

希尔排序

假设9个数

在第一轮组内排序，分组间隔为4

在第二轮组内排序，分组间隔为2

在第三轮组内排序，分组间隔为1（插入排序）

洗牌算法

var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
function shuffle (arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    // 生成 0 到 i 之间的随机整数
    var index = Math.floor(Math.random() * (i + 1));
    // 使用 ES6 中的解构赋值完成两个变量值的交换
    [arr[i], arr[index]] = [arr[index], arr[i]];
  }
  return arr;
}
console.log('Shuffled arr: ', shuffle(arr));

map和forEach区别

map可以用来遍历并返回一个由return值组成的新数组，forEach只用来遍历，返回值为undefined

let arr = [1, 2, 3];
let newArr = arr.forEach(function (item, index) {
  return item * item;
});
console.log(arr, newArr);// [ 1, 2, 3 ] undefined
 
arr = [1, 2, 3];
newArr = arr.map(function (item, index) {
  return item * item;
});
console.log(arr, newArr);// [ 1, 2, 3 ] [ 1, 4, 9 ]

promise实现打印红绿灯，循环3次

function timeout(timer){
    return function(){
     return new Promise(function(resolve,reject){ 
        setTimeout(resolve,timer)
     }) 
    }
}

var green=timeout(1000)
var yellow=timeout(1000)
var red=timeout(1000)

var n=0
function restart(){
    n++
    console.log('green')
    green()
    .then(function(){
        console.log('yellow')
        return yellow()
    })
    .then(function(){
        console.log('red')
        return red()
    }).then(function(){
        if(n<3){
            restart()
        }
    })
}
restart()

Promise.all题目

公司放映系统最近要上线一个『预定随机推荐电影』功能，每天用户通过系统预定名额，由系统每日推荐一部电影，按时推送到用户。现在，在系统已有如下异步方法封装的前提下 • getTodayUsers ( callback ): 获取今日预定的用户id列表，使用如下 getTodyUsers(userIds=>{ console.log(userIds )}), 即回调中拿到用户id列表 • getTodayMovie(callback): 获取今日推荐的电影id, 使用如下 getTodayMovie( movieId=> {console.log(movieId )}) ，即回调中拿到今日的电影id • bookMovieForUsers(userIds, movieId, callback): 使用用户id列表预定某部电影，使用如下bookMovieForUsers([1,2,3], 1000, ()=>{console.log(‘预定成功了')}) 请封装一个bookTodayMovieForTodayUser()的方法，它的作用是为今天预定的用户订阅今天系统推荐的电影。它返回一个promise, 这个promise在请求后被resolve. 使用方式如下 bookTodayMovieForTodayUser().then( ()=> console.log('预定成功’) ) 注: 简单起见，所有情况都不需要考虑失败情况

function bookTodayMovieForTodayUser(){
    let m=new Promise((resolve,reject)=>{
        getTodyUsers(userIds=>{
            resolve(userIds)
        })
    })
    let n=new Promise((resolve,reject)=>{
        getTodayMovie(movieId=>{
            resolve(movieId)
        })
    })
    return new Promise.all([m,n]).then((result)=>{
        bookMovieForUsers(...result,resolve)
    })
}

BFS与DFS

广度优先搜索（BFS）

简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。

深度优先搜索（DFS）

深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标

请实现一个简单的事件机制，能够实现对事件的触发和监听。

如：EventEmitter.on(); EventEmitter.trigger();

const EventEmitter = {
    on:function(type,handle){
        //创建一个缓存
        this.cache = {};
        console.log(this);
        //判断是否有这个类型的事件
        if(!this.cache[type]){
            //没有则创建一个
            this.cache[type] = [handle];
        }else{
            //已经存在就推入
            this.cache[type].push(handle);
        }
    },
    trigger:function(type){
        //判断是否传入了参数，如果传入了就把它填进一个数组中
        var params = arguments.length > 1 ? Array.prototype.slice.call(arguments, 1) : [];
        if(this.cache[type]){
            this.cache[type].forEach(item => {
                //执行函数，并将参数传入
                item(params);
            })
        }
    }
}

递归嵌套对象（shopee真题）

var data={
    company:{
        name:"shopee",
        location:{
            country:"China",
            city:"SZ"
        }
    },
    industry:"XXX"
}

let arr=['company','location','city']


var i=0
function fn(data,arr,i){
    for(let item in data){ 
        // console.log(data[item])
        if(item.toString()===arr[i]){
            if((typeof data[item])!=='object'){
                // console.log(data[item])
                return data[item]             
            }else{
                // console.log(data[item])
                return fn(data[item],arr,i+1)
            }
        }
    }
}
console.log(fn(data,arr,i))

时间戳格式转换

function timestampToTime(timestamp) {
    var date = new Date(timestamp * 1000);//时间戳为10位需*1000，时间戳为13位的话不需乘1000
    var Y = date.getFullYear() + '-';
    var M = (date.getMonth() + 1 < 10 ? '0' + (date.getMonth() + 1) : date.getMonth() + 1) + '-';
    var D = date.getDate() + ' ';
    var h = date.getHours() + ':';
    var m = date.getMinutes() + ':';
    var s = date.getSeconds();
    return Y + M + D + h + m + s;
}
// 注:时间戳转时间（ios手机NaN）
function getTime(nS) {
    var date=new Date(parseInt(nS)* 1000);
    var year=date.getFullYear();
    var mon = date.getMonth()+1;
    var day = date.getDate();
    var hours = date.getHours();
    var minu = date.getMinutes();
    var sec = date.getSeconds();

    return year+'/'+mon+'/'+day+' '+hours+':'+minu+':'+sec;
}

大数相加(有赞面试)

我们要用字符串来表示数据！

let a = "9007199254740991";
let b = "1234567899999999999";

function add(a ,b){
   //取两个数字的最大长度
   let maxLength = Math.max(a.length, b.length);
   //用0去补齐长度
   a = a.padStart(maxLength , 0);//"0009007199254740991"
   b = b.padStart(maxLength , 0);//"1234567899999999999"
   //定义加法过程中需要用到的变量
   let t = 0;
   let f = 0;   //"进位"
   let sum = "";
   for(let i=maxLength-1 ; i>=0 ; i--){
      t = parseInt(a[i]) + parseInt(b[i]) + f;
      f = Math.floor(t/10);
      sum = t%10 + sum;
   }
   if(f == 1){
      sum = "1" + sum;
   }
   return sum;
}