【2020秋招_前端】微软一面 2020.10.12

1.经典题目leetcode1-twoSum
function twoSum(arr, target) {
    let l = arr.length;
    if (l < 2) return [];
    arr.sort((a, b) => a - b);
    let i = 0, j = l - 1, res = [];
    while (i < j){
        let cur = arr[i] + arr[j];
        if (cur == target) {
            res.push(i);
            res.push(j);
            return res;
        } else if (cur < target) {
            i++;
        } else {
            j--;
        }
    }
}
function twoSum(arr, target) {
    let map = new Map(), l = arr.length, res;
    for(let i = 0; i < l; i++){
        let t = target - arr[i];
        if (map.has(t)){
            res = [i, map.get(t)];
            return res;
        } else {
            map.set(arr[i], i);
        }
    }
}
2.合并有序数组
function mergeArray(arr1, arr2) {
    let arr = [];
    let i = 0, j = 0;
    let l1 = arr1.length, l2 = arr2.length;
    while (i < l1 && j < l2) {
        if (arr1[i] <= arr2[j]) {
            arr.push(arr1[i]);
            i++;
        }else {
            arr.push(arr2[j]);
            j++;
        }
    }
    while (i < l1){
        arr.push(arr1[i]);
        i++;
    }
    while(j < l2) {
        arr.push(arr2[j]);
        j++;
    }
    return arr;
}
3.大数据相加
function bigSum(num1, num2) {
    let l1 = num1.length, l2 = num2.length;
    let str1 = num1, str2 = num2;
    if (l1 > l2) {
        let arr = new Array(l1-l2).fill(0);
        str2 = arr.join('') + str2;
    } else if (l1 < l2) {
        let arr = new Array(l2-l1).fill(0);
        str1 = arr.join('') + str1;
    }
    let l = Math.max(l1, l2), res = [], carry = 0;
    for(let i = l - 1; i >= 0; i--) {
        let cur = parseInt(str1[i]) + parseInt(str2[i]) + carry;
        if (cur >= 10) {
            carry = 1;
            cur = cur - 10;
        } else {
            carry = 0;
        }
        res.push(cur);
    }
    if (carry == 1) res.push(carry)
    return res.reverse().join('');
}
4.数组中有个数字的出现次数超过了一半，怎么找出来
function getMost(arr){
    let map = new Map();
    for(let i = 0; i < arr.length; i++){
        if (map.has(arr[i])){
            map.set(arr[i], map.get(arr[i])+1);
        } else {
            map.set(arr[i], 1);
        }
    }
    for(let [key, value] of map.entries()){
        if (value > parseInt(arr.length/2)){
            return value;
        }
    }
}
function moreThanHalfNum(arr) {
    let l = arr.length;
    let res = arr[0], times = 1;
    for(let i = 1; i < l; i++) {
        if (times == 0) {
            res = arr[i];
            times = 1;
        } else if (arr[i] == res) {
            times++;
        } else {
            times--;
        }
    }
    return res;
}
let arr = [1,2,3,1,2,1,1];
let res = moreThanHalfNum(arr);
console.log(res);