代码随想录算法训练营day24 | 题目77、题目35
题目一描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 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循环做这个。
代码实现
方法一：
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 个
// 当前已经选择的元素 path.size()个, 不要用startIndex来表示这个量，因为每次size都会变
// startIndex 目前要选择的第一个元素
// n - (k - path.size()) + 1 代表i能取到的最大的元素，比如 n = 4, k = 3, size = 0
// 由于要取3个数，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);
}
}
}
题目二描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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 为 无重复元素 的 升序 排列数组
-10^4 <= target <= 10^4
解题思路
在一般的二分查找中，如果没有找到元素，终止条件之后left一定等于right+1，而left的位置一定就是这个元素要插入的位置。
代码实现
方法一：
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;
}
}
