class062 宽度优先遍历及其扩展【算法】-阿里云开发者社区

class062 宽度优先遍历及其扩展【算法】

算法讲解062【必备】宽度优先遍历及其扩展

code1 1162. 地图分析

// 地图分析

// 你现在手里有一份大小为 n x n 的网格 grid

// 上面的每个单元格都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。

// 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的

// 并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

// 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：

// (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

// 测试链接 : https://leetcode.cn/problems/as-far-from-land-as-possible/

多源bfs

package class062;
// 地图分析
// 你现在手里有一份大小为 n x n 的 网格 grid
// 上面的每个 单元格 都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。
// 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的
// 并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
// 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
// (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
// 测试链接 : https://leetcode.cn/problems/as-far-from-land-as-possible/
public class Code01_AsFarFromLandAsPossible {
  public static int MAXN = 101;
  public static int MAXM = 101;
  public static int[][] queue = new int[MAXN * MAXM][2];
  public static int l, r;
  public static boolean[][] visited = new boolean[MAXN][MAXM];
  // 0:上，1:右，2:下，3:左
  public static int[] move = new int[] { -1, 0, 1, 0, -1 };
  //                                      0  1  2  3   4
  //                                               i
  // (x,y)  i来到0位置 : x + move[i], y + move[i+1] -> x - 1, y
  // (x,y)  i来到1位置 : x + move[i], y + move[i+1] -> x, y + 1
  // (x,y)  i来到2位置 : x + move[i], y + move[i+1] -> x + 1, y
  // (x,y)  i来到3位置 : x + move[i], y + move[i+1] -> x, y - 1
  public static int maxDistance(int[][] grid) {
    l = r = 0;
    int n = grid.length;
    int m = grid[0].length;
    int seas = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (grid[i][j] == 1) {
          visited[i][j] = true;
          queue[r][0] = i;
          queue[r++][1] = j;
        } else {
          visited[i][j] = false;
          seas++;
        }
      }
    }
    if (seas == 0 || seas == n * m) {
      return -1;
    }
    int level = 0;
    while (l < r) {
      level++;
      int size = r - l;
      for (int k = 0, x, y, nx, ny; k < size; k++) {
        x = queue[l][0];
        y = queue[l++][1];
        for (int i = 0; i < 4; i++) {
          // 上、右、下、左
          nx = x + move[i];
          ny = y + move[i + 1];
          if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
            visited[nx][ny] = true;
            queue[r][0] = nx;
            queue[r++][1] = ny;
          }
        }
      }
    }
    return level - 1;
  }
}

code2 691. 贴纸拼词

// 贴纸拼词

// 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

// 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们

// 如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

// 返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1

// 注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的

// 并且 target 被选择为两个随机单词的连接。

// 测试链接 : https://leetcode.cn/problems/stickers-to-spell-word/

package class062;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
// 贴纸拼词
// 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
// 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们
// 如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
// 返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1
// 注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的
// 并且 target 被选择为两个随机单词的连接。
// 测试链接 : https://leetcode.cn/problems/stickers-to-spell-word/
public class Code02_StickersToSpellWord {
  public static int MAXN = 401;
  public static String[] queue = new String[MAXN];
  public static int l, r;
  // 下标0 -> a
  // 下标1 -> b
  // 下标2 -> c
  // ...
  // 下标25 -> z
  public static ArrayList<ArrayList<String>> graph = new ArrayList<>();
  static {
    for (int i = 0; i < 26; i++) {
      graph.add(new ArrayList<>());
    }
  }
  public static HashSet<String> visited = new HashSet<>();
  // 宽度优先遍历的解法
  // 也可以使用动态规划
  // 后续课程会有动态规划专题讲解
  public static int minStickers(String[] stickers, String target) {
    for (int i = 0; i < 26; i++) {
      graph.get(i).clear();
    }
    visited.clear();
    for (String str : stickers) {
      str = sort(str);
      for (int i = 0; i < str.length(); i++) {
        if (i == 0 || str.charAt(i) != str.charAt(i - 1)) {
          graph.get(str.charAt(i) - 'a').add(str);
        }
      }
    }
    target = sort(target);
    visited.add(target);
    l = r = 0;
    queue[r++] = target;
    int level = 1;
    // 使用队列的形式是整层弹出
    while (l < r) {
      int size = r - l;
      for (int i = 0; i < size; i++) {
        String cur = queue[l++];
        for (String s : graph.get(cur.charAt(0) - 'a')) {
          String next = next(cur, s);
          if (next.equals("")) {
            return level;
          } else if (!visited.contains(next)) {
            visited.add(next);
            queue[r++] = next;
          }
        }
      }
      level++;
    }
    return -1;
  }
  public static String sort(String str) {
    char[] s = str.toCharArray();
    Arrays.sort(s);
    return String.valueOf(s);
  }
  public static String next(String t, String s) {
    StringBuilder builder = new StringBuilder();
    for (int i = 0, j = 0; i < t.length();) {
      if (j == s.length()) {
        builder.append(t.charAt(i++));
      } else {
        if (t.charAt(i) < s.charAt(j)) {
          builder.append(t.charAt(i++));
        } else if (t.charAt(i) > s.charAt(j)) {
          j++;
        } else {
          i++;
          j++;
        }
      }
    }
    return builder.toString();
  }
}

