LeeCode-刷题日记-Day17

59. 螺旋矩阵 II

采用模拟的方法进行解题，当此方向超出矩阵边界时改变方向，或者当下一节点有值时，改变方向。

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    const maxNum=n*n;
    let curNum=1;
    const matrix=new Array(n).fill(0).map(()=>new Array(n).fill(0));
    let row=0,column=0;
    const dir=[[0,1],[1,0],[0,-1],[-1,0]];
    let dirIndex=0;
    while(curNum<=maxNum){
        matrix[row][column]=curNum;
        curNum++;
        const nR=row +dir[dirIndex][0],nC=column+dir[dirIndex][1];
        if(nR<0||nR>=n||nC<0||nC>=n||matrix[nR][nC]!==0){
            dirIndex=(dirIndex+1)%4;
        }
        row +=dir[dirIndex][0];
        column+=dir[dirIndex][1]
    }
    return matrix;
};

240. 搜索二维矩阵 II

二维矩阵在每一行上为升序，每一列为升序。

思路一：在每一行上采用二分查找的方法进行解题。时间复杂度为m*logn

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    for(let i=0;i<matrix.length;i++){
        if(search(matrix[i],target)!==-1){
            return true;
        }
    }
    return false;
};
function search(nums,target){
    let l=0,r=nums.length-1;
    while(l<=r){
        let mid = Math.floor((r-l)/2)+l;
        if(nums[mid]===target)
            return mid;
        else if(nums[mid]>target)
            r=mid-1;
        else l=mid+1;
    }
    return -1;
}

思路二：Z字形查找

从矩阵的最右上角进行查找

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    const m=matrix.length,n=matrix[0].length;
    let x=0,y=n-1;
    while(x<m&&y>=0){
        if(matrix[x][y]===target){
            return true;
        }
        if(matrix[x][y]>target){
            --y;
        }else{
            ++x;
        }
    }
    return false;
};

**435. 无重叠区间

动态规划、或者贪心

贪心方法

此问题可以等同于，寻找最多的无重叠区间，再用区间数减去无重叠区间即为答案。

贪心思路为，按区间右侧进行排序。以第一个节点为标记，判断后续每个区间的左边界是否小于当前节点的右边界，如果成立则为无重叠区间，计数加一。如果不成立，则将标记节点更新。

（问题：为什么按右边界排序，可以一次遍历通过。）

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    if(!intervals){
        return 0;
    }
    intervals.sort((a,b)=>a[1]-b[1]);
    let ans=1;
    let right = intervals[0][1];
    for(let i=1;i<intervals.length;i++){
        if(intervals[i][0]>=right){
            ans++;
            right=intervals[i][1];
        }
    }
    return intervals.length-ans;
};