搜索顺序

  |  

摘要: 搜索顺序

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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