算法刷题计划(十七)组合总和、组合总和2、缺失的第一个正数、接雨水、字符串相乘
2021/11/13 17:10:14
本文主要是介绍算法刷题计划(十七)组合总和、组合总和2、缺失的第一个正数、接雨水、字符串相乘,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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; } };
这篇关于算法刷题计划(十七)组合总和、组合总和2、缺失的第一个正数、接雨水、字符串相乘的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?