考虑性质就复杂多了

发布时间：2025-06-24 07:40:27  作者：北方职教升学中心  阅读量：593


leves记录字符串编码，然后利用数组出重。每个块都有一个颜色，用一个字母表示。C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

我想对大家说的话
《喜缺全书算法册》以原理、模式是以三个字母字符串的列表形式 allowed 给出的，其中模式的前两个字符分别表示左右底部块，第三个字符表示顶部块。每种状态：组织字符串，时间复杂度O(n),出重大约O(10)，故总时间复杂度为：O(mnnm10n)，理论上严重超时，实际略微超时。每一行的块比它下面的行 少一个块 ，并且居中。

代码

classSolution{public:boolpyramidTransition(string bottom,vector<string>&allowed){unordered_map<string,vector<char>>mAllow;for(constauto&str :allowed){mAllow[str.substr(0,2)].emplace_back(str[2]);;}vector<vector<string>>leves ={{bottom}};for(inti =0;i+1<bottom.length();i++){unordered_set<string>nexts;std::function<void(string&,conststring&,int)>BackTrack =[&](string&str,conststring&cur,intbegin){if(begin +1==cur.length()){if(-1==str.find(' ')){nexts.emplace(str);}return;}for(constauto&ch :mAllow[cur.substr(begin,2)]){str[begin]=ch;BackTrack(str,cur,begin +1);}};for(constauto&cur :leves[i]){string str(cur.length()-1,' ');BackTrack(str,cur,0);}if(nexts.empty()){returnfalse;}leves.emplace_back(vector<string>(nexts.begin(),nexts.end()));}returntrue;}};

单元测试

string bottom;vector<string>allowed;TEST_METHOD(TestMethod1){bottom ="BCD",allowed ={"BCC","CDE","CEA","FFF"};autores =Solution().pyramidTransition(bottom,allowed);AssertEx(true,res);}TEST_METHOD(TestMethod2){bottom ="AAAA",allowed ={"AAB","AAC","BCD","BBE","DEF"};autores =Solution().pyramidTransition(bottom,allowed);AssertEx(false,res);}TEST_METHOD(TestMethod3){bottom ="AA",allowed ={};autores =Solution().pyramidTransition(bottom,allowed);AssertEx(false,res);}TEST_METHOD(TestMethod4){bottom ="AA",allowed ={"AAB"};autores =Solution().pyramidTransition(bottom,allowed);AssertEx(true,res);}TEST_METHOD(TestMethod5){bottom ="AAB",allowed ={"AAB"};autores =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"};autores =Solution().pyramidTransition(bottom,allowed);AssertEx(true,res);}TEST_METHOD(TestMethod7){bottom ="DBCDA",allowed ={"DBD","BCC","CDD","DAD","DDA","AAC","CCA","BCD"};autores =Solution().pyramidTransition(bottom,allowed);AssertEx(true,res);}

C++BFS（总时间超时)

mAllow 用二维数组替换。一个状态对应的后续状态：(n-1)m。

子墨子言之：事无终始，无务多业。
你从底部的一排积木 bottom 开始，作为一个单一的字符串，你 必须 使用作为金字塔的底部。总结为主。正确性证明、
从最底层(游戏邦注:即第4个关卡)开始，创造第3个关卡有多种方法，但如果尝试所有可能性，你便会在创造第1个关卡前陷入困境。也就是我们常说的专业的人做专业的事。考虑性质就复杂多了。

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。只需要处理leves[i]内部的重复。

本文涉及知识点

C++BFS算法
C++回溯

LeetCode756. 金字塔转换矩阵

你正在把积木堆成金字塔。都是允许的。
金字塔中有三种三角形图案，分别是“BCC”、

提示：
2 <= bottom.length <= 6
0 <= allowed.length <= 216
allowed[i].length == 3
所有输入字符串中的字母来自集合 {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}。“CDE”和“CEA”。
为了使金字塔美观，只有特定的 三角形图案 是允许的。


BFS的后续状态：所有可能的倒数i+1层。
BFS的初始状态：leves = {{bottom}}。
unorder_map<string,vector> mAllow。如果要打包下载源码（CSDN下载频道偶尔审核不通过，原因未知），也请加QQ群。
在给定 bottom 和 allowed 的情况下，如果你能一直构建到金字塔顶部，使金字塔中的 每个三角形图案 都是允许的，则返回 true ，否则返回 false 。
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
如果程序是一条龙，那算法就是他的是睛

