dfs及常見搜索問題

dfs以及搜索問題

DFS是搜索的手段之一忆某。它從某個狀態(tài)開始鹃唯，不斷地轉(zhuǎn)移狀態(tài)直到無法轉(zhuǎn)移，然后回退到前一步的狀態(tài)阵幸，繼續(xù)轉(zhuǎn)移到其他狀態(tài)花履。直到找到最終的解。

全排列

給定一個沒有重復(fù)數(shù)字的序列侨嘀，返回其所有可能的全排列臭挽。

示例:

輸入: [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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)咬腕，非商業(yè)轉(zhuǎn)載請注明出處欢峰。

題解：

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;

        
    }
};

另一種全排列的方法，回溯的思想

思路來源于網(wǎng)友們涨共。
但是后來發(fā)現(xiàn)這樣好像順序不是那種遞增的順序
所以如果希望順序輸出纽帖，可以把string放到vector里vector<string>，在最后加一個sort举反，后排序方式懊直？？
但是我在呕鸨牵客網(wǎng)這樣做意外出錯室囊，不曉得怎么回事雕崩。但是我看別人有這么做
思路，遞歸方法backsee(數(shù)組融撞，index坐標(biāo)）
第一個位置 for循環(huán)盼铁，每個數(shù)字循環(huán)一次（這里保證每個數(shù)字坐一次用的是swap方法），第一個數(shù)字確定后尝偎，考慮index+1~n之后的數(shù)字

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++){//可以想象第一個數(shù)有n種選擇饶火，第二個數(shù)位置就是n-1種了
            swap(nums[i],nums[index]);
            backsee(n,res,nums,index+1);//問題縮小到第二個數(shù)
            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思想是怎么回事了肤寝。
需要兩個數(shù)組（或者類似）
一個表示這個位置是否讀過
一個表示組成的新的排列
//在dfs時，有for循環(huán)抖僵，相當(dāng)于對每個起始點遍歷
在爬鹂矗客網(wǎng)調(diào)程序好煩 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;
}

帶剪枝的全排列

給定一個可包含重復(fù)數(shù)字的序列世吨，返回所有不重復(fù)的全排列。

示例:

輸入: [1,1,2]
輸出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutations-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有寝殴。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)局齿，非商業(yè)轉(zhuǎn)載請注明出處扯罐。

題解：

1、使用了STL 的count函數(shù)來剪枝沐祷，然后時間復(fù)雜度驚人。

執(zhí)行用時 :2280 ms, 在所有 C++ 提交中擊敗了5.03%的用戶

內(nèi)存消耗 :10 MB, 在所有 C++ 提交中擊敗了65.48%的用戶

class Solution {
public:
   void backsee(int n,vector<vector<int>>& res,vector<int>& nums,int index){
       //參數(shù)：總長度n,結(jié)果res,中間結(jié)果nums,index
        if(index==n&&count(res.begin(),res.end(),nums)==0)
            res.push_back(nums);
        for(int i=index;i<n;i++){//可以想象第一個數(shù)有n種選擇攒岛，第二個數(shù)位置就是n-1種了
            swap(nums[i],nums[index]);
            backsee(n,res,nums,index+1);//問題縮小到第二個數(shù)
            swap(nums[i],nums[index]);
        }
        
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        //題目思路赖临，看題解，可用set<vector>剔除重復(fù)的
        
        vector<vector<int>> res;
        backsee(nums.size(),res,nums,0);
        return res;
        
    }
};

2灾锯、使用C++自帶全排列

可以使用next_permutation兢榨，前提是先從小到大排序，該函數(shù)輸出的就是無重復(fù)的全排列顺饮，運行時間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;
}
去重兼雄，考慮重復(fù)的定義吟逝，其實就是同一位選進去了多個相同的數(shù)，換句話說就是若要不重復(fù)赦肋，同一位對同樣的數(shù)只能使用一個块攒，因此我們可以在每次DFS之前励稳，也就是為本位置選數(shù)之前，判斷是否已經(jīng)使用過相同的數(shù)了囱井，若沒有則正常DFS驹尼，若有則跳過本次循環(huán)，這樣不僅去掉了重復(fù)琅绅，而且減少了遞歸次數(shù)扶欣。
作者：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）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)千扶，非商業(yè)轉(zhuǎn)載請注明出處料祠。

3、參考了評論區(qū)大佬

用map進行改進

執(zhí)行用時 :8 ms, 在所有 C++ 提交中擊敗了95.62%的用戶

內(nèi)存消耗 :11.1 MB, 在所有 C++ 提交中擊敗了25.72%的用戶

class Solution {
public:
   void backsee(int n,vector<vector<int>>& res,vector<int>& nums,int index,int used[]){
       //參數(shù)：總長度n,結(jié)果res,中間結(jié)果nums,index
        map<int,int> ex;
        if(index==n)
            res.push_back(nums);
        for(int i=index;i<n;i++){//可以想象第一個數(shù)有n種選擇澎羞，第二個數(shù)位置就是n-1種了
            // cout<<i<<endl;
            if(ex.count(nums[i])==1){//這個位置某數(shù)已經(jīng)待過了,所以不考慮了
                continue;
            }
            
                
            swap(nums[i],nums[index]);
            backsee(n,res,nums,index+1,used);//問題縮小到第二個數(shù)
            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;
        
    }
};

子集

題目

給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums髓绽，返回該數(shù)組所有可能的子集（冪集）。

說明：解集不能包含重復(fù)的子集妆绞。

示例:

輸入: nums = [1,2,3]
輸出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/subsets
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有顺呕。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處括饶。

題解

這個問題類似于下面的目標(biāo)和株茶、部分和問題。

執(zhí)行用時 :0 ms, 在所有 C++ 提交中擊敗了100.00%的用戶

內(nèi)存消耗 :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  動態(tài)規(guī)劃
        vector<vector<int>> res;
        // res.push_back(nums);
        sousuo(res,nums,0);
        return res;
        
    }
};

部分和&&目標(biāo)和問題

部分和問題

這一段來自《挑戰(zhàn)程序設(shè)計語言（第二版）》

給定整數(shù)a1图焰、a2启盛、.......an，判斷是否可以從中選出若干數(shù)技羔，使它們的和恰好為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$ 開始按順序決定每個數(shù)加或者不加，在全部n個數(shù)后判斷它們的和是不是k即可藤滥。

狀態(tài)數(shù)是 $2^{n+1}$ 所以復(fù)雜度是O( $2^n$ )

int a[MAX_N];
int n,k;

//已經(jīng)從前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");
}

目標(biāo)和問題[動態(tài)規(guī)劃等解法待補充]

類似問題

給定一個非負整數(shù)數(shù)組向图，a1, a2, ..., an, 和一個目標(biāo)數(shù)，S∈毖剑現(xiàn)在你有兩個符號 + 和 -张漂。對于數(shù)組中的任意一個整數(shù)，你都可以從 + 或 -中選擇一個符號添加在前面谨娜。

返回可以使最終數(shù)組和為目標(biāo)數(shù) S 的所有添加符號的方法數(shù)航攒。

示例 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種方法讓最終目標(biāo)和為3。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/target-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有趴梢。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)漠畜，非商業(yè)轉(zhuǎn)載請注明出處币他。

這是一種類似暴力的解法

執(zhí)行用時 :1776 ms, 在所有 C++ 提交中擊敗了8.70%的用戶

內(nèi)存消耗 :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;
    }
};