力扣热题7-原地矩阵置零

---

按照leetcode刷一遍：leetcode hot

66. 加一

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        int[] result = new int[n+1];
        int carry = 1;
        int cur;
        for(int i=n-1;i>=0;i--) {
            cur = digits[i]+carry;
            result[i+1] = cur%10;
            carry = cur/10;
        }
        result[0] = carry;
        if(carry!=0) return result;
        // 左闭右开
        return Arrays.copyOfRange(result,1,n+1);
    }
}

69. x 的平方根

class Solution {
    public int mySqrt(int x) {
        // 二分
        if(x==0||x==1) return x;
        long lx = (long)x;
        long left = 1;
        long right = x;
        long mid = 0;
        while(left<=right) {
            mid = (left+right)/2;
            //System.out.printf("%d %d %d\n",left,right,mid);
            if(mid*mid==lx) return (int)mid;
            else if(mid*mid>lx) {
                right = mid-1;
            } else if(mid*mid<lx) {
                if(left==mid) return right*right<=lx?(int)right:(int)mid;
                else left = mid;
            }
        }
        return (int)mid;
    }
}

二分的思路没啥问题，就是代码写的有点丑陋，看看别人的。

简洁二分

class Solution {
    public int mySqrt(int x) {
        // 二分
        if(x==0||x==1) return x;
        int left = 1;
        int right = x;
        int mid = 0;
        while(left<right) {
            //这样在只有两位的时候不会死循环
            mid = (left+right+1)/2;
            if(mid>x/mid) {
                right = mid-1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}

70. 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        int a = 1;
        int b = 1;
        int cur = 0;
        for(int i=2;i<=n;i++) {
            cur = a+b;
            a = b;
            b = cur;
        }
        return b;
    }
}

73. 矩阵置零

两次遍历记录行列

O(m+n)记录所在行、列。

记录所在行、列，之后再置位。

class Solution {
    public void setZeroes(int[][] matrix) {
        Set<Integer> rowSet = new HashSet<>();
        Set<Integer> colSet = new HashSet<>();
        int m = matrix.length;
        int n = matrix[0].length;
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(matrix[i][j]==0) {
                    rowSet.add(i);
                    colSet.add(j);
                }
            }
        }
        for(int r:rowSet) {
            for(int j=0;j<n;j++) {
                matrix[r][j] = 0;
            }
        }
        for(int c:colSet) {
            for(int i=0;i<m;i++) {
                matrix[i][c] = 0;
            }
        }
    }
}

第一行第一列作为标志位

class Solution {
    public void setZeroes(int[][] matrix) {
        //[[1, 2,  3, 4],
        // [5, 0,  7, 8],
        // [0, 10, 11,12],
        // [13,14, 15,0]]
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRowTOZero = false;
        boolean firstColToZero = false;
        for(int i=0;i<m;i++) {
            if(matrix[i][0]==0) firstColToZero = true;
        }
        for(int j=0;j<n;j++) {
            if(matrix[0][j]==0) firstRowTOZero = true;
        }
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                if(matrix[i][j]==0) {
                    // 用第一行，第一列原地做标志位
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i=1;i<m;i++) {
            if(matrix[i][0]!=0) continue;
            for(int j=0;j<n;j++) {
                matrix[i][j] = 0;
            }
        }
        for(int j=1;j<n;j++) {
            if(matrix[0][j]!=0) continue;
            for(int i=0;i<m;i++) {
                matrix[i][j] = 0;
            }
        }
        if(firstColToZero) {
            for(int i=0;i<m;i++) {
                matrix[i][0] = 0;
            }
        }
        if(firstRowTOZero) {
            for(int j=0;j<n;j++) {
                matrix[0][j] = 0;
            }
        }
    }
}