二三年十一月每日一题

07 2586. 统计范围内的元音字符串数

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
  public int vowelStrings(String[] words, int left, int right) {
    int ans = 0;
    List<Character> vowelList = Arrays.asList('a', 'e', 'i', 'o', 'u');
    Set<Character> vowelSet = new HashSet<>(vowelList);
    for (int i = left; i <= right; i++) {
      char firstChar = words[i].charAt(0);
      char lastChar = words[i].charAt(words[i].length() - 1);
      if (vowelSet.contains(firstChar) && vowelSet.contains(lastChar)) {
        ans += 1;
      }
    }
    return ans;
  }

  public static void main(String[] args) {
    // Test 1
    String[] words = new String[] { "are", "amy", "u" };
    int left = 0;
    int right = 2;
    Solution solu = new Solution();
    int ans = solu.vowelStrings(words, left, right);
    System.out.println(ans);

    // Test 2
    words = new String[] { "hey", "aeo", "mu", "ooo", "artro" };
    left = 1;
    right = 4;
    ans = solu.vowelStrings(words, left, right);
    System.out.println(ans);
  }
}

08 2609. 最长平衡子字符串

public class Solution {
  public int findTheLongestBalancedSubstring(String s) {
    int ans = 0;
    int sLen = s.length();
    int[] count = new int[2];
    for (int i = 0; i < sLen; i++) {
      if (s.charAt(i) == '1') {
        count[1] += 1;
        ans = Math.max(ans, 2 * Math.min(count[0], count[1]));
      } else if (i == 0 || s.charAt(i - 1) == '1') { // 如果 s[i] == '0'
        count[0] = 1;
        count[1] = 0;
      } else {
        count[0] += 1;
      }
    }
    return ans;
  }

  public static void main(String[] args) {
    /*
     * 示例 1：
     * 输入：s = "01000111"
     * 输出：6
     * 解释：最长的平衡子字符串是 "000111" ，长度为 6 。
     *
     * 示例 2：
     * 输入：s = "00111"
     * 输出：4
     * 解释：最长的平衡子字符串是 "0011" ，长度为 4 。
     *
     * 示例 3：
     * 输入：s = "111"
     * 输出：0
     * 解释：除了空子字符串之外不存在其他平衡子字符串，所以答案为 0 。
     */
    Solution solu = new Solution();
    String s = "01000111";
    int ans = solu.findTheLongestBalancedSubstring(s);
    System.out.println(ans);

    s = "00111";
    ans = solu.findTheLongestBalancedSubstring(s);
    System.out.println(ans);

    s = "111";
    ans = solu.findTheLongestBalancedSubstring(s);
    System.out.println(ans);
  }
}

09 2258. 逃离火灾

这道题其实难倒不是很难，但是有点烦。

import java.util.ArrayList;
import java.util.List;

public class Solution {
  private static final int[][] DIRS = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // 上、右、下、左

  /**
   * 火的 bfs
   *
   * grid: 格子
   * fire: 标记格子上的点是否着火
   * f: bfs 的起始需要遍历的值
   *
   * return bfs 一圈之后所有的着火点
   */
  private List<int[]> spreadFire(int[][] grid, boolean[][] fire, List<int[]> f) {
    int m = grid.length;
    int n = grid[0].length;
    List<int[]> tmp = f;
    f = new ArrayList<>();
    for (int[] p : tmp) {
      for (int[] d : DIRS) { // 枚举上右下左四个方向
        int x = p[0] + d[0];
        int y = p[1] + d[1];
        if (0 <= x && x < m && 0 <= y && y < n && !fire[x][y] && grid[x][y] == 0) {
          fire[x][y] = true; // 标记着火的位置
          f.add(new int[] { x, y });
        }
      }
    }
    return f;
  }