code3 2290. 到达角落需要移除障碍物的最小数目

// 到达角落需要移除障碍物的最小数目

// 给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n

// 每个单元格都是两个值之一：

// 0 表示一个空单元格，

// 1 表示一个可以移除的障碍物

// 你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。

// 现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1)

// 返回需要移除的障碍物的最小数目

// 测试链接 : https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/

01bfs模板

package class062;
import java.util.ArrayDeque;
// 到达角落需要移除障碍物的最小数目
// 给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n
// 每个单元格都是两个值之一：
// 0 表示一个 空 单元格，
// 1 表示一个可以移除的 障碍物
// 你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
// 现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) 
// 返回需要移除的障碍物的最小数目
// 测试链接 : https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/
public class Code03_MinimumObstacleRemovalToReachCorner {
  public static int minimumObstacles(int[][] grid) {
    int[] move = { -1, 0, 1, 0, -1 };
    int m = grid.length;
    int n = grid[0].length;
    int[][] distance = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        distance[i][j] = Integer.MAX_VALUE;
      }
    }
    ArrayDeque<int[]> deque = new ArrayDeque<>();
    deque.addFirst(new int[] { 0, 0 });
    distance[0][0] = 0;
    while (!deque.isEmpty()) {
      int[] record = deque.pollFirst();
      int x = record[0];
      int y = record[1];
      if (x == m - 1 && y == n - 1) {
        return distance[x][y];
      }
      for (int i = 0; i < 4; i++) {
        int nx = x + move[i], ny = y + move[i + 1];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
            distance[x][y] + grid[nx][ny] < distance[nx][ny]) {
          distance[nx][ny] = distance[x][y] + grid[nx][ny];
          if (grid[nx][ny] == 0) {
            deque.addFirst(new int[] { nx, ny });
          } else {
            deque.addLast(new int[] { nx, ny });
          }
        }
      }
    }
    return -1;
  }
}

code4 1368. 使网格图至少有一条有效路径的最小代价

// 使网格图至少有一条有效路径的最小代价

// 给你一个 m * n 的网格图 grid 。 grid 中每个格子都有一个数字

// 对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：

// 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]

// 2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]

// 3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]

// 4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]

// 注意网格图中可能会有无效数字，因为它们可能指向 grid 以外的区域

// 一开始，你会从最左上角的格子 (0,0) 出发

// 我们定义一条有效路径为从格子 (0,0) 出发，每一步都顺着数字对应方向走

// 最终在最右下角的格子 (m - 1, n - 1) 结束的路径

// 有效路径不需要是最短路径

// 你可以花费1的代价修改一个格子中的数字，但每个格子中的数字只能修改一次

// 请你返回让网格图至少有一条有效路径的最小代价

// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

01bfs

code5 407. 接雨水 II

// 二维接雨水

// 给你一个 m * n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度

// 请计算图中形状最多能接多少体积的雨水。

// 测试链接 : https://leetcode.cn/problems/trapping-rain-water-ii/

bfs+优先队列

