Skip to content

搜索问题汇总.md

Latest commit

 

History

History
383 lines (340 loc) · 11.5 KB

搜索问题汇总.md

File metadata and controls

383 lines (340 loc) · 11.5 KB

搜索

使用递归回溯搜索，一般是深度优先，dfs搜索，具有如下模板：

void dfs(int k) {
    if (满足条件) {
        记录结果
        return ;
    }

    for(int i = 0; i < n; i++){
        //记录搜索结果
        dfs(k+1); //搜索下一层
        // 恢复现场
    }
}

搜索的题目通过画树来帮助思考。

LeetCode 39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复被选取。

对于一个target，如果选了当前数组中的数，那么对应下次搜索的target-candidates[i]。由于每个数可以选，也可以不选，那么有两个分支。

candidates = [2,3,6,7], target = 7

            target = 7，idx = 0
            /                 \
 target = 5，idx = 0   target = 7，idx = 1
      选2                      不选2
     /   \
target=3  target=5
idx = 0    idx=1
  选2       不选2

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tmp;

    void dfs(vector<int> &candidates, int target, int idx) {
        if (idx == candidates.size()) {
            return ;
        }

        if (target == 0) {
            // target 为 0 代表终止条件
            ans.push_back(tmp);
            return ;
        }

        // 有两种选择，选当前的数，或者不选，idx++
        dfs(candidates, target, idx+1);
        // 这里有个剪枝操作，如果target 比当前这个数还小，那么没必要进行搜索下去了
        if (target >= candidates[idx]) {
            tmp.push_back(candidates[idx]);
            dfs(candidates, target - candidates[idx], idx);
            tmp.pop_back();
            // 恢复现场
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);
        return ans;
    }
};

LeetCode 39. 组合总和 II

给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。

这道题按照上面的思路去做，会有重复的问题。两种思路，一种是排序好之后，每次选定一个，然后for循环找下一个，如果下一个位置和当前位置相同，那么需要排除掉。

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ans;
    void dfs(vector<int> &candidates, int target, int idx) {
        if (target == 0) {
            ans.push_back(tmp);
            return;
        }  
        for(int i = idx; i < candidates.size(); i++){
            if (i > idx && candidates[i] == candidates[i-1]) continue;
            if (target >= candidates[i]) {
                tmp.push_back(candidates[i]);
                dfs(candidates, target - candidates[i], i+1);
                tmp.pop_back();
            } else {
                break;
            }

        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0);
        return ans;
    }   
    // 这个做法可以排除掉重复的结果，是因为在进到下一层循环前，判断下一个的值是否和前一个一样，如果一样那么跳过
};

另一种做法，每个只能用一次，实际上和上面那道题一样，多了一个次数限制，如果存在多个这个值，那么就代表着这个值可以被用这么多次，这样能和上面的方法统一起来。

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ans;
    vector<pair<int,int>> freq;
    void dfs2(vector<int> &candidates, int target, int idx) {
        if (target == 0) {
            ans.push_back(tmp);
            return ;
        }
        if (idx == freq.size() || target < freq[idx].first) {
            return ;
        }

        dfs2(candidates, target, idx+1);
        int most = min(target/freq[idx].first, freq[idx].second);
        for(int i = 1; i <= most; i++){
            tmp.push_back(freq[idx].first);
            dfs2(candidates, target-i * freq[idx].first, idx+1);
            // i * freq[idx].first
        }
        for(int i = 1; i<=most; i++) {
            tmp.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for(int num : candidates) {
            if (freq.empty() || num != freq.back().first ) {
                freq.emplace_back(num, 1);
            } else {
                freq.back().second++;
            }
        }
        dfs2(candidates, target, 0);
        return ans;
    }   
};

LeetCode 46. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

每个位置可以选择用或者不用，用一个used的bool数组来表示。注意每次使用了之后恢复现场即可。

另一种方法是可以不使用used数组，使用交换的思想，一个排列是当前所有位置和其他位置交换得到。

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ans;
    vector<bool> used;
    void dfs(vector<int> &nums, int idx) {
        if (idx == nums.size()) {
            ans.push_back(tmp);
            return ;
        }
        for(int i = 0; i < nums.size(); i++){
            if (!used[i]){
                used[i] = true;
                tmp.push_back(nums[i]);
                dfs(nums,idx+1);
                tmp.pop_back();
                used[i] = false;
            }
        }
    }
    void dfs2(vector<int> &nums, int idx) {
        if (idx == nums.size()) {
            ans.push_back(nums);
            return ;
        }
        for(int i = idx; i < nums.size(); i++){
            swap(nums[idx], nums[i]);
            dfs2(nums, idx + 1);
            swap(nums[idx], nums[i]);
        }

    }
    vector<vector<int>> permute(vector<int>& nums) {
        used.resize(nums.size());
        dfs(nums, 0);
        dfs2(nums, 0);
        return ans;
    }
};

