回溯法

本文学习自labuladong的算法小抄

回溯问题,实际上就是一个决策树的遍历过程。需要思考 3 个问题:

  1. 路径:也就是已经做出的选择。

  2. 选择列表:也就是你当前可以做的选择。

  3. 结束条件:也就是到达决策树底层,无法再做选择的条件。

代码方面,回溯算法的框架:

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return

for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

其核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」,特别简单。

什么叫做选择和撤销选择呢,这个框架的底层原理是什么呢?下面我们就通过「全排列」这个问题来解开之前的疑惑,详细探究一下其中的奥妙!

24点游戏

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *,/,+,-,(,) 的运算得到 24。

示例 1:

输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24
示例 2:

输入: [1, 2, 1, 2]
输出: False
注意:

除法运算符 / 表示实数除法,而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如,[1, 1, 1, 1] 作为输入时,表达式 -1 - 1 - 1 - 1 是不允许的。
你不能将数字连接在一起。例如,输入为 [1, 2, 1, 2] 时,不能写成 12 + 12 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/24-game
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法

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
44
45
46
47
48
49
50
51
52
class Solution {
public:
static constexpr int TARGET=24;
static constexpr double EPISILON = 1e-6;
static constexpr int ADD = 0,MULTIPLY = 1,SUBTRACT = 2,DIVIDE = 3; //四则运算
bool judgePoint24(vector<int>& nums) {
vector<double> l;
for(int num:nums)
l.emplace_back(static_cast<double>(num));
return solve(l);
}
bool solve(vector<double> &l){
if(l.size()==0)
return false;
if(l.size()==1)
return abs(l[0]-TARGET)<EPISILON;
int size = l.size();
for(int i = 0;i<size;i++){
for(int j = 0;j<size;j++){
if(i==j)
continue;
vector<double> list2;
//先把剩下的数字添加到队列中
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2.emplace_back(l[k]);
}
}
//添加新增的运算结果
for(int k = 0;k<4;k++){
if(k<2&&i>j)
continue;
switch(k){
case ADD: list2.emplace_back(l[i]+l[j]);break;
case MULTIPLY: list2.emplace_back(l[i]*l[j]);break;
case SUBTRACT: list2.emplace_back(l[i]-l[j]);break;
case DIVIDE: {
if(abs(l[j])<EPISILON)
continue;
list2.emplace_back(l[i]/l[j]);
}
default: break;
}
if(solve(list2))
return true;
list2.pop_back();
}
}
}
return false;
}
};
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2019-2022 guoben
  • PV: UV:

微信