栈的压入、弹出序列
思路一：纯数学处理
对于出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。
比如入栈顺序为：1 2 3 4。
出栈顺序：4 3 2 1是合法的，对于数字 4 而言，比它小的后面的数字是：3 2 1，且这个顺序是递减顺序。同样地，对于数字 3 而言，比它小的后面的数字是： 2 1，且这个顺序是递减的。....
出栈顺序：1 2 3 4 也是合法的，对于数字 1 而言，它后面没有比它更小的数字。同样地，对于数字 2 而言，它后面也没有比它更小的数字。
出栈顺序：3 2 4 1 也是合法的，对于数字 3 而言，它后面比 3 小的数字有： 2 1，这个顺序是递减的；对于数字 2 而言，它后面的比它 小的数字只有 1，也算符合递减顺序；对于数字 4 而言，它后面的比它小的数字也只有1，因此也符合递减顺序。
出栈顺序：3 1 4 2 是不合法的，因为对于数字 3 而言，在3后面的比3小的数字有：1 2，这个顺序是一个递增的顺序(1-->2)。
因此，当给定一个序列时，通过这个规律 可以轻松地判断 哪些序列是合法的，哪些序列是非法的。
class Solution {
public:
bool IsPopOrder(vector<int> pushV, vector<int> popV) {
for (int i = 0; i < popV.size(); i++) {
int temp = 10e9;
for (int j = i + 1; j < popV.size(); j++) {
if (popV[j] < popV[i]) {
if (temp < popV[j]) {
return false;
}
temp = popV[j];
}
}
}
return true;
}
};
思路二： 软工方向
class Solution1 {
public:
bool IsPopOrder(vector<int> pushV, vector<int> popV) {
vector<int> temp;//临时数组
for (int i = 0,j=0; i < pushV.size(); i++) {
temp.push_back(pushV[i]);
while (j < popV.size() && temp.back() == popV[j]) {
temp.pop_back();
j++;
}
}
return temp.empty();
}
};
出栈序列
给定一个入栈顺序：1 2 3 .... n，一共有多少种合法的出栈顺序？参考：百度百科卡特兰数
答案是 卡特兰数。即一共有：h(n)=c(2n,n)/(n+1) 种合法的出栈顺序，那么输出所有的情况该怎么办呢，其实上边的问题也可以用出栈序列来处理，找出所有的出栈序列，和给定的出栈序列对比即可。
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
void printAllOutStackSeq(queue<int> inQueue, int n, stack<int> st, queue<int> out)
{
if (n <= 0 || (inQueue.empty() && st.empty() && out.empty())) return;
if (out.size() == n)
{
while (!out.empty()){
cout << out.front() << ' ';
out.pop();
}
cout << endl;
return;
}
stack<int> stCopy = st; // 备份一下，否则储转
queue<int> outCopy = out;
if (!st.empty()) // 出栈，将元素出栈，push到结果队列中
{
out.push(st.top());
st.pop();
printAllOutStackSeq(inQueue, n, st, out);
}
if (!inQueue.empty()) // 入栈，将输入队列出队，进行入栈
{
stCopy.push(inQueue.front());
inQueue.pop();
printAllOutStackSeq(inQueue, n, stCopy, outCopy);
}
return;
}
int main()
{
int a[] = { 1, 2, 3, 4 };
queue<int> inQueue ;
for (int i = 0; i < 4; i++)
inQueue.push(a[i]);
stack<int> st;
queue<int> out;
printAllOutStackSeq(inQueue, 4, st, out);
return 0;
}
12个高矮不同的人
12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？
问题分析:
我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排.
用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案.
比如
000000111111就对应着
第一排:0 1 2 3 4 5
第二排:6 7 8 9 10 11
010101010101就对应着
第一排:0 2 4 6 8 10
第二排:1 3 5 7 9 11
问题转换为,这样的满足条件的01序列有多少个.
我们来观察，什么样的序列符合要求。
对于某一个1的出现，观察在这个1之前的这些数（比当前的1所对应的人个子小的人），所对应的这些人：要么是在当前这个1的人同一排左边（即为1），要么是在第一排（即为0）。
而且，肯定要有一个0的(在当前这个1的人的前正方)。
那么，对于当前这个1之前的数，我们的要求就是：0的个数大于1的个数。
如果把0看成入栈操作，1看成出栈操作，就是说给定12个元素，合法的入栈出栈序列有多少个。c(2n, n)/(n+1)。
代码为了方便展示，设置为6个人，逻辑是一样的。
#include <iostream>
using namespace std;
int bit_cnt(int n)
{
int result = 0;
for (; n; n &= n - 1, ++result);
return result;
}
int main(void)
{
int F[3], B[3];//前排、后排
int i, j, k, state, ok, ans = 0;
for (state = 0; state < (1 << 6); ++state)
{
if (bit_cnt(state) == 3)//有3个1
{
i = j = 0;
for (int k = 0; k < 6; ++k)
{
if (state&(1 << k))//第K位是不是1
F[i++] = k;
else
B[j++] = k;
}
ok = 1;
for (k = 0; k < 3; ++k)
{
if (B[k] < F[k])//后排比前排小，跳出
{
ok = 0;
break;
}
}
if (ok == 1) {
cout << state << endl;
cout << F[0] << " " << F[1] << " " << F[2] << " " << endl;
cout << B[0] << " " << B[1] << " " << B[2] << " " << endl;
cout << endl;
}
ans += ok;
}
}
cout << ans << endl;
return 0;
}
网友评论