是网站建设专业好,微商分销商城,长春网络推荐,成都网站优化seo本文涉及知识点
回溯 代数系统
LeetCode679. 24 点游戏
给定一个长度为4的整数数组 cards 。你有 4 张卡片#xff0c;每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 [‘’, ‘-’, ‘*’, ‘/’] 和括号 ‘(’ 和 ‘)’ 将这些卡片上的数字排列成数学表达式…本文涉及知识点
回溯 代数系统
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) 组成代数系统任何结果都可以用ab*c表示。 初始{0,1,c1} 加法 {ab × \times ×c,1,x} 减法{ab × \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(vectorint cards) {sort(cards.begin(), cards.end());do {int hasDo 0;std::functionvoid(pairint, int, pairint, int, pairint, int) BackTrack [](pairint, int a, pairint, int b, pairint, intc ){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;}pairint, int Mul(const pairint, int a, const pairint, int b) {return { a.first * b.first,a.second * b.second };}pairint, int Cal(const pairint, int a, const pairint, int b, const pairint, 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 pairint, int a) {if (0 a.second) { return false; }return a.second * 24 a.first;}bool m_bRes false;
};回溯
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(vectorint cards) {std::functionvoid(vectorpairint, int) BackTrack [](vectorpairint, 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; }vectorpairint, 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);}}};vectorpairint, int card { {cards[0],1},{cards[1],1},{cards[2],1},{cards[3],1} };BackTrack(card);return m_bRes;}pairint, int Mul(const pairint, int a, const pairint, int b) {return { a.first * b.first,a.second * b.second };}pairint, int Add(const pairint, int a, const pairint, int b) {return { a.first * b.second b.first * a.second,b.second * a.second };}bool Is(const pairint, int a) {if (0 a.second) { return false; }return a.second * 24 a.first;}bool m_bRes false;
};2023年5月
struct SDecimal { SDecimal(int iNum0, 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_iNum0;//分子 int m_iDeno1;//分母 };
class Solution { public: bool judgePoint24(vector cards) { m_cards cards; vectorint indexs;DFS(indexs);return m_bSuc;
}
void DFS(vectorint indexs )
{if (4 indexs.size()){vectorSDecimal 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 vectorSDecimal datas)
{if ((1 datas.size()) (datas[0] 24 )){m_bSuc true;return;}vectorSDecimal vRet;for (int i 0; i 1 datas.size(); i){vectorSDecimal 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);}
}
vectorint m_cards;
bool m_bSuc false;}; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
