LeetCode 441, 57, 79

441. 排列硬币

题目链接

441. 排列硬币

标签

数学 二分查找

思路

由于本题所返回的 答案在区间 [1, n] 内，并且 答案越大，所需要的硬币越大 (有序)，所以采用 二分枚举答案 的思想。

由于要找 最多 的完整阶梯的总行数，所以使用二分法的 前驱 实现，因为一个数的前驱是 最后一个小于该数 的数。不了解二分法的后继与前驱的可以看这篇文章：算法——二分法。

代码

class Solution {public int arrangeCoins(int n) {// 二分枚举答案long left = 1, right = n; // 答案的区间为 [1, n]while (left < right) { // 使用二分法的 前驱 实现long mid = left + (right - left + 1 >> 1); // 猜想答案if (n < sum(mid)) { // 如果 猜想的答案 太大了right = mid - 1; // 则 缩小 猜想的答案} else { // 如果 猜想的答案 太小了 或 猜对了left = mid; // 则 扩大 猜想的答案}}return (int) left;}// 获取 layer 层阶梯 需要的硬币总数private long sum(long layer) {return layer * (layer + 1) / 2;}
}

57. 插入区间

题目链接

57. 插入区间

标签

数组

思路

由于题目中提示 可以不原地修改 intervals，所以可以创建一个 List<int[]> 类型的变量 list，将所有的区间都添加到 list 中，同时 合并重叠的区间，在最后返回 list 转换为 int[][] 的形式。本题的重点在于如何合并区间。

两个区间的情况

如上图，区间 curr 和 区间 new 之间共有 3 中情况：

• 如果 interval[1] < left，则 curr 在 new 左边。
• 如果 right < interval[0]，则 curr 在 new 右边。
• 如果以上两种情况都不满足，并且有 interval[0] < right，则 curr 与 new 有交集。注意：此情况包含 $curr\subset new$、$new\subset curr$ 和 $curr=new$ 这三种特殊情况。

对每个区间的处理

令 新区间newInterval 的左、右端点分别为 left, right，从区间的集合 intervals 中取出单个区间 interval，其左、右端点分别为 interval[0], interval[1]，则对于 新区间 new 和 当前选取的区间 curr，根据不同情况可分为以下三种处理方式：

• 当 curr 在 new 左边时，直接将 当前区间curr 加入到 list 中。
• 当 curr 在 new 右边时，将 新区间new 加入到 list 中，并把 当前区间curr 当作 新区间new。
• 当 curr 与 new 有交集时，将 当前区间curr 合并到 新区间new 中，此时新区间的端点值需要被更新，左端点更新为 较小 的左端点，右端点更新为 较大 的右端点。

最终的处理

这种处理方式会导致 最后的新区间 没有被加入到 list 中，以下，针对 倒数第二个区间curr 和 新区间new 做如下讨论，证明 最后的新区间 没有被加入到 list 中：

• 当 curr 在 new 左边时，只将 倒数第二个区间curr 加入到 list 中，而没有将 new 加入到 list 中。
• 当 curr 在 new 右边时，只将 新区间new 加入到 list 中，而没有将被看作 新区间new 的倒数第二个区间curr 加入到 list 中。
• 当 curr 与 new 有交集时，只是更新了 新区间new 的左、右端点，而没有将其加入到 list 中。

综上所述，最后的新区间 确实没有被加入到 list 中，所以在返回结果之前得先把 最后的新区间 加入到 list 中。

代码

class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {if (intervals.length == 0){ // 如果 intervals 为空return new int[][]{newInterval}; // 则将 newInterval 作为唯一的区间返回}int left = newInterval[0], right = newInterval[1]; // left, right 分别为 合并后的新区间的 左端点 和 右端点List<int[]> list = new ArrayList<>(intervals.length);for (int[] interval : intervals) {if (right < interval[0]) { // 如果 当前区间的左端点 大于 新区间的右端点，即 curr 在 new 右边// 注意这里不能直接写 list.add(newInterval)// 因为新区间可能经过合并，此时左、右端点可能就与原来不同了list.add(new int[]{left, right}); // 则将新区间加入 list// 将 当前区间 当作 新区间left = interval[0];right = interval[1];} else if (interval[1] < left) { // 如果 当前区间的右端点 小于 新区间的左端点，即 curr 在 new 左边list.add(interval); // 将当前区间加入 list} else { // 当前区间与新区间有交集，合并它们left = Math.min(left, interval[0]); // 取 左端点 的较小值right = Math.max(right, interval[1]); // 取 右端点 的较大值}}// 将 最后的新区间 加入 listlist.add(new int[]{left, right});return list.toArray(new int[list.size()][]); // 将 List<int[]> 转为 int[][]}
}

79. 单词搜索

题目链接

79. 单词搜索

标签

数组 字符串 回溯 矩阵

原理

思路

本题可以使用 深度优先搜索 的思想：以矩阵中每个元素作为 word 的起始字符，搜索合适的字符串，如果能找到合适的字符串，则返回 true。步骤如下：

• 如果要遍历一个字符，那么它得满足以下 3 个条件，如果任意一个不成立，则返回 false；否则继续匹配。
  1. 当前字符在矩阵 board 中
  2. 当前字符没有被遍历过
  3. 当前字符与本轮搜索要匹配的 word 中的字符相等
• 如果当前字符匹配的是 word 中的最后一个字符，则可以返回 true，代表找到合适的字符串了；否则继续匹配。
• 标记当前字符已被遍历过了。
• 分别向上下左右搜索下一个字符，如果其中有一个方向匹配成功，则直接返回 false。
• 取消遍历过当前字符的标记，清除本次搜索对下一次搜索的影响。
• 如果能到这一步，则说明没有匹配成功，返回 false。

由于 同一个单元格内的字母不允许被重复使用，所以 在搜索时得记录每个元素是否遍历过，可以使用 boolean[][] 来记录 board 中的每个元素是否遍历过。

代码

class Solution {public boolean exist(char[][] board, String word) {// 对成员变量进行赋值ROW = board.length;COL = board[0].length;this.vis = new boolean[ROW][COL];this.board = board;this.word = word.toCharArray();// 以矩阵中每个元素作为 word 的起始字符，搜索合适的字符串for (int r = 0; r < ROW; r++) {for (int c = 0; c < COL; c++) {if (dfs(r, c, 0)) { // 如果能找到合适的字符串return true; // 则返回 true}}}return false; // 找不到合适的字符串，返回 false}// (r, c) 指向 board 中的字符，curr 指向 word 中的字符private boolean dfs(int r, int c, int curr) {if (!(r >= 0 && r < ROW && c >= 0 && c < COL) // 如果 (r, c) 指向的元素在矩阵外|| vis[r][c] // 或 (r, c) 指向的元素已被遍历过|| board[r][c] != word[curr]) { // 或 字符匹配失败return false; // 则返回 false} else if (curr == word.length - 1) { // 当前字符匹配成功，如果当前字符匹配的是最后一个字符return true; // 则返回 true}vis[r][c] = true; // 标记遍历过 (r, c) 指向的元素for (int k = 0; k < 4; k++) { // 枚举四个方向int kr = r + dir[k][0], kc = c + dir[k][1]; // (kr, kc) 指向待遍历的元素if (dfs(kr, kc, curr + 1)) { // 如果后面的字符都匹配成功了return true; // 则返回 true}}vis[r][c] = false; // 取消 遍历过 (r, c) 指向元素的标记return false; // 匹配失败，返回 false}private int ROW; // 矩阵的行数private int COL; // 矩阵的列数private char[][] board; // 使用成员变量保存 boardprivate char[] word; // 使用成员变量保存 wordprivate boolean[][] vis; // 判断某个元素是否遍历过private int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 方向数组，分别为 向右、向下、向左、向上
}

优化

思路

上面的代码运行起来比较慢，主要有两个优化点：

1. 不使用方向数组 dir，而是一个一个地将四个方向写出来。
2. 标记是否遍历过某个元素时可以不使用 boolean[][] vis，而是将 board 的字符变为一个与英文字母不相关的字符——'\0'，然后再将其还原为原本的字母，这样在判断时就将 vis[r][c] 合并到 匹配字符的操作 board[r][c] != word[curr] 中，这样做可以减少时间的浪费。

代码

class Solution {public boolean exist(char[][] board, String word) {// 对成员变量进行赋值ROW = board.length;COL = board[0].length;this.board = board;this.word = word.toCharArray();// 以矩阵中每个元素作为 word 的起始字符，搜索合适的字符串for (int r = 0; r < ROW; r++) {for (int c = 0; c < COL; c++) {if (dfs(r, c, 0)) { // 如果能找到合适的字符串return true; // 则返回 true}}}return false; // 找不到合适的字符串，返回 false}// (r, c) 指向 board 中的字符，curr 指向 word 中的字符private boolean dfs(int r, int c, int curr) {if (!(r >= 0 && r < ROW && c >= 0 && c < COL) // 如果 (r, c) 指向的元素在矩阵外=|| board[r][c] != word[curr]) { // 或 字符匹配失败return false; // 则返回 false} else if (curr == word.length - 1) { // 当前字符匹配成功，如果当前字符匹配的是最后一个字符return true; // 则返回 true}board[r][c] = '\0'; // 标记遍历过 (r, c) 指向的元素boolean res = dfs(r, c + 1, curr + 1) // 向右|| dfs(r + 1, c, curr + 1) // 向下|| dfs(r - 1, c, curr + 1) // 向左|| dfs(r, c - 1, curr + 1); // 向上 分别向四个方向搜索能否找到合适的字符串board[r][c] = word[curr]; // 取消 遍历过 (r, c) 指向元素的标记return res; // 返回 分别向四个方向搜索能否找到合适的字符串}private int ROW; // 矩阵的行数private int COL; // 矩阵的列数private char[][] board; // 使用成员变量保存 boardprivate char[] word; // 使用成员变量保存 word
}