dfs以及搜索问题
DFS是搜索的手段之一。它从某个状态开始,不断地转移状态直到无法转移,然后回退到前一步的状态,继续转移到其他状态。直到找到最终的解。
全排列
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解:
C++可以用库
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());//先排序
do
{
res.push_back(nums);
}while(next_permutation(nums.begin(),nums.end()));
return res;
}
};
另一种全排列的方法,回溯的思想
思路来源于网友们。
但是后来发现这样好像顺序不是那种递增的顺序
所以如果希望顺序输出,可以把string放到vector里vector<string>,在最后加一个sort,后排序方式??
但是我在牛客网这样做意外出错,不晓得怎么回事。但是我看别人有这么做
思路, 递归方法backsee(数组,index坐标)
第一个位置 for循环,每个数字循环一次(这里保证每个数字坐一次用的是swap方法),第一个数字确定后,考虑index+1~n之后的数字
class Solution {
public:
void backsee(int n,vector<vector<int>>& res,vector<int>& nums,int index){
if(index==n)
res.push_back(nums);
for(int i=index;i<n;i++){//可以想象第一个数有n种选择,第二个数位置就是n-1种了
swap(nums[i],nums[index]);
backsee(n,res,nums,index+1);//问题缩小到第二个数
swap(nums[i],nums[index]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
//类似搜索树
vector<vector<int>> res;
backsee(nums.size(),res,nums,0);
return res;
}
};
第三种方式,dfs思想,我终于知道dfs思想是怎么回事了。
需要两个数组(或者类似)
一个表示这个位置是否读过
一个表示组成的新的排列
//在dfs时,有for循环,相当于对每个起始点遍历
在牛客网调程序好烦 LeetCode真美好
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;
void dfs(int n,string s,int res[],string tmp){
if(n==s.length()){
cout<<tmp<<endl;
}
for(int i=0;i<s.length();i++){
if(res[i]==0){
res[i]=1;
tmp[n]=s[i];
dfs(n+1,s,res,tmp);
res[i]=0;
}
}
}
int main(){
string s;
cin>>s;
string tmp;
int x=s.length();
sort(s.begin(),s.end());
tmp=s.substr(0,s.length());//string赋初值??不能用fill??
int res[s.length()];
fill(res,res+x,0);
dfs(0,s,res,tmp);
// }
//sort(s.begin(),s.end());
//vector<vector<string>> tmp,
cout<<endl;
return 0;
}
带剪枝的全排列
给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解:
1、使用了STL 的count函数来剪枝,然后时间复杂度惊人。
执行用时 :2280 ms, 在所有 C++ 提交中击败了5.03%的用户
内存消耗 :10 MB, 在所有 C++ 提交中击败了65.48%的用户
class Solution {
public:
void backsee(int n,vector<vector<int>>& res,vector<int>& nums,int index){
//参数:总长度n,结果res,中间结果nums,index
if(index==n&&count(res.begin(),res.end(),nums)==0)
res.push_back(nums);
for(int i=index;i<n;i++){//可以想象第一个数有n种选择,第二个数位置就是n-1种了
swap(nums[i],nums[index]);
backsee(n,res,nums,index+1);//问题缩小到第二个数
swap(nums[i],nums[index]);
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
//题目思路,看题解,可用set<vector>剔除重复的
vector<vector<int>> res;
backsee(nums.size(),res,nums,0);
return res;
}
};
2、使用C++自带全排列
可以使用next_permutation,前提是先从小到大排序,该函数输出的就是无重复的全排列,运行时间24ms,击败98.87%。
vector<vector<int>> permuteUnique(vector<int>& nums)
{
sort(nums.begin(), nums.end());
vector<vector<int>>result;
result.push_back(nums);
while (next_permutation(nums.begin(), nums.end()))
{
result.push_back(nums);
}
return result;
}
去重,考虑重复的定义,其实就是同一位选进去了多个相同的数,换句话说就是若要不重复,同一位对同样的数只能使用一个,因此我们可以在每次DFS之前,也就是为本位置选数之前,判断是否已经使用过相同的数了,若没有则正常DFS,若有则跳过本次循环,这样不仅去掉了重复,而且减少了递归次数。
作者:luo-ben-zhu-xiao-man-tou
链接:https://leetcode-cn.com/problems/permutations-ii/solution/dfsqu-zhong-huo-zhe-shi-yong-czi-dai-quan-pai-lie-/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
3、参考了评论区大佬
用map进行改进
执行用时 :8 ms, 在所有 C++ 提交中击败了95.62%的用户
内存消耗 :11.1 MB, 在所有 C++ 提交中击败了25.72%的用户
class Solution {
public:
void backsee(int n,vector<vector<int>>& res,vector<int>& nums,int index,int used[]){
//参数:总长度n,结果res,中间结果nums,index
map<int,int> ex;
if(index==n)
res.push_back(nums);
for(int i=index;i<n;i++){//可以想象第一个数有n种选择,第二个数位置就是n-1种了
// cout<<i<<endl;
if(ex.count(nums[i])==1){//这个位置某数已经待过了,所以不考虑了
continue;
}
swap(nums[i],nums[index]);
backsee(n,res,nums,index+1,used);//问题缩小到第二个数
swap(nums[i],nums[index]);
ex[nums[i]]=1;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
int used[nums.size()];
memset(used,0,sizeof(used));
sort(nums.begin(),nums.end());
backsee(nums.size(),res,nums,0,used);
return res;
}
};
子集
题目
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
这个问题类似于下面的目标和、部分和问题。
执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :13.1 MB, 在所有 C++ 提交中击败了7.49%的用户
class Solution {
public:
void sousuo(vector<vector<int>>& res,vector<int>& nums,int index){
if(index==nums.size()){
res.push_back(nums);
return;
}
int tmp=nums[index];
//该元素不在
nums.erase(nums.begin()+index);
sousuo(res,nums,index);
//该元素在
nums.insert(nums.begin()+index,tmp);
sousuo(res,nums,index+1);
}
vector<vector<int>> subsets(vector<int>& nums) {
//想了一下方法 dfs 动态规划
vector<vector<int>> res;
// res.push_back(nums);
sousuo(res,nums,0);
return res;
}
};
部分和&&目标和问题
部分和问题
这一段来自《挑战程序设计语言(第二版)》
给定整数a1、a2、.......an,判断是否可以从中选出若干数,使它们的和恰好为K。
1580957138(1).png
样例输入:
n=4
a={1,2,4,7}
k=13
样例输出
Yes {13=2+4+7}
样例输入:
n=4
a={1,2,4,7}
k=15
样例输出
No
题解思路:从开始按顺序决定每个数加或者不加,在全部n个数后判断它们的和是不是k即可。
状态数是所以复杂度是O()
int a[MAX_N];
int n,k;
//已经从前i项得到了和sum,然后对于i项之后进行分支。
bool dfs(int i,int sum){
//如果前n项都计算过了,则返回sum是否与k相等
if(i==n) return sum==k;
//不加上a[i]的情况
if(dfs(i+1,sum)) return ture;
//加上a[i]的情况
if(dfs(i+1,sum+a[i])) return true;
return false;
}
void solve(){
if (dfs(0,0)) printf("Yes\n");
else printf("No\n");
}
目标和问题[动态规划等解法待补充]
类似问题
给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这是一种类似暴力的解法
执行用时 :1776 ms, 在所有 C++ 提交中击败了8.70%的用户
内存消耗 :8.8 MB, 在所有 C++ 提交中击败了29.83%的用户
class Solution {
public:
int jieguo(vector<int>& nums, int S,int now,int index,int count){
if(index==nums.size()){
if(now==S)
return count+=1;
else
return count;
}
int res=0;
res=jieguo(nums,S,now+nums[index],index+1,count);
res=jieguo(nums,S,now-nums[index],index+1,res);
return res;
}
int findTargetSumWays(vector<int>& nums, int S) {
//用dfs方法
int res=jieguo(nums,S,0,0,0);
return res;
}
};
网友评论