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

假设有2n封信，每封信上都写有1到n之间的整数。有两封信上写有相同的数字。这些信被分成m堆，第i堆上有stack[i]封信。我们的任务是以以下方式清空所有堆：

• 我们必须选择任意两堆，并从两堆中移除顶部的信件。

• 我们所移除的信件必须具有相同的数字。

如果我们能以这种方式清空m堆，则打印true，否则返回false。

立即学习“C++免费学习笔记（深入）”；

LobeHub

LobeChat brings you the best user experience of ChatGPT, OLLaMA, Gemini, Claude

下载

因此，如果输入是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

示例

让我们看看以下实现，以便更好地理解 -

#include 
using namespace std;

bool solve(int n, int m, vector> stacks){
   vector> dp(n + 1);
   vector 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 tp(n + 1);
   for(int i = 1; i <= n; i++){
      queue 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> stacks = {{2, 1, 3}, {2, 1, 3}};
   cout<< solve(n, m, stacks);
   return 0;
}

输入

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

输出

1