面試算法題四部曲：
- clarification（詢問題目細節(jié)旺入，邊界條件，可能的極端錯誤情況）绕娘。
- Possible Solutions （所有可能的解法都和面試官溝通一遍）
- Compare time &space Complexity（時間&空間復雜度）
- Optimal Solution （最優(yōu)解）
- Coding （寫代碼）
- Test Cases （寫測試用例）
- 兩數(shù)之和
題述：給定一個整數(shù)數(shù)組nums和一個目標值target愚争，請你在該數(shù)組中找出和為目標值的那 兩個 整數(shù)渊跋，并返回他們的數(shù)組下標。
/**
* @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. 兩個數(shù)組的交集
給定兩個數(shù)組舷手，編寫一個函數(shù)來計算它們的交集拧簸。
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... 循環(huán)在可迭代對象（包括 Array，Map男窟，Set盆赤，String，TypedArray歉眷，arguments 對象等等）上創(chuàng)建一個迭代循環(huán)牺六，調用自定義迭代鉤子，并為每個不同屬性的值執(zhí)行語句姥芥。
for...in... 循環(huán)語句以任意順序遍歷一個對象的除Symbol以外的可枚舉屬性兔乞。
- 排序鏈表（148）
在 O(n log n) 時間復雜度和常數(shù)級空間復雜度下，對鏈表進行排序凉唐。
示例 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;
}
};
- 插入排序
插入排序是遍歷數(shù)組中的每一個元素咱娶，并尋找到前一個比它小的數(shù)，并插入該數(shù)后面强品。
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();
}
