leetcode刷题打卡

• 一、组合总和
• 二、组合总和2
• 三、缺失的第一个正数
• 四、接雨水
• 五、字符串相乘

一、组合总和

• 题目：
  

• 题解（递归）：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }

        // 如果 sum + candidates[i] > target 就终止遍历
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();

        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        sort(candidates.begin(), candidates.end()); // 需要排序
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

二、组合总和2

• 题目：
  

• 题解（递归–剪枝）：

  该解法比上一题的解法多了剪枝：

   if(i>index&&candiates[i]==candiates[i-1])  
  continue;
  

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        if(candidates[0]>target)    return {};
        vector<vector<int>>res;
        vector<int>cabine;
        dfs(res,candidates,cabine,target,0);
        return res;
    }  
private:
    void dfs(vector<vector<int>>&res,vector<int>&candiates,vector<int>&cabine,int target,int index){
        if(target==0){
            res.emplace_back(cabine);
            return;
        }
        for(int i=index;i<candiates.size()&&target-candiates[i]>=0;i++){
            if(i>index&&candiates[i]==candiates[i-1])   continue;
            cabine.emplace_back(candiates[i]);
            dfs(res,candiates,cabine,target-candiates[i],i+1);
            cabine.pop_back();
        }
        
    }
};

三、缺失的第一个正数

• 题目:
  

• 题解：
  把数组中的数字按大小排序并遍历数组

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

四、接雨水

• 题目：
  

• 题解
  • 双指针：

class Solution {
public:
    int trap(vector<int>& height) {
        int left=0,right=height.size()-1;
        int max_left=0,max_right=0,res=0;
        while(left<right){
            if(height[left]<height[right]){
                height[left]>=max_left?max_left=height[left]:res+=max_left-height[left];
                left++;
            }else{
                height[right]>=max_right?max_right=height[right]:res+=max_right-height[right];
                right--;
            }
        }
        return res;
    }
};

• 暴力解决（超出时间限制）：

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        int ans=0;
        for(int i =1;i<n-1;i++){
            int max_left=0,max_right=0;
            for(int j=i;j>=0;j--)
                max_left=max(max_left,height[j]);
            for(int j=i;j<n;j++)
                max_right=max(max_right,height[j]);
            ans+=min(max_right,max_left)-height[i];
        }
        return ans;
     }
};

五、字符串相乘

• 题解：
  

• 题解：
  做乘法：

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1=="0"||num2=="0")    return "0";
        int m=num1.size(),n=num2.size();
        auto len=vector<int>(m+n);
        for(int i=m-1;i>=0;i--){
            int x=num1[i]-'0';
            for(int j=n-1;j>=0;j--){
                int y=num2[j]-'0';
                len[i+j+1]+=x*y;
            }
        }
        for(int i =len.size()-1;i>0;i--){
            len[i-1] += len[i]/10;
            len[i]=len[i]%10;
        }
        int index=len[0]==0?1:0;
        string str;
        while(index<len.size()){
            str.push_back(len[index]);
            index++;
            cout<<str<<endl;
        }
        for(auto&c:str){
            c+='0';
        }
        return str;
    }
};