LeetCode 74, 228, 39

74. 搜索二维矩阵

题目链接

74. 搜索二维矩阵

标签

数组 二分查找 矩阵

思路

对于本题条件中的矩阵，有两种做法：

• 可以把矩阵的每一行都“拼接”起来，形成一个“一维数组”，在这个“一维数组”中使用二分查找即可，实际上不是拼接，而是将 对一维数组的索引 映射到 矩阵的行和列 中
• 还可以使用两次二分查找，第一次二分查找找到合适的行，第二次二分查找在合适的行中找target。

本题解采用的做法是第二种，在确定具体做法前希望大家对二分法的后继和前驱有一定的理解，这很重要！如果不理解，则可以看这篇文章：算法——二分法。里面提到了两个东西：

1. 找值或其后继 的位置 意味着如果能找到值，则返回值的位置；否则找比 这个值大的第一个数的位置。
2. 找值或其前驱 的位置 意味着如果能找到值，则返回值的位置；否则找比 这个值小的最后一个数的位置。

对于找合适的行，本题解将每行 第一个 数与 target 做比较，如果某一行第一个数比 target 小，并且它的下一行第一个数比 target 大，则说明这一行就是合适的行。这样的场景恰好适合使用 前驱 实现：合适的行就是 最后一个满足 第一个值小于 target 的行。

对于在合适的行中找 target，这是一个最简单的二分查找，无论使用 后继 还是 前驱 都可以。

代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 找到合适的行，使用前驱实现
        int leftRow = 0, rightRow = matrix.length - 1;
        while (leftRow < rightRow) {
            int mid = leftRow + (rightRow - leftRow + 1 >> 1);
            if (target < matrix[mid][0]) {
                rightRow = mid - 1;
            } else if (target > matrix[mid][0]) {
                leftRow = mid;
            } else {
                return true;
            }
        }

        // 在合适的行中寻找target，使用后继实现(使用前驱实现也可以)
        int[] nums = matrix[leftRow];
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left >> 1);
            if (target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return nums[left] == target;
    }
}

228. 汇总区间

题目链接

228. 汇总区间

标签

数组

思路

本题的解法很简单，最明显的思路就是 找连续子序列，连续子序列中的第一个元素和最后一个元素的值就是区间的左端点和右端点。如果连续子序列只有一个值，则直接将这个值作为区间字符串加入结果集合；否则使用 left->right 的形式，将区间的左右端点放入对应位置，并将这个字符串加入结果集合。

现在讲讲 找连续子序列 的思路：使用 快慢指针，慢指针指向区间的左端点，快指针搜索区间右端点的索引，快指针始终应该比慢指针 快1，快指针每次都向右移动一个单位，直到 快指针遍历完整个数组 或 快指针指向的值与上一个快指针指向的值 的差不等于1，快指针才停止移动，最终快指针指向区间右端点的下一个值，所以区间右端点就是快指针减一。

将合适的字符串加入结果集合后，应该把区间的慢指针更新到最终快指针指向的位置，然后快指针右移一位。

代码

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>(); // 存储结果的集合

        int n = nums.length; // 数组长度
        int slow = 0, fast = 1; // slow, fast分别是 慢指针 和 快指针，快指针始终应该比慢指针快一
        while (fast <= n) { // 当fast==n时，slow==n-1，此时还剩最后一个元素没有遍历
            // 直到 fast指向的元素 减 i - 1指向的元素 不等于1 或 超出数组范围 才退出循环
            while (fast < n && nums[fast] - nums[fast - 1] == 1) {
                fast++;
            }

            // 先拼接左端点的值，如果左右端点相同，直接将本StringBuilder转成字符串即可
            StringBuilder builder = new StringBuilder(nums[slow] + "");
            if (slow < fast - 1) { // 如果左右端点不同，则再拼接 -> 和 右端点的值
                builder.append("->").append(nums[fast - 1] + "");
            }
            res.add(builder.toString());

            slow = fast; // 更新慢指针到快指针位置处
            fast++; // 让快指针右移一位，这是为了让快指针比慢指针快一
        }
        
        return res;
    }
}

39. 组合总和

题目链接

39. 组合总和

标签

数组 回溯

思路

本题就是在候选数组 candidates 中任意选取元素，然后将其组合起来，看和是否等于 目标值 target，对于这种 选取，我们可以使用 深度优先搜索 的思想，具体的步骤如下：

• 检查本次的目标值是否为 0，如果是，则说明组合中的元素满足要求，将其放入结果集合中；如果不是，则对候选数组 candidates 中的“每个”元素都进行搜索。
• 如果当前元素比目标值大，则跳过对当前元素的组合；否则才进行组合。
• 将当前元素放入组合中。
• 搜索组合中的下一个元素（进行递归）。
• 将当前元素从组合中移除。

由于要保证 组合是不重复的，所以不能遍历整个候选数组 candidates，而应该 跳过已经遍历的元素，即在搜索的方法中要传 当前元素索引 这个参数，遍历直接从 当前元素索引 处开始。

针对组合的操作有三个：

1. 将组合中的元素放入结果集合
2. 将当前元素放入组合
3. 将当前元素从组合中移除

后两个操作是典型的 先进后出，而 栈 也可以作为构造 ArrayList 的参数，所以组合使用 栈 这种数据结构来存储比较好。

代码

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0);
        return res;
    }

    private List<List<Integer>> res = new ArrayList<>(); // 存储结果的集合
    private LinkedList<Integer> stack = new LinkedList<>(); // 存储数字的栈

    private void dfs(int[] candidates, int target, int curr) {
        if (target == 0) { // 如果本次要找的目标值为0
            res.add(new ArrayList<>(stack)); // 则将栈中的数字作为集合放到结果集合中
            return; // 并返回
        }

        // 从索引为curr的元素开始，不断地组合
        for (int i = curr; i < candidates.length; i++) {
            int c = candidates[i]; // 获取当前元素
            if (target < c) { // 如果当前元素比target大
                continue; // 则无需组合，跳过它
            }

            // 将当前元素入栈
            stack.push(c);

            // 搜索栈中的下一个元素
            dfs(candidates, target - c, i);

            // 将当前元素出栈
            stack.pop();
        }
    }
}