代码随想录算法训练营day25 | 题目34、题目2476、题目216、题目17
题目一描述
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9
解题思路
寻找左右边界的一个较为通用的解法，找到目标值后继续移动指针。
代码实现
方法一：
class Solution {
int[] searchRange(int[] nums, int target) {
int leftBorder = getLeftBorder(nums, target);
int rightBorder = getRightBorder(nums, target);
return new int[] { leftBorder, rightBorder };
}
int getLeftBorder(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int leftBorder = -1; // 记录一下leftBorder没有被赋值的情况
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] == target) { // 寻找左边界，nums[middle] == target的时候更新right
leftBorder = middle;
right = middle - 1;
} else if (nums[middle] > target) {
if (leftBorder != -1) {
leftBorder = middle;
}
right = middle - 1;
} else {
left = middle + 1;
}
}
return leftBorder;
}
int getRightBorder(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int rightBorder = -1; // 记录一下rightBorder没有被赋值的情况
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] == target) { // 寻找右边界，nums[middle] == target的时候更新left
rightBorder = middle;
left = middle + 1;
} else if (nums[middle] < target) {
if (rightBorder != -1) {
rightBorder = middle;
}
left = middle + 1;
} else if (nums[middle] > target) {
right = middle - 1;
}
}
return rightBorder;
}
}
题目二描述
给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。
请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：
mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。
返回数组 answer 。
示例 1 ：
输入：root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
输出：[[2,2],[4,6],[15,-1]]
解释：按下面的描述找出并返回查询的答案：
- 树中小于等于 2 的最大值是 2 ，且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。
- 树中小于等于 5 的最大值是 4 ，且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。
- 树中小于等于 16 的最大值是 15 ，且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。
示例 2 ：
输入：root = [4,null,9], queries = [3]
输出：[[-1,4]]
解释：树中不存在小于等于 3 的最大值，且大于等于 3 的最小值是 4 。所以查询的答案是 [-1,4] 。
提示：
树中节点的数目在范围 [2, 10^5] 内
1 <= Node.val <= 10^6
n == queries.length
1 <= n <= 10^5
1 <= queries[i] <= 10^6
解题思路
直接在树上搜索可能会超时，因为没说平衡，最坏的情况，树退化成链表。
所以先把搜索二叉树中序遍历变成数组，再在数组上用二分查找来使用类似找左右边界的方法找到结果。
代码实现
方法一：
class Solution {
public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> nodeList = new ArrayList<>();
dfsToArray(root, nodeList);
int[] nodes = new int[nodeList.size()];
for (int i = 0; i < nodes.length; i++) {
nodes[i] = nodeList.get(i);
}
for (int target : queries) {
res.add(Arrays.asList(findMax(nodes, target), findMin(nodes, target)));
}
return res;
}
private void dfsToArray(TreeNode root, List<Integer> nodeList) {
if (root == null)
return;
dfsToArray(root.left, nodeList);
nodeList.add(root.val);
dfsToArray(root.right, nodeList);
}
private int findMax(int[] nodes, int target) {
int left = 0;
int right = nodes.length - 1;
int res = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nodes[mid] == target) {
return nodes[mid];
} else if (nodes[mid] > target) {
right = mid - 1;
} else if (nodes[mid] < target) {
res = nodes[mid];
left = mid + 1;
}
}
return res;
}
private int findMin(int[] nodes, int target) {
int left = 0;
int right = nodes.length - 1;
int res = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nodes[mid] == target) {
return nodes[mid];
} else if (nodes[mid] > target) {
res = nodes[mid];
right = mid - 1;
} else if (nodes[mid] < target) {
left = mid + 1;
}
}
return res;
}
}
题目三描述
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 9
1 <= n <= 60
解题思路
也是回溯，注意搜索树的最大宽度就是k。
注意剪枝的操作。
代码实现
方法一：
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtracking(k, n, 1, path, res, 0);
return res;
}
private void backtracking(int k, int n, int startIndex, List<Integer> path, List<List<Integer>> res, int sum) {
if (path.size() == k) {
if (sum == n)
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝，限制startIndex取到的范围
sum += i;
if (sum > n) { // 第二处剪枝，当前和大于目标值就没必要再加新的路径
return;
}
path.add(i);
backtracking(k, n, i + 1, path, res, sum);
sum -= i;
path.removeLast();
}
}
}
技巧总结
removeLast的运用，这里其实是错的，
只有 LinkedList<Integer> path = new LinkedList<>(); 才能用
List是不行的，统一用path.remove(path.size() - 1)比较好。
题目四描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
解题思路
回溯算法，注意for循环范围是从0开始，与startIndex无关。
代码实现
方法一：
class Solution {
List<String> map = Arrays.asList("", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz");
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits.length() == 0)
return res;
StringBuilder path = new StringBuilder();
backtracking(digits, 0, res, path);
return res;
}
private void backtracking(String digits, int startIndex, List<String> res, StringBuilder path) {
if (path.length() == digits.length()) {
res.add(path.toString());
return;
}
int curKey = digits.charAt(startIndex) - '0'; // char类型转整型，用这种方法
String letters = map.get(curKey);
for (int i = 0; i < letters.length(); i++) { // 注意从0开始
path.append(letters.charAt(i));
backtracking(digits, startIndex + 1, res, path);
path.deleteCharAt(path.length() - 1); // 删除最后一个字符
}
}
}
技巧总结
学会char类型转整型
学会stringBuilder删除最后一个字符
