c******0
发帖数: 260 | 1 这题是之前版上的面经，其实也是他家的codesprint 的一道题。
原题见：
http://get-that-job-at-google.blogspot.com/2013/02/rocketfuel-c
一个deque，但是只支持pushBack，pushFront，popBack， 没有popFront
给一个1-N的排列，问能否把1-N按照从小到大的顺序push到deque，pop的时机可以任选
，使得pop出的顺序刚好是给定的排列
比如： 给定 23145， 那么对12345对应的操作序列是pushBack，pushBack，popBack，
pushBack，popBack，popBack，pushBack，popBack，pushBack，popBack
要求如果可能，输出任意一个可能的操作序列，如果没有可能的操作序列，输出
impossible
下面是版上的一个大牛给出的答案，不过我太弱，完全无法理解大神的思路。。。求大
家提供点思路~~
//return operations, empty if impossible
vector getOps(string seq) {
int last = -1, pushCount = 0, N = (int)seq.length();
vector v(2*N, "");
for (int i = 0; i < N; ++i) {
int index = seq[i] - '0';
++last;
if (index > pushCount) {
if (pushCount + 1 <= index - 1) {
int head = i + 1, tail = N - 1;
for (int j = index - 1; j >= pushCount + 1; --j) {
int pos = last + j - pushCount - 1;
while (head < N && seq[head] - '0' > index)
++head;
while (tail >= 0 && seq[tail] - '0' > index)
--tail;
if (head == N || tail < 0) {
v.clear();
return v;
}
if (seq[head] - '0' == j) {
v[pos] = "pushBack";
++head;
}
else if (seq[tail] - '0' == j) {
v[pos] = "pushFront";
--tail;
}
else {
v.clear();
return v;
}
}
}
last += index - pushCount;
pushCount = index;
v[last - 1] = "pushBack";
}
v[last] = "POPBACK";
}
return v;
} | g*****g
发帖数: 212 | 2 给你举个例子：
25134 作为输入
这个结果应该是
push_back 1 -> push_back 2 -> pop_back 2 ->
push_back 5 -> push_front 3 -> push_front 4->
pop_back 1 ->pop_back 3 ->pop_back 4
假设你已经维护了一个堆栈到当前状态
front - > end: 1, 下个输入 3
如何决定push 前还是后？
在原来输入顺序里，3是在1的后面的，所以要保证pop 1在3前，只能push 3在front。
那么现在 堆栈状态： 3，1
基于这个原则：
1) 如果当前数字的原始顺序在back的前面 =〉push_back 保证先输出
2) 如果当前数字的原始顺序在front的后面 =〉push_front 保证后输出
如果与两个规则抵触即， 在back和front的中间，不可能。直接返回：
//////////
vector getOps(string seq) {
vector v;
int n = seq.length();
unordered_map pos;
for(int i=0; i
{
pos[seq[i] - '0'] = i;
}
deque stack;
for(int i=1, j=0; i<=n; i++)
{
if (stack.empty() || pos[stack.back()] > pos[i])
{
stack.push_back(i);
v.push_back("push_back");
}
else if (pos[stack.front()] < pos[i])
{
stack.push_front(i);
v.push_back("push_front");
}
else
{
v.clear();
break;
}
while(!stack.empty() && stack.back() == seq[j]- '0')
{
stack.pop_back();
v.push_back("pop_back");
j++;
}
}
return v;
} | f*******w
发帖数: 1243 | | r****c
发帖数: 2585 | | k*****o
发帖数: 43 | | f**********t
发帖数: 1001 | 6 // 一个deque，但是只支持pushBack，pushFront，popBack， 没有popFront
// 给一个1-N的排列，问能否把1-N按照从小到大的顺序push到deque，pop的时机可以
任选
// ，使得pop出的顺序刚好是给定的排列
// 比如： 给定 23145， 那么对12345对应的操作序列是pushBack，pushBack，
popBack，
// pushBack，popBack，popBack，pushBack，popBack，pushBack，popBack
// 要求如果可能，输出任意一个可能的操作序列，如果没有可能的操作序列，输出
// impossible
bool OpSequense(vector vi) {
deque dq;
size_t cur = 0;
vector indexes(vi.size() + 1);
for (size_t i = 0; i < vi.size(); ++i) {
indexes[vi[i]] = i;
}
for (int i = 1; i <= (int)vi.size(); ++i) {
if (i == vi[cur]) {
cout << "pushback ";
cout << "popback ";
++cur;
while (!dq.empty() && dq.back() == vi[cur]) {
dq.pop_back();
cout << "popback ";
++cur;
}
if (cur == vi.size()) {
cout << "done" << endl;
return true;
}
} else {
if (dq.empty()) {
dq.push_back(i);
cout << "pushback ";
} else {
bool front = indexes[*dq.begin()] < indexes[i];
for (auto it = dq.begin() + 1; it != dq.end(); ++it) {
if ((indexes[*it] < indexes[i]) ^ front) {
cout << "fail" << endl;
return false;
}
}
if (front) {
dq.push_front(i);
cout << "pushfront ";
} else {
dq.push_back(i);
cout << "pushback ";
}
}
}
}
return true;
}
void OpSequenseTest() {
OpSequense({2,3,1,4,5});
OpSequense({1,2,3,4,5});
OpSequense({5,4,3,2,1});
OpSequense({5,1,4,2,3});
} | z******t
发帖数: 25 | 7 谢谢分享你的思路，非常简洁漂亮。
只不过25134的解应该是：
push_back 1 -> push_back 2 -> pop_back 2 ->
push_front 3 -> push_front 4 -> push_back 5 ->
pop_back 5 -> pop_back 1 -> pop_back 3 -> pop_back 4
【在 g*****g 的大作中提到】
: 给你举个例子：
: 25134 作为输入
: 这个结果应该是
: push_back 1 -> push_back 2 -> pop_back 2 ->
: push_back 5 -> push_front 3 -> push_front 4->
: pop_back 1 ->pop_back 3 ->pop_back 4
: 假设你已经维护了一个堆栈到当前状态
: front - > end: 1, 下个输入 3
: 如何决定push 前还是后？
: 在原来输入顺序里，3是在1的后面的，所以要保证pop 1在3前，只能push 3在front。
|
|