测试环境

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

在这里插入图片描述

输入：bottom = “AAAA”, allowed = [“AAB”,“AAC”,“BCD”,“BBE”,“DEF”]
输出：false
解释：允许的三角形模式显示在右边。请注意，这与 “BAC” 不同，“B” 在左下角，“A” 在右下角。
BFS的重复处理： leves[i]的长度为：bottom.length - i，故当i ≠ \neq =j是，leves[i]的任意元素不会和leves[j]相同。 key是：allower.substr(0,2) value是：allower[2]。
例如，“ABC” 表示一个三角形图案，其中一个 “C” 块堆叠在一个 ‘A’ 块(左)和一个 ‘B’ 块(右)之上。
BFS的返回值：任意leves[i]为空，返回false；否则返回true。


如果有不明白的，请加文末QQ群。
从最底层(第3层)开始，我们可以在第2层构建“CE”，然后在第1层构建“E”。
示例 1：

在这里插入图片描述

输入：bottom = “BCD”, allowed = [“BCC”,“CDE”,“CEA”,“FFF”]
输出：true
解释：允许的三角形模式显示在右边。单个测试用例不超时，总时间超时。 O(10n)变成O(1)。

classSolution{public:boolpyramidTransition(string bottom,vector<string>&allowed){constintN =bottom.length();vector<int>mAllow[7][7];for(constauto&str :allowed){mAllow[str[0]-'A'][str[1]-'A'].emplace_back(str[2]-'A');}queue<int>que;vector<string>codes[7];intiCodeCnt =1;for(intlen =1;len <=N;len++){iCodeCnt *=7;for(intcode =0;code <iCodeCnt;code++){vector<char>tmp;intremain =code;for(inti =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(inti =N;i >=2;i--){queue<int>nextQue;vector<bool>vis(codes[i-1].size());while(que.size()){constautocur =que.front();que.pop();std::function<void(int,conststring&,int)>BackTrack =[&](intcode,conststring&cur,intbegin){if(begin +1==cur.length()){if(!vis[code]){nextQue.emplace(code);vis[code]=true;}return;}constauto&v =mAllow[cur[begin]-'A'][cur[begin +1]-'A'];if(v.empty()){return;}for(constauto&num :v){BackTrack(code *7+num,cur,begin +1);}};BackTrack(0,codes[i][cur],0);}que.swap(nextQue);}returnque.size();}};

C++BFS

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

vector<string>codes[7];classSolution{public:boolpyramidTransition(string bottom,vector<string>&allowed){constintN =bottom.length();vector<int>mAllow[7][7];for(constauto&str :allowed){mAllow[str[0]-'A'][str[1]-'A'].emplace_back(str[2]-'A');}Init();queue<int>que;for(intcode =0;code <codes[N].size();code++){if(codes[N][code]==bottom){que.emplace(code);}}for(inti =N;i >=2;i--){queue<int>nextQue;vector<bool>vis(codes[i -1].size());while(que.size()){constautocur =que.front();que.pop();std::function<void(int,conststring&,int)>BackTrack =[&](intcode,conststring&cur,intbegin){if(begin +1==cur.length()){if(!vis[code]){nextQue.emplace(code);vis[code]=true;}return;}constauto&v =mAllow[cur[begin]-'A'][cur[begin +1]-'A'];if(v.empty()){return;}for(constauto&num :v){BackTrack(code *7+num,cur,begin +1);}};BackTrack(0,codes[i][cur],0);}que.swap(nextQue);}returnque.size();}voidInit(){if(codes[1].size()){return;}constintN =6;intiCodeCnt =1;for(intlen =1;len <=N;len++){iCodeCnt *=7;for(intcode =0;code <iCodeCnt;code++){vector<char>tmp;intremain =code;for(inti =0;i <len;i++){tmp.emplace_back('A'+remain %7);remain /=7;}string str(tmp.rbegin(),tmp.rend());codes[len].emplace_back(str);}}}};

总结

如果不考虑性能，本题很简单。一个三角形的图案由 两个块 和叠在上面的 单个块 组成。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、
allowed 中所有值都是 唯一的

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

BFS的状态表示：leves[i]记录倒数第0层所有可能。所有的状态数为：mn,n = bottom.length， ,m = 7(A到G)即空间复杂度为：O(mn)。按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。

上一篇：[集成ChatGPT等AI模型]Python
下一篇：单机卡牌游戏：探索未知的冒险