  /**
   * 返回能否在初始位置停留 t 分钟，并安全到达安全屋
   */
  private boolean check(int[][] grid, int t) {
    int m = grid.length;
    int n = grid[0].length;
    boolean[][] onFire = new boolean[m][n];
    List<int[]> f = new ArrayList<>();
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (grid[i][j] == 1) {
          onFire[i][j] = true; // 标记着火的位置
          f.add(new int[] { i, j }); // dfs 的初始值
        }
      }
    }

    // 让火扩散 t 分钟，就是向外扩展 t 圈
    while (t-- > 0 && !f.isEmpty()) { // 如果火无法扩散就提前退出
      f = spreadFire(grid, onFire, f);
    }

    if (onFire[0][0]) { // 起点着火了
      return false;
    }

    // 人的 bfs
    boolean[][] vis = new boolean[m][n];
    vis[0][0] = true;
    List<int[]> nextCircle = List.of(new int[] { 0, 0 }); // 人从 (0, 0) 的位置开始尝试
    while (!nextCircle.isEmpty()) {
      List<int[]> curCircle = nextCircle;
      nextCircle = new ArrayList<>(); // 下一圈
      for (int[] p : curCircle) {
        if (onFire[p[0]][p[1]]) {
          // 如果这个位置已经着火了，因为人走过这一圈之后，火也会走一圈，
          // 这里不需要考虑安全屋，因为如果已经到安全屋的话，那么，就直接返回 true 了
          continue;

        }
        for (int[] d : DIRS) { // 四个方向
          int x = p[0] + d[0];
          int y = p[1] + d[1];
          // 如果在 grid 的边界内，并且这个位置没有着火，并且未访问过，并且这个格子是草地
          if (0 <= x && x < m && 0 <= y && y < n && !onFire[x][y] && !vis[x][y] && grid[x][y] == 0) {
            if (x == m - 1 && y == n - 1) { // 到达安全屋了
              return true;
            }
            vis[x][y] = true; // 防止重复访问
            nextCircle.add(new int[] { x, y });
          }
        }
      }
      f = spreadFire(grid, onFire, f); // 火也要同时扩散
    }
    return false;
  }

  public int maximumMinutes(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int left = -1;
    int right = m * n + 1; // 右边界可以取得大一点
    while (left + 1 < right) {
      int mid = (left + right) >>> 1; // 无符号右移一位
      if (check(grid, mid)) { // 符合条件就延长时间继续尝试
        left = mid;
      } else { // 否则缩减边界
        right = mid;
      }
    }
    return left < m * n ? left : 1_000_000_000;
  }

  public static void main(String[] args) {
    /*
     * 示例 1：
     * 输入：grid =
     * [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0
     * ,0]]
     * 输出：3
     * 解释：上图展示了你在初始位置停留 3 分钟后的情形。
     * 你仍然可以安全到达安全屋。
     * 停留超过 3 分钟会让你无法安全到达安全屋。
     * 
     * 示例 2：
     * 输入：grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
     * 输出：-1
     * 解释：上图展示了你马上开始朝安全屋移动的情形。
     * 火会蔓延到你可以移动的所有格子，所以无法安全到达安全屋。
     * 所以返回 -1 。
     * 
     * 示例 3：
     * 输入：grid = [[0,0,0],[2,2,0],[1,2,0]]
     * 输出：1000000000
     * 解释：上图展示了初始网格图。
     * 注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。
     * 所以返回 109 。
     */
    Solution solu = new Solution();
    int[][] grid = new int[][] { { 0, 2, 0, 0, 0, 0, 0 }, { 0, 0, 0, 2, 2, 1, 0 }, { 0, 2, 0, 0, 1, 2, 0 },
        { 0, 0, 2, 2, 2, 0, 2 }, { 0, 0, 0, 0, 0, 0, 0 } };
    int ans = solu.maximumMinutes(grid);
    System.out.println(ans);

    grid = new int[][] { { 0, 0, 0, 0 }, { 0, 1, 2, 0 }, { 0, 2, 0, 0 } };
    ans = solu.maximumMinutes(grid);
    System.out.println(ans);

    grid = new int[][] { { 0, 0, 0 }, { 2, 2, 0 }, { 1, 2, 0 } };
    ans = solu.maximumMinutes(grid);
    System.out.println(ans);
  }
}

10 2300. 咒语和药水的成功对数

import java.util.Arrays;

public class Solution {

  /**
   * 二分查找
   * 查找最左边的第一个大于 needle 的数
   * 返回其位置
   */
  private int findFirstPotion(int[] potions, long needle) {
    int res = potions.length;
    int left = 0;
    int right = potions.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (potions[mid] > needle) {
        res = mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }

    return res;
  }

  public int[] successfulPairs(int[] spells, int[] potions, long success) {
    int[] pairs = new int[spells.length];
    Arrays.sort(potions);
    for (int i = 0; i < spells.length; i++) {
      long needle = (success + spells[i] - 1) / spells[i] - 1;
      int cur = findFirstPotion(potions, needle);
      if (potions.length != cur) {
        pairs[i] = potions.length - cur;
      }
    }

    return pairs;
  }