LeetCode 47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

还是两种思路，一种是用一个集合，记录下当前层，哪个已经被用过了，比如idx为2时，这时可能用相同的值，如果已经在set里面了，那么说明重复了，可以跳过。坏处是每一层递归都要维护一个set。

另一种思路是先将数组按顺序排好，重复的选择发生在当这一层的选择和之前的选择相同，且之前没有被选过，因为我们是按顺序选的，按顺序恢复，这说明上一层已经递归完了，这相同说明已经存在重复，直接略过即可。

class Solution {
public:
    vector<vector<int>> ans; 
    vector<int> path;
    vector<bool> used;
    int n;
    void dfs(int u, vector<int> & nums){
        if (u == n) {
            ans.push_back(path);
            return ;
        }
        set<int> isRepeated;
        for(int i = 0; i < n; i++) {
            if (isRepeated.count(nums[i]) != 0) {
                continue;
            }
            if (!used[i]) {
                path[u] = nums[i];
                used[i] = true;
                isRepeated.insert(nums[i]);
                dfs(u+1, nums);
                used[i] = false;
            }
        }
    }

    void dfs2(vector<int> &nums, int idx) {
        if (idx == nums.size()) {
            ans.push_back(path);
            return ;
        }
        for(int i = 0; i < nums.size(); i++){
            if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) ) continue;
            //要么这个用过了
            //如果这个没用过，且这个和前面那个相等，且前面那个没用过，这说明这递归到之前重复的状态了
            //这种方式要求数组是按序的
            path[idx] = nums[i];
            used[i] = true;
            dfs2(nums, idx+1);
            used[i] = false;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        n = nums.size();
        path.resize(n);
        used.resize(n);
        // dfs(0, nums);
        dfs2(nums, 0);
        return ans;
    }
};

LeetCode 78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

每次迭代就把当前的数组保存到结果中，本质上也是一个树，选中这个位置，递归到下一层选择中。

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ans;
    void dfs(vector<int> &nums, int idx) {
        ans.push_back(tmp);
        for(int i = idx; i < nums.size(); i++){
            tmp.push_back(nums[i]);
            dfs(nums, i+1);
            tmp.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};

LeetCode 90. 子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

比上道题多了重复的条件，和之前一样要么在同一层里用set去重，要么用一个used数组，思路和之前的题目相同。

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ans;
    vector<bool> used;
    void dfs(vector<int> &nums, int idx) {
        ans.push_back(tmp);
        set<int> used; 
        for(int i = idx; i < nums.size(); i++) {
            if (used.count(nums[i]) > 0) continue;
            tmp.push_back(nums[i]);
            used.insert(nums[i]);
            dfs(nums, i+1);
            tmp.pop_back();
        }
    }
    void dfs2(vector<int> &nums, int idx) {
        ans.push_back(tmp);
        for(int i = idx; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            tmp.push_back(nums[i]);
            used[i] = true;
            dfs2(nums, i+1);
            tmp.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        used.resize(nums.size());
        sort(nums.begin(), nums.end());
        dfs2(nums, 0);
        return ans;
    }   
};

LeetCode 51. N 皇后

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> board;
    const static int N = 100;
    bool col[N]; //列
    bool ug[N];    // 对角线
    bool dug[N];   // 反对角线
    // 对角线反对线表示
    // y = x + b 或 y = -x + b， 这里用截距b代表这一条线
    // 因此 b = y - x (因为可能为负，给他加上一个row) b = y + x
    int row;
    void dfs(int r) {   // r 代表行
        if (r == row) {
            ans.push_back(board);
            return ;
        }
        for(int i = 0; i < row; i++){   //这个i代表列
            if (!col[i] && !ug[i-r+row] && !dug[i+r]) {
                col[i] = ug[i-r+row] = dug[i+r] = true;
                board[r][i] = 'Q';
                dfs(r+1);
                board[r][i] = '.';
                col[i] = ug[i-r+row] = dug[i+r] = false;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        memset(col, false, sizeof col);
        memset(ug, false, sizeof ug);
        memset(dug, false, sizeof dug);
        row = n;
        string line;
        for(int i = 0; i < n; i++) {
            line.push_back('.');
        }
        for(int i = 0; i < n; i++) {
            board.push_back(line);
        }
        dfs(0);
        return ans;
    }
};