首页 > 编程语言 >【C++BFS 回溯】756. 金字塔转换矩阵

【C++BFS 回溯】756. 金字塔转换矩阵

时间：2024-07-20 19:27:22浏览次数：19  
标签：code 756 bottom int C++ BFS str allowed cur

本文涉及知识点

C++BFS算法
C++回溯

LeetCode756. 金字塔转换矩阵

你正在把积木堆成金字塔。每个块都有一个颜色，用一个字母表示。每一行的块比它下面的行 少一个块 ，并且居中。
为了使金字塔美观，只有特定的 三角形图案 是允许的。一个三角形的图案由 两个块 和叠在上面的 单个块 组成。模式是以三个字母字符串的列表形式 allowed 给出的，其中模式的前两个字符分别表示左右底部块，第三个字符表示顶部块。
例如，“ABC” 表示一个三角形图案，其中一个 “C” 块堆叠在一个 ‘A’ 块(左)和一个 ‘B’ 块(右)之上。请注意，这与 “BAC” 不同，“B” 在左下角，“A” 在右下角。
你从底部的一排积木 bottom 开始，作为一个单一的字符串，你 必须 使用作为金字塔的底部。
在给定 bottom 和 allowed 的情况下，如果你能一直构建到金字塔顶部，使金字塔中的 每个三角形图案 都是允许的，则返回 true ，否则返回 false 。
示例 1：

在这里插入图片描述

输入：bottom = “BCD”, allowed = [“BCC”,“CDE”,“CEA”,“FFF”]
输出：true
解释：允许的三角形模式显示在右边。
从最底层(第3层)开始，我们可以在第2层构建“CE”，然后在第1层构建“E”。
金字塔中有三种三角形图案，分别是“BCC”、“CDE”和“CEA”。都是允许的。
示例 2：

在这里插入图片描述

输入：bottom = “AAAA”, allowed = [“AAB”,“AAC”,“BCD”,“BBE”,“DEF”]
输出：false
解释：允许的三角形模式显示在右边。
从最底层(游戏邦注:即第4个关卡)开始，创造第3个关卡有多种方法，但如果尝试所有可能性，你便会在创造第1个关卡前陷入困境。

提示：
2 <= bottom.length <= 6
0 <= allowed.length <= 216
allowed[i].length == 3
所有输入字符串中的字母来自集合 {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}。
allowed 中所有值都是 唯一的

C++BFS(极端情况超时)

BFS的状态表示：leves[i]记录倒数第0层所有可能。所有的状态数为：mn,n = bottom.length， ,m = 7(A到G)即空间复杂度为：O(mn)。
BFS的后续状态：所有可能的倒数i+1层。一个状态对应的后续状态：(n-1)m。每种状态：组织字符串，时间复杂度O(n),出重大约O(10)，故总时间复杂度为：O(mnnm10n)，理论上严重超时，实际略微超时。
BFS的初始状态：leves = {{bottom}}。
BFS的返回值：任意leves[i]为空，返回false；否则返回true。
BFS的重复处理： leves[i]的长度为：bottom.length - i，故当i ≠ \neq = j是，leves[i]的任意元素不会和leves[j]相同。只需要处理leves[i]内部的重复。
unorder_map<string,vector> mAllow。 key是：allower.substr(0,2) value是：allower[2]。

代码

class Solution {
		public:
			bool pyramidTransition(string bottom, vector<string>& allowed) {
				unordered_map<string, vector<char>> mAllow;
				for (const auto& str : allowed) {
					mAllow[str.substr(0, 2)].emplace_back(str[2]);;
				}				
				vector<vector<string>> leves = { {bottom} };
				for (int i = 0; i+1 < bottom.length(); i++) {
					unordered_set<string> nexts;
					std::function<void(string&,const string&, int)> BackTrack = [&](string& str,const string& cur, int begin) {
						if (begin + 1 == cur.length()) {
							if(-1 == str.find(' ')){ nexts.emplace(str); }						
							return;
						}
						for (const auto& ch : mAllow[cur.substr(begin, 2)]) {
							str[begin] = ch;
							BackTrack(str, cur, begin + 1);
						}
					};
					for (const auto& cur : leves[i]) {
						string str(cur.length() - 1, ' ');
						BackTrack(str, cur, 0);
					}
					if (nexts.empty()) { return false; }
					leves.emplace_back(vector<string>(nexts.begin(), nexts.end()));
				}
				return true;
			}
		};

