c*0
2 楼
这题是之前版上的面经，其实也是他家的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;
}
原题见：
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
int last = -1, pushCount = 0, N = (int)seq.length();
vector
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;
}
z*8
3 楼
看广告上怎么只有画那种KID的和漱口水什么的是10反5，其他成人牙刷那些事包括的呀
。哪位大牛知道一下怎么买吧。唉，电动牙刷不好用，手动牙刷又用完了。
谢谢
。哪位大牛知道一下怎么买吧。唉，电动牙刷不好用，手动牙刷又用完了。
谢谢
t*1
4 楼
对 用bubble mail比较好
g*g
5 楼
给你举个例子：
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;
}
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
vector
int n = seq.length();
unordered_map
for(int i=0; i
pos[seq[i] - '0'] = i;
}
deque
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;
}
j*u
6 楼
手动的牙刷用完了？
这个不用急，手动的，cvs和wags经常有免费，或者倒赚的
呵呵，下次去屯多点
你看看sd，上面有具体的coupon
【在 z*****8 的大作中提到】
: 看广告上怎么只有画那种KID的和漱口水什么的是10反5，其他成人牙刷那些事包括的呀
: 。哪位大牛知道一下怎么买吧。唉，电动牙刷不好用，手动牙刷又用完了。
: 谢谢
这个不用急，手动的，cvs和wags经常有免费，或者倒赚的
呵呵，下次去屯多点
你看看sd，上面有具体的coupon
【在 z*****8 的大作中提到】
: 看广告上怎么只有画那种KID的和漱口水什么的是10反5，其他成人牙刷那些事包括的呀
: 。哪位大牛知道一下怎么买吧。唉，电动牙刷不好用，手动牙刷又用完了。
: 谢谢
f*w
7 楼
mark
z*8
8 楼
呵呵，我已经买过昨天1送1的coupon了，但是就是不知道哪些是包括在里面的
过去倒是屯了好多，但是2年多的新牙刷感觉也不能用了吧
【在 j******u 的大作中提到】
: 手动的牙刷用完了？
: 这个不用急，手动的，cvs和wags经常有免费，或者倒赚的
: 呵呵，下次去屯多点
: 你看看sd，上面有具体的coupon
过去倒是屯了好多，但是2年多的新牙刷感觉也不能用了吧
【在 j******u 的大作中提到】
: 手动的牙刷用完了？
: 这个不用急，手动的，cvs和wags经常有免费，或者倒赚的
: 呵呵，下次去屯多点
: 你看看sd，上面有具体的coupon
r*c
9 楼
5 3 4 2 1怎么搞
j*u
10 楼
应该没事吧
牙刷不会有什么保质期的吧
呵呵
你得胖子拿到手，看看小字，就行了
【在 z*****8 的大作中提到】
: 呵呵，我已经买过昨天1送1的coupon了，但是就是不知道哪些是包括在里面的
: 过去倒是屯了好多，但是2年多的新牙刷感觉也不能用了吧
牙刷不会有什么保质期的吧
呵呵
你得胖子拿到手，看看小字，就行了
【在 z*****8 的大作中提到】
: 呵呵，我已经买过昨天1送1的coupon了，但是就是不知道哪些是包括在里面的
: 过去倒是屯了好多，但是2年多的新牙刷感觉也不能用了吧
k*o
11 楼
mark
f*t
12 楼
// 一个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});
}
// 给一个1-N的排列，问能否把1-N按照从小到大的顺序push到deque，pop的时机可以
任选
// ，使得pop出的顺序刚好是给定的排列
// 比如： 给定 23145， 那么对12345对应的操作序列是pushBack，pushBack，
popBack，
// pushBack，popBack，popBack，pushBack，popBack，pushBack，popBack
// 要求如果可能，输出任意一个可能的操作序列，如果没有可能的操作序列，输出
// impossible
bool OpSequense(vector
deque
size_t cur = 0;
vector
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
13 楼
谢谢分享你的思路，非常简洁漂亮。
只不过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。
只不过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。
相关阅读
kohls的家具性价比怎么样？一堆kohls cash 不知道买什么好kohls 今天有啥好买？ 就想把15 刀 kohls cash 花了。要买gps的可以买了UA 100,000 points 10 万里程点 (转载)没赶上newegg 50% skype的大家都在macys买啥了？买surface pro 2或3最近有好deal嘛？网上买的TARGET GC大家都收到了没？一点音讯都没有啊！～～～kohls cash必须一次用完吗ebay MK tote会假吗？请问怎么查chase 的UA 里程卡消费累计急问：如何使用5OFF25 PAYPAL在TOYSRUS的OFFER？Safeway乐芝饼干和cheese丢Free FreedomPop USB nationwide modemkohls的20%off和kohls cash不能同时用吗刚和citi客服聊天，说safew和qfc都属于这个季度的5%Cashback的department stores各位大侠请教问一下kmart/sears的10 off 10胖子Iphone 6 + apple store 还有promotion吗？Cyber Monday错过的好dealrite aid 买29.97出白条吗？