C++第二阶段——数据结构和算法,之前学过一点点数据结构,当时是基于Python来学习的,现在基于C++查漏补缺,尤其是树的部分。这一部分计划一个月,主要利用代码随想录来学习,刷题使用力扣网站,不定时更新,欢迎关注!
文章目录
- 一、77. 组合
- 二、216. 组合总和 III
- 三、17. 电话号码的字母组合
- 四、39. 组合总和
- 五、40. 组合总和 II
一、77. 组合
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
vector<vector<int>> combine(int n, int k) {
insertVector(n,k,1);
return result;
}
void insertVector(int n,int k,int startIndex){
if(path.size()==k){
result.push_back(path);
return;
}
for(int i=startIndex;i<=n;i++){
path.push_back(i);
insertVector(n,k,i+1);
path.pop_back();
}
}
};
二、216. 组合总和 III
class Solution {
public:
int targetSum;
vector<int> path;
vector<vector<int>> result;
vector<vector<int>> combinationSum3(int k, int n) {
insertVector(k,n,1);
return result;
}
void insertVector(int k,int n,int startIndex){
if(path.size()==k){
if(targetSum==n){
result.push_back(path);
return;
}
}
for(int i=startIndex;i<=9;i++){
path.push_back(i);
targetSum+=i;
insertVector(k,n,i+1);
path.pop_back();
targetSum-=i;
}
}
};
三、17. 电话号码的字母组合
class Solution {
public:
vector<string> result;
string s="";
string stringV[10] = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
vector<string> letterCombinations(string digits) {
insertString(digits,0);
return result;
}
void insertString(string digits,int index){
if(index==digits.size()){
// 收获结果
if(s==""){
return;
}
result.push_back(s);
return ;
}
int digit = digits[index]-'0';
string nextS = stringV[digit];
// 遍历
for(int i=0;i<nextS.size();i++){
s+= nextS[i];
insertString(digits,index+1);
s.pop_back();
}
}
};
四、39. 组合总和
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
int Asum =0;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
insertV(candidates,target,0);
return result;
}
void insertV(vector<int> candidates,int target,int startIndex){
if(Asum==target){
// 收获结果
result.push_back(path);
return;
}
else if(Asum>target){
return;
}
for(int i=startIndex;i<candidates.size();i++){
path.push_back(candidates[i]);
Asum+=candidates[i];
insertV(candidates,target,i);
// 回溯
path.pop_back();
Asum-=candidates[i];
}
}
};
五、40. 组合总和 II
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
int Asum;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// 首先进行排序
sort(candidates.begin(),candidates.end());
vector<bool> used(candidates.size(),false); // 和candidates等长,并且全为0;
insertS(candidates,target,0,used);
return result;
}
void insertS(vector<int> candidates,int target,int startIndex,vector<bool> used){
if(Asum==target){
result.push_back(path);
return;
}
if(Asum>target){
return;
}
// 用一个used数组表示是否使用过
for(int i=startIndex;i<candidates.size();i++){
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
continue;
}
path.push_back(candidates[i]);
Asum+= candidates[i];
used[i] = true;
insertS(candidates,target,i+1,used);
used[i] =false;
path.pop_back();
Asum-= candidates[i];
}
}
};