LeetCode 374, 128, 17

374. 猜数字大小

题目链接

374. 猜数字大小

标签

二分查找 交互

思路

看到本题的标签 交互 感觉有些奇怪，交互 意味着需要调用题目给出的方法。我们写的 guessNumber() 是用来猜数字的，而给出的 guess() 则是裁判。

本题可以采用二分法的常规实现——求指定值的位置或其后继的位置，如果不懂二分法的后继和前驱，可以看这篇文章：算法——二分法。

唯一不同于普通二分法的是：没有给出 数组nums 和目标值target，但是给出了 对猜想值大小的判断，即 guess()方法。实际上，二分法 在判断下一次查找是在左子区间还是右子区间时 使用的 if-else 就是 对猜想值大小的判断，例如：target <= nums[mid] 的含义是 目标值小于或等于区间中点，也就是 猜大了 或者 猜对了，即 guess() 返回 -1, 0。

代码

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 0, right = n;
        while (left < right) {
            int mid = left + (right - left >> 1); // mid是猜想的值
            if (guess(mid) <= 0) { // 如果guess的结果小于或等于0，即 猜大了 或 猜对了
                right = mid; // 让right变小，从而缩小猜想的值
            } else { // 如果guess的结果大于0，即 猜小了
                left = mid + 1; // 让left变大，从而增大猜想的值
            }
        }
        return left;
    }
}

128. 最长连续序列

题目链接

128. 最长连续序列

标签

并查集 数组 哈希表

Set

思路

最长连续序列不关心数字的顺序，也不关心数字出现的次数，所以可以对数字做 预处理，即将数字存储到 HashSet 中，这是因为 HashSet 中不存放重复元素，也就是说对数字做了 去重 操作。

将所有数字都放入到 HashSet 中后，就可以遍历整个 HashSet，然后从其中获取元素，并判断这个元素是否存在它的下一个元素、下下一个元素等，直到不存在为止。判断存在性时，需要记录连续元素的最大值，即 判断存在性之前 应该 先获取判断的是哪一个数是否存在，这个数就是连续元素的最大值；此外，还需要使用一个变量来记录连续的元素个数，当退出判断时这个变量就是本次连续元素的长度，将其与结果值中的较大值赋值给结果值。

本题解的精髓不在上面这些基本操作，而是在于 控制时间复杂度。如果真的像上面这样写，则时间复杂度为 $O(n^2)$。可以发现，对于 元素num 和 元素num - 1，上面的思路会将这两个元素都判断一遍，但以 num 为起始元素的连续元素的长度 一定比 以 num - 1 为起始元素的连续元素的长度 小 $1$。对于获取最大连续元素长度的要求，对 num 的判断 不是必需的。所以在 num - 1 存在时，跳过对 num 的判断，这就将 $O(n^2)$ 的复杂度转化为 $O(n)$ 的复杂度了。

代码

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>(); // 储存数字的集合

        // 先把所有数字都加入集合，即对数字去重
        for (int num : nums) {
            set.add(num);
        }

        int res = 0; // 储存结果
        for (int num : set) {
            if (set.contains(num - 1)) { // 如果集合中存在当前数的上一个数
                continue; // 则跳过本次循环，这是O(n)的关键
            }

            int currNum = num; // 连续数字的最大数
            int currLen = 1; // 连续数字的长度
            while (set.contains(++currNum)) { // 直到不存在连续的数为止
                currLen++; // 增加连续数字的长度
            }
            res = Math.max(res, currLen); // 取更大的连续数字长度作为结果值
        }
        return res;
    }
}

Sort

思路

HashSet 的操作，例如 add(), contains() 都是外部API调用，在力扣的判题系统中很浪费时间，而上面这种解法需要使用很多次这样的操作，所以需要少调用一些外部API。

本题的核心在于 顺序+去重，HashSet 用自身的不重复性满足了 去重，使用 contains() 满足了 顺序；除此之外，还可以使用 排序 满足 顺序，通过 只有相邻元素之差等于 1 时才让长度加一 的操作来满足 去重。

代码

class Solution {
    public int longestConsecutive(int[] nums) {
        int n = nums.length; // 存储数组长度
        if (n < 2) { // 如果数组长度比2小
            return n; // 则直接返回它的长度，不需要判断
        }

        Arrays.sort(nums); // 对数组进行排序

        int res = 0; // 存储结果
        // 从第二个元素开始判断，默认第一个元素是为连续元素中的第一个元素
        int curr = 1; // 存储 连续元素的最大值的索引
        while (curr < n) { // 直到遍历完整个nums才退出循环
            int currLen = 1; // 存储当前连续元素的长度
            // curr在nums内 并且 相邻元素之差小于等于1 才进行循环
            while (curr < n && nums[curr] - nums[curr - 1] <= 1) {
                if (nums[curr] != nums[curr - 1]) { // 如果相邻元素不相等，即差为1
                    currLen++; // 则当前连续元素的个数+1
                }
                curr++; // 判断下一个元素是否连续
            }

            res = Math.max(res, currLen); // 更新结果值
            curr++; // 从下一个元素开始判断，默认当前元素是连续元素中的第一个元素
        }
        return res;
    }
}

17. 电话号码的字母组合

题目链接

17. 电话号码的字母组合

标签

哈希表 字符串 回溯

思路

组合 就是 将多个选择的结果聚合到一起。在本题中，字符 2-9 都对应着不同的多个字符，本题的组合就是 对于 digits 中的每个数字，从其对应的字符中选取一个字符，最终拼接而成的字符串。

本题可以使用 深度优先搜索 的思想：在 digits 上进行搜索，每次搜索都将当前数字对应的所有字符都选取一遍。每次选择完毕一个字符，就搜索下一个数字所对应的字符，直到将整个 dights 搜索完，此时将拼接的字符串加入结果集合。

代码

class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) { // 如果字符串为空
            return res; // 则返回空集合
        }
        dfs(digits.toCharArray(), 0);
        return res;
    }

    private List<String> res = new ArrayList<>(); // 储存结果的集合
    private StringBuilder builder = new StringBuilder(); // 存储拼接的字符串

    /**
     * 对digits进行深度优先搜索
     * @param digits 待搜索数组
     * @param curr 当前元素的索引
     */
    private void dfs(char[] digits, int curr) {
        if (curr == digits.length) { // 如果遍历完了整个数组
            res.add(builder.toString()); // 则将拼接的字符串放入结果集合
            return; // 然后返回
        }
        for (char ch : mapper[digits[curr] - '2']) { // 取出当前元素映射的所有字符
            builder.append(ch); // 先将字符拼接到字符串

            dfs(digits, curr + 1); // 然后进行下一个元素的遍历

            builder.deleteCharAt(builder.length() - 1); // 最后将这个字符从字符串中删去
        }
    }
    
    private char[][] mapper = new char[][]{
        {'a', 'b', 'c'},
        {'d', 'e', 'f'},
        {'g', 'h', 'i'},
        {'j', 'k', 'l'},
        {'m', 'n', 'o'},
        {'p', 'q', 'r', 's'},
        {'t', 'u', 'v'},
        {'w', 'x', 'y', 'z'}
    }; // 数字2-9与字符的映射
}