文章目录
33. 搜索旋转排序数组 - 中等 - 9/17
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
解法一：
直接遍历查找
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int i=0;
while(i<len){
if(nums[i] == target){
return i;
}
i++;
}
return -1;
}
}
解法二：
二分查找，把数组分成左右两半部分，判断哪一部分是有序的，然后在有序的部分判断target是否在范围内，在 就 继续二分缩小范围，不在就到另外一半部分里查找。
class Solution {
public int search(int[] nums, int target) {
int right = nums.length-1; //右指针
if(right<0) return -1;
if(right == 0) return nums[0]==target? 0:-1;
int left = 0; //左指针
int mid = 0; //中位数下标
while(left<=right){
mid = (left+right)/2; //计算中位数
if(nums[mid] == target) return mid;
if(nums[left] <= nums[mid]){ //左半边有序
if(target >= nums[left] && target < nums[mid]){ //target在左半边
right = mid - 1;
}else{
left = mid + 1;
}
}else{ //右半边有序
if(target > nums[mid] && target <= nums[right]){//target在右半边
left = mid + 1;
}else{
right = mid - 1;
}
}
}
return -1;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置 - 中等 - 9/18
34. 在排序数组中查找元素的第一个和最后一个位置 - 中等 - 9/18
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
- 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
解析：
l 指针掌管左边蓝色区域， rr 指针掌管右边红色区域，两者互不冲突，通过不断向目标元素靠近扩大掌管区域，直到两者掌管区域接壤。
二分查找起始状态：
二分查找终止状态：
＜ 、≤ 、≥ 、＞ 目标元素对应的蓝红区域划分
总结模板：
class Solution {
public int[] searchRange(int[] nums, int target) {
//左边界
int leftIdx = binarySearchLeft(nums, target);
//右边界
int rightIdx = binarySearchRight(nums, target);
//判断是否符合
if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
return new int[]{leftIdx, rightIdx};
}
return new int[]{-1, -1};
}
//找左边界的二分查找
public int binarySearchLeft(int[] nums, int target) {
//注意左右指针的初始值
int left = -1, right = nums.length;
while (left+1 != right) {
int mid = (left + right) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid;
}
}
return right;
}
//找右边界的二分查找
public int binarySearchRight(int[] nums, int target) {
//注意左右指针的初始值
int left = -1, right = nums.length;
while (left+1 != right) {
int mid = (left + right) / 2;
if (nums[mid] <= target) {
left = mid;
} else {
right = mid;
}
}
return left;
}
}
时间复杂度：O（log（n））。
空间复杂度：O（1）。
39. 组合总和 - 中等 - 9/22
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
解析：
先向前列举所有情况，得到一个解或者走不通的时候就回溯。
class Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//存放结果
res = new ArrayList<>();
//排序
Arrays.sort(candidates);
//回溯
backtrack(candidates,target,new ArrayList<>(),0);
return res;
}
//回溯
private void backtrack(int[] candidates,int remains,List<Integer> path,int start){
//如果做减法后剩下0，则把这条路径添加进来
if(remains == 0){
res.add(new ArrayList<>(path));
return;
}
//遍历
for(int i=start; i<candidates.length; i++){
//如果剩余值小于0，就返回
if(remains-candidates[i] < 0) return;
//剪枝 即去掉相同数的路径 如[2,2,3,7] 去掉第二个2。
if(i > 0 && candidates[i] == candidates[i-1]) continue;
//添加元素到路径
path.add(candidates[i]);
//回溯
backtrack(candidates, remains-candidates[i], path, i);
//找到了一个解或者 remains < 0 了，将当前数字移除，然后继续尝试
path.remove(path.size()-1);
}
}
}
42. 接雨水 - 困难 - 9/23
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
方法一：双指针
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1; //定义左右指针
int ans = 0; //结果
int left_max = 0, right_max = 0; //左右当前的最大值
while(left<right){
if(height[left] < height[right]){ //如果左边高度比右边小
if (height[left] >= left_max){ //如果左边当前值 大于等于 左边最大值，则更新左边最大值
left_max = height[left];
} else { //否则 就可累加计算雨水量
ans += (left_max - height[left]);
}
++left; //移动左指针
} else { //如果左边高度比右边大
if(height[right] >= right_max){ //如果右边当前值 大于等于 右边最大值，则更新右边最大值
right_max = height[right];
} else { //否则 就可累加计算雨水量
ans += (right_max - height[right]);
}
--right; //移动右指针
}
}
return ans;
}
}
时间复杂度：O(n)。
空间复杂度：O(1)。
方法二：动态规划
class Solution {
public int trap(int[] height) {
int len = height.length; //长度
if(len == 0){
return 0;
}
//从左往右遍历，记录左边最高值
int[] left_max = new int[len];
left_max[0] = height[0];
for(int i=1; i<len; i++){
left_max[i] = Math.max(left_max[i-1],height[i]);
}
//从右往左遍历，记录右边最高值
int[] right_max = new int[len];
right_max[len-1] = height[len-1];
for(int j=len-2; j>=0; j--){
right_max[j] = Math.max(right_max[j+1],height[j]);
}
//计算接水量
int sum = 0;
for(int k=0; k<len; k++){
sum += Math.min(left_max[k],right_max[k]) - height[k];
}
return sum;
}
}
时间复杂度：O(n)，其中n是数组height的长度。计算数组leftMax和rightMax的元素值各需要遍历数组height一次，计算能接的雨水总量还需要遍历一次。
空间复杂度：O(n)，其中n是数组height的长度。需要创建两个长度为n的数组leftMax 和 rightMax。
46. 全排列 - 中等 - 9/24
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
解析：回溯法
利用递归每次向 temp 里添加一个数字，数字添加够以后再回来进行回溯，再向后添加新的解。
可以理解成一层一层的添加，每一层都是一个 for 循环。
每调用一层就进入一个 for 循环，相当于列出了所有解，然后挑选了我们需要的。其实本质上就是深度优先遍历 DFS。
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>(); //存放结果
backtrack(nums,res,new ArrayList<>()); //回溯
return res; //返回结果
}
private void backtrack(int[] nums,List<List<Integer>> res, List<Integer> tempList){
if(tempList.size() == nums.length){ //如果临时列表长度 等于 数组的长度 就添加并返回
res.add(new ArrayList<>(tempList));
return;
}
for(int i=0; i<nums.length; i++){
if(tempList.contains(nums[i])) continue; //如果已经存在元素，跳过
tempList.add(nums[i]); //添加元素
backtrack(nums,res,tempList); //回溯 向后继续添加
tempList.remove(tempList.size() - 1); //将 tempList 刚添加的元素，去掉，尝试新的元素
}
}
}
分析：
递归之前 => [1]
递归之前 => [1, 2]
递归之前 => [1, 2, 3]
递归之后 => [1, 2]
递归之后 => [1]
递归之前 => [1, 3]
递归之前 => [1, 3, 2]
递归之后 => [1, 3]
递归之后 => [1]
递归之后 => []
递归之前 => [2]
递归之前 => [2, 1]
递归之前 => [2, 1, 3]
递归之后 => [2, 1]
递归之后 => [2]
递归之前 => [2, 3]
递归之前 => [2, 3, 1]
递归之后 => [2, 3]
递归之后 => [2]
递归之后 => []
递归之前 => [3]
递归之前 => [3, 1]
递归之前 => [3, 1, 2]
递归之后 => [3, 1]
递归之后 => [3]
递归之前 => [3, 2]
递归之前 => [3, 2, 1]
递归之后 => [3, 2]
递归之后 => [3]
递归之后 => []
输出的结果：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]