几道面试题

作者: 周伟林 分类: 求职面试 发布时间: 2018-05-22 23:47

手写快速排序

// 快速排序 O(nlogn) 
// 要求: 就地排序(修改原数组),空间复杂度要求O(1)

function quickSort(arr, lo, hi)
{
    if(arr.length <= 1 || lo >= hi) return arr;
    let pivotIdx = partition(arr, lo, hi)
    quickSort(arr, lo, pivotIdx-1);
    quickSort(arr, pivotIdx+1, hi);
}
function partition(arr, lo, hi)
{
    let pivot = arr[lo];
    hi++;
    while(lo < hi){
        while(lo < hi && arr[--hi] >= pivot);
        arr[lo] = arr[hi];
        while(lo < hi && arr[++lo] <= pivot);
        arr[hi] = arr[lo];
    }
    arr[lo] = pivot;
    return lo;
}
let arr = [34, 12, 56, 39, 29, 9, 15, 28, 77, 36, 99, 76];
quickSort(arr, 0, arr.length-1);
console.log(arr);   // [ 9, 12, 15, 28, 29, 34, 36, 39, 56, 76, 77, 99 ]

字符串分割

题目描述,从小数点为起点,用逗号每隔三位分割字符串。

输入 9123456.7891234
输出 9,123,456.789,123,4
function normalize(str){
    var pointIdx = str.indexOf('.');
    var arrL = [], arrR = [];
    for(var i = pointIdx-3; i > -3; i-=3)
        arrL.unshift(str.substring(i, i+3));
    for(var i = pointIdx+1; i < str.length; i+=3)
        arrR.push(str.substring(i, i+3));
    return arrL.join(',')+'.'+arrR.join(',');
}
console.log(normalize('9123456.7891234')); // 9,123,456.789,123,4

数组拍平

数组内含有数组,请把二维数组拍平位一维数组。

function paiping(arr){
    for(var l = arr.length, i = 0; i < l; ++i){
        if(Array.isArray(arr[i])){
            arr.splice(i, 1, ...arr[i]);
        }
    }
    return arr;
}
console.log(paiping([1, [2,3]]));               // [ 1, 2, 3 ]
console.log(paiping([1, [2,3,[4]], [5,6]]));    // [ 1, 2, 3, [ 4 ], [ 5, 6 ] ]

发表评论

电子邮件地址不会被公开。 必填项已用*标注