单元测试

		string bottom;
		vector<string> allowed;
		TEST_METHOD(TestMethod1)
		{
			bottom = "BCD", allowed = { "BCC", "CDE", "CEA", "FFF" };
			auto res = Solution().pyramidTransition(bottom, allowed);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod2)
		{
			bottom = "AAAA", allowed = { "AAB", "AAC", "BCD", "BBE", "DEF" };
			auto res = Solution().pyramidTransition(bottom, allowed);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod3)
		{
			bottom = "AA", allowed = {  };
			auto res = Solution().pyramidTransition(bottom, allowed);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod4)
		{
			bottom = "AA", allowed = { "AAB"};
			auto res = Solution().pyramidTransition(bottom, allowed);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod5)
		{
			bottom = "AAB", allowed = { "AAB" };
			auto res = Solution().pyramidTransition(bottom, allowed);
			AssertEx(false, res);
		}

		TEST_METHOD(TestMethod6)
		{
			bottom = "FDBACE", allowed = { "EEF","BFE","EDD","EFB","EFC","DCE","CCE","ABB","BBB","EDC","ADD","AFE","CAF","DEF","ABE","BBD","CBB","ADB","ABD","EDF","FAE","CAA","CFB","BCA","BDC","EAB","FFE","FBF","EFF","AFD","DFA","BED","BDD","ABA","FCB","CBD","CDC","CEC","ECC","ECA","EBC","DFD","FFB","BDE","DBD","EBB","DEB","BEF","FFA","AEA","CCC","BFF","DCD","BBA","CFF","ECD","CBF","CCD","FAA","EDA","ADF","ECE","FCF","FFF","FCE","BFC","CCF","ACD","FDB","DBA","AED","FDD","BDF","FBE","DCB","ACE","FBC","FEF","FDF","AEF","DDB","CFA","BCB","EFA","EAC","FBD","CFC","AEE","CEB","AFA","CCA","BFD","BAC","BAA","CEE","DAB","AFC","DBE","BEE","DAF","DCA","EEA","BDB","EEB","EAA","BEC","DED","CDE","CDB","EEE","DAC","EBF","EBD","FDE","ABC","ACB","DBC","FBA","BAE","EFE","BBC","CBC","FED","FEA","ACF","DCF","FDA","BCC","ADE","DAE","DCC","EDB","AFB","CEA","DFE","BAD","FEC","EEC","EBE","CEF","EAD","ABF","EFD","AAB","AAD","FAB","FEE","CBE","BBE","ADC","FAD","DBB","CAB","CDA","AAF","DBF","FCA","DEE","EDE","FFC","DDD","DDA","DEC","DFF","BCD","ECF","DDF","AEB","BDA","FBB","BCE","DAA","ACC","CCB","FAC","BAF","BEA","CFD","EBA","ACA","DAD","BFB","ECB","CAD","DDC","FCC","BEB","FAF","BBF","AAA","AAC","CED","AAE","CDD","DDE","DEA","FFD","DFC","CFE","FEB","FDC","ADA","BCF","AFF","EAE","AEC","CAC","CDF","BAB","EED","CAE","FCD","BFA","EAF","CBA","DFB" };
			auto res = Solution().pyramidTransition(bottom, allowed);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod7)
		{
			bottom = "DBCDA", allowed = { "DBD","BCC","CDD","DAD","DDA","AAC","CCA","BCD" };
			auto res = Solution().pyramidTransition(bottom, allowed);
			AssertEx(true, res);
		}

C++BFS（总时间超时)

mAllow 用二维数组替换。leves记录字符串编码，然后利用数组出重。 O(10n)变成O(1)。单个测试用例不超时，总时间超时。

