您的位置:首页 > 健康 > 养生 > 大学生毕业论文管理系统入口_怎么做网页?_企业网站优化关键词_网页制作软件推荐

大学生毕业论文管理系统入口_怎么做网页?_企业网站优化关键词_网页制作软件推荐

2024/12/23 14:56:54 来源:https://blog.csdn.net/2301_79706435/article/details/144279116  浏览:    关键词:大学生毕业论文管理系统入口_怎么做网页?_企业网站优化关键词_网页制作软件推荐
大学生毕业论文管理系统入口_怎么做网页?_企业网站优化关键词_网页制作软件推荐

目录

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];}};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com