  public static void main(String[] args) {

    /*
     * 示例 1：
     * 输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
     * 输出：[4,0,3]
     * 解释：
     * - 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
     * - 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
     * - 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
     * 所以返回 [4,0,3] 。
     *
     * 示例 2：
     * 输入：spells = [3,1,2], potions = [8,5,8], success = 16
     * 输出：[2,0,2]
     * 解释：
     * - 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
     * - 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
     * - 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
     * 所以返回 [2,0,2] 。
     */
    Solution solu = new Solution();
    int[] spells = new int[] { 5, 1, 3 };
    int[] portions = new int[] { 1, 2, 3, 4, 5 };
    long success = 7;
    int[] pairs = solu.successfulPairs(spells, portions, success);
    System.out.println(Arrays.toString(pairs));

    spells = new int[] {3,1,2};
    portions = new int[] {8,5,8};
    success = 16;
    pairs = solu.successfulPairs(spells, portions, success);
    System.out.println(Arrays.toString(pairs));
  }
}

注意这里的这一行处理，

long needle = (success + spells[i] - 1) / spells[i] - 1;

这是一个很有趣的处理方式，这个式子可以保证其结果是，

$$
needle = \left \lceil \frac{success}{spells[i]}\right \rceil - 1
$$

然后，我们只要二分查找，从左找刚好比这个 needle 的第一个数就可以了。

注意看 $spells[i] - 1$ 这个整体，然后，我们知道这里涉及的都是整数，就不难理解了。

11 765. 情侣牵手

这题如果是理解了并查集这个数据结构的话，那么，其实是比较简单的。

核心的地方是这个式子，

$$
(N_1 - 1) + (N_2 - 1) + \dots + (N_n + 1) = (N_1 + N_2 + \dots + N_n) - n = N - n
$$

其中，N 代表的是节点的总数，也就是情侣的对数(总人数除以二)，而 n 则代表的是连通分量的总数。

这里是把两个可以配对的情侣看成是一个节点，然后，如果实际上这两个人没有坐在一起，那么，就是和其他的情侣节点 union 了在了一起。

public class Solution {
  /**
   * 这里是使用路径压缩来处理(递归)，这里 size 其实就没有什么必要了，直接去掉
   */
  private class UnionFind {
    // 记录连通分量
    private int count;
    // 节点 x 的父节点是 parent[x]
    private int[] parent;

    // 构造函数，n 为图的节点总数
    public UnionFind(int n) {
      // 一开始互不连通
      this.count = n;
      // 指向父节点的指针一开始指向自己
      parent = new int[n];
      for (int i = 0; i < n; i++) {
        parent[i] = i;
      }
    }

    // 返回某个节点 x 的根节点
    // 路径压缩，压缩得很彻底，最终除了根节点，所有节点都是指向那唯一一个根节点
    private int find(int x) {
      if (parent[x] != x) {
        parent[x] = find(parent[x]);
      }
      return parent[x];
    }

    // 把 p 和 q 连通起来
    public void union(int p, int q) {
      int rootP = find(p);
      int rootQ = find(q);

      if (rootP == rootQ) {
        return;
      }
      // 将两棵树合并成一棵，并且，要使小树连在大树上面，这样会比较平衡
      parent[rootQ] = rootP;

      count--; // 两个分量合二为一
    }

    // 返回当前的连通分量个数
    public int count() {
      return count;
    }

    public boolean connected(int p, int q) {
      int rootP = find(p);
      int rootQ = find(q);
      return rootP == rootQ;
    }
  }

  public int minSwapsCouples(int[] row) {
    int len = row.length;
    int N = len / 2;
    UnionFind unionFind = new UnionFind(N);
    for (int i = 0; i < len; i += 2) {
      unionFind.union(row[i] / 2, row[i + 1] / 2);
    }
    return N - unionFind.count();
  }

  public static void main(String[] args) {
    /*
     * 示例 1:
     * 输入: row = [0,2,1,3]
     * 输出: 1
     * 解释: 只需要交换row[1]和row[2]的位置即可。
     *
     * 示例 2:
     * 输入: row = [3,2,0,1]
     * 输出: 0
     * 解释: 无需交换座位，所有的情侣都已经可以手牵手了。
     */
    var solu = new Solution();
    int[] row = new int[] { 0, 2, 1, 3 };
    int ans = solu.minSwapsCouples(row);
    System.out.println(ans);

    row = new int[] { 3, 2, 0, 1 };
    ans = solu.minSwapsCouples(row);
    System.out.println(ans);
  }
}