【Day13】每天三算法

【Day13】每天三算法

文章目录

• 【Day13】每天三算法
• • 题目
  • • NC136 输出二叉树的右视图
    • • 描述
      • 思考
      • 题解
      • 小结
    • NC109_岛屿数量
    • • 描述
      • 思考
      • 题解
      • 小结
    • NC13 二叉树的最大深度
    • • 描述
      • 思考
      • 题解
      • 总结

【Day13】每天三算法 题目 NC136 输出二叉树的右视图 描述

思考

对于这道题，我们有两步要走

**1、**建树

**2、**获取右视图

建树这个好说，我们之前做过类似的题目，这里就不再赘述了

而获取右视图，我们可以通过层次遍历，然后每次去除当前层的最后一个元素即可

题解

• 根据先序和中序构造二叉树

我对 buildTree 方法有封装了一层，这是编码的常见 *** 作了，可以理解为我们对其他调用者封装了一层 API，方便后续调用

同时，咱们封装的方法可以对入参进行更好的条件判断，可谓是一举多得

public TreeNode buildTree(int[] xianxu, int[] zhongxu) {
  if (xianxu==null || xianxu.length==0) return null;
  return buildTree(xianxu,zhongxu,0,xianxu.length-1,0,zhongxu.length-1);
}

// 构建二叉树
private TreeNode buildTree(int[] xianxu, int[] zhongxu,int xl,int xr,int zl,int zr) {
  if (xl>xr) return null;
  int midVal = xianxu[xl];
  TreeNode root = new TreeNode(midVal);
  // 获取左边的长度
  int llen=0;
  for (int i = zl; i <=zr ; i++) {
    if (zhongxu[i]==midVal) {
      llen=i-zl;
      break;
    }
  }
  root.left=buildTree(xianxu,zhongxu,xl+1,xl+llen,zl,zl+llen-1);
  root.right=buildTree(xianxu,zhongxu,xl+llen+1,xr,zl+llen+1,zr);
  return root;
}

• 根据二叉树，获取右视图

这里就是按照我之前的思路，层次遍历，然后每次获取每层最后一个元素

public List getRightView(TreeNode root) {
  List rightView = new ArrayList<>();
  Queue queue = new linkedList<>();
  queue.add(root);
  while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
      TreeNode tmp = queue.poll();
      if (i==size-1) {
        rightView.add(tmp.val);
      }
      if (tmp.left!=null) queue.add(tmp.left);
      if (tmp.right!=null) queue.add(tmp.right);
    }
  }
  return rightView;
}

• 被调函数

我们的根调用函数如下

其顺序就是先构造二叉树，然后获取右视图

public int[] solve (int[] xianxu, int[] zhongxu) {
  if (xianxu.length==0) return new int[0];
  // 只有1个或2个节点的情况下，其右视图一定是和先序遍历一样的
  if (xianxu.length<=2) return xianxu;
  TreeNode root = buildTree(xianxu, zhongxu);
  List rightView = getRightView(root);
  int[] res = new int[rightView.size()];
  for (int i = 0; i < res.length; i++) {
    res[i]=rightView.get(i);
  }
  return res;
}

• 完整代码如下

public int[] solve (int[] xianxu, int[] zhongxu) {
  if (xianxu.length==0) return new int[0];
  // 只有1个或2个节点的情况下，其右视图一定是和先序遍历一样的
  if (xianxu.length<=2) return xianxu;
  TreeNode root = buildTree(xianxu, zhongxu);
  List rightView = getRightView(root);
  int[] res = new int[rightView.size()];
  for (int i = 0; i < res.length; i++) {
    res[i]=rightView.get(i);
  }
  return res;
}

public TreeNode buildTree(int[] xianxu, int[] zhongxu) {
  if (xianxu==null || xianxu.length==0) return null;
  return buildTree(xianxu,zhongxu,0,xianxu.length-1,0,zhongxu.length-1);
}

// 构建二叉树
private TreeNode buildTree(int[] xianxu, int[] zhongxu,int xl,int xr,int zl,int zr) {
  if (xl>xr) return null;
  int midVal = xianxu[xl];
  TreeNode root = new TreeNode(midVal);
  // 获取左边的长度
  int llen=0;
  for (int i = zl; i <=zr ; i++) {
    if (zhongxu[i]==midVal) {
      llen=i-zl;
      break;
    }
  }
  root.left=buildTree(xianxu,zhongxu,xl+1,xl+llen,zl,zl+llen-1);
  root.right=buildTree(xianxu,zhongxu,xl+llen+1,xr,zl+llen+1,zr);
  return root;
}


