Re: 告诉你美国高等教育为什么不行。 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

Re: 告诉你美国高等教育为什么不行。 (转载)

Re: 告诉你美国高等教育为什么不行。 (转载)# Joke - 肚皮舞运动

y*e2014-08-17 07:08

1 楼

马上onsite了，看到新题好抓狂。。。。
引用帖子：
第二道题：
面试官说是道新题 finding ali baba
就是ali baba是个怪兽，他可能在[0，1, ..., numCaves-1]出现，他每隔一天就要换
一个地方，但他每次只能移左右一格。
然后给你一个strategy[]数组，数组里面是猜测每天ali baba的位置。如果里面有一个
猜中了，这个strategy就是正确的。
问题就是让你写一个判断函数 alibaba(int numCaves, int[] strategy)来判别这个
strategy数组是不是稳赢的策略。写完后问时间复杂度，然后问了下大概怎么样可以优
化～～～
我感觉这题是DP，但不知道转移方程怎么写，不知走过路过的大神能给点idea咩？

H*g2014-08-17 07:08

2 楼

【以下文字转载自 Military 讨论区】
发信人: ossacomu (lee), 信区: Military
标题: Re: 告诉你美国高等教育为什么不行。
发信站: BBS 未名空间站 (Sat Jul 26 01:13:22 2014, 美东)
本文采用夸张，想象，顺序，插序，倒序等艺术表象手法，借景抒情，托物言志；实乃
不可多得的一片议论文。

s*o2014-08-17 07:08

3 楼

抛砖引玉. 这题其实不算新题
一上来直接code，找小偷问题，有n个房间，其中一个房间有小偷。早上我们
可以打开一个房间的门看小偷在不在里面，晚上小偷会向左边或者右边的房间走。
现在给你一个开门的sequence，你输出这个sequence能不能保证找到小偷。
比如：如果只有三个房间那么如果打开房间的sequence是{1，1}那么一定会找到小偷。
因为如果小偷在中间那么第一天就会被找到，如果小偷在两边那么第二天一定回来
到中间也会被找到。房间数为n，sequence长度为k
跟着我开始brute force假设小偷在某个房间然后dfs所有路径，大概是O(n*n^k)。
考官说好，如果考虑cut branch呢？跟着我就说可以拿一个n*k的matrix跟着根据
sequence来cut branch，reduce到O(n*n*k)。他说有没有可能同时从所有房间
开始呢？我说可以跟着直接在那个n*kmatrix上做一个类似dp的东西。跟着reduce 到
O(n*k)。他说有没有可能把space reduce呢？我说可以我只要O(n)的space
跟着他就让我再写一个叫nextRow的function来实现O(n)space。我觉得这题我
基本是答得非常漂亮的而且思路很清晰，考官也很开心

H*g2014-08-17 07:08

4 楼

原文是这个：
=
发信人: qiaoak (房东老乔), 信区: Military
标题: 告诉你美国高等教育为什么不行。
发信站: BBS 未名空间站 (Fri Jul 25 02:08:14 2014, 美东)
美国早期的白人确实意识到一个问题,刀叉吃饭的文明人和满脑子穷酸的泥腿子都能把
数学和历史达到很高分数，但社会穷人比例占多数，这样就会导致社会庸俗化和平民暴
政。
所以一些美国权贵家庭在新英格兰地区创建了很多顶尖文理学院。这种意识和英国牛津
大学学院分级制很像，穷人很难进到欧洲贵族，英国皇室，英国权贵子女一级学院和教
育社交圈子。这样就很难形成大面积的阶级移动和穷人暴证，这也是为什么美国高等教
育一直被欧洲鄙视的根本原因。
就像美国这个国家一样，墨黑人口和墨黑总统会一步步地形成新的拉美文化和低等国家。

n*n2014-08-17 07:08

5 楼

没看懂你的答案。

【在 s********o 的大作中提到】

: 抛砖引玉. 这题其实不算新题
: 一上来直接code，找小偷问题，有n个房间，其中一个房间有小偷。早上我们
: 可以打开一个房间的门看小偷在不在里面，晚上小偷会向左边或者右边的房间走。
: 现在给你一个开门的sequence，你输出这个sequence能不能保证找到小偷。
: 比如：如果只有三个房间那么如果打开房间的sequence是{1，1}那么一定会找到小偷。
: 因为如果小偷在中间那么第一天就会被找到，如果小偷在两边那么第二天一定回来
: 到中间也会被找到。房间数为n，sequence长度为k
: 跟着我开始brute force假设小偷在某个房间然后dfs所有路径，大概是O(n*n^k)。
: 考官说好，如果考虑cut branch呢？跟着我就说可以拿一个n*k的matrix跟着根据
: sequence来cut branch，reduce到O(n*n*k)。他说有没有可能同时从所有房间