class Solution {
		public:
			bool pyramidTransition(string bottom, vector<string>& allowed) {
				const int N = bottom.length();
				vector<int> mAllow[7][7];
				for (const auto& str : allowed) {
					mAllow[str[0] - 'A'][str[1] - 'A'].emplace_back(str[2]-'A');
				}	
				queue<int> que;				
				vector<string> codes[7];
				int iCodeCnt =1;
				for (int len = 1; len <= N; len++) {
					iCodeCnt *= 7;
					for (int code = 0; code < iCodeCnt; code++) {
						vector<char> tmp;
						int remain = code;
						for (int i = 0; i < len; i++) {
							tmp.emplace_back('A' + remain % 7);
							remain /= 7;
						}
						string str(tmp.rbegin(), tmp.rend());
						codes[len].emplace_back(str);
						if (str == bottom) {
							que.emplace(code);							
						}
					}
				}
				
				for (int i = N; i >= 2;i--) {
					queue<int> nextQue;
					vector<bool> vis(codes[i-1].size());
					while (que.size()) {
						const auto cur = que.front();
						que.pop();
						std::function<void(int, const string&, int)> BackTrack = [&](int code, const string& cur, int begin) {
							if (begin + 1 == cur.length()) {
								if (!vis[code])
								{
									nextQue.emplace(code);
									vis[code] = true;
								}
								return;
							}
							const auto& v = mAllow[cur[begin] - 'A'][cur[begin + 1] - 'A'];
							if (v.empty()) { return; }
							for (const auto& num : v) {
								BackTrack(code * 7 + num, cur, begin + 1);
							}
						};
						BackTrack(0, codes[i][cur], 0);
					}
					que.swap(nextQue);
				}
				return que.size();
			}
		};

C++BFS

codes变成全局变量，所有测试用例只初始化一次。

vector<string> codes[7];

class Solution {
		public:
			bool pyramidTransition(string bottom, vector<string>& allowed) {
				const int N = bottom.length();
				vector<int> mAllow[7][7];
				for (const auto& str : allowed) {
					mAllow[str[0] - 'A'][str[1] - 'A'].emplace_back(str[2]-'A');
				}	
				Init();
				queue<int> que;				
				for (int code = 0; code < codes[N].size();code++) {
					if (codes[N][code] == bottom) {
						que.emplace(code);
					}
				}
				for (int i = N; i >= 2; i--) {
					queue<int> nextQue;
					vector<bool> vis(codes[i - 1].size());
					while (que.size()) {
						const auto cur = que.front();
						que.pop();
						std::function<void(int, const string&, int)> BackTrack = [&](int code, const string& cur, int begin) {
							if (begin + 1 == cur.length()) {
								if (!vis[code])
								{
									nextQue.emplace(code);
									vis[code] = true;
								}
								return;
							}
							const auto& v = mAllow[cur[begin] - 'A'][cur[begin + 1] - 'A'];
							if (v.empty()) { return; }
							for (const auto& num : v) {
								BackTrack(code * 7 + num, cur, begin + 1);
							}
						};
						BackTrack(0, codes[i][cur], 0);
					}
					que.swap(nextQue);
				}
				
				return que.size();
			}
			void Init() {
				if (codes[1].size()) { return; }
				const int N = 6;
				int iCodeCnt = 1;
				for (int len = 1; len <= N; len++) {
					iCodeCnt *= 7;
					for (int code = 0; code < iCodeCnt; code++) {
						vector<char> tmp;
						int remain = code;
						for (int i = 0; i < len; i++) {
							tmp.emplace_back('A' + remain % 7);
							remain /= 7;
						}
						string str(tmp.rbegin(), tmp.rend());
						codes[len].emplace_back(str);						
					}
				}
			}			
		};

总结

如果不考虑性能，本题很简单。考虑性质就复杂多了。


如果有不明白的，请加文末QQ群。如果要打包下载源码（CSDN下载频道偶尔审核不通过，原因未知），也请加QQ群。

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

标签：code,756,bottom,int,C++,BFS,str,allowed,cur
From： https://blog.csdn.net/he_zhidan/article/details/140428577

