美文网首页
每日一练 -- 简单的小笔试

每日一练 -- 简单的小笔试

作者: 宋乐怡 | 来源:发表于2020-02-24 23:37 被阅读0次

1.找出数组中重复次数最多的元素
2.返回字符串第一个重复字符
3.快排 O(nlogN)
4.二分查找 O(nlogN)
5.Fibonacci
6.解析URL参数
7.深度优先遍历O(N)
8.广度优先遍历O(N)
9.嵌套数组展开

1.找出数组中重复次数最多的元素

var arr = [1,2,2,1,1]
function highFrequency(arr){
    var most = 0, map = {}, res = -1;
    if(!arr.length){
        return
    }else if(arr.length == 1){
        return arr[0];
    }else{
        for(let i = 0 ; i<arr.length ; i++){
            map[arr[i]] ? map[arr[i]]++ : map[arr[i]] = 1;
            if(map[arr[i]] > most){
                most = map[arr[i]];
                res = arr[i];
            }
        }
    }
    console.log(res);
}
highFrequency(arr);

2.返回字符串第一个重复字符

function getFirstDouble(str){
    var anotherArr = [] , res = null;
    for(let i = 0; i<str.length ; i++){
        if(anotherArr.includes(str[i]) ){
            res = str[i] ;
             break;
        }else{
            anotherArr.push(str[i]);
        }
    }
    console.log(res)
}

3.快排 O(nlogN)

至于为什么没有用阮一峰老师的方法,那个方法被众人所诟病的原因一是没有使用最方便的下标取值,二是左右数组新开辟内存空间,多余。

var arr=[5,7,2,9,3,8,4,7,1];
// 每次选择最左边的数作为基数
function quickSort(arr){
  if (arr.length<2) { return arr; }
  // 定义左指针
  var left=0;
  // 定义右指针
  var right=arr.length-1;
  //开启每一轮的排序
  while(left<right){
    // 寻找右边比arr[0]小的数的下标
    while(arr[right]>=arr[0] && left<right){
      right=right-1;
    }
    // 寻找左边比arr[0]大的数的下标
    while(arr[left]<=arr[0] && left<right){
      left++;
    }
    //当左边指针与右边指针相遇后,交换arr[0]与当前两个指针所在的元素
    if (right==left) {
      let mid=arr[right];
      arr[right]=arr[0];
      arr[0]=mid;
      break;
    }
    // 当左指针小于右指针的位置,交换两个指针当前位置的元素
    let tem=arr[right];
    arr[right]=arr[left];
    arr[left]=tem;
  }
  //递归实现
  return quickSort(arr.slice(0,left)).concat(arr.slice(left,right+1)).concat(quickSort(arr.slice(right+1)));
}
//对数组进行排序
console.log(quickSort(arr));

4.二分查找 O(nlogN)

function binarySearch(arr,key){
    var low  = 0, high = arr.length - 1;
    while (low <= high){
        let mid = parseInt((low + high)/2);
        if(arr[mid] == key){
            return mid;
        }else if(key > arr[mid]){
            low = mid + 1;
        }else if(key < arr[mid]){
            high = mid - 1;
        }
    }
    return -1
}
var arr = [1,2,3,4,5,6,7,8,9,10];
console.log(binarySearch(arr,3));

5.Fibonacci

function fibonacci(n , ac1 = 1 , ac2 = 1){
    if(n <= 1){
        return ac2;
    }
    return fibonacci(n-1 , ac2 , ac1+ac2);
}
console.log(fibonacci(5))

6.解析URL参数

function getQueryStringArgs(){
    //取得查询字符串并去掉开头问号
    var qs = (location.search.length > 0 ? location.search.substring(1) : "");
    //保存数据的对象
    var args = {};
    //取得每一项
    var items = qs.length ? qs.split("&") : [];
    var item = null , name = null ,value = null;
    //在for循环中使用
    var i = 0 , len = items.length;
    //将每一项添加到args对象中
    for(i = 0 ; i < len ; i++){
        item = items[i].split('=');
        name = item.decodeURIComponent(item[0]);
        value = item.decodeURIComponent(item[1]);
        if(name.length){
            args[name] = value;
        }
    }
    return args;
}

7.深度优先遍历O(N)

//  递归方式
let deepTraversall = (node,nodeList=[]) => {
    if(node !=null){
        nodeList.push(node);
        let children = node.children;
        for(let i=0 ; i<children.length ; i++){
            deepTraversall(children[i],nodeList);
        }
    }
    return nodeList;
}
// 非递归
function deepTraversall(node){
    let nodes = [];
    if(node != null){
        let stack = [];
        stack.push(node);
        while(stack.length){
            let item = stack.shift();
            nodes.push(item);
            let children = item.children;
            for(let i=0 ; i<children.length ; i++){
                stack.push(children[i]);
            }
        }
    }
    return nodes;
}

8.广度优先遍历O(N)

// 非递归
function widthTraversal(node){
    var nodes = [];
    if(node){
        var queue = [];
        queue.unshift(node);
        while(queue.length){
            var item = queue.shift();
            nodes.push(item);
            var children = item.children;
            for(let i=0 ; i<children.length ; i++){
                queue.push(children[i]);
            }
        }
    }
}

9.嵌套数组展开

// 递归
function flattenMd(arr) {
    var result = [];
    for(var i = 0; i < arr.length; i++){
        if(arr[i] instanceof Array) {
            result = result.concat(flattenMd(arr[i]));
        }
        else {
            result.push(arr[i]);
        }
    }
    return result;
}
var arr=[1, [2, 3, [4, 5], 6], 7, 8]
console.log(flattenMd(arr));
// 非递归
function flattenDeep(arr){
    const res = [];
    const stack = [...arr];
    while(stack.length){
        let item = stack.shift();
        Array.isArray(item)?stack.unshift(...item):res.push(item);
    }
    return res;
}
var arr = [1,[2,[3,[[5]]],[4]]];
console.log(flattenDeep(arr))

相关文章

网友评论

      本文标题:每日一练 -- 简单的小笔试

      本文链接:https://www.haomeiwen.com/subject/jqngqhtx.html