知名互联网公司校招中常见的算法题（9-10）

短命女 2024-03-22 09:15 15阅读 0赞

## 知名互联网公司校招中常见的算法题（9-10） ##

题目九：岛屿数量

给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。一个岛被水包围，并且通过水平方向或竖直方向上相邻的陆地连接而成。你可以假设网格的四个边均被水包围。

解决思路：

我们可以用深度优先搜索（DFS）来解决这个问题。我们遍历整个网格，如果遇到一个陆地（'1'），就用 DFS 将与该陆地相邻的陆地全部标记为已访问。最后遍历完整个网格后，岛屿的数量就是 DFS 的执行次数。

代码实现：

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

题目十：二叉树的最近公共祖先

给定一个二叉树，找到该树中两个指定节点的最近公共祖先。

解决思路：

我们可以用递归的方法来解决这个问题。如果当前节点是 p 或 q，那么最近公共祖先就是当前节点。否则，我们分别在左子树和右子树中查找 p 和 q，如果左子树中不存在 p 或 q，那么最近公共祖先一定在右子树中，反之亦然。

代码实现：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if (root == null || root == p || root == q) {
          return root;
      }
      TreeNode left = lowestCommonAncestor(root.left, p, q);
      TreeNode right = lowestCommonAncestor(root.right, p, q);
      if (left != null && right != null) {
          return root;
      }
      if (left != null) {
          return left;
      }
      if (right != null) {
          return right;
      }
      return null;
    }

以上是关于常见算法题的解决思路、代码实现以及实际案例的详细讲解。对于互联网公司的校招来说，掌握这些算法题可以帮助我们更好地应对面试。当然，还需要多多练习，才能真正掌握这些算法。同时，我们还需要了解一些常见的数据结构和算法，比如哈希表、堆排序、快速排序等等。只有全面掌握了这些知识，我们才能在面试中更加游刃有余。