c*n2014-08-17 07:08

6 楼

不是很明白题目，但是你怎么确定“稳赢” 呢？
我们可以给出一个稳赢的办法，就是从右往坐一步步推，缩小包围圈，
不管alibaba 怎么移动，肯定要跟包围圈碰到，这样就“猜”到了。
但是，如果对方给一个任意的prediction sequence, 你又不知道alibaba 怎么move,
你怎么知道是否稳赢呢？

【在 y*****e 的大作中提到】

: 马上onsite了，看到新题好抓狂。。。。
: 引用帖子：
: 第二道题：
: 面试官说是道新题 finding ali baba
: 就是ali baba是个怪兽，他可能在[0，1, ..., numCaves-1]出现，他每隔一天就要换
: 一个地方，但他每次只能移左右一格。
: 然后给你一个strategy[]数组，数组里面是猜测每天ali baba的位置。如果里面有一个
: 猜中了，这个strategy就是正确的。
: 问题就是让你写一个判断函数 alibaba(int numCaves, int[] strategy)来判别这个
: strategy数组是不是稳赢的策略。写完后问时间复杂度，然后问了下大概怎么样可以优

d*v2014-08-17 07:08

7 楼

没看懂，占个座，等大牛解答。

b*n2014-08-17 07:08

8 楼

继续抛砖吧，二楼应该正解。
就是判断是不是有某一天，怪兽在所有位置出现的可能都已经cover到了。
dp[n][k] 表示第n天怪兽出现在index k的情况是不是被都被cover到了
dp[n][k] == true if dp[n - 1][k - 1] == true || dp[n - 1][k + 1] == true
遍历一遍strategy即可，因为dp[n][k]只跟前一天的状态有关，所以用一个size为n的
array就够了。

m*32014-08-17 07:08

9 楼

请问求出dp[n][k]以后，遍历一遍strategy是不是这个意思
遍历strategy array , 对于第i个元素，检查dp[i][strategy[i]]是否为true,如果是
，这个strategy是稳赢的。
另外能不能说说为什么因为dp[n][k]只跟前一天的状态有关，所以用一个size为n的
array就够了?我怎么感觉是一个size为k的array呢？

m*22014-08-17 07:08

10 楼

validate的时候，假设小偷在某个房间，然后dfs所有路径，这个不应该是O(n*2^k)么
？因为固定一个点，然后之后每天怪兽只能move两个方向，那么k天就只有2^k个组合。

....

【在 s********o 的大作中提到】

i*o2014-08-17 07:08

11 楼

If you create a NxN matrix (each column is for one day), mark the cells
with the prediction sequence. It becomes doing a back traversal from the
cells in last column except one corresponding to the last element in the
sequence. If traversal is successful reaching day zero without hitting any
marked cell. That is not a good strategy. O(n^2)
Does it miss anything?
Update: if using BFS, space will be O(n). second floor is smart.

y*e2014-08-17 07:08

12 楼

不太明白。。。。dp[n][k] true代表什么？代表这天，怪兽不可能出现在kth
position?
dp[n - 1][k - 1] == true || dp[n - 1][k + 1] == true
这两个相邻的状态是不是应该用and啊？还是or?

【在 b*****n 的大作中提到】

: 继续抛砖吧，二楼应该正解。
: 就是判断是不是有某一天，怪兽在所有位置出现的可能都已经cover到了。
: dp[n][k] 表示第n天怪兽出现在index k的情况是不是被都被cover到了
: dp[n][k] == true if dp[n - 1][k - 1] == true || dp[n - 1][k + 1] == true
: 遍历一遍strategy即可，因为dp[n][k]只跟前一天的状态有关，所以用一个size为n的
: array就够了。

d*g2014-08-17 07:08

13 楼

能不能来个人发个网上这道题的详细解法啊，光这样说谁能明白啊

s*x2014-08-17 07:08

14 楼

矩阵是 NxK 吧？因为N个房间，K天。
我尝试解释下看看是否真的理解了你的思路。在N*K array中间把prediction sequence
都标记下。
从最后一天往前看，出发，如果有一个结果能够从array[k-1][n] (0 <=n <=N-1)一直
回溯到array[0][l]
(0 <=l <=N-1),那么就不算是个好的strategy。
出发点有N个，每一次回溯都是2个选择（向左或者向右），那么不是N*2^K吗？
所以我还是没看懂，请赐教，谢谢！

