本文涉及知识点
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);
}
}
}
};
