【2021秋招_微软软开面经】2020.10.13 微软三面

function spiralMatrix(n){
    let matrix = new Array(n).fill(0).map(ele => new Array(n).fill(0));
    helper(n, matrix, 0, n*n);
    return matrix;
    
    function helper(n, matrix, level, count) {
        if (n % 2 == 0 && level * 2 == n) return;
        if (n % 2 != 0) {
            if (level * 2 + 1 == n) {
                matrix[level][level] = count;
                return;
            }
        }
        
        for(let i = level; i < n - level; i++) {
            matrix[level][i] = count--;
        }
        for(let i = level + 1; i < n - level; i++) {
            matrix[i][n-level-1] = count--;
        }
        for(let i = n - 2 - level; i >= level; i--) {
            matrix[n-level-1][i] = count--;
        }
        for(let i = n - 2 - level; i > level; i--) {
            matrix[i][level] = count--;
        }
        helper(n, matrix, ++level, count);
    }
}

function getFirstPos(arr, target, l, r) {
    let i = l, j = r, mid;
    while ( i <= j) {
        mid = parseInt(i + (j-i)/2);
        if (arr[mid] > target) {
            j = mid - 1;
        } else if (arr[mid] < target) {
            i = mid + 1;
        } else {
            if (mid > l && arr[mid-1] == target) {
                j = mid - 1;
            } else {
                return mid;
            }
        }
    }
    return -1;
}

	

let res = getFirstPos([1,2,2,3,4], 2, 0, 4);
console.log(res);

function getLastPos(arr, target, l, r) {
    let i = l, j = r, mid;
    while ( i <= j ) {
        mid = parseInt(i + (j-i)/2);
        if (arr[mid] > target) {
            j = mid - 1;
        } else if (arr[mid] < target) {
            i = mid + 1;
        } else {
            if (mid + 1 <= r && arr[mid+1] == target) {
                i = mid + 1;
            } else {
                return mid;
            }
        }
    }
    return -1;
}

function getNums(nums, target) {
    let l = nums.length;
    let left = getFirstPos(nums, target, 0, l-1);
    let right = getLastPos(nums, target, 0, l-1);
    if (left == -1 || right == -1) return 0;
    return right - left + 1;
}

function biSearch(arr, target, l, r) {
    let i = l, j = r, mid;
    while ( i <= j) {
        mid = parseInt(i + (j-i)/2);
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            i = mid + 1;
        } else {
            j = mid - 1;
        }
    }
    return -1;
}

function getFirstPos(arr, target, l, r) {
    let index = biSearch(arr, target, l, r);
    if (index != -1 && index > 0 && arr[index-1] == target) {
        index = getFirstPos(arr, target, l, index - 1);
    }
    return index;
}

function getLastPos(arr, target, l, r) {
    let index = biSearch(arr, target, l, r);
    if (index != -1 && index < r - 1 && arr[index+1] == target) {
        index = getLastPos(arr, target, index+1, r);
    }
    return index;
}

let res = getNums([1,2,3,3,4,4,4,5], 4);
console.log(res);

function getLIS(arr) {
    let l = arr.length;
    let sum = new Array(l).fill(0);
    sum[0] = arr[0];
    for(let i = 1; i < l; i++) {
        sum[i] = (arr[i] == 1)? sum[i-1] + 1  : sum[i-1] - 1;
    }
    let res = 0, i = 0, j = l - 1, loop = 0;
    while (loop < l) {
        i = loop, j = l - 1;
        while (j > i && sum[j] != sum[i]) --j;
        if (j > i && sum[j] == sum[i]) {
            res = Math.max(j - i, res);
            break;
        }
        loop++;
    }
    return res;
}

let res = getLIS([1,1,1,0,0,1]);
console.log(res);