any

【在 i*****o 的大作中提到】

: If you create a NxN matrix (each column is for one day), mark the cells
: with the prediction sequence. It becomes doing a back traversal from the
: cells in last column except one corresponding to the last element in the
: sequence. If traversal is successful reaching day zero without hitting any
: marked cell. That is not a good strategy. O(n^2)
: Does it miss anything?
: Update: if using BFS, space will be O(n). second floor is smart.

k*e2014-08-17 07:08

15 楼

占个座

i*o2014-08-17 07:08

16 楼

There are N*2^K trails, but there are only N*K cells accommodated. It doesn
't have to care how it gets here (trails) than whether it hits the
prediction (cell). so traverse the matrix will be sufficient.

l*c2014-08-17 07:08

17 楼

二楼的是正解啊，DFS＋cut branch和BFS都可以，但是BFS可以省空间。
不知道bottom up 的DP转移方程怎么写，要注意奇偶性？

m*22014-08-17 07:08

18 楼

nextDay[k][n] : 第k天，第n个房间小偷是否可以survive
nextDay[i][j] = (nextDay[i-1][j-1] or nextDay[i-1][j+1]) && strategy[i] != j
// O(n*k) time, O(n) space
boolean canCatchTheft(int n, int strategy[]) {
int k = strategy.length;
// nextDay[i] means theft can survive in spot i or not on this day
boolean nextDay[] = new boolean[n];
boolean canSurvive, pre, a, b;
// init the first day
Arrays.fill(nextDay, true); nextDay[strategy[0]] = false;
for (int i = 1; i < k; ++i) {
canSurvive = false; pre = false;
for (int j = 0; j < n; ++j) {
a = j == 0 ? false : pre;
b = j == n - 1 ? false : nextDay[j + 1];
pre = nextDay[j]; // store current day for the next round
nextDay[j] = ((a || b) && strategy[i] != j) ? true : false;
if(nextDay[j] == true) canSurvive = true;
}
if (!canSurvive) return true;
}
return false;
}

s*x2014-08-17 07:08

19 楼

很赞！
谢谢。

j

【在 m******2 的大作中提到】

: nextDay[k][n] : 第k天，第n个房间小偷是否可以survive
: nextDay[i][j] = (nextDay[i-1][j-1] or nextDay[i-1][j+1]) && strategy[i] != j
: // O(n*k) time, O(n) space
: boolean canCatchTheft(int n, int strategy[]) {
: int k = strategy.length;
: // nextDay[i] means theft can survive in spot i or not on this day
: boolean nextDay[] = new boolean[n];
: boolean canSurvive, pre, a, b;
: // init the first day
: Arrays.fill(nextDay, true); nextDay[strategy[0]] = false;

x*82014-08-17 07:08

20 楼

根据mitkook2大神的代码改了一下，思路是一致的，大家参考一下
// O(n*k) time, O(n) space
boolean alibaba(int numCaves, int[] strategy) {
// survival[i] means theft can be in spot i or not on this day
boolean survival[] = new boolean[n + 2];

// init the first day
// 在头尾加一个房间，且小偷不可能出现在这两个房间（为了处理下面j - 1
和j + 1越界的情况）
Arrays.fill(survival, true);
survival[0] = false;
survival[n + 1] = false;
survival[strategy[0]] = false;

for (int i = 1; i < strategy.length; ++i) {
for (int j = 1; j < n + 1; ++j) {
survival[j] = ((survival[j - 1] || survival[j + 1]) &&
strategy[i] != j) ? true : false;
}
}

// 最后survival数组保存小偷可能出现的房间，如果都为false表示经过这个
strategy寻找后小偷不可能在任何一个房间
for(int i = 1; i < n + 1; ++i){
if(survival[i]){
return false;
}
}

return true;
}

j

【在 m******2 的大作中提到】

l*82014-08-17 07:08

21 楼

来个气死人的程序 :-)
boolean canCatchTheft(int n, int strategy[]) {
if (n <= 1 && strategy.length > 0) return true;

if (n >=4) return false;
for (int i=0; i+1 < strategy.length; i++)
if (strategy[i] == strategy[i+1] && (strategy[i] == 1 || strategy[i] =
= n - 2))
return true;
return false;
}

s*x2014-08-17 07:08

22 楼

这个能解释下么？

=

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

