C++程序检查两个字母栈是否可以清空


假设有2n个字母,每个字母上都写有一个1到n之间的整数。恰好有两个字母上写着相同的数字。这些字母被排列成m个栈,栈i上放着stack[i]个字母。我们的任务是以如下方式清空所有栈

  • 我们必须选择任意两个栈,并从这两个栈中移除顶部的字母。

  • 我们移除的字母必须在两个栈上都写有相同的数字。

如果我们能以这种方式清空m个栈,则输出true,否则返回false。

因此,如果输入类似于n = 3,m = 2,stacks = {{2, 1, 3}, {2, 1, 3}},则输出为true。

有两个栈,每个栈上的字母分别写着数字2、1、3。因此,我们可以从两个栈中移除字母并以给定的方式清空它们。

为了解决这个问题,我们将遵循以下步骤:

Define one 2D array dp
Define an array tvec
for initialize i := 0, when i < m, update (increase i by 1), do:
   k := size of stacks[i]
   for initialize j := 0, when j < k, update (increase j by 1), do:
      if j < 0, then:
         insert p at the end of dp[stacks[i, j]]
         (increase tvec[p] by 1)
      p := stacks[i, j]
Define an array tp
for initialize i := 1, when i <= n, update (increase i by 1), do:
   Define one queue q
   insert i into q
   while (q is not empty), do:
    if not tp[first element of q] and tvec[first element of q] is same as 0, then:
         for each element next in dp[first element of q], do:
             (decrease tvec[next] by 1)
             insert next into q
         tp[first element of q] := true
   delete first element from q
for initialize i := 1, when i <= n, update (increase i by 1), do:
   if tvec[i] is not equal to 0, then:
return false
return true

示例

让我们看看以下实现,以便更好地理解:

Open Compiler
#include <bits/stdc++.h> using namespace std; bool solve(int n, int m, vector<vector<int>> stacks){ vector<vector<int>> dp(n + 1); vector<int> tvec(n + 1); for(int i = 0; i < m; i++){ int k = stacks[i].size(); int p; for(int j = 0; j < k; j++){ if(j > 0){ dp[stacks[i][j]].push_back(p); tvec[p]++; } p = stacks[i][j]; } } vector<bool> tp(n + 1); for(int i = 1; i <= n; i++){ queue<int> q; q.push(i); while(!q.empty()){ if(!tp[q.front()] && tvec[q.front()] == 0){ for(auto next: dp[q.front()]){ tvec[next]--; q.push(next); } tp[q.front()]=true; } q.pop(); } } for(int i = 1; i <= n; i++){ if(tvec[i] != 0){ return false; } } return true; } int main() { int n = 3, m = 2; vector<vector<int>> stacks = {{2, 1, 3}, {2, 1, 3}}; cout<< solve(n, m, stacks); return 0; }

输入

3, 2, {{2, 1, 3}, {2, 1, 3}}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

1

更新于: 2022年3月2日

122 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告