面试算法题四部曲：
- clarification（询问题目细节，边界条件，可能的极端错误情况）。
- Possible Solutions （所有可能的解法都和面试官沟通一遍）
- Compare time &space Complexity（时间&空间复杂度）
- Optimal Solution （最优解）
- Coding （写代码）
- 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();
}
