面试经典150题(78-81)

本文介绍: 第三十六天：早日跳槽！！！

leetcode 150道题计划花两个月时候刷完，今天（第三十六天）完成了4道(78-81)150：

78.（230. 二叉搜索树中第K小的元素）题目描述：

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

第一版（铭记！！二叉搜索树的中序遍历为递增的）

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack=new Stack();
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(--k==0){
                return root.val;
            }
            root=root.right;
        }
        return -1;
    }
}

79.（98. 验证二叉搜索树）题目描述：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

第一版（我第一反应就是递归，但是递归了好久没弄出来，就用中序遍历为递增的去判断了，算是个兜底办法）

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        Integer preNum=null;
        Stack<TreeNode> stack=new Stack();
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(preNum!=null&&root.val<=preNum){
                return false;
            }
            preNum=root.val;
            root=root.right;
        }
        return true;
    }
}

第二版（看了解题，递归是真的牛，但是这个我也应该能想出来的。。但是没有）

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode root,long min,long max) {
        if(root==null){
            return true;
        }
        if(root.val<=min||root.val>=max){
            return false;
        }
        return isValidBST(root.left,min,root.val)&&isValidBST(root.right,root.val,max);
    }
}

80.（200. 岛屿数量）题目描述：

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

第一版（这题我是真不会，看了解题，怎么说解题无敌！！）

class Solution {
    public int numIslands(char[][] grid) {
        // 卧槽解题太叼了
        int m=grid.length;
        int n=grid[0].length;
        int resNum=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    resNum++;
                    dfs(grid,i,j);
                }
            }
        }
        return resNum;
    }

    public void dfs(char[][] grid,int l,int r){
        int m=grid.length;
        int n=grid[0].length;
        if(l<0||r<0||l>=m||r>=n||grid[l][r]=='0'){
            return ;
        }
        grid[l][r]='0';
        dfs(grid,l,r-1);
        dfs(grid,l,r+1);
        dfs(grid,l-1,r);
        dfs(grid,l+1,r);
    }
}

81.（130. 被围绕的区域）题目描述：

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

第一版（有了上一题经验，在做这一题时候，确实有一点点思路，但是还是没转过来。。还是那句话解题真牛！！！）

class Solution {
    public void solve(char[][] board) {

        int m=board.length;
        int n=board[0].length;
        int[][] flag=new int[m][n];
        // 标记
        for(int i=0;i<m;i++){
           
            if(board[i][n-1]=='O'){
                dfs(flag,board,i,n-1);
            }
            
             if(board[i][0]=='O'){
                dfs(flag,board,i,0);
            }
        }
        for(int i=0;i<n;i++){
            if(board[m-1][i]=='O'){
                dfs(flag,board,m-1,i);
            }
            if(board[0][i]=='O'){
                dfs(flag,board,0,i);
            }
        }
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='O'&&flag[i][j]==0){
                    board[i][j]='X';
                }
            }
        }


    }
     public void dfs(int[][] flag,char[][] grid,int l,int r){
        int m=grid.length;
        int n=grid[0].length;
        if(l<0||r<0||l>=m||r>=n||grid[l][r]=='X'||flag[l][r]==1){
            return ;
        }
        flag[l][r]=1;
        dfs(flag,grid,l,r-1);
        dfs(flag,grid,l,r+1);
        dfs(flag,grid,l-1,r);
        dfs(flag,grid,l+1,r);
    }
}