dfs及常见搜索问题

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

题解思路：从 $a_1$ 开始按顺序决定每个数加或者不加，在全部n个数后判断它们的和是不是k即可。

状态数是 $2^{n+1}$ 所以复杂度是O( $2^n$ )

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