数据结构的一道题求大神解救

时间:2022-08-06 10:27:36
Description
小明很喜欢玩射击游戏。他刚考完了数据结构期末考试,感觉不错,于是又来到了射击娱乐场放松一下。和上次一样,先从老板那租了一把步枪和装有N发子弹的弹夹。这里,再把规则说一遍。在射击的过程中,小明每次都有两种选择:从弹夹中取出一颗子弹上膛,或者打一发子弹出去。注意:所有的子弹都从枪口上膛。小明感觉这有点像《数据结构》课程中的“栈”的特点。因此在打完了这N发子弹之后,他想验证一下这些子弹打出来的顺序是不是真的满足“栈”的特性。假设N颗子弹的编号为1,2,…,N。子弹从弹夹中取出的顺序也是从1到N,这里N = 10。给定一个子弹被打出的顺序,你可以帮小明验证它满不满足“栈”的打出顺序吗?
Input
可能有多个测试输入,第一行给出总共的测试输入的个数。
每个测试输入只有一行:用空格隔开的十个数,表示子弹打出的编号顺序。
Output
对每个测试输入,输出只有一行:
“Yes”,如果打出顺序满足“栈”的特点;
“No”,如果打出顺序不满足“栈”的特点。
Sample Input
3
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
3 1 2 4 5 6 7 8 9 10
Sample Output
Yes
Yes
No

这是我的代码,为什么WA啊?求救啊

#include <iostream>
#include <stack>
using namespace std;

int main() {
int a[10], n = 0, i = 0, j = 0;
bool k = true;
stack<int> s[10];
cin >> n;
while (n--) {
for (i = 0; i < 10; i++) {
cin >> a[i];
}
for (i = 0; i < 10; i++) {
if (i > 0) {
if (a[i] - a[i - 1]) {
j++;
}
}
s[j].push(a[i]);
}
j = 0;
for (i = 0; i < 10; i++) {
if (s[j].empty()) {
j++;
}
if (i + 1 != s[j].top()) {
k = false;
}
s[j].pop();
}
if (k == true) {
cout << "Yes\n";
} else {
cout << "No\n";
}
j = 0, k = true;
}
return 0;
}

4 个解决方案

#1


和我想象中的解法完全不同。你得解释为什么你觉得这个代码是对的。

#2


提出错了。输入必须是1到10,否则编号有什么用?

#3


一道经典面试题哦:如果“给定的出栈序列”是一个可能的序列,则必需在某种入栈方式下(要保证入栈的先后顺序是1~N),出栈序列的下一个元素是栈顶

bool isPossible(int popSequence[], int N)
{
    int n = 1, nextToPopOut;
    stack<int> st;
    
    for(nextToPopOut = 0; nextToPopOut < N; ++nextToPopOut){
        while(st.empty() || st.top() != popSequence[nextToPopOut]){
            if(n > N) return false;//1~N已经全部入栈过一次了,但是仍不能满足出栈顺序
            st.push(n++);
        }
        //能运行到这里必然有st.top() = popSequence[nextToPopOut]了
        st.pop();
    }
    return true;
}

#4


做程序员的小明果然比上学的小明聪明

#1


和我想象中的解法完全不同。你得解释为什么你觉得这个代码是对的。

#2


提出错了。输入必须是1到10,否则编号有什么用?

#3


一道经典面试题哦:如果“给定的出栈序列”是一个可能的序列,则必需在某种入栈方式下(要保证入栈的先后顺序是1~N),出栈序列的下一个元素是栈顶

bool isPossible(int popSequence[], int N)
{
    int n = 1, nextToPopOut;
    stack<int> st;
    
    for(nextToPopOut = 0; nextToPopOut < N; ++nextToPopOut){
        while(st.empty() || st.top() != popSequence[nextToPopOut]){
            if(n > N) return false;//1~N已经全部入栈过一次了,但是仍不能满足出栈顺序
            st.push(n++);
        }
        //能运行到这里必然有st.top() = popSequence[nextToPopOut]了
        st.pop();
    }
    return true;
}

#4


做程序员的小明果然比上学的小明聪明