简单算法

面试算法题四部曲：

1. clarification（询问题目细节，边界条件，可能的极端错误情况）。
2. Possible Solutions （所有可能的解法都和面试官沟通一遍）
   • Compare time &space Complexity（时间&空间复杂度）
   • Optimal Solution （最优解）
3. Coding （写代码）
4. Test Cases （写测试用例）

• 两数之和
  题述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var temp = {};
    for(let i =0;i<nums.length;i++) {
        if(temp[nums[i]] >= 0) return [temp[nums[i]], i];
        else temp[target-nums[i]] = i;
    }
};

• 349. 两个数组的交集
  给定两个数组，编写一个函数来计算它们的交集。

var intersection = function(nums1, nums2) {
    var set1 = new Set(nums1);
    var set2 = new Set(nums2);
    var res = [];
    
    for(let num of set1.values()){
        if(set2.has(num))
            res.push(num);
    }
    return res;
};

for...of... 循环在可迭代对象（包括 Array，Map，Set，String，TypedArray，arguments 对象等等）上创建一个迭代循环，调用自定义迭代钩子，并为每个不同属性的值执行语句。

for...in... 循环语句以任意顺序遍历一个对象的除Symbol以外的可枚举属性。

• 排序链表（148）
  在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
  示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

解题思路常见的归并排序，先将链表四分为二，二分为一（快慢指针），直接二分等方法，排序，然后再将已排序的分段链表合并。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
  if(head === null) 
    return head;
  
  var len = 0;
  var p = head;
  while(p) {
    len++;
    p = p.next;
  }
  
  var newHead = sort(len);
  return newHead;
  
  function sort(len) {
    if(len === 1) {
      var temp = head;
      head = head.next;
      temp.next = null;
      return temp;
    }
    
    var leftHead = sort(parseInt(len/2));
    var rightHead = sort(len - parseInt(len/2));
    
    var newHead = merge(leftHead, rightHead);
    
    return newHead;
  }
  
  function merge(leftHead, rightHead) {
    var h = ListNode(-1);
    var cur = h;
    while(leftHead && rightHead) {
      if(leftHead.val <= rightHead.val) {
        cur.next = leftHead;
        leftHead = leftHead.next;
      }else {
        cur.next = rightHead;
        rightHead = rightHead.next;
      }
      
      cur = cur.next;
    }
    
    if(leftHead) {
      cur.next = leftHead;
    }
    if(rightHead) {
      cur.next = rightHead;
    }
    cur = h.next;
    h.next = null;
    return cur;
  }
};

• 插入排序
  插入排序是遍历数组中的每一个元素，并寻找到前一个比它小的数，并插入该数后面。

function insertSort(arr) {
  for(var a = 1;a<arr.length;a++) {
    let key = arr[a];
    let temp = a-1;

    while(temp>0 && arr[temp]>key) {
      arr[temp+1] = arr[temp];
      temp -=1;
    }
    arr[temp+1] = key;    
  }
  return arr;
}

let demoArr = [1,3,2,4,6,9,5];
console.log(insertSort(demoArr));
// [1, 2, 3, 4, 5, 6, 9]

• 奖牌排序

  
  奖牌题目

// 奖牌排序
var result = [];
let countryKeys = [];
let countrys = ['322834China', '123422England', '233302France', '123425Japan', '234300Rusia', '123422Korea'];

countrys = countrys.sort().reverse();

countrys.forEach(item => {
  let key = item.match(/\d+/g);
  countryKeys.push(key+'');
});

countryKeys.forEach(item => {
  let names = medalRepeat(item);
  
  names.forEach(name => {
    if(result.indexOf(name)==-1) {
      result.push(name);
    }
  });
});

console.log(result);

function medalRepeat(medalNumStr) {
  var a = 0;
  var countryArr = [];
  var reg = new RegExp(medalNumStr);
  
  while(a< countrys.length) {
    var temp = reg.test(countrys[a]);
    
    if(temp){
      let countryName = countrys[a].replace(/\d+/g,'');
      countryArr.push(countryName);
    }
    a++;
  }
  
  return countryArr.sort();
}

源码