資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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示例
讓我們看看以下實現，以便更好地理解：
#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}}輸出
1
更新於: 2022年3月2日
122 次瀏覽
廣告