大厂面试算法（二）搜索算法

Bertha 。 2023-01-20 11:49 19阅读 0赞

# 搜索算法 #

搜索算法的分类：

1.  枚举法（暴力搜索）
2.  深度优先搜索
3.  广度优先搜索
4.  回溯

深度优先搜索（DFS）

问题：

假如有编号1-3的3张扑克牌和编号为1-3的3个盒子，现在需要将3张牌分别放到3个盒子中去，且每个盒子只能放一张牌，一共有多少种不同方法？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

#include<iostream>
    #include<vector>
    using namespace std;
    
    void dfs(vector<int>& box, vector<int>& used, int idx)
    {
    	//边界
    	if (idx == box.size())
    	{
    		//说明最后一个盒子也完成扑克牌放置
    		for (int i = 1; i < box.size(); i++)
    		{
    			cout << box[i] << " ";
    		}
    		cout << endl;
    		return;
    	}
    	//处理当前这个盒子，当前这个盒子该如何放置
    	//扑克牌数量与盒子数相同
    	for (int i = 1; i < box.size(); i++)
    	{
    		//遍历所有牌  判断当前的牌i是否用过
    		if (used[i] == 0)
    		{
    			//把没有用过的牌放入到当前盒子中
    			box[idx] = i;
    			used[i] = 1;
    
    			//处理下一个盒子
    			//此处即为深度优先搜索的思想体现，处理完当前的一种可能后，处理下一个盒子，并非找出当前所有可能情况
    			dfs(box, used, idx + 1);
    			//回收当前使用的牌，所有盒子都放置一张牌后，进行回收，重新放置
    			used[i] = 0;
    		}
    	}
    }
    
    int main()
    {
    	int n;
    	cin >> n;
    	vector<int>box(n + 1, 0);
    	vector<int>used(n+1,0);
    	dfs(box, used, 1);
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5][]

**例：来源leetcode**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6][]

class Solution {
    public:
        vector<vector<int>> res;
        vector<int> path;
        void dfs( vector<int>& nums, vector<int>& used, int depth)
        {
            //边界
            if( depth == nums.size() ){ 
                res.push_back(path);
                return;
            }
            for(int i = 0 ; i < nums.size();++i )
            {   
                if(used[i]==1) continue;//如果使用过 直接跳过，找下一个可使用元素进行放置    
                
                path.push_back(nums[i]);
                used[i]=1;
                dfs(nums, used, depth+1);
                used[i]=0;//回收
                path.pop_back();
            }
        }
        vector<vector<int>> permute(vector<int>& nums) {
            int n=nums.size();
            vector<int> used(n,0);
            dfs( nums, used, 0 );
            return res;
        }
    };

### 未完待续。。。 ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221021/f1f7c43d440c44a4a28704351f05d237.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221021/553a3ae5bf9d49f5af796e4bbfeda44e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221021/4b8660403fc346b19a0932f6e0688619.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: /images/20221021/b864f56fec554003ba6d2619437a7cec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4]: /images/20221021/3bdb61aac2dc426cb21b2e9253315969.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5]: /images/20221021/e0034f1a1d5546a0a7efedf2dd6b8a1c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6]: /images/20221021/5e5f59a319a2417095c7c014bca53d66.png