LIKE CODING: MJ [27] Catch Thief
A thief steals from n houses denoted from 0 to n-1. To avoid to be caught, the thief cannot stay in the same house in two successive days and can only move to the left or right house on the next day. For example, if the thief steals house 5 on day 8, he must move to house 4 or 6 one day 9.
The police is trying to catch the thief with a strategy. strategy[i] (i=0,...,k-1) indicates the house to be searched on day i. The police catches the thief if they are in the same house on the same day. Write a program to determine whether the police can catch the thief by the strategy.
http://www.mitbbs.com/article_t1/JobHunting/32978937_0_1.html
找小偷问题，有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
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;
}
// 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;
}
https://gist.github.com/gcrfelix/19e0dd64a7f8e9192158
就是ali baba是个怪兽，他可能在[0，1, ..., numCaves-1]出现，他每隔一天就要换
一个地方，但他每次只能移左右一格。
然后给你一个strategy[]数组，数组里面是猜测每天ali baba的位置。如果里面有一个
猜中了，这个strategy就是正确的。
问题就是让你写一个判断函数 alibaba(int numCaves, int[] strategy)来判别这个
strategy数组是不是稳赢的策略。写完后问时间复杂度，然后问了下大概怎么样可以优
化
*/
public class FindAlibaba {
// 可以用 res[i][j] 来表示 第j天在Cave i能不能捉到alibaba. 如果捉到，则为true, 否则为false
// 然后状态转换方程就是res[i][j] = res[i][j] || res[i - 1][j - 1] && res[i + 1][j - 1], 它的解依赖于往左跳一格和往右跳一格
// 然后最后再check res[i][days - 1]是不是全是true， 是的话就代表这个strategy稳赢
// 时间复杂度就是O(numCaves * len(strategy))
public boolean alibaba(int numCaves, int[] strategy) {
int days = strategy.length;
boolean[][] res = new boolean[numCaves][days];
for(int i=0; i<days; i++) {
res[strategy[i]][i] = true;
}
for(int i=0; i<numCaves; i++) {
for(int j=1; j<days; j++) {
if(i == numCaves-1) {
res[i][j] = res[i][j] || res[i-1][j-1];
} else if(i == 0) {
res[i][j] = res[i][j] || res[i+1][j-1];
} else {
res[i][j] = res[i][j] || (res[i-1][j-1] && res[i+1][j-1]);
}
}
}
boolean result = true;
for(int i=0; i<numCaves; i++) {
if(!result) {
break;
} else {
result = result && res[i][days-1];
}
}
return result;
}
}
http://paul198247.blogspot.com/2015/08/fb.html
找小偷问题，有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。 我觉得这题我
基本是答得非常漂亮的而且思路很清晰，考官也很开心
Read full article from LIKE CODING: MJ [27] Catch Thief
A thief steals from n houses denoted from 0 to n-1. To avoid to be caught, the thief cannot stay in the same house in two successive days and can only move to the left or right house on the next day. For example, if the thief steals house 5 on day 8, he must move to house 4 or 6 one day 9.
The police is trying to catch the thief with a strategy. strategy[i] (i=0,...,k-1) indicates the house to be searched on day i. The police catches the thief if they are in the same house on the same day. Write a program to determine whether the police can catch the thief by the strategy.
http://www.mitbbs.com/article_t1/JobHunting/32978937_0_1.html
找小偷问题，有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
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;
}
// 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;
}
int closestValue(TreeNode* root, double target) { int ret = root->val; closestValue(root, target, ret); return ret; } void closestValue(TreeNode* root, double target, int &ret){ if(root){// if(target == (double)(root->val)) {ret = target; return;} if(abs(root->val - target)<abs(ret - target)) ret = root->val; if(target<(double)root->val) closestValue(root->left, target, ret); else closestValue(root->right, target, ret); } }就是ali baba是个怪兽，他可能在[0，1, ..., numCaves-1]出现，他每隔一天就要换
一个地方，但他每次只能移左右一格。
然后给你一个strategy[]数组，数组里面是猜测每天ali baba的位置。如果里面有一个
猜中了，这个strategy就是正确的。
问题就是让你写一个判断函数 alibaba(int numCaves, int[] strategy)来判别这个
strategy数组是不是稳赢的策略。写完后问时间复杂度，然后问了下大概怎么样可以优
化
*/
public class FindAlibaba {
// 可以用 res[i][j] 来表示 第j天在Cave i能不能捉到alibaba. 如果捉到，则为true, 否则为false
// 然后状态转换方程就是res[i][j] = res[i][j] || res[i - 1][j - 1] && res[i + 1][j - 1], 它的解依赖于往左跳一格和往右跳一格
// 然后最后再check res[i][days - 1]是不是全是true， 是的话就代表这个strategy稳赢
// 时间复杂度就是O(numCaves * len(strategy))
public boolean alibaba(int numCaves, int[] strategy) {
int days = strategy.length;
boolean[][] res = new boolean[numCaves][days];
for(int i=0; i<days; i++) {
res[strategy[i]][i] = true;
}
for(int i=0; i<numCaves; i++) {
for(int j=1; j<days; j++) {
if(i == numCaves-1) {
res[i][j] = res[i][j] || res[i-1][j-1];
} else if(i == 0) {
res[i][j] = res[i][j] || res[i+1][j-1];
} else {
res[i][j] = res[i][j] || (res[i-1][j-1] && res[i+1][j-1]);
}
}
}
boolean result = true;
for(int i=0; i<numCaves; i++) {
if(!result) {
break;
} else {
result = result && res[i][days-1];
}
}
return result;
}
}
http://paul198247.blogspot.com/2015/08/fb.html
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;
}
http://www.mitbbs.com/article_t/JobHunting/32978937.html找小偷问题，有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。 我觉得这题我
基本是答得非常漂亮的而且思路很清晰，考官也很开心
Read full article from LIKE CODING: MJ [27] Catch Thief