相关文章

  • GESP C++ 二级真题（2023年12月）T1 小杨做题
    问题描述：为了准备考试，小杨每天都要做题。第一天做了a道题；第二天做了b道题；从第三天起，小杨每天做的题目数量是前两天的总和。此外，小杨还规定当自己某一天做了大于或等于m题时，接下来的日子，他就不做题了。请问到了第n天，小杨总共做了多少道题？输入描述：总共4行。第一行一个整数a，......
  • 使用GDAL（C++库）从末尾行开始向上读取图像数据
    使用GDAL（C++库）从末尾行读取图像数据OpenCV等图像库默认的读取方式都是从第一行开始，逐行读取数据（自顶向下），填充到内存缓冲区；对于某些特殊应用，需要反行序读取（从末尾行读到起始行）的图像数据结果。GDAL提供了灵活的栅格数据读取方式RasterIO，下面介绍RasterIO的调用方式，以及如何......
  • 在VS2022中通过Nuget将vcpkg环境集成/卸载到c++项目
    在VS2022中通过Nuget将vcpkg环境集成/卸载到c++项目vcpkg是微软和C++社区维护的免费开源C/C++包管理器。利用它，可以一条命令编译安装用户所需的库；提供CMake配置文件；并且对于Windows开发者，在VisualStudio中集成后还可以自动链接静态库，非常方便易用。一般而言，开发者仅需要......
  • C++的输入输出（ACM模式）
    原文1.输入首先，在C++语言中，要使用标准的输入，需要包含头文件<iostream>1.1cincin是c++中标准的输入流对象，cin有两个用法，单独读入和批量读入cin的原理：简单来讲，有一个缓冲区，键盘输入的数据会先存到缓冲区，用cin可以从缓冲区中读取数据。注意：cin可以连续从键盘读入数据cin......
  • 如何编写一个C++程序来整蛊你的好基友
    如何编写一个C++程序来整蛊你的好基友如何编写一个C++程序来整蛊你的好基友整蛊按照危险性来排序3星类1.每行输出一句2.一直输出，不换行3.给控制台换一个颜色（较有威慑力）颜色代码4.扫盘（配上第三个效果更好，可以用来装B）4星类（含部分解药）弹窗类弹窗代码按下反馈键判定另......
  • c++里数的存储
    hello，大家好啊，这里是文宇，不是文字，是文宇哦。C++中的数的存储方式涵盖了整数、浮点数、字符等多种类型。每种类型的数有不同的位数和存储规则。下面将详细介绍C++中数的存储。首先，整数类型的存储通常使用二进制来表示。C++中提供了多种整数类型，包括char、short、int、longlon......
  • C++生化危机2.0.yl.3已更新
    本版本修复了一个BUG，邻居家无法进入已修复一些小BUG也修复完成（作者体验游戏时发现的）下载链接：生化危机2.0.yl.3.rar-蓝奏云代码如下（建议下载，因为rar解压包内内容更全）：#include<bits/stdc++.h>#include<windows.h>#include<time.h>#include<conio.h>usingnamespacestd......
  • C++学习笔记
    第一章预备知识C++融合了三种不同的编程方式：过程性编程（C语言代表的）、面向对象编程（C语言基础上添加的类代表的）、泛型编程（C++模板支持）。Linux上源代码文件编译完后生成后缀.o的目标代码文件，然后执行链接后生成文件名为a.out（默认取名）的可执行程序。C++源文件名的后缀有.cpp......
  • FFmpeg开发笔记（三十九）给Visual Studio的C++工程集成FFmpeg
    ​《FFmpeg开发实战：从零基础到短视频上线》一书的“第11章 FFmpeg的桌面开发”介绍了如何在Windows环境对Qt结合FFmpeg实现桌面程序，那么Windows系统通过VisualStudio开发桌面程序也是很常见的，下面就介绍如何在VisualStudio的C++工程中集成FFmpeg库和SDL2库。首先按照《FFmpe......
  • c++零基础知识要点整理（5）
    1.位与运算符：& （位与：代表把二进制的每个数的每一位从低到高进行运算（有0必0））逻辑与：&&（有假必假）(1)位与的定义：inta=0b1001;//0b1001是二进制表示法，0b代表用二进制表示，0b1001对应十进制数为：9intb=0b0101;//对应十进制数为：5a&b=0b0001;//12.位或运算符：| （有1即1）逻辑或：||......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99