1. 知识点总结

1hAK~奖励自己晚上写课设TASK3🧐

题目	难度	知识点
搜索旋转排序数组	🐸	数组
在排序元素中查找元素的第一位和最后一位	🐸	二分数组（注意边界判别）
组合总和	🐸+0.5🐸	DFS+剪枝胜率太低啦，虽然过了，但是耿耿于怀，需要回炉😐
接雨水	🐸	emm找规律叭，没想到前缀最大这个思路还是蛮难解的

2. 分题题解

2.1 搜索旋转排序数组

emm，LeetCode是不是对于中档题有什么误解……感觉没有PTA乙级难

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len=nums.size();
        //找到目标值，找不到返回-1
        for(int i=0;i<len;i++){
            if(nums[i]==target){
                return i;
            }
        }
        return -1;
    }
};

2.2 在排序元素中查找元素的第一位和最后一位

二分可以降低时间复杂度，其实不二分也不卡就是了

执行用时：4 ms, 在所有 C++ 提交中击败了93.38%的用户

内存消耗：13.2 MB, 在所有 C++ 提交中击败了88.80%的用户

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //挑战log(n)
        int len=nums.size();
        if(len==1){
            if(nums[0]==target){
                return {0,0};
            }else{
                return {-1,-1};
            }
        }
        int left=0,right=len-1;
        bool flag=false;
        while(left<=right){
            int mid=(left+right)/2;
            if(mid<0||mid>=len){
                break;
            }
            if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                flag=true;
                left=mid;
                right=mid;
                break;
            }
        }
        if(!flag){
            return {-1,-1};
        }
        //搜索一下最左和最右
        while(left>=0&&nums[left]==target){
            left--;
        }
        left+=1;
        while(right<len&&nums[right]==target){
            right++;
        }
        right-=1;
        return {left,right};
    }
};

2.3 组合总和

怎么说呢，写出来了但是这个胜率感觉和没写出来木得区别🤣用的思路是DFS，可能没怎么剪枝？

执行用时：136 ms, 在所有 C++ 提交中击败了5.10%的用户

内存消耗：37.2 MB, 在所有 C++ 提交中击败了6.14%的用户

class Solution {
public:
    int len;
    int goal;
    vector<vector<int>>ans;
    vector<int>can;
    void dfs(vector<int>temp,int sum,int num,int nid){
        //首先需要加上num个number
        int number=can[nid];
        for(int i=0;i<num;i++){
            temp.push_back(number);
        }
        sum+=num*number;
        if(sum==goal){
            ans.push_back(temp);
        }else if(sum<goal){
            for(int i=nid+1;i<len;i++){
            //遍历可能的形况
            for(int nnum=1;nnum*can[i]<=goal;nnum++){
                dfs(temp,sum,nnum,i);
            }
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        can=candidates;
        len=candidates.size();
        goal=target;
        for(int i=0;i<len;i++){
            //遍历可能的形况
            for(int num=1;num*candidates[i]<=target;num++){
                dfs({},0,num,i);
            }
        }
        return ans;
    }
};

2.4 接雨水

前缀最大preMax记录下标i之前最大的，后最最大tailMax记录下标i之后最大的

对于每一个位置i接到的雨水=min(preMax[i],tailMax[i])-height[i]

优化的话，其实不需要三遍遍历的，preMax可以在计算雨水的时候算而不是一开始就存下来

执行用时：12 ms, 在所有 C++ 提交中击败了59.88%的用户

内存消耗：17.9 MB, 在所有 C++ 提交中击败了5.34%的用户

class Solution {
public:
    int trap(vector<int>& height) {
        //接雨水
        int len=height.size();
        //前缀最大，后缀最大
        vector<int>preMax(len);
        vector<int>tailMax(len);
        int maxH=-1;
        for(int i=0;i<len;i++){
            maxH=max(height[i],maxH);
            preMax[i]=maxH;
        }
        maxH=-1;
        for(int i=len-1;i>=0;i--){
            maxH=max(height[i],maxH);
            tailMax[i]=maxH;
        }
        int sum=0;
        for(int i=0;i<len;i++){
            sum+=min(tailMax[i],preMax[i])-height[i];
        }
        return sum;
    }
};