面试经典150题【101-110】

6道偏数学的题和4道二维dp

9.回文数

一开始想转为字符串再判断。后来发现可以直接取后一半数字再判断。

class Solution {
    public boolean isPalindrome(int x) {
        //因为如果x后面出现0，后面算法会出错
        if(x<0 || x%10==0 && x!=0){
            return false;
        }
        int temp=0;
        while(temp<x){
            temp = temp*10 + x%10;
            x = x/10;
        }
        // x从1221 -> 12;  x: 12321 -> 12 <123
        return x==temp || x==temp/10;

    }
}

61.加一

class Solution {
    public int[] plusOne(int[] digits) {
        for(int i=digits.length-1;i>=0;i--){
            digits[i]++;
            digits[i] = digits[i]%10;
            if(digits[i] != 0) return digits;
        }
        //都加完了还不返回，说明是999这种
        int[] ans=new int[digits.length+1];
        ans[0]=1;
        return ans;

    }
}

直接加，最后遇到999这种则扩容。

172.阶乘后的0

25 = 25 *。。。 *5。。。
答案是3，看有几个5.其中25这个数字代表两个5

class Solution {
    public int trailingZeroes(int n) {
        int count=0;
        for(int i=0;i<n+1;i++){
            int temp=i;
            //最后temp会被干到0
            while(temp %5==0 && temp!=0){
                count++;
                temp =temp/5;
            }
        }
        return count;
    }
}

69.x的平方根

直接二分去搜，牛顿的数学太复杂。

50.Pow(x,n)

要将n进行二进制的拆分

class Solution {
    public double myPow(double x, int n) {
        if(x ==0.0f) return 0;
        long b=n;
        double res=1;
        if(b<0){
            x = 1/x;
            b = -b;
        }
        while(b>0){
            if((b&1)==1){
                res = res*x;
            }
            x =x*x;
            b = b>>1;
        }
        return res;
    }
}

149.直线上最多的点数

三个点，ABC，AB和BC的斜率应该一样。
暴力的话就是先确定两个点，再依次遍历其他的点，看斜率是否等于AB的斜率。
用哈希表就是，先确定一个点(N),计算与其他所有点（N）的斜率，将斜率k存储到哈希表中。取哈希表中value的最大值即可。

public class LC149 {
    public static int maxPoints(int[][] points) {

        int ans=0;
        for(int i=0;i<points.length;i++){
            HashMap<String,Integer>map =new HashMap<>();
            int[] x=points[i];
            for(int j=i+1;j<points.length;j++){
                int[] y=points[j];
                int x1=x[0],x2=y[0],y1=x[1],y2=y[1];
                int deltax = x1-x2,deltay=y1-y2;
                int gcdxy=gcd(deltax,deltay);
                String key=deltax/gcdxy +"_"+deltay/gcdxy;
                map.put(key,map.getOrDefault(key,0)+1);
                //[1,1]-[2,2],  [1,1]-[3,3]   [2,2]-[3,3]   [7,9] - [9,11]
                int value = map.get(key);
                ans =  ans=Math.max(ans,value+1);

            }
        }
        return ans;

    }
    public static int gcd(int x,int y){
        return y==0? x:gcd(y,x%y);

    }

    public static void main(String[] args) {
        int[][]points= {{1,1},{2,2},{3,3}};
        System.out.println(maxPoints(points));

    }

}

一个要注意最小公约数gcd的写法。
HashMap应该是针对于每一个 i 点的，则每一个 j 点都要统计。

52.N皇后II

老解法，回溯。先在每一行下棋，然后下一行，然后回溯到这一行没下。去下这一行的下一列。

public class LC52 {
    private static int ans=0;
    public static int totalNQueens(int n) {

        char[][] board=new char[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                board[i][j]='.';
            }
        }
        dfs(board,0);
        return ans;
    }
    public static void dfs(char[][] board,int row){
        if(row == board.length){
            ans++;
            return;
        }
        for(int j=0;j< board.length;j++){
            if(check(board,row,j)){
                board[row][j]='Q';
                dfs(board,row+1);
                board[row][j]='.';
            }
        }
    }
    public static boolean check(char[][]board,int row,int col){
        // 这一列
        for(int i=0;i< board.length;i++){
            if(board[i][col]=='Q') return false;
        }
        // 检查 135度角是否有皇后
        for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // 检查 45度角是否有皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(totalNQueens(4));
    }
}

120.三角形最小路径和

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 最后一行全是0
        int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];

    }
}

这个是倒序的，从三角形的下边到上面。
迭代公式：
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);

64.最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0)
                    continue;
                else if (i == 0)
                    grid[i][j] = grid[i][j - 1] + grid[i][j];
                else if (j == 0)
                    grid[i][j] = grid[i - 1][j] + grid[i][j];
                else
                    grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];

    }
}

这个是从上到下迭代的，迭代公式：
grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];

63.不同路径II

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        if(obstacleGrid[0][0]==1) return 0;
        int[][] dp=new int[m][n];
        dp[0][0]=1;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 && j==0) continue;
                if(i>0 && j>0 && obstacleGrid[i][j]==0){
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }else if(i==0 && obstacleGrid[i][j]==0){
                    dp[i][j]=dp[i][j-1];
                }else if(j==0 && obstacleGrid[i][j]==0){
                    dp[i][j]=dp[i-1][j];
                }else{
                    //有障碍物
                    dp[i][j]=0;
                }
            }
        }
        return dp[m-1][n-1];
    }

递推公式： dp[i][j]=dp[i-1][j]+dp[i][j-1];
应该先用俩for循环初始一下第一行和第一列。然后ij都从1开始循环也蛮好的。