首页 > 其他分享 >【性能优化】 【回溯】 【字符串】1307. 口算难题

【性能优化】 【回溯】 【字符串】1307. 口算难题

时间：2024-03-28 18:32:53浏览次数：28  
标签：1307 const int leve result words 回溯 字符串 setSel

作者推荐

视频算法专题

本文涉及知识点

数学 回溯 字符串 性能优化

LeetCode1307. 口算难题

给你一个方程，左边用 words 表示，右边用 result 表示。
你需要根据以下规则检查方程是否可解：
每个字符都会被解码成一位数字（0 - 9）。
每对不同的字符必须映射到不同的数字。
每个 words[i] 和 result 都会被解码成一个没有前导零的数字。
左侧数字之和（words）等于右侧数字（result）。
如果方程可解，返回 True，否则返回 False。
示例 1：
输入：words = [“SEND”,“MORE”], result = “MONEY”
输出：true
解释：映射 ‘S’-> 9, ‘E’->5, ‘N’->6, ‘D’->7, ‘M’->1, ‘O’->0, ‘R’->8, ‘Y’->‘2’
所以 “SEND” + “MORE” = “MONEY” , 9567 + 1085 = 10652
示例 2：

输入：words = [“SIX”,“SEVEN”,“SEVEN”], result = “TWENTY”
输出：true
解释：映射 ‘S’-> 6, ‘I’->5, ‘X’->0, ‘E’->8, ‘V’->7, ‘N’->2, ‘T’->1, ‘W’->‘3’, ‘Y’->4
所以 “SIX” + “SEVEN” + “SEVEN” = “TWENTY” , 650 + 68782 + 68782 = 138214
示例 3：

输入：words = [“THIS”,“IS”,“TOO”], result = “FUNNY”
输出：true
示例 4：

输入：words = [“LEET”,“CODE”], result = “POINT”
输出：false

提示：

2 <= words.length <= 5
1 <= words[i].length, results.length <= 7
words[i], result 只含有大写英文字母
表达式中使用的不同字符数最大为 10

回溯

简单的例子
AB + AC = BCD
10A+B+10A+C = 100B+10C+D
20A-99B -9C-D = 0
系数20,-99,-9,-1 放到向量v中，并排序。如果直接回溯，时间复杂度1010超时。
将v排序，从后到前处理。处理v[i]，先估算v[0,i)的最小值iMin和最大值iMax，如果已有值x+iMin > 0或 x+iMax < 0，则剪枝忽略。
求最小值：
如果存在负数，最小的负数（绝对值最大）对应最大的未选择值。如果存在正数，最大的正数取最小的未选择数。
求最大值：
如果存在负数，最小的负数（绝对值最大）对应最小的未选择值。如果存在正数，最大的正数取最大的未选择数。

代码

核心代码（超时）

class Solution {
public:
	bool isSolvable(vector<string>& words, string result) {
		unordered_map<char, int> mCharCnt;	
		unordered_map<char, bool> mCharNot0;//开头不能为0
		auto Add = [&](int iMul, const string& s)
		{
			for (int i = s.length() - 1; i >= 0; i--, iMul*=10)
			{
				mCharCnt[s[i]] += iMul;
			}
			if (s.length() > 1)
			{
				mCharNot0[s[0]] = true;
			}
		};
		for (const auto& s : words)
		{
			Add(1, s);
		}
		Add(-1, result);
		vector<pair<int,int>> v;
		for (const auto& [tmp, cnt] : mCharCnt)
		{
			v.emplace_back(cnt,mCharNot0[tmp]);
		}
		sort(v.begin(), v.end());
		set<int> setSel;
		for (int i = 0; i < 10; i++)
		{
			setSel.emplace(i);
		}
		return DFS(v, setSel, 0, 0);
	}
	template<class Pr>
	int MinMax(const pair<int, int>*p, int n, set<int,Pr> setSel)
	{
		int result = 0;
		for (int i = 0; i != n;)
		{
			if (p[i].first < 0)
			{
				result += *setSel.begin()*p[i++].first;
				setSel.erase(setSel.begin());
			}
			else
			{
				result += *setSel.rbegin()*p[--n].first;
				setSel.erase(std::prev(setSel.end()));
			}
		}
		return result;
	}
	bool DFS(const vector<pair<int,int>> & v, set<int>& setSel, int leve, int result)
	{
		if (v.size() == leve)
		{
			return 0 == result;
		}
		const int iMin = MinMax(v.data()+leve, v.size()-leve, set<int, std::greater<int>>(setSel.begin(), setSel.end()));
		const int iMax = MinMax(v.data() + leve, v.size() - leve, setSel);
		if ((iMin + result > 0) || (iMax + result < 0))
		{
			return false;
		}
		for (int i = 9; i >= v[leve].second; i--)
		{
			if (!setSel.count(i))
			{
				continue;
			}
			setSel.erase(i);			
			if (DFS(v, setSel, leve + 1, result + v[leve].first * i))
			{
				return true;
			}
			setSel.emplace(i);
		}
		return false;
	}	
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<string> words;
	string result;
	{
		Solution sln;
		words = { "A","B" }, result = "A";
		auto res = sln.isSolvable(words, result);
		Assert(true, res);
	}
	{
		Solution sln;
		words = { "CBA","CBA","CBA","CBA","CBA" }, result = "EDD";
		auto res = sln.isSolvable(words, result);
		Assert(false, res);
	}
	{
		Solution sln;
		words = { "SEND", "MORE" }, result = "MONEY";
		auto res = sln.isSolvable(words, result);
		Assert(true, res);
	}
	{
		Solution sln;
		words = { "SIX", "SEVEN", "SEVEN" }, result = "TWENTY";
		auto res = sln.isSolvable(words, result);
		Assert(true, res);
	}
	{
		Solution sln;
		words = { "THIS", "IS", "TOO" }, result = "FUNNY";
		auto res = sln.isSolvable(words, result);
		Assert(true, res);
	}
	{
		Solution sln;
		words = { "LEET", "CODE" }, result = "POINT";
		auto res = sln.isSolvable(words, result);
		Assert(false, res);
	}
}

