C/C++教程

算法题解(Leetcode 33、34、39、42、46)

本文主要是介绍算法题解(Leetcode 33、34、39、42、46),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

    • 33. 搜索旋转排序数组 - 中等 - 9/17
    • 34. 在排序数组中查找元素的第一个和最后一个位置 - 中等 - 9/18
    • 39. 组合总和 - 中等 - 9/22
    • 42. 接雨水 - 困难 - 9/23
    • 46. 全排列 - 中等 - 9/24

33. 搜索旋转排序数组 - 中等 - 9/17

33. 搜索旋转排序数组 - 中等

整数数组 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

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

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

46. 全排列 - 中等

给定一个不含重复数字的数组 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]]

在这里插入图片描述

这篇关于算法题解(Leetcode 33、34、39、42、46)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!