只有KID手动牙刷是10反5么？应该怎么买？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PennySaver - 省钱一族

只有KID手动牙刷是10反5么？应该怎么买？

只有KID手动牙刷是10反5么？应该怎么买？# PennySaver - 省钱一族

p*n2010-09-27 07:09

1 楼

一定要用bubble mail吗？first class寄行不行？要不要买保险？

c*02010-09-27 07:09

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;
}

z*82010-09-27 07:09

3 楼

看广告上怎么只有画那种KID的和漱口水什么的是10反5，其他成人牙刷那些事包括的呀
。哪位大牛知道一下怎么买吧。唉，电动牙刷不好用，手动牙刷又用完了。
谢谢

t*12010-09-27 07:09

4 楼

对用bubble mail比较好

g*g2010-09-27 07:09

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;
}

j*u2010-09-27 07:09

6 楼

手动的牙刷用完了？
这个不用急，手动的，cvs和wags经常有免费，或者倒赚的
呵呵，下次去屯多点
你看看sd，上面有具体的coupon

【在 z*****8 的大作中提到】

: 看广告上怎么只有画那种KID的和漱口水什么的是10反5，其他成人牙刷那些事包括的呀
: 。哪位大牛知道一下怎么买吧。唉，电动牙刷不好用，手动牙刷又用完了。
: 谢谢

f*w2010-09-27 07:09

7 楼

mark

z*82010-09-27 07:09

8 楼

呵呵，我已经买过昨天1送1的coupon了，但是就是不知道哪些是包括在里面的
过去倒是屯了好多，但是2年多的新牙刷感觉也不能用了吧

【在 j******u 的大作中提到】

: 手动的牙刷用完了？
: 这个不用急，手动的，cvs和wags经常有免费，或者倒赚的
: 呵呵，下次去屯多点
: 你看看sd，上面有具体的coupon

r*c2010-09-27 07:09

9 楼

5 3 4 2 1怎么搞

j*u2010-09-27 07:09

10 楼

应该没事吧
牙刷不会有什么保质期的吧
呵呵
你得胖子拿到手，看看小字，就行了

【在 z*****8 的大作中提到】

: 呵呵，我已经买过昨天1送1的coupon了，但是就是不知道哪些是包括在里面的
: 过去倒是屯了好多，但是2年多的新牙刷感觉也不能用了吧

k*o2010-09-27 07:09

11 楼

mark

f*t2010-09-27 07:09

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});
}

z*t2010-09-27 07:09

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。