估算最小值最大值

pair<int,int> MinMaxSingle(const pair<int, int>* p, int n)
{
	int less0 = 0, more0 = 0;
	for (int i = 0; i < n ; i++ )
	{
		if (p[i].first < 0)
		{
			less0 += p[i].first;
		}
		else
		{
			more0 += p[i].first;
		}
	}
	return { less0 * 9,more0 * 9 };
}

可以提升一倍，还是过不了。
一，for循环也可以省略。
二，向量变原生数组。
这两个方法效果很小。

class Solution {
public:
	bool isSolvable(vector<string>& words, string result) {
		unordered_map<char, int> mCharCnt;	
		unordered_map<char, bool> mCharNot0;//开头不能为0
		auto Add = [&](int iMul, const string& s)
		{
			for (int i = s.length() - 1; i >= 0; i--, iMul*=10)
			{
				mCharCnt[s[i]] += iMul;
			}
			if (s.length() > 1)
			{
				mCharNot0[s[0]] = true;
			}
		};
		for (const auto& s : words)
		{
			Add(1, s);
		}
		Add(-1, result);
		pair<int, int> v[10];
		int less0 = 0, more0 = 0;
		for (const auto& [tmp, cnt] : mCharCnt)
		{
			v[m_c++] = { cnt,mCharNot0[tmp] };			
			if (cnt < 0)
			{
				less0 += cnt;
			}
			else
			{
				more0 += cnt;
			}
		}
		sort(v, v+m_c);
		set<int> setSel;
		for (int i = 0; i < 10; i++)
		{
			setSel.emplace(i);
		}
		return DFS(v, setSel, 0, 0,more0,less0);
	}
	bool DFS(const pair<int, int>* p, set<int>& setSel, int leve, int result,int more0,int less0)
	{
		if (m_c == leve)
		{
			return 0 == result;
		}
		if ((less0*9 + result > 0) || (more0*9 + result < 0))
		{
			return false;
		}
		for (int i = 9; i >= p[leve].second; i--)
		{
			if (!setSel.count(i))
			{
				continue;
			}
			setSel.erase(i);		
			const int curLess0 = min(0, p[leve].first);
			const int curMore0 = max(0, p[leve].first);
			if (DFS(p, setSel, leve + 1, result + p[leve].first * i,more0+curMore0,less0+curLess0))
			{
				return true;
			}
			setSel.emplace(i);
		}
		return false;
	}	
	int m_c = 0;
};

先处理绝对值大的

速度提升大约1000倍。

class Solution {
public:
	bool isSolvable(vector<string>& words, string result) {
		unordered_map<char, int> mCharCnt;	
		unordered_map<char, bool> mCharNot0;//开头不能为0
		auto Add = [&](int iMul, const string& s)
		{
			for (int i = s.length() - 1; i >= 0; i--, iMul*=10)
			{
				mCharCnt[s[i]] += iMul;
			}
			if (s.length() > 1)
			{
				mCharNot0[s[0]] = true;
			}
		};
		for (const auto& s : words)
		{
			Add(1, s);
		}
		Add(-1, result);
		pair<int, int> v[10];
		int less0 = 0, more0 = 0;
		for (const auto& [tmp, cnt] : mCharCnt)
		{
			v[m_c++] = { cnt,mCharNot0[tmp] };			
			if (cnt < 0)
			{
				less0 += cnt;
			}
			else
			{
				more0 += cnt;
			}
		}
		sort(v, v + m_c, [&](const auto& pr1, const auto& pr2) {return abs(pr1.first) > abs(pr2.first); });
		set<int> setSel;
		for (int i = 0; i < 10; i++)
		{
			setSel.emplace(i);
		}
		return DFS(v, setSel, 0, 0,more0,less0);
	}
	bool DFS(const pair<int, int>* p, set<int>& setSel, int leve, int result,int more0,int less0)
	{
		if (m_c == leve)
		{
			return 0 == result;
		}
		if ((less0*9 + result > 0) || (more0*9 + result < 0))
		{
			return false;
		}
		for (int i = 9; i >= p[leve].second; i--)
		{
			if (!setSel.count(i))
			{
				continue;
			}
			setSel.erase(i);		
			const int curLess0 = min(0, p[leve].first);
			const int curMore0 = max(0, p[leve].first);
			if (DFS(p, setSel, leve + 1, result + p[leve].first * i,more0-curMore0,less0-curLess0))
			{
				return true;
			}
			setSel.emplace(i);
		}
		return false;
	}	
	int m_c = 0;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

标签：1307,const,int,leve,result,words,回溯,字符串,setSel
From： https://blog.csdn.net/he_zhidan/article/details/136420248

相关文章

