刷题日志【1】

目录

1.全排列【力扣】

代码1：

代码2：

2、子集【力扣】

3、全排列Ⅱ【力扣】

4、组合【力扣】 

---

1.全排列【力扣】

代码1：

class Solution {bool check[7];vector <int> path;vector<vector<int>> ret;public:vector<vector<int>> permute(vector<int>& nums) {for(int i=0;i<7;i++)
{check[i]=true;
}dfs(nums);
return ret;}void dfs(vector <int>& nums)
{if(path.size()==nums.size())
{ret.push_back(path);//回去再处理check和path;
return ;}int size=nums.size();for(int i=0;i<size;i++)
{
if(check[i]==true)
{path.push_back(nums[i]);check[i]=false;
dfs(nums);
path.pop_back();
check[i]=true;}}}};

这里使用全局变量去记录，不足在于要手动处理入口和出口的状态修改逻辑（这里可以对比着看下面的第二种，第二种只是用了ret这个全局口袋去接收）

这种写法的dfs只用传递一个固定不变的参数，只有全局变量在处理变化（如哪些数字已使用，记录完整的一组数据的收纳）

递归出口是path的size和nums的size相同，即path是完整的一种排列，此时入库（收入ret中）
此时，return 将会返回上级函数，此时path应该失去最后一个数，check对映的这个数应该改为true(true代表没被使用过，false代表使用过)

很明显，在出口处我们没有处理check和path，所以要在出来函数的另一端（即入口后）去写对check和path的逻辑

代码2：

class Solution {vector<vector<int>> ret;public:vector<vector<int>> permute(vector<int>& nums) {vector<int> path;
int total_size=nums.size();dfs(nums,path,total_size);return ret;}void dfs(vector<int> nums,vector<int> path,int total_size)
{
if(path.size()==total_size)
{
ret.push_back(path);
return;}int size=nums.size();for(int i=0;i<size;i++)
{//制造新的nums和path
vector<int> tmp=nums;
vector<int>ppath=path;
ppath.push_back(tmp[i]);
swap(tmp[size-1],tmp[i]);
tmp.pop_back();
dfs(tmp,ppath,total_size);}}};

代码2的效果是很差的，dfs的for里面制造新的nums和path，基本就是手动画树状图，把可选的nums和对应此时的path的情况都列出来，供代码运行，这么大的工作量之后的效果，就是形成在出入口像二叉树一样自然自动的感觉，其实就是单一改为多方向，二叉树实现传入参数可退回（即path在return会自动减去当前加上的），因为二叉树的传入参数变换是单一的，而全排列的传入参数会有多个方向所以就创建了ppath这个中转接口，以实现可逆效果

2、子集【力扣】

这个题目有两种思路：一是以是否选择i数据的决策树，这个决策树在叶子节点会得到我们需要的答案，二是以i个数据为划分（如对{1，2，3}来说数据量为1的答案有{1}，{2}，{3}这三个）

dfs传入参数k是为了统计是否到达叶子节点

class Solution {vector<vector<int>> ret;vector<int> path;
public:void dfs(vector<int> &nums,int k)
{
ret.push_back(path);
int size=nums.size();for(int i=k;i<size;i++)
{
path.push_back(nums[i]);
dfs(nums,i+1);
path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}
};

3、全排列Ⅱ【力扣】

class Solution {bool check[8];
vector<vector<int>> ret;
vector<int> path;public:vector<vector<int>> permuteUnique(vector<int>& nums) {for(int i=0;i<8;i++){
check[i]=true;}
sort(nums.begin(),nums.end());dfs(nums);return ret;}void dfs(vector<int>& nums)
{
if(path.size()==nums.size())
{
ret.push_back(path);
return;
}for(int i=0;i<nums.size();i++)
{if(check[i]==true&&(i==0||nums[i]!=nums[i-1]||check[i-1]==false))
{check[i]=false;
path.push_back(nums[i]);dfs(nums);
path.pop_back();
check[i]=true;}
}
}
};

上面逻辑最关键的是for里面的if判断，什么时候可以进入dfs，决策树的一支路如下：

4、组合【力扣】 

 

设置全局变量：_n ; _k ; path ; ret

决策树：

函数出口：当path的size==_k时，入ret

dfs(int x)-->x是为了实现下一层从当前的下一个数字开始（即现在是1，下一层dfs从2开始）

class Solution {vector<int> path;
vector<vector<int>> ret;int _n;
int _k;public:vector<vector<int>> combine(int n, int k) {_n=n;_k=k;dfs(1);return ret;}void dfs(int x)
{
if(_k==path.size())
{ret.push_back(path);return;}
for(int i=x;i<=_n;i++)
{path.push_back(i);
dfs(i+1);
path.pop_back();}}};

5、目标和

这个题目可以使用暴力搜索或是动态规划实现

下面使用的是暴力搜索 

 

class Solution {
int num=0;
int target;
int path=0;public:int findTargetSumWays(vector<int>& nums, int _target) {target=_target;dfs(nums,0);return num;}
void dfs(vector<int>&nums,int k)
{
if(path==target&&k==nums.size())
{
num++;
return ;
}
if(k>=nums.size())
{return;
}
path+=nums[k];
dfs(nums,k+1);
path-=nums[k];path-=nums[k];
dfs(nums,k+1);
path+=nums[k];}};