每日算法：朋友圈、岛屿数量、合法二叉树、后继者

短命女 2023-02-10 08:01 4阅读 0赞

### 1、朋友圈 ###

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N \* N 的矩阵 M，表示班级中学生之间的朋友关系。如果M\[i\]\[j\] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

输入: 
    [[1,1,0],
     [1,1,0],
     [0,0,1]]
    输出: 2 
    说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
    第2个学生自己在一个朋友圈。所以返回2。

输入: 
    [[1,1,0],
     [1,1,1],
     [0,1,1]]
    输出: 1
    说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

class Solution {
        public int findCircleNum(int[][] arr) {
            if(arr == null || arr.length == 0){
               return 0;
           }
           int[] visited = new int[arr.length];
           int count = 0;
           for(int i = 0;i < arr.length;i++) {
               if(visited[i] == 0){
                   visited[i] = 1;
                   dfs(arr,visited,i);
                   count++;
               }
           }
           return count;
        }
    
         public  void dfs(int[][] arr, int[] visited,int index){
            for(int j = 0;j < arr.length;j++){
                if(visited[j] == 0 && arr[index][j] == 1){
                    visited[j] = 1;
                    dfs(arr,visited,j);
                }
            }
        }
    }

解题思路也特别easy，就是深度优先遍历就解决了。就是看连着的他们这一个圈子有多少。

### 2、岛屿数量 ###

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

输入:
    11110
    11010
    11000
    00000
    输出: 1

输入:
    11000
    11000
    00100
    00011
    输出: 3
    解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

class Solution {
        public int numIslands(char[][] grid) {
           if(grid == null || grid.length == 0){
                return 0;
            }
            int n = grid.length;
            int m = grid[0].length;
            int result = 0;
            for(int i = 0;i < n;i++){
                for(int j = 0;j < m;j++){
                    if(grid[i][j] == '1'){
                        result++;
                        grid[i][j] = '0';
                        dfs(grid,i,j);
                    }
                }
            }
            return result;
        }
    
        public  void dfs(char[][] grid,int i,int j){
            
            int m = grid.length - 1;
            int n = grid[0].length - 1;
            if(i - 1 >= 0 && grid[i - 1][j] == '1'){
                grid[i - 1][j] = '0';
                dfs(grid,i - 1,j);
            }
            if(i + 1 <= m && grid[i + 1][j] == '1'){
                grid[i + 1][j] = '0';
                dfs(grid,i + 1,j);
            }
            if(j - 1 >= 0 && grid[i][j - 1] == '1'){
                grid[i][j - 1] = '0';
                dfs(grid,i,j - 1);
            }
            if(j + 1 <= n && grid[i][j + 1] == '1'){
                grid[i][j + 1] = '0';
                dfs(grid,i,j + 1);
            }
        }
    }

这个也是找连在一块儿的岛屿，但是与朋友圈有本质的不同，只能搜索的时候按照上下左右来。搜索过的值设置0

### 3、合法二叉树 ###

实现一个函数，检查一棵二叉树是否为二叉搜索树。

输入:
        2
       / \
      1   3
    输出: true

输入:
        5
       / \
      1   4
         / \
        3   6
    输出: false
    解释: 输入为: [5,1,4,null,null,3,6]。
         根节点的值为 5 ，但是其右子节点值为 4 。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isValidBST(TreeNode root) {
            if (root == null){
                return true;
            }
            TreeNode maxLeft = root.left, minRight = root.right;
            while (maxLeft != null && maxLeft.right != null){
                maxLeft = maxLeft.right;
            }
            while (minRight != null && minRight.left != null){
                minRight = minRight.left;
            }
            boolean ret = (maxLeft == null || maxLeft.val < root.val) && (minRight == null || root.val < minRight.val);
            return  ret && isValidBST(root.left) && isValidBST(root.right);
        }
    }

最简单的方法就是中序遍历，然后看是否是升序序列，但是那样效率低。看到一个大神的做法是，从根节点开始，依次判断左子树的最大节点比当前节点小，右子树的最小节点比当前节点大，之后对于每一个节点，都是这么操作，其中有一次不满足，就失败！就做成功了。

### 4、后继者 ###

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回`null`。

输入: root = [2,1,3], p = 1
    
      2
     / \
    1   3
    
    输出: 2

输入: root = [5,3,6,2,4,null,null,1], p = 6
    
          5
         / \
        3   6
       / \
      2   4
     /   
    1
    
    输出: null

class Solution {
        boolean flag = false;
        TreeNode aimNode;
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if(root==null){
                return aimNode;
            }
            inorderSuccessor(root.left,p);
            if(root==p){
                flag = true;
            }else if(flag){
                aimNode = root;
                flag =false;
            }
            inorderSuccessor(root.right,p);
            return aimNode;
        }
    }

中序遍历，当发现前一个节点是目标节点的时候就记录下来，设置一个标志，之后发现后续节点了，直接就保存。