  • Python 字符串转为字典的两种常用方式（接口交互时）
    结论：在做接口时，请求、响应信息，必须要用json格式 原因：常规的字符串转为字典有两种方式，但两种方式都存在一定的问题：1、ast.literal_eval()（包含eval等类型方法）问题1：安全性，（literal_eval安全性好一些，eval不安全）问题2：需要将字符串中的 true false  null  =》 True......
  • (55/60)两个字符串的删除操作、编辑距离
    两个字符串的删除操作leetcode：583.两个字符串的删除操作动态规划思路先求最长子序长度然后计算两个原字符串离最长子序长度差多少。代码实现classSolution{public:/*（之前搞错了）最长子序长度word[0:i-1]和word2[0:j-1]的最长子序长dp[i][j]if(word1[i-1]==wo......
  • 08天【代码随想录算法训练营34期】第四章 字符串part02（KMP）
    KMP算法解决字符串匹配问题文本串aabaabaaf模式串aabaaf问：模式串是否在文本串中出现过？1）暴力解法，ptr指向文本串index0，遍历一遍发现不匹配，ptr再移向index1，遍历……依次重复，直到ptr指向32）KMP算法，ptr指向文本串index0，遍历到f发现不匹配，由于“aa”在字符串中index3和4时也出现......
  • 08天【代码随想录算法训练营34期】第四章 字符串part01(● 344.反转字符串 ● 541. 反
    **344.反转字符串**classSolution:defreverseString(self,s:List[str])->None:left=0right=len(s)-1whileleft<right:temp=s[left]s[left]=s[right]s[right]=temp......
  • #3. MOO字符串
    题目描述农夫约翰给了奶牛贝西Q个新字符串，其中只有字符M和O，她想将Q个字符串都变成MOO。贝西可以用如下的方式改变字符串：1.用相反的字符替换第一个或最后一个字符（将M变成O，将O变成M）。2.删除第一个或最后一个字符。贝西只想用最少的次数完成改变。请你帮她找......
  • 2024-03-27：用go语言，多维费用背包。 给你一个二进制字符串数组 strs 和两个整数 m 和 n
    2024-03-27：用go语言，多维费用背包。给你一个二进制字符串数组strs和两个整数m和n，请你找出并返回strs的最大子集的长度，该子集中最多有m个0和n个1。如果x的所有元素也是y的元素，集合x是集合y的子集。输入：strs=["10","0001","111001","1","0"],m=......
  • 16使用正则表达式处理字符串
    1<!DOCTYPEhtml>2<htmllang="en">3<head>4<metacharset="UTF-8">5<metaname="viewport"content="width=device-width,initial-scale=1.0">6<title>Document......
  • 如何打乱字符串中的内容
    importjava.util.Random;importjava.util.Scanner;publicclassdaluan{publicstaticvoidmain(String[]args){//键盘输入任意字符串，打乱里面的内容//1。键盘录入字符串Scannersc=newScanner(System.in);Stringstr=s......
  • Python学习——例题详解1、字符串简单加密和解密
    1、加密原理    基于按位异或(^)，对字符串进行简单的加密算法原理：ord('A')^ord('P')#加密,运算结果：17chr(17^ord('p'))#解密，运算结果：‘A’2、例题    给定字符串text作为明文（要加密的原文，同上述A）和key作为密钥（同上述P），使用按位异或循环处理text的每一个......
  • python-列表、元组、字符串、集合、字典等用法
    目录1.列表（list）1.1  列表的定义语法1.2  列表的下标索引1.3  列表的常用操作1.4  列表的循环遍历示例2.元组（tuple）3.字符串4.数据容器（序列）的切片4.2序列切片课后练习5.集合（set）5.1  集合的操作方法6.字典（dict）7.容器排序，排序之后会变成列表对象1.......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99