本文涉及知识点
回溯 代数系统
LeetCode679. 24 点游戏
给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 [‘+’, ‘-’, ‘*’, ‘/’] 和括号 ‘(’ 和 ‘)’ 将这些卡片上的数字排列成数学表达式，以获得值24。
你须遵守以下规则:
除法运算符 ‘/’ 表示实数除法，而不是整数除法。
例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起
例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。
如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。
示例 1:
输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24
示例 2:
输入: cards = [1, 2, 1, 2]
输出: false
提示:
cards.length == 4
1 <= cards[i] <= 9
回溯、代数系统：错误
枚举cards的所有排列。每种排列的两张卡牌直接枚举加减乘除。从左向右向右运行，可以理解为加了括号。
比如：c1,c2,c3,c4 ，((c1?c2)?c3)?c4 ?表示运算符。
可以用分数（pair) 组成代数系统，任何结果都可以用a+b*c表示。
初始：{0,1,c1}
加法： {a+b
×
\times
×c,1,x}
减法：{a+b
×
\times
×c,-1,x}
乘法：{a,b
×
\times
×c,x}
除法：{a,b
×
\times
×c,
1
x
\frac {1} {x }
x1}
错误原因
6/(1 - 3/4) 无法用代数系统表示
核心代码
class Solution {
public:
bool judgePoint24(vector<int>& cards) {
sort(cards.begin(), cards.end());
do {
int hasDo = 0;
std::function<void(pair<int, int>, pair<int, int>, pair<int, int>)> BackTrack = [&](pair<int, int> a, pair<int, int> b, pair<int, int>c )
{
if (3 == hasDo) {
auto res = Cal(a, b, c);
m_bRes |= Is(res);
return ;
}
auto x = cards[hasDo + 1];
hasDo++;
BackTrack(Cal(a, b, c), { 1,1 }, { x,1 });
BackTrack(Cal(a, b, c), { -1,1 }, { x,1 });
BackTrack(a, Mul(b,c), { x,1 });
BackTrack(a, Mul(b, c), { 1,x });
hasDo--;
};
BackTrack({ 0,1 }, { 1,1 }, { cards[0],1 });
} while (next_permutation(cards.begin(), cards.end()));
return m_bRes;
}
pair<int, int> Mul(const pair<int, int>& a, const pair<int, int>& b) {
return { a.first * b.first,a.second * b.second };
}
pair<int, int> Cal(const pair<int, int>& a, const pair<int, int>& b, const pair<int, int>& c) {
auto d = Mul(b,c);
if ((0 == d.second) || (0 == a.second)) { return { 1,0 }; }
return {a.first*d.second +d.first*a.second,d.second *a.second};
}
bool Is(const pair<int, int>& a) {
if (0 == a.second) { return false; }
return a.second * 24 == a.first;
}
bool m_bRes = false;
};
- 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
回溯
4个任意选两个数，考虑顺序。也就是P
4
2
_4^2
42。枚举4个运算符。4个数变成48种3个数。
从任意三个数中选择2个，由于考虑顺序，有6种可能。枚举4种运算符，也就是24种。
对于任意两个数，考虑顺序，有2个选择可能。枚举4种运算符，也就是8种可能。
总时间复杂度：O(48248) < O(105)
代码
class Solution {
public:
bool judgePoint24(vector<int>& cards) {
std::function<void(vector<pair<int, int>>&)> BackTrack = [&](vector<pair<int, int>>& card)
{
if (1 == card.size()) {
m_bRes |= Is(card[0]);
return;
}
for (int i = 0; i < card.size(); i++) {
for (int j = 0; j < card.size(); j++) {
if (i == j) { continue; }
vector<pair<int, int>> tmp;
for (int k = 0; k < card.size(); k++) {
if ((k == i) || (k == j)) { continue; }
tmp.emplace_back(card[k]);
}
tmp.emplace_back(make_pair( 0,0));
tmp.back() = Mul(card[i], card[j]);
BackTrack(tmp);
tmp.back() = Mul(card[i], { card[j].second,card[j].first });
BackTrack(tmp);
tmp.back() = Add(card[i], card[j]);
BackTrack(tmp);
tmp.back() = Add(card[i], { -card[j].first,card[j].second });
BackTrack(tmp);
}
}
};
vector<pair<int, int>> card = { {cards[0],1},{cards[1],1},{cards[2],1},{cards[3],1} };
BackTrack(card);
return m_bRes;
}
pair<int, int> Mul(const pair<int, int>& a, const pair<int, int>& b) {
return { a.first * b.first,a.second * b.second };
}
pair<int, int> Add(const pair<int, int>& a, const pair<int, int>& b) {
return { a.first * b.second + b.first * a.second,b.second * a.second };
}
bool Is(const pair<int, int>& a) {
if (0 == a.second) { return false; }
return a.second * 24 == a.first;
}
bool m_bRes = false;
};
- 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
2023年5月
struct SDecimal
{
SDecimal(int iNum=0, int iDeno = 1)
{
m_iNum = iNum;
m_iDeno = iDeno;
int iGCD = GCD(abs(m_iNum), abs(m_iDeno));
m_iNum /= iGCD;
m_iDeno /= iGCD;
if (m_iDeno < 0)
{
m_iDeno = -m_iDeno;
m_iNum = -m_iNum;
}
}
SDecimal operator*(const SDecimal& o)const
{
return SDecimal(m_iNumo.m_iNum, m_iDenoo.m_iDeno);
}
SDecimal operator/(const SDecimal& o)const
{
return SDecimal(m_iNumo.m_iDeno, m_iDenoo.m_iNum);
}
SDecimal operator+(const SDecimal& o)const
{
const int iGCD = GCD(m_iDeno, o.m_iDeno);
const int iDeno = m_iDenoo.m_iDeno / iGCD;
return SDecimal(m_iNum(iDeno / m_iDeno) + o.m_iNum*(iDeno / o.m_iDeno), iDeno);
}
SDecimal operator-(const SDecimal& o)const
{
const int iGCD = GCD(m_iDeno, o.m_iDeno);
const int iDeno = m_iDenoo.m_iDeno / iGCD;
return SDecimal(m_iNum(iDeno / m_iDeno) - o.m_iNum*(iDeno / o.m_iDeno), iDeno);
}
bool operator==(const SDecimal& o)const
{
return (m_iNum == o.m_iNum) && (m_iDeno == o.m_iDeno);
}
bool operator<(const SDecimal& o)const
{
auto tmp = *this - o;
return tmp.m_iNum < 0;
}
int m_iNum=0;//分子
int m_iDeno=1;//分母
};
class Solution {
public:
bool judgePoint24(vector& cards) {
m_cards = cards;
vector indexs;
DFS(indexs);
return m_bSuc;
}
void DFS(vector& indexs )
{
if (4 == indexs.size())
{
vector datas;
for (const auto& index : indexs)
{
datas.emplace_back(m_cards[index]);
}
DFSCal(datas);
return;
}
for (int i = 0; i < 4; i++)
{
if (indexs.end() != std::find(indexs.begin(), indexs.end(), i))
{
continue;
}
indexs.emplace_back(i);
DFS(indexs);
indexs.pop_back();
}
}
void DFSCal(const vector& datas)
{
if ((1 == datas.size()) && (datas[0] == 24 ))
{
m_bSuc = true;
return;
}
vector vRet;
for (int i = 0; i + 1 < datas.size(); i++)
{
vector vParam;
for (int j = 0; j < i; j++)
{
vParam.emplace_back(datas[j]);
}
vParam.emplace_back(0);
for (int j = i + 2; j < datas.size(); j++)
{
vParam.emplace_back(datas[j]);
}
vParam[i] = datas[i] * datas[i + 1];
DFSCal(vParam);
if (0 != datas[i + 1].m_iNum)
{
vParam[i] = datas[i] / datas[i + 1];
DFSCal(vParam);
}
vParam[i] = datas[i] + datas[i + 1];
DFSCal(vParam);
vParam[i] = datas[i] - datas[i + 1];
DFSCal(vParam);
}
}
vector m_cards;
bool m_bSuc = false;
- 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
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
QQ群名片
评论记录：
回复评论：