// 层次遍历，每次获取每层的最后一个元素
public List getRightView(TreeNode root) {
  List rightView = new ArrayList<>();
  Queue queue = new linkedList<>();
  queue.add(root);
  while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
      TreeNode tmp = queue.poll();
      if (i==size-1) {
        rightView.add(tmp.val);
      }
      if (tmp.left!=null) queue.add(tmp.left);
      if (tmp.right!=null) queue.add(tmp.right);
    }
  }
  return rightView;
}

小结

这道题在牛客上定级是 medium

其实，就是两个 easy 题目的综合

希望各位以后在见到 medium 甚至 hard 的时候，不要慌张，因为，思路往往就在以前做过的题目中

NC109_岛屿数量 描述

思考

这道题，我们可以先考虑遍历图形

一旦遇到1，说明我们遇到岛屿，那么我们可以计数+1，并将这座岛屿弄沉

以此往复，直到遍历结束

这种方式，也有前人总结出了一个名词，叫“岛屿沉没法”

题解

public int solve (char[][] grid) {
  if (grid==null || grid.length==0) return 0;
  int count = 0;
  for (int i = 0; i < grid.length; i++) {
    for (int j = 0; j < grid[0].length; j++) {
      if (grid[i][j]=='1') count++;
      sinkIsland(i,j,grid);
    }
  }
  return count;
}

// 将当前岛屿沉没
private void sinkIsland(int r,int c,char[][] grid) {
  int R = grid.length;
  int C = grid[0].length;
  if (r<0 || r>=R || c<0 || c>=C) return;
  if (grid[r][c]!='1') return;
  grid[r][c]='0';
  int[] rs = {0,0,1,-1};
  int[] cs = {1,-1,0,0};
  for (int i = 0; i < 4; i++) {
    sinkIsland(r+rs[i],c+cs[i],grid);
  }
}

小结

这道题其实没啥难度

但是我想考考各位，我这个方法的时间复杂度是多少呢？

我估计有同学可能会说 O(n^3)

答案其实是 O(n^2)

别看有个 二重 for 循环 和一个 DFS

其实那个二重 for 循环的时间复杂度我们只能算 n，我们的数据是以二维数组的形式存储的，其遍历方式就必须借用到二重 for 循环，你总不能把相同量的数据，从二维改为一维存储，就说遍历它的时间复杂度变为 O(n) 了把？

如果要再细致一点，这道题的时间复杂度应该是在 O(n) - O(n^2) 之间

O(n) 即不存在岛屿，O(n^2) 即整张图都是岛屿

NC13 二叉树的最大深度 描述

思考

这道题是最最经典，也是最容易的 dfs 题目了（也不知道是怎么混到我的题库里的）

我们只需对二叉树进行深度遍历，然后记录每次到叶子的深度并进行比较即可

题解

public int maxDepth (TreeNode root) {
  if(root==null) return 0;
  return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}

总结

这种 easy 其实没啥好总结的，我主要是想提一提 dfs 和 bfs 的选择

BFS 适合找出路这类问题，我们拿迷宫举例，想想你每次走迷宫的时候，是不是都是先一条道走到黑，发现这条道走不通，再返回之前最后一个岔路口，然后选其他路走的。DFS 就是这个原理，它每次都会尝试一条道路到尽头，直到走不了了才会尝试其他的道路。这样的好处就是，一旦某条路走通了，那么剩下的路我们就可以不走了。

BFS 适合最短路径这类问题，你想象水面上有一个漂浮物，你随机向水中丢一块石头，石头产生的涟漪拨散开，直到碰到那个漂浮物。BFS 不会说一条道走到黑，因为最短路径的终点不一定永远在边缘，可能就在起点很近的地方。假如我们还是使用 DFS 一条道走到黑的方法，那么我们可能会多走许多冤枉路。

回到这道题，虽然 DFS 和 BFS 都能解决，并且无论是 DFS 还是 BFS，都是要对所有节点进行遍历的。但是基于二者的思想，还是选择 DFS 更为合适。况且 DFS 相比 BFS ，还要少建一个队列呢。