由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - latest interview questions
相关主题
请教word ladder| |A家面经 (三轮电面)
FB电面的标准就那么高?明天A家onsite
被问到一个题目leetcode出了新题word ladder
Leetcode 的 Surrounded Regions 好难过大OJ (in JAVA)leetcode 上 wordladderII 求教
Level order traversal只让用一个Queue怎么做?贡献G电 估计挂了
怎么计算一个网站过去5min的访问量?Google电面
A家来两道电面题这段word ladder II怎么改?
G家电面面经--佛云了~~大家看看我哪道题做错了?
相关话题的讨论汇总
话题: point话题: visited话题: sum话题: int话题: queue
进入JobHunting版参与讨论
1 (共1页)
l******c
发帖数: 2555
1
There is a monkey which can walk around on a planar grid. The monkey can
move one space at a time left, right, up or down. That is, from (x, y) the
monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where
the sum of the digits of the absolute value of the x coordinate plus the sum
of the digits of the absolute value of the y coordinate are lesser than or
equal to 19 are accessible to the monkey. For example, the point (59, 79) is
inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another
example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7
= 12, which is less than 19. How many points can the monkey access if it
starts at (0, 0), including (0, 0) itself? There is no input for this
program.
Print out the how many points can the monkey access. (The number should be
printed as an integer whole number eg. if the answer is 10 (its not !!),
print out 10, not 10.0 or 10.00 etc)
==================================================
My comment, if you use recursive method, very slow and stack overflow.
Also, if replace 19 with 25, what's the result?
p*****2
发帖数: 21240
2
BFS不行吗?
l******c
发帖数: 2555
3
apparentely, points (0, 298), (298, 0) (0, -298) (-298, 0) are the corner
value.
how to BFS?

【在 p*****2 的大作中提到】
: BFS不行吗?
p*****2
发帖数: 21240
4

从(0,0)开始,一层一层往外走不行吗。

【在 l******c 的大作中提到】
: apparentely, points (0, 298), (298, 0) (0, -298) (-298, 0) are the corner
: value.
: how to BFS?

l******c
发帖数: 2555
5
there are two directions, x & y,
some points will be visited twice

【在 p*****2 的大作中提到】
:
: 从(0,0)开始,一层一层往外走不行吗。

c****p
发帖数: 6474
6
在y=0和x-y=0,并x>=0的区间搜索。搜完了*8再扣掉重复计算过的点。
搜索是一层一层地搜【 在 lclclclc (home) 的大作中提到: 】
sum
or
is
Another
7
g**********y
发帖数: 14569
7
就是简单的BFS, 运行很快,对N=25, 16ms。f(19)=299, f(25)=899
public class MonkeyWalk {
public final static void main(String[] args) {
new MonkeyWalk().run(25);
}

private void run(int N) {
ArrayDeque queue = new ArrayDeque();
queue.add(new Point(0, 0));
HashSet visited = new HashSet();
visited.add("0 0");

while (!queue.isEmpty()) {
Point p = queue.pop();
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
}

System.out.println(visited.size());
}

private void visit(int x, int y, ArrayDeque queue, HashSet > visited, int N) {
String key = x + " " + y;
if (visited.contains(key) || sum(x)+sum(y)>N) return;
queue.add(new Point(x, y));
visited.add(key);
}
private int sum(int x) {
if (x < 0) return sum(-x);
int sum = 0;
while (x > 0) {
sum += x%10;
x /= 10;
}
return sum;
}

private class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
l******e
发帖数: 149
8
和我的结果不一样
f(19) = 102485
f(25) = 1033841

【在 g**********y 的大作中提到】
: 就是简单的BFS, 运行很快,对N=25, 16ms。f(19)=299, f(25)=899
: public class MonkeyWalk {
: public final static void main(String[] args) {
: new MonkeyWalk().run(25);
: }
:
: private void run(int N) {
: ArrayDeque queue = new ArrayDeque();
: queue.add(new Point(0, 0));
: HashSet visited = new HashSet();

g**********y
发帖数: 14569
9
是每个点都可以走到的?你计算的是valid的点吧?

【在 l******e 的大作中提到】
: 和我的结果不一样
: f(19) = 102485
: f(25) = 1033841

l******e
发帖数: 149
10
你程序里这段是什么意思?
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);

【在 g**********y 的大作中提到】
: 就是简单的BFS, 运行很快,对N=25, 16ms。f(19)=299, f(25)=899
: public class MonkeyWalk {
: public final static void main(String[] args) {
: new MonkeyWalk().run(25);
: }
:
: private void run(int N) {
: ArrayDeque queue = new ArrayDeque();
: queue.add(new Point(0, 0));
: HashSet visited = new HashSet();

g**********y
发帖数: 14569
11
汗死,你是对的,我copy-paste之后,忘改了 :)

【在 l******e 的大作中提到】
: 你程序里这段是什么意思?
: visit(p.x+1, p.y, queue, visited, N);
: visit(p.x+1, p.y, queue, visited, N);
: visit(p.x+1, p.y, queue, visited, N);
: visit(p.x+1, p.y, queue, visited, N);

g**********y
发帖数: 14569
12
把HashSet换成boolean的话,对N=25, 速度可以从2.8秒提到0.2秒。
对N=25, x/y = +/-899 就是边界,所以二维数组[2000][2000]就足够存储所有访问过的点。
程序:
public class MonkeyWalk {
public final static void main(String[] args) {
long t0 = System.currentTimeMillis();
new MonkeyWalk().run(25);
long t1 = System.currentTimeMillis();
System.out.println(t1 - t0);
}

private ArrayDeque queue;
private boolean[][] visited;
private int count = 0;

private void run(int N) {
queue = new ArrayDeque();
queue.add(new Point(0, 0));
visited = new boolean[2000][2000];
visited[1000][1000] = true;
count++;

while (!queue.isEmpty()) {
Point p = queue.remove();
visit(p.x+1, p.y, N);
visit(p.x-1, p.y, N);
visit(p.x, p.y+1, N);
visit(p.x, p.y-1, N);
}

System.out.println(count);
}

private void visit(int x, int y, int N) {
if (visited[1000+x][1000+y] || sum(x)+sum(y)>N) return;
queue.add(new Point(x, y));
count++;
visited[1000+x][1000+y] = true;
}
private int sum(int x) {
if (x < 0) return sum(-x);
int sum = 0;
while (x > 0) {
sum += x%10;
x /= 10;
}
return sum;
}

private class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
大家看看我哪道题做错了?Level order traversal只让用一个Queue怎么做?
word ladder 时间空间复杂度是多少, bfs 解的怎么计算一个网站过去5min的访问量?
[面试题] 如何打印一个二叉树level by level?A家来两道电面题
print a BST level by level, last row firstG家电面面经--佛云了~~
请教word ladder| |A家面经 (三轮电面)
FB电面的标准就那么高?明天A家onsite
被问到一个题目leetcode出了新题word ladder
Leetcode 的 Surrounded Regions 好难过大OJ (in JAVA)leetcode 上 wordladderII 求教
相关话题的讨论汇总
话题: point话题: visited话题: sum话题: int话题: queue