: 来个气死人的程序 :-)
: boolean canCatchTheft(int n, int strategy[]) {
: if (n <= 1 && strategy.length > 0) return true;
:
: if (n >=4) return false;
: for (int i=0; i+1 < strategy.length; i++)
: if (strategy[i] == strategy[i+1] && (strategy[i] == 1 || strategy[i] =
: = n - 2))
: return true;
: return false;

l*82014-08-17 07:08

23 楼

我觉得当n>=4的时候，没有稳赢策略的。不知谁能给个例子？

【在 s******x 的大作中提到】

: 这个能解释下么？
:
: =

b*m2014-08-17 07:08

24 楼

n = 4
strategy=[1,1,2,2,1]
it should be true

=

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

l*82014-08-17 07:08

25 楼

谢谢，我错了....

【在 b**m 的大作中提到】

: n = 4
: strategy=[1,1,2,2,1]
: it should be true
:
: =

l*c2014-08-17 07:08

26 楼

这个DFS对吗？
bool FindThiefDFS(const vector& S, int idx, int n, int pos,
unordered_map, bool, HashPair>& cache) {
if (idx >= S.size()) return false;
if (S[idx] == pos) return true;
if (cache.find({idx, pos}) != cache.end()) return false;
if (pos >= 1 && FindThiefDFS(S, idx + 1, n, pos - 1, cache))
return true;
if (pos <= n - 2 && FindThiefDFS(S, idx + 1, n, pos + 1, cache))
return true;
cache[{idx, pos}] = false;
return false;
}
bool FindThief(const vector& S, int n) {
unordered_map, bool, HashPair> cache;
for (int i = 0; i < n; i++) { // intial position of thief
if (!FindThiefDFS(S, 0, n, i, cache)) return false;
}
return true;
}

b*p2014-08-17 07:08

27 楼

n = 2
[1,1] or [2,2]
n = 3
[2,2]
n = 4
[ 3, 2, 2, 3]
理由如下（*代表被猜对的）
day 1 2 3....
pos 1 2*
pos 2 1 2*
pos 2 3 2*
pos 2 3 4 3*
pos 3*
pos 4 3 2*
pos 4 3 4 3*

【在 b**m 的大作中提到】

: n = 4
: strategy=[1,1,2,2,1]
: it should be true
:
: =

c*p2014-08-17 07:08

28 楼

倒是能找到一个稳赢的策略……

【在 y*****e 的大作中提到】

b*p2014-08-17 07:08

29 楼

n=5比较复杂
目前找到一个解
[4,4,2,2,3,4,4,3,2]
[4]干掉4
[4,4]干掉5
[4,4,2,2,3,4]干掉1和3
[4,4,2,2,3,4,4,3,2]干掉2

【在 b*****p 的大作中提到】

: n = 2
: [1,1] or [2,2]
: n = 3
: [2,2]
: n = 4
: [ 3, 2, 2, 3]
: 理由如下（*代表被猜对的）
: day 1 2 3....
: pos 1 2*
: pos 2 1 2*

r*72014-08-17 07:08

30 楼

如果复杂度没有要求，应该可以用和你L家电面的题一样的解法吧。。。
可能有简单点的解法

【在 y*****e 的大作中提到】

j*72014-08-17 07:08

31 楼

boolean alibaba(int numCaves, int[] strategy) {
boolean[] DP = new boolean[numCaves];
boolean canWin = true;
for (int k = strategy.length - 1; k >= 0; k--) {
boolean[] temp = new boolean[numCaves];
for (int i = 0; i < numCaves; i++) {
temp[i] = (strategy[k] == i) ? true : false;
if (k + 1 < strategy.length) {
if (i - 1 >= 0) {
temp[i] = temp[i] || DP[i - 1];
}
if (i + 1 < numCaves) {
temp[i] = temp[i] || DP[i + 1];
}
}
}
DP = temp;
}
for (int i = 0; i < numCaves; i++) {
canWin = canWin && DP[i];
}
return canWin;
}

D*d2014-08-17 07:08

32 楼

从后往前一步一步推，最后没选择了是不是就是抓住了？
假设四个房间，8天
策略12344321
可能的位置
8-234
7-134
6-24
5-13
4-2
3-1
2-
没得选了，挂了

【在 y*****e 的大作中提到】

z*o2014-08-17 07:08

33 楼

cave=4(0-3), strategy[1,1,2,2]
有问题

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

: boolean alibaba(int numCaves, int[] strategy) {
: boolean[] DP = new boolean[numCaves];
: boolean canWin = true;
: for (int k = strategy.length - 1; k >= 0; k--) {
: boolean[] temp = new boolean[numCaves];
: for (int i = 0; i < numCaves; i++) {
: temp[i] = (strategy[k] == i) ? true : false;
: if (k + 1 < strategy.length) {
: if (i - 1 >= 0) {
: temp[i] = temp[i] || DP[i - 1];

c*n2014-08-17 07:08

34 楼

第一次接触这种题目，觉得很有意思。
本质是 2^i 次的分解, 即将 n = n1 + n2 s.t. |n1 - n2| == 0, or 1.
e.g 4 = 2 + 2, 5 = 3 + 2, 6 = 3 + 3, 7 = 4 + 3 = (2 + 2) + 3.
前面已经给出 n = 2, 3 时的解法。以此作用基础，按上述分解即可推出任意 n > 3
的解法。感觉这样的解法应该可以以数学归纳法来推证为最优的。有兴趣的朋友可以证
明一下。
以 n = 5 为例来说明我的解法。五个位置记作 {A, B, C, D, E}. n = 5 = 3 + 2 即
是按 %2 = 0 or 1 分成两个子集 {A,C,E} and {B, D}. 可以分别检验子集 (注意子集
的检验次序是先小后大)。
对于子集 {B, D}，是 n = 2 的情况，按照 n = 2 集合为 {A',B'}时的解法是 (B',B'
). 第一步 Map to "n = 5" 的位置是 "D". 若没有找到，到了第二步要注意了，原来
在 {B, D} 的，已经转移到 {A, C, E}, 但是当第一步 "D" 没有找到, 第二步到 "E"
没有可能。所以只有 {A,C} 两种情况。那么 n = 2 第二步到 "B'" 可以 map 到 "n
= 5" 的 C. 若没有找到，到第三步 {A} 只转移到 {B}，所以再到 "B" 找即可。总的
来说，对于子集 {B, D}, 检验的次序是 (D, C, B). 如果没有找到，则可以排除子集
{B, D}.
当排除完子集 {B, D} 后，k = 3. 则按照奇偶性，子集 {A, C, E} 只可以出现在位置
{B,D} 上。实际上已经变成了一个 "n = 2" 的问题，同理可解。
主要计算量在于 n=n1+n2 的时候如何 map 位置变量。

j*72014-08-17 07:08

35 楼

boolean alibaba(int numCaves, int[] strategy) {
boolean[] DP = new boolean[numCaves];
boolean canWin = true;
for (int k = strategy.length - 1; k >= 0; k--) {
boolean[] temp = new boolean[numCaves];
for (int i = 0; i < numCaves; i++) {
temp[i] = (strategy[k] == i) ? true : false;
if (k + 1 < strategy.length) {
boolean result= true;
if (i - 1 >= 0) {
result=result && DP[i - 1];
}
if (i + 1 < numCaves) {
result= result&& DP[i + 1];
}
temp[i]= temp[i]|| result;
}
}
DP = temp;
}
for (int i = 0; i < numCaves; i++) {
canWin = canWin && DP[i];
}
return canWin;
}

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

: cave=4(0-3), strategy[1,1,2,2]
: 有问题

b*p2014-08-17 07:08

36 楼

我的伪码
假设有N个房间，strategy[0..k]
首先initialize一个N+2的数组[0..N+1],其中0和N+1是dummy
boolean eval(int N, int[] strategy)
{
//assert N>1
ArrayList room = new ArrayList();
//room[0..N+1]都为initialized为1

for (i=0;iif (finished(room)){
return true;
}
room[strategy[i]] = 0; //执行strategy
expand(room); //根据题意来确定下一状态
}
if (finished(room)){
return true;
}
return false;
}
boolean finish(ArrayList room){
if room[1..room.size()-2] 都为 0 return true;
else return false;
}
void expand(ArrayList room){
ArrayList possible = new ArrayList();
//1. 把room中不为0的idx给possible
//2. 把room所有项清为0
//3. 遍历possible,把possible[idx]-1 和 possible[idx]+1的room项赋为1
}
for example:
N=4, [3,2,2,3]
=3= =2= =2= =3=
1 1 1 0 0
2 1 0 0 0
3 0 1 0 0
4 1 0 1 0
return true

p*s2014-08-17 07:08

37 楼

234432就可以了
对于n个数，怪兽一定是奇偶相间地跳，先猜234...(n-1)，那么奇偶性与怪兽全相同或
全不同，全相同的话，猜的房间和怪兽的位置距离都是偶数，并且每次变化不超过2，
而且是从非负变到非正，所以一定在中间变成0，如果全不同，那就(n-1)(n-2)...432
再猜一遍，这次奇偶性就全相同了。

【在 b*****p 的大作中提到】

: n=5比较复杂
: 目前找到一个解
: [4,4,2,2,3,4,4,3,2]
: [4]干掉4
: [4,4]干掉5
: [4,4,2,2,3,4]干掉1和3
: [4,4,2,2,3,4,4,3,2]干掉2

b*p2014-08-17 07:08

38 楼

你的是正解。学术版也给出了答案123..NN..321。思路是一致的。

432

【在 p**s 的大作中提到】

: 234432就可以了
: 对于n个数，怪兽一定是奇偶相间地跳，先猜234...(n-1)，那么奇偶性与怪兽全相同或
: 全不同，全相同的话，猜的房间和怪兽的位置距离都是偶数，并且每次变化不超过2，
: 而且是从非负变到非正，所以一定在中间变成0，如果全不同，那就(n-1)(n-2)...432
: 再猜一遍，这次奇偶性就全相同了。

b*p2014-08-17 07:08

39 楼

我的证明更机械化一些。
以N=5为例子
R - 2 e 3 e 4 e 4 e 3 e 2
1 1 1 0 0 1 1 0 0 1 1 0 0
2 1 0 1 1 0 0 1 1 0 0 1 0
3 1 1 1 0 1 1 0 0 1 0 0 0
4 1 1 1 1 1 0 1 0 0 0 0 0
5 1 1 1 1 1 1 0 0 0 0 0 0
e = expand

432

【在 p**s 的大作中提到】

q*12014-08-17 07:08

40 楼

MARK

g*y2014-08-17 07:08

41 楼

有人能够给出清晰的解释么？包括DFS，还有怎么利用n * k matrix cut branch? 感觉
dp倒是好理解。

b*b2014-08-17 07:08

42 楼

这个思路太赞了，面试的时候能想出来真是大神！

j

【在 m******2 的大作中提到】

b*e2014-08-17 07:08

43 楼

这个才是正解。所以这道题根本也不用什么DP，也不需要O(n*k) time with O(n)
space. This optimal solution should be a linear scan of the guessing
sequence with O(k) time and O(1) space. We simple need to know if the "
correct" sequence presents in the guess, because that's the only way you can
catch the thief.

432

【在 p**s 的大作中提到】

f*e2014-08-17 07:08

44 楼

没看懂。

w*g2014-08-17 07:08

45 楼

is this the only solution
how about symmetric solution like
n-1,n-2,...,3,2,2,3,...,n-2,n-1

can

【在 b***e 的大作中提到】

: 这个才是正解。所以这道题根本也不用什么DP，也不需要O(n*k) time with O(n)
: space. This optimal solution should be a linear scan of the guessing
: sequence with O(k) time and O(1) space. We simple need to know if the "
: correct" sequence presents in the guess, because that's the only way you can
: catch the thief.
:
: 432

b*e2014-08-17 07:08

46 楼

好，就送佛送到西吧。
贼的位置可以分为两种情况：
1. 第一天贼在奇数号房子。在这种情况下，贼在奇数天必在奇数号房子，偶数天必在
偶数号房子。我们称这种贼为顺贼。
2. 第一天贼在偶数号房子。在这种情况下，贼在奇数天必在偶数号房子，偶数天必在
奇数号房子。我们称这种贼为逆贼。
显然，这两种情况是完全不相交的，即顺贼永远不可能变成逆贼，逆贼也永远不可能变
成顺贼。
一个抓捕的序列，如果能抓住这个贼，那么只能是从一头向另外一头把他逼到死角。这
一共就四种可能性：
1. 从左向右抓顺贼
2. 从左向右抓逆贼
3. 从右向左抓顺贼
4. 从右向左抓逆贼
所以判断抓捕序列的有效性等同于判断(1 or 3) and (2 or 4)，即顺贼逆贼都会落网
。这四种情况是完全对称的。所以以下仅说明情况1的做法，即判断一个抓捕序列是否
可以从左向右抓住顺贼。
这个抓捕的顺序必须包含一个顺捕序列，其开始必然是在某一奇数天在一号房进行抓捕
。然后每一天向右挪一，以做到每次控制抓捕房子以左的地盘，把贼限制在右侧。如果
有一天没有按照计划向右挪一，那就会丢失一座房子的地盘。所以最后有效的抓捕序列
必然控制了所有的地盘。代码如下：
var catch1 = function(n, a) {
var lookingFor;
for (var i = 0; i < a.length; i++) {
if (lookingFor == 1) {
if (i % 2 == 0 && a[i] == 1) {
lookingFor = 2;
}
} else {
if (a[i] == lookingFor) {
lookingFor++;
} else {
lookingFor--;
}
if (lookingFor == n) {
return true;
}
}
}
return false;
};
同理可定义catch2, catch3 and catch4. 最终，catch = (catch1 || catch3) && （
catch2 || catch 4)。

【在 w*******g 的大作中提到】

: is this the only solution
: how about symmetric solution like
: n-1,n-2,...,3,2,2,3,...,n-2,n-1
:
: can

w*d2014-08-17 07:08

47 楼

各位都是大牛，我只有写代码的份。
根据mitkook2的算法，采用DP，复杂度O(NK) time, O(N) space
bool solve1(int n, const vector & seq)
{
if (n < 1 || (n < 2 && !seq.empty()))
return true;
vector dp(n, true);
for (int s : seq) {
assert(0 <= s && s < n);
bool survive = false, prev = false;
for (int i = 0; i < n; ++i) {
const bool c = (s != i
&& ((i && prev)
|| (i + 1 < n && dp[i + 1])));
if (c)
survive = true;
prev = dp[i];
dp[i] = c;
}
if (!survive)
return true;
}
return false;
}

w*d2014-08-17 07:08

48 楼

根据plus和blaze的算法，扫描一遍seq即可，复杂度O(N) time, O(1) space。
bool solve2(int n, const vector & seq)
{
if (n < 1 || (n < 2 && !seq.empty()))
return true;
//search for S1 or S2 in seq, and mark odd/even in r
for (int i = 0, n1 = 1, n2 = n - 2, i1 = 0, r = 0; i < seq.size();++i) {
if (1 == seq[i])
i1 = i;
if (n1 == seq[i]) {
if (++n1 > n - 2)
r |= 1 << (i1 & 1);
} else
n1 = (1 == seq[i] ? 2 : 1);
if (n2 == seq[i]) {
if (--n2 < 1)
r |= 1 << (i1 & 1);
} else
n2 = (n - 2 == seq[i] ? n - 3 : n - 2);
if (3 == r)
return true; //found both odd and even sequences in seq
}
return false;
}

w*d2014-08-17 07:08

49 楼

上面的算法解释：
只有序列{2, 3, ..., n-1}或{n-1, n-2, ..., 2}能排除相同奇偶情况下的所有位置，
所以必须要有奇偶性不同的两个序列，才能排除所有位置。
如何判断一个序列的奇偶性？其实只要看'2'所在的位置是奇数还是偶数即可。
所以整个算法为：
1. 令 S1={2, 3, ..., n-1}，S2={n-1, n-2, ..., 2}；
2. 寻找sequence里面是否包含两个S1或S2，且处在不同的奇偶位置；
3. 找到则返回true；否则返回false。
注意：程序的房间编号从0开始

w*g2014-08-17 07:08

50 楼

what you described is an optimal solution but there could worse but correct
solution like any sequence that including yours but has extra numbers.
the original question is a verification problem, not an optimization problem
so I still don't a way better than n by k complexity

【在 b***e 的大作中提到】

: 好，就送佛送到西吧。
: 贼的位置可以分为两种情况：
: 1. 第一天贼在奇数号房子。在这种情况下，贼在奇数天必在奇数号房子，偶数天必在
: 偶数号房子。我们称这种贼为顺贼。
: 2. 第一天贼在偶数号房子。在这种情况下，贼在奇数天必在偶数号房子，偶数天必在
: 奇数号房子。我们称这种贼为逆贼。
: 显然，这两种情况是完全不相交的，即顺贼永远不可能变成逆贼，逆贼也永远不可能变
: 成顺贼。
: 一个抓捕的序列，如果能抓住这个贼，那么只能是从一头向另外一头把他逼到死角。这
: 一共就四种可能性：

l*s2014-08-17 07:08

51 楼

private static bool catchable(int[] strategy, int numCaves){
bool bOdd = false, bEven = false;
for(int i = 0; i < strategy.Length && strategy[i] < numCaves; i++){
int left = i;
if (strategy[i] != 1 && strategy[i] != numCaves - 2) continue;
if (numCaves > 3 && Math.Abs(strategy[i] - strategy[i + 1]) > 1)
continue;
if (numCaves > 3 && i < strategy.Length - 1){
int diff = strategy[i + 1] - strategy[i];
while (i - left + 1 < numCaves - 2 && i < strategy.Length - 1 &&
strategy[i + 1] - strategy[i] == diff)
i++;
}
if(i - left + 1 >= numCaves - 2)
if ((left + strategy[left]) % 2 == 0) bEven = true;
else bOdd = true;
}
return bOdd && bEven;
}

b*e2014-08-17 07:08

52 楼

You either didn't read or you didn't understand it. The whole point for me
to write such an usual long post is to tell why I am NOT only covering the
optimal case, but also all the cases, regardless whether optimal or not.
Essentially every possible solution must contain an subsequence which is
optimal solution, and my algorithm finds that subsequence.

correct
problem

【在 w*******g 的大作中提到】

: what you described is an optimal solution but there could worse but correct
: solution like any sequence that including yours but has extra numbers.
: the original question is a verification problem, not an optimization problem
: so I still don't a way better than n by k complexity

M*n2014-08-17 07:08

53 楼

面试考这种题真无聊，如果不提前看过想过，当场有多少人能弄明白题意就不错了。
就算考这种题会做，最后上手能做出来公司的project么，我也看不出来有任何相关性
。还不如问一些经典的hadoop算法做个变种管用。

w*g2014-08-17 07:08

54 楼

I stand corrected. thank you for the ingenious solution.

me

【在 b***e 的大作中提到】

: You either didn't read or you didn't understand it. The whole point for me
: to write such an usual long post is to tell why I am NOT only covering the
: optimal case, but also all the cases, regardless whether optimal or not.
: Essentially every possible solution must contain an subsequence which is
: optimal solution, and my algorithm finds that subsequence.
:
: correct
: problem

w*d2014-08-17 07:08

55 楼

我来举一个反例吧：
7个房间，编号0-6，检查序列为{1,2,3,0,3,4,5,5,4,3,6,3,2,1}，必然能找到小偷（
通过DP解法验证）。
但是并不是从左到右或从右到左连续搜索的。

【在 b***e 的大作中提到】

w*g2014-08-17 07:08

56 楼

but it still contain that sequence
which the algorithm can find

【在 w*****d 的大作中提到】

: 我来举一个反例吧：
: 7个房间，编号0-6，检查序列为{1,2,3,0,3,4,5,5,4,3,6,3,2,1}，必然能找到小偷（
: 通过DP解法验证）。
: 但是并不是从左到右或从右到左连续搜索的。

w*d2014-08-17 07:08

57 楼

我不知道你是如何判断“contain that sequence”的。
我再提供一个序列{1,2,3,3,4,5,5,4,6,4,3,2,1}，与前面例子的唯一区别就是去掉了0
。但是这个序列是无法找到小偷的。

【在 w*******g 的大作中提到】

: but it still contain that sequence
: which the algorithm can find

b*e2014-08-17 07:08

58 楼

Just feed your input to my algorithm, you will see why it should return
false.

了0

【在 w*****d 的大作中提到】

: 我不知道你是如何判断“contain that sequence”的。
: 我再提供一个序列{1,2,3,3,4,5,5,4,6,4,3,2,1}，与前面例子的唯一区别就是去掉了0
: 。但是这个序列是无法找到小偷的。

w*g2014-08-17 07:08

59 楼

if you miss a number in the correct sequence, you have to backtrack by one
number, so your example actually fails to pass the test.

了0

【在 w*****d 的大作中提到】

x*42014-08-17 07:08

60 楼

排除法：逐个扫描输入序列，假设当前猜得不对，要据怪物前一天可能在的房间，算出
今天他可能在的房间。如果今天可能的房间没有，则证明猜测有效。
class Solution:
def find(self, n, guess):
safe = set(range(n))
for num in guess:
new_safe = set()
for i in safe:
if 0 <= i - 1 < n and i - 1 != num: new_safe.add(i - 1)
if 0 <= i + 1 < n and i + 1 != num: new_safe.add(i + 1)
safe = new_safe
if not safe: return True
return False
sol = Solution()
print(sol.find(7, [1,2,3,0,3,4,5,5,4,3,6,3,2,1]))
print(sol.find(7, [1,2,3,3,4,5,5,4,6,4,3,2,1]))
print(sol.find(4, [2, 1, 1, 2]))
====
True
False
True

r*g2014-08-17 07:08

61 楼

大概思路理解，但是感觉程序似乎有点小问题，pre为什么是在里层函数更新？pre难道
不是k-1天的情况，怎么在计算每个房间时候就更新了？

j

【在 m******2 的大作中提到】

z*e2014-08-17 07:08

62 楼

看一眼，然后默默地走开,继续刷题去