【回溯 代数系统】679. 24 点游戏

本文涉及知识点

回溯 代数系统

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;
};

回溯

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;
};

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<int> indexs;
	DFS(indexs);
	return m_bSuc;
}
void DFS(vector<int>& indexs )
{
	if (4 == indexs.size())
	{
		vector<SDecimal> 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<SDecimal>& datas)
{
	if ((1 == datas.size()) && (datas[0] == 24 ))
	{
		m_bSuc = true;
		return;
	}
	vector<SDecimal> vRet;
	for (int i = 0; i + 1 < datas.size(); i++)
	{
		vector<SDecimal> 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<int> 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 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/624779.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Java面试八股之Java中的IO流分为几种

Java面试八股之Java中的IO流分为几种

Java中的IO流分为几种 按数据单位分类&#xff1a; 字节流&#xff08;Byte Stream&#xff09;&#xff1a;以字节&#xff08;8位二进制数&#xff09;为基本单位进行数据读写。字节流适合处理所有类型的数据&#xff0c;包括文本、图像、音频、视频等二进制文件。抽象基类…
阅读更多...
小米打印机Mi All-in-One Inkjet Printer进行扫描

小米打印机Mi All-in-One Inkjet Printer进行扫描

1&#xff0c;打开电脑的控制面板&#xff0c;找到打印机 2&#xff0c;&#xff0c;选择小米打印机【Mi All-in-One Inkjet Printer】&#xff1b;右键&#xff0c;选择开始扫描 3&#xff0c;可以预览&#xff0c;或者直接扫描 4&#xff0c;点击下一步&#xff0c;导入图片 …
阅读更多...
redis深入理解之实战

redis深入理解之实战

1、SpringBoot整合redis 1.1 导入相关依赖 <dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId> </dependency> <dependency><groupId>org.springframework.boot</groupId><artifactId&g…
阅读更多...
高校普法|基于SSM＋vue的高校普法系统的设计与实现(源码+数据库+文档)

高校普法|基于SSM＋vue的高校普法系统的设计与实现(源码+数据库+文档)

高校普法系统 目录 基于SSM&#xff0b;vue的高校普法系统的设计与实现 一、前言 二、系统设计 三、系统功能设计 1系统功能模块 2管理员功能模块 3律师功能模块 4学生功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获…
阅读更多...
sklearn中多分类和多标签分类评估方法总结

sklearn中多分类和多标签分类评估方法总结

一、任务区分 多分类分类任务&#xff1a;在多分类任务中&#xff0c;每个样本只能被分配到一个类别中。换句话说&#xff0c;每个样本只有一个正确的标签。例如&#xff0c;将图像分为不同的物体类别&#xff0c;如猫、狗、汽车等。 多标签分类任务&#xff1a;在多标签分类任…
阅读更多...
抖音小店无货源怎么做？超详细教程，新手看这一篇就够了！

抖音小店无货源怎么做？超详细教程，新手看这一篇就够了！

哈喽~我是电商月月 实体店做生意开店或是卖菜摆地摊&#xff0c;商家大部分都不是厂家自销&#xff0c;基本都是从批发厂里进货&#xff0c;然后加价卖出去的 “中间商赚差价”的行为在网上做店也是一种合理的行为 抖音小店里面的商家大部分选择的都是无货源模式运营 无货源…
阅读更多...
Jmeter接口测试之参数化

Jmeter接口测试之参数化

在接口测试中&#xff0c;某些时候一些场景会使用到参数化的场景&#xff0c;参数化简单的说就是同一个请求需要不同的数据&#xff0c;比如在性能测试中需要并发多个用户的场景&#xff0c;这样的目的是为了模拟真实的用户场景&#xff0c;需要模拟不同的账号&#xff0c;这里…
阅读更多...
2. C++入门：缺省参数及函数重载

2. C++入门：缺省参数及函数重载

缺省参数 缺省参数是声明或定义函数时为函数的参数指定一个缺省值。在调用该函数时&#xff0c;如果没有指定实参则采用该形参的缺省值&#xff0c;否则使用指定的实参。 void Func(int a 0) {cout << a << endl; }int main() {Func();Func(10);return 0; }在形…
阅读更多...
【simulink】Scrambling 加扰

【simulink】Scrambling 加扰

https://ww2.mathworks.cn/help/comm/ug/additive-scrambling-of-input-data-in-simulink.html 草图 simulink 代码图
阅读更多...
GPT-4o正式发布；零一万物发布千亿参数模型；英国推出AI评估平台

GPT-4o正式发布；零一万物发布千亿参数模型；英国推出AI评估平台

OpenAI 正式发布 GPT-4o 今天凌晨&#xff0c;OpenAI 正式发布 GPT-4o&#xff0c;其中的「o」代表「omni」&#xff08;即全面、全能的意思&#xff09;&#xff0c;这个模型同时具备文本、图片、视频和语音方面的能力&#xff0c;甚至就是 GPT-5 的一个未完成版。 并且&…
阅读更多...
mysql 一次删除多个备份表

mysql 一次删除多个备份表

show tables时&#xff0c;发现备份的表有点多&#xff0c;想要一个sql就删除 总不能drop table xx ; 写多次吧。 方式一 1.生成删除某个数据库下所有的表SQL -- 查询构建批量删除表语句&#xff08;根据数据库名称&#xff09; select concat(drop table , TABLE_NAME, ;)…
阅读更多...
Axure10_win安装教程(安装、汉化、授权码，去弹窗）

Axure10_win安装教程(安装、汉化、授权码，去弹窗）

1.下载Axure10 链接&#xff1a;https://pan.baidu.com/s/1fc8Bgyic8Ct__1IOv-afUg 提取码&#xff1a;9qew 2.安装Axure10 因为我的电脑是Windows操作系统&#xff0c;所以我下载的AxureRP-Setup-Beta v10.0.0.3816 (Win).exe 一直点下一步就行 3.Axure10中文 打开Axure…
阅读更多...
fdatool中的幅值响应 怎么计算

fdatool中的幅值响应 怎么计算

设计一个幅值是100&#xff0c;45hz的正弦波&#xff0c;设计一个滤波器&#xff0c;观察滤波器的幅值响应&#xff1a; 滤波前的数据的峰峰值是100*2&#xff1b; 假设滤波后的数据峰峰值变成95*2&#xff1b;&#xff08;95*2是滤波后的数据的峰峰值&#xff0c;不是fft后的值…
阅读更多...
豆浆机缺水检测功能如何实现的

豆浆机缺水检测功能如何实现的

豆浆机缺水检测功能的实现是通过光学液位传感器来完成的。这种传感器具有多种优势&#xff0c;如内部所有元器件经过树脂胶封处理&#xff0c;没有任何机械活动部件&#xff0c;免调试、免检验、免维护等特点。它采用了光电液位传感器内置的光学电子元件&#xff0c;体积小、功…
阅读更多...
自动化神器Autolt，让你不再重复工作！

自动化神器Autolt，让你不再重复工作！

随着互联网不断发展&#xff0c;它给我们带来便利的同时&#xff0c;也带来了枯燥、重复、机械的重复工作。今天&#xff0c;我要和大家分享一款老牌实用的自动化工具&#xff1a;AutoIt&#xff0c;它能够让你告别繁琐的重复性工作&#xff0c;提高工作效率。 这里透露一下&am…
阅读更多...
python 虚拟环境多种创建方式

python 虚拟环境多种创建方式

【一】说明介绍 &#xff08;1&#xff09;什么是虚拟环境 在Python中&#xff0c;虚拟环境&#xff08;Virtual Environment&#xff09;是一个独立的、隔离的Python运行环境&#xff0c;它拥有自己的Python解释器、第三方库和应用程序。通过创建虚拟环境&#xff0c;可以确…
阅读更多...
解析流中 apts 与 vpts的分布

解析流中 apts 与 vpts的分布

流中 apts 与 vpts的分布情况&#xff0c;同时使用图显示出来 一&#xff0c;最好的方式是使用EasyICE 来查看&#xff0c;这个自动化工具是很好用的&#xff1a; 二&#xff0c; 当EasyICE不能打出理想的数据的时候&#xff0c;可以自己来提取数据&#xff0c;画出对应的图&a…
阅读更多...
老铁，对不住了，没有B端成品界面可售，都是定制化设计

老铁，对不住了，没有B端成品界面可售，都是定制化设计

经常有粉丝老铁问我有没有成品的UI图可以出售&#xff0c;实在对不住&#xff0c;我们不销售设计成品。 UI设计图是一种设计稿&#xff0c;它是用来展示和呈现产品的界面设计和交互效果的&#xff0c;而不是一个完整的、可交付的成品。UI设计图通常是以静态的形式呈现&#xf…
阅读更多...
HTML常见标签-标题标签

HTML常见标签-标题标签

标题标签 标题标签一般用于在页面上定义一些标题性的内容,如新闻标题,文章标题等,有h1到h6六级标题 代码 <body><h1>一级标题</h1><h2>二级标题</h2><h3>三级标题</h3><h4>四级标题</h4><h5>五级标题</h5>…
阅读更多...
没有申请域名的情况下，用navicat远程连接我们的服务器的Mysql数据库

没有申请域名的情况下，用navicat远程连接我们的服务器的Mysql数据库

我们可以根据公网ip用shell来远程连接 首先我们打开自己买的服务器 例如你看这个&#xff0c;就是我们的公网IP 如果服务器里面没有安装mysql数据库的话&#xff0c;那么我们可以用一个轻量级的docker来安装数据库代替一下 我们用docker弄个轻量级的mysql5.7.36&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023