深夜算法杂记一

在刷leetcode，从easy开始第二题，题目如下：

image.png

阅读后可以简单的理解下题目就是需要将数组进行排序，然后再将1,3,5...等位置的数字相加就可实现两两组合后，组合数中最小数相加尽可能的大。我的第一反应是之前在刷面试题目时候用到的数组排序终于能用上了，附上代码：

var arrayPairSum = function(nums) {
    var sum=0;
    //排序后的数组
    var temp= getArr(nums);
    //将排序后的数组1,3,5相加
    if(temp.length>2){
        for(var i=0;i<temp.length;){
            sum+=temp[i];
            i+=2;
        }
    }else{
        sum= temp[0];
    }

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

这边排序的思想应该很容易能懂的，用了递归。但是问题出现了，我在提交检测的时候，很尴尬第一次没给我通过，理由是时间过长了，厚着脸皮再去提交了一次算是被接受了，最后耗时：

image.png

很尴尬啊，抱着学习的心态，果断的去了讨论区，然后就看到了：

var arrayPairSum = function(nums) {
    var number = 0;
    nums.sort(function(a,b){return a-b});
    for (var i = 0; i < nums.length; i=i+2) {
        number += nums[i];
    }
    return number;
};

image.png

很尴尬，没啥好说的，赶紧去恶补了下array.sort，这玩意很强势，正排逆排都行，参数搞定，很强，这看着自己写的这三四十行代码，别人3,4行就搞定了，性能还比你好，很尴尬。只能说 学学学 。

续：
看到了之前面试的时候面试官让我去做的一题；如下

//看到后就明白了题意，转化为树形对象
var input = {
  h3: {
    parent: 'h2',
    name: '副总经理(市场)'
  },
  h1: {
    parent: 'h0',
    name: '公司机构'
  },
  h7: {
    parent: 'h6',
    name: '副总经理(总务)'
  },
  h4: {
    parent: 'h3',
    name: '销售经理'
  },
  h2: {
    parent: 'h1',
    name: '总经理'
  },
  h8: {
    parent: 'h0',
    name: '财务总监'
  },
  h6: {
    parent: 'h4',
    name: '仓管总监'
  },
  h5: {
    parent: 'h4',
    name: '销售代表'
  },
  h0: {
    parent: '',
    name: 'root'
  }
};

之前面试的时候想了很久的，当时想着用的递归，但是最后还是没做出来，但是其实是一个循环就能实现：

//循环对象，一一对应过去，然后将根节点取出来即可
    var plain2Tree = function (obj) {
        var key, res;
        for(key in obj) {
            var parent = obj[key].parent
            if(parent === ''") {
                res = obj[key]
            } else {
                obj[parent][key] = obj[key]
            }
        }
        return res
    }