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 有交集。注意：此情况包含 $\subset new$ 、 $\subset curr$ 和 $c u rr = n e w$ 这三种特殊情况。

对每个区间的处理

令新区间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]); // 取 右端点 的较大值
            }
        }

        // 将 最后的新区间 加入 list
        list.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; // 使用成员变量保存 board
    private char[] word; // 使用成员变量保存 word
    private boolean[][] vis; // 判断某个元素是否遍历过
    private int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 方向数组，分别为 向右、向下、向左、向上
}

优化

思路

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

不使用方向数组 dir，而是一个一个地将四个方向写出来。
标记是否遍历过某个元素时可以不使用 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; // 使用成员变量保存 board
    private char[] word; // 使用成员变量保存 word
}