算法搜索

搜索顺序：改变搜索树的形态使得尽早剪枝

字数统计: 913字   |   阅读时长: 4分
,

摘要: 搜索顺序

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

搜索问题中，搜索树的各个层次，各个分支之间的顺序是不定的。不同的搜索顺序会产生不同的搜索树形态。

改变搜索顺序使得尽早剪枝是搜索中的重要优化手段。例如在数独问题中，优先搜索能填的合法数字最少的位置就属于这种策略。

473. 火柴拼正方形

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

提示:

1
2
1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 1e8

示例 1:
输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:
输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

算法：搜索顺序

在 DFS 之前先排序 sort(nums.begin(), nums.end(), greater<int>()); 使得较长的火柴先搜索。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// DFS + 搜索顺序
class Solution {
public:
    bool makesquare(vector<int>& nums) {
        if(nums.empty()) return false;
        int sum = 0;
        int maxx = 0;
        for(int num: nums)
        {
            sum += num;
            maxx = max(maxx, num);
        }
        int c = sum / 4;
        if(c * 4 != sum) return false;
        if(maxx > c) return false;
        vector<int> lens(4, c); // 4条边的剩余长度
        sort(nums.begin(), nums.end(), greater<int>());
        return dfs(nums, lens, 0, (int)nums.size());
    }

private:
    bool dfs(const vector<int>& nums, vector<int>& lens, int pos, int n)
    {
        if(pos == n) return true;

        int cur = nums[pos];
        for(int i = 0; i < 4; ++i)
        {
            if(lens[i] >= cur)
            {
                lens[i] -= cur;
                if(dfs(nums, lens, pos + 1, n))
                    return true;
                lens[i] += cur;
            }
        }
        return false;
    }
};

698. 划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

提示：

1
2
3
1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
每个元素的频率在 [1,4] 范围内

示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

示例 2:
输入: nums = [1,2,3,4], k = 3
输出: false

算法：搜索顺序

  • 从大到小搜索
  • 可以对状态压缩后的整数做记忆化

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        int maxx = 0;
        for(int num: nums)
        {
            sum += num;
            maxx = max(maxx, num);
        }
        if(sum % k != 0) return false;
        int block = sum / k;
        if(maxx > block) return false;
        vector<bool> visited((int)nums.size(), false);
        sort(nums.begin(), nums.end(), greater<int>());
        return dfs(nums, visited, 0, block, k);
    }

private:
    bool dfs(const vector<int>& nums, vector<bool>& visited, int cur, int block, int k)
    {
        if(k == 0)
            return true;

        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            if(visited[i]) continue;
            int nxt = cur + nums[i];
            if(nxt > block)
                continue;
            visited[i] = true;
            if(nxt < block)
                if(dfs(nums, visited, nxt, block, k))
                    return true;
            if(nxt == block)
                if(dfs(nums, visited, 0, block, k - 1))
                    return true;
            visited[i] = false;
        }
        return false;
    }
};

1240. 铺瓷砖

最优性剪枝 + 搜索顺序，参考文章 【搜索难题】力扣1240-铺瓷砖。

Share