代碼隨想錄算法訓練營day24 | 題目77、題目35

題目一描述

77. 組合

給定兩個整數(shù) n 和 k，返回范圍 [1, n] 中所有可能的 k 個數(shù)的組合。
你可以按 任何順序 返回答案。

示例 1：
輸入：n = 4, k = 2
輸出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2：
輸入：n = 1, k = 1
輸出：[[1]]

提示：

1 <= n <= 20
1 <= k <= n

解題思路

理解并背下來回溯的模板，與之前的path回溯很接近。

def backtrack(...):
    for 選擇 in 選擇列表:
        做選擇
        backtrack(...)
        撤銷選擇

注意剪枝的操作，一般是在for循環(huán)做這個。

代碼實現(xiàn)

方法一：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtrack(1, n, k);
        return res;
    }

    private void backtrack(int startIndex, int n, int k) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 一共需要的元素 k 個
        // 當前已經(jīng)選擇的元素 path.size()個, 不要用startIndex來表示這個量，因為每次size都會變
        // startIndex 目前要選擇的第一個元素
        // n - (k - path.size()) + 1 代表i能取到的最大的元素，比如 n = 4, k = 3, size = 0
        // 由于要取3個數(shù)，i范圍是從1到2，從3開始取沒有意義了。
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            backtrack(i + 1, n, k);
            path.remove(path.size() - 1);
        }
    }
}

題目二描述

35. 搜索插入位置

給定一個排序數(shù)組和一個目標值，在數(shù)組中找到目標值，并返回其索引。如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置。

請必須使用時間復雜度為 O(log n) 的算法。

示例 1:
輸入: nums = [1,3,5,6], target = 5
輸出: 2

示例 2:
輸入: nums = [1,3,5,6], target = 2
輸出: 1

示例 3:
輸入: nums = [1,3,5,6], target = 7
輸出: 4

提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 為 無重復元素 的 升序 排列數(shù)組
-10^4 <= target <= 10^4

解題思路

在一般的二分查找中，如果沒有找到元素，終止條件之后left一定等于right+1，而left的位置一定就是這個元素要插入的位置。

代碼實現(xiàn)

方法一：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return left;
        // return right + 1;
    }
}