package class062;
import java.util.PriorityQueue;
// 二维接雨水
// 给你一个 m * n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度
// 请计算图中形状最多能接多少体积的雨水。
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water-ii/
public class Code05_TrappingRainWaterII {
  public static int trapRainWater(int[][] height) {
    int[] move = new int[] { -1, 0, 1, 0, -1 };
    int n = height.length;
    int m = height[0].length;
    // 0 : 行
    // 1 : 列
    // 2 : 水线
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    boolean[][] visited = new boolean[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
          // 边界
          heap.add(new int[] { i, j, height[i][j] });
          visited[i][j] = true;
        } else {
          visited[i][j] = false;
        }
      }
    }
    int ans = 0;
    while (!heap.isEmpty()) {
      int[] record = heap.poll();
      int r = record[0];
      int c = record[1];
      int w = record[2];
      ans += w - height[r][c];
      for (int i = 0, nr, nc; i < 4; i++) {
        nr = r + move[i];
        nc = c + move[i + 1];
        if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc]) {
          heap.add(new int[] { nr, nc, Math.max(height[nr][nc], w) });
          visited[nr][nc] = true;
        }
      }
    }
    return ans;
  }
}

code6 126. 单词接龙 II

// 单词接龙 II

// 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化

// 一个表示此过程的转换序列是形式上像

// beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：

// 每对相邻的单词之间仅有单个字母不同

// 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词

// 注意，beginWord 不必是字典 wordList 中的单词

// sk == endWord

// 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList

// 请你找出并返回所有从 beginWord 到 endWord 的最短转换序列

// 如果不存在这样的转换序列，返回一个空列表

// 每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回

// 测试链接 : https://leetcode.cn/problems/word-ladder-ii/

bfs+深度优先队列，生成路径

package class062;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
// 单词接龙 II
// 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化
// 一个表示此过程的 转换序列 是形式上像 
// beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
// 每对相邻的单词之间仅有单个字母不同
// 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词
// 注意，beginWord 不必是字典 wordList 中的单词
// sk == endWord
// 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList
// 请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列
// 如果不存在这样的转换序列，返回一个空列表
// 每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回
// 测试链接 : https://leetcode.cn/problems/word-ladder-ii/
public class Code06_WordLadderII {
  // 单词表 ： list -> hashSet
  public static HashSet<String> dict;
  public static HashSet<String> curLevel = new HashSet<>();
  public static HashSet<String> nextLevel = new HashSet<>();
  // 反向图
  public static HashMap<String, ArrayList<String>> graph = new HashMap<>();
  // 记录路径，当生成一条有效路的时候，拷贝进ans！
  public static LinkedList<String> path = new LinkedList<>();
  public static List<List<String>> ans = new ArrayList<>();
  public static void build(List<String> wordList) {
    dict = new HashSet<>(wordList);
    graph.clear();
    ans.clear();
    curLevel.clear();
    nextLevel.clear();
  }
  public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    build(wordList);
    if (!dict.contains(endWord)) {
      return ans;
    }
    if (bfs(beginWord, endWord)) {
      dfs(endWord, beginWord);
    }
    return ans;
  }
  // begin -> end ，一层层bfs去，建图
  // 返回值：真的能找到end，返回true；false
  public static boolean bfs(String begin, String end) {
    boolean find = false;
    curLevel.add(begin);
    while (!curLevel.isEmpty()) {
      dict.removeAll(curLevel);
      for (String word : curLevel) {
        // word : 去扩
        // 每个位置，字符a~z，换一遍！检查在词表中是否存在
        // 避免，加工出自己
        char[] w = word.toCharArray();
        for (int i = 0; i < w.length; i++) {
          char old = w[i];
          for (char ch = 'a'; ch <= 'z'; ch++) {
            w[i] = ch;
            String str = String.valueOf(w);
            if (dict.contains(str) && !str.equals(word)) {
              if (str.equals(end)) {
                find = true;
              }
              graph.putIfAbsent(str, new ArrayList<>());
              graph.get(str).add(word);
              nextLevel.add(str);
            }
          }
          w[i] = old;
        }
      }
      if (find) {
        return true;
      } else {
        HashSet<String> tmp = curLevel;
        curLevel = nextLevel;
        nextLevel = tmp;
        nextLevel.clear();
      }
    }
    return false;
  }
  public static void dfs(String word, String aim) {
    path.addFirst(word);
    if (word.equals(aim)) {
      ans.add(new ArrayList<>(path));
    } else if (graph.containsKey(word)) {
      for (String next : graph.get(word)) {
        dfs(next, aim);
      }
    }
    path.removeFirst();
  }
}

2023-12-8 21:13:01

class062 宽度优先遍历及其扩展【算法】