g***s
发帖数: 3811 | 1 贡献几道当年google面试题,其实都很经典的题目,但的确是google的面试题。
１。 ８瓶水，一瓶有毒。老鼠喝了毒水第二天会死去。问用几只老鼠能尽快的找到毒
水。
２。二叉树给两nodes找最近公共祖先
３。给n＊m的字符矩阵。然后给你一个字符串。问是否可以在矩阵中找到他的track。
track是指从其
中一个符出发，可以向四周走，可以重复，可以回头。
e.g.
a b
c d
string: 'bdba' could be found but not for 'bcd'. |
g*********s
发帖数: 1782 | 2
按你的描述，7只，1天。估计你漏了条件。
经典。无父指针的话，time O(N) and space O(N)比较容易。RMQ比较难，而且对多组
输入才有
优势。
将字符矩阵转换成状态图，用基于有限自动机的模式匹配。
【在 g***s 的大作中提到】
: 贡献几道当年google面试题,其实都很经典的题目,但的确是google的面试题。
: １。 ８瓶水，一瓶有毒。老鼠喝了毒水第二天会死去。问用几只老鼠能尽快的找到毒
: 水。
: ２。二叉树给两nodes找最近公共祖先
: ３。给n＊m的字符矩阵。然后给你一个字符串。问是否可以在矩阵中找到他的track。
: track是指从其
: 中一个符出发，可以向四周走，可以重复，可以回头。
: e.g.
: a b
: c d
|
g***s
发帖数: 3811 | 3 1. It is not 7. you missed some thing from the question.
2. missed some conditions: 1) every node has the parent pointer. 2) can
only use O(1) extra space
3. DP
【在 g*********s 的大作中提到】
:
: 按你的描述，7只，1天。估计你漏了条件。
: 经典。无父指针的话，time O(N) and space O(N)比较容易。RMQ比较难，而且对多组
: 输入才有
: 优势。
: 将字符矩阵转换成状态图，用基于有限自动机的模式匹配。
|
l*****a
发帖数: 14598 | 4 显然他同时希望老鼠数目最少
【在 g*********s 的大作中提到】
:
: 按你的描述，7只，1天。估计你漏了条件。
: 经典。无父指针的话，time O(N) and space O(N)比较容易。RMQ比较难，而且对多组
: 输入才有
: 优势。
: 将字符矩阵转换成状态图，用基于有限自动机的模式匹配。
|
C***y
发帖数: 2546 | 5 我感觉应该是问7
7的话，3只老鼠
8的话，4只
条件是可以混合
【在 g***s 的大作中提到】
: 1. It is not 7. you missed some thing from the question.
: 2. missed some conditions: 1) every node has the parent pointer. 2) can
: only use O(1) extra space
: 3. DP
|
g*********s
发帖数: 1782 | 6
here u have acutally 2 goals: minimize the # of days and the # of rats?
the lower bound for each is 1 and 4, but can't be achieved at the same
time, right?
then it becomes: given two lists, find the first common elements.
intuitively this is not hard even for O(1) space.
i don't see how it links to dp.
【在 g***s 的大作中提到】
: 1. It is not 7. you missed some thing from the question.
: 2. missed some conditions: 1) every node has the parent pointer. 2) can
: only use O(1) extra space
: 3. DP
|
g***s
发帖数: 3811 | 7 8 的话 3 is enough.
2^3 = 8
【在 C***y 的大作中提到】
: 我感觉应该是问7
: 7的话，3只老鼠
: 8的话，4只
: 条件是可以混合
|
C***y
发帖数: 2546 | 8 第八瓶水怎么encoding？
如果只有3位（3只老鼠）的话
【在 g***s 的大作中提到】
: 8 的话 3 is enough.
: 2^3 = 8
|
g*********s
发帖数: 1782 | 9
then we have to assume the poison is very strong that after mixing it with
water it is still lethal.
【在 C***y 的大作中提到】
: 我感觉应该是问7
: 7的话，3只老鼠
: 8的话，4只
: 条件是可以混合
|
g***s
发帖数: 3811 | 10
3 rats for 1 day is the best solution.
yes, it is a simple question.
It is a DP question. space and time complexity = O (m * n * k) k is the
length of the string.
【在 g*********s 的大作中提到】
:
: then we have to assume the poison is very strong that after mixing it with
: water it is still lethal.
|
|
|
g***s
发帖数: 3811 | 11 yes.
with
【在 g*********s 的大作中提到】
:
: then we have to assume the poison is very strong that after mixing it with
: water it is still lethal.
|
T*o
发帖数: 363 | 12 原来2是google的题啊，经典题啊。
【在 g***s 的大作中提到】
: 贡献几道当年google面试题,其实都很经典的题目,但的确是google的面试题。
: １。 ８瓶水，一瓶有毒。老鼠喝了毒水第二天会死去。问用几只老鼠能尽快的找到毒
: 水。
: ２。二叉树给两nodes找最近公共祖先
: ３。给n＊m的字符矩阵。然后给你一个字符串。问是否可以在矩阵中找到他的track。
: track是指从其
: 中一个符出发，可以向四周走，可以重复，可以回头。
: e.g.
: a b
: c d
|
g***s
发帖数: 3811 | 13 mark the bottles with 0..7. giving three rats x,y,z.
x y z #
0 0 0 0
0 0 1 1
0 1 0 2
0 1 1 3
1 0 0 4
1 0 1 5
1 1 0 6
1 1 1 7
x,y,z分别喝列上对应是1的瓶号的水。
x drinks 4,5,6,7
y drinks 2,3,6,7
z drinks 1,3,5,7
【在 C***y 的大作中提到】
: 第八瓶水怎么encoding？
: 如果只有3位（3只老鼠）的话
|
l*****a
发帖数: 14598 | 14 how do u hold the two lists with O(1) memory?
【在 g*********s 的大作中提到】
:
: then we have to assume the poison is very strong that after mixing it with
: water it is still lethal.
|
s******c
发帖数: 1920 | 15 1.
3只老鼠，测一轮：第一只老鼠喝一口编号为001，011，101和111的水（最低位为1）；
第二只老鼠喝一口中间位为1的4瓶水；第三只老鼠喝最高位为1的水。第二天，从3只老
鼠的生死能推出有毒的水的编号。
2.
如果给了parent指针的话，应该就是向上trace就可以了吧？把visit过的node mark一
下，第一个被mark两次的node就是公共祖先了吧？
3.
求详解。。。。 |
g*********s
发帖数: 1782 | 16 it's already exists in the tree implicitly through parent pointers.
【在 l*****a 的大作中提到】
: how do u hold the two lists with O(1) memory?
|
g*********s
发帖数: 1782 | 17 interesting puzzle. i think this links to some test coverage
theory/algorithms.
【在 g***s 的大作中提到】
: mark the bottles with 0..7. giving three rats x,y,z.
: x y z #
: 0 0 0 0
: 0 0 1 1
: 0 1 0 2
: 0 1 1 3
: 1 0 0 4
: 1 0 1 5
: 1 1 0 6
: 1 1 1 7
|
l*****a
发帖数: 14598 | 18 if so
u can say search node in BST is also O(1) for time complexity,
doesn't it???
search in BT is also O(1)
【在 g*********s 的大作中提到】
: it's already exists in the tree implicitly through parent pointers.
|
C***y
发帖数: 2546 | 19 如果第0瓶有毒的话？
哪只老鼠死？
还是你有个附加条件，肯定有瓶是有毒的?
【在 g***s 的大作中提到】
: mark the bottles with 0..7. giving three rats x,y,z.
: x y z #
: 0 0 0 0
: 0 0 1 1
: 0 1 0 2
: 0 1 1 3
: 1 0 0 4
: 1 0 1 5
: 1 1 0 6
: 1 1 1 7
|
g*********s
发帖数: 1782 | 20
can u give ur solution to show why it is dp?
【在 g***s 的大作中提到】
: mark the bottles with 0..7. giving three rats x,y,z.
: x y z #
: 0 0 0 0
: 0 0 1 1
: 0 1 0 2
: 0 1 1 3
: 1 0 0 4
: 1 0 1 5
: 1 1 0 6
: 1 1 1 7
|
|
|
g*********s
发帖数: 1782 | 21 then no rat die.
【在 C***y 的大作中提到】
: 如果第0瓶有毒的话？
: 哪只老鼠死？
: 还是你有个附加条件，肯定有瓶是有毒的?
|
g***s
发帖数: 3811 | 22 none.
yes, already mentioned: one of the eight is poisoned.
【在 C***y 的大作中提到】
: 如果第0瓶有毒的话？
: 哪只老鼠死？
: 还是你有个附加条件，肯定有瓶是有毒的?
|
g*********s
发帖数: 1782 | 23 how could search gives u O(1)? bt is O(N) while bst is O(h).
【在 l*****a 的大作中提到】
: if so
: u can say search node in BST is also O(1) for time complexity,
: doesn't it???
: search in BT is also O(1)
|
g***s
发帖数: 3811 | 24 define
f(x,y,z) x,y means the position in the matrix
z means the right z-length sub string of orig search string.
f(x,y,z) true if from x,y, we can find the right z-length sub string of
orig search string; otherwise false
t(z) means the z-th char from the right.
f(x,y,z) =
f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||
f(x , y - 1, z -1) && isValidY(y-1) && mtx[x,y-1] == t(z) ||
f(x , y + 1, z -1) && isValidY(y+1) && mtx[x,y+1] == t(z)
【在 g*********s 的大作中提到】
: how could search gives u O(1)? bt is O(N) while bst is O(h).
|
l*****a
发帖数: 14598 | 25 then why u can say the path from node to root is O(1)???
even for comparing two paths,it is also O(1)?
【在 g*********s 的大作中提到】
: how could search gives u O(1)? bt is O(N) while bst is O(h).
|
g***s
发帖数: 3811 | 26 The requirement for this question is using extra O(1) space.
the key idea for this question is: calculate the depth of the two nodes
first(dx,dy, assume dx>dy). then move one node for (dx-dy) steps. then
they are in the same level. then both move together until reach the same
node.
【在 l*****a 的大作中提到】
: then why u can say the path from node to root is O(1)???
: even for comparing two paths,it is also O(1)?
|
s******c
发帖数: 1920 | 27 恍然大雾。。。
【在 g***s 的大作中提到】
: The requirement for this question is using extra O(1) space.
: the key idea for this question is: calculate the depth of the two nodes
: first(dx,dy, assume dx>dy). then move one node for (dx-dy) steps. then
: they are in the same level. then both move together until reach the same
: node.
|
l*****a
发帖数: 14598 | 28 u r right,
no need to store them
think too much...
【在 g***s 的大作中提到】
: The requirement for this question is using extra O(1) space.
: the key idea for this question is: calculate the depth of the two nodes
: first(dx,dy, assume dx>dy). then move one node for (dx-dy) steps. then
: they are in the same level. then both move together until reach the same
: node.
|
p****g
发帖数: 355 | 29 一定要指向父节点的指针么？做post-order traverse，用两个bool表示那两个点是否
被traversed，返回第一个both bool are true的点。 |
g***s
发帖数: 3811 | 30 这用了超过O(1)的空间
【在 p****g 的大作中提到】
: 一定要指向父节点的指针么？做post-order traverse，用两个bool表示那两个点是否
: 被traversed，返回第一个both bool are true的点。
|
|
|
p****g
发帖数: 355 | 31 只用了两个bool啊
【在 g***s 的大作中提到】
: 这用了超过O(1)的空间
|
g***s
发帖数: 3811 | 32 post-order traverse实际上是用recursive的方式实现了一个栈。额外空间是tree的深
度。
而且，这个算法，如果两个结点在最右边，那么要遍历玩所有节点。时间复杂度是O(n).
而用同时向parent移动找的方式，算法时间是树的深度。
【在 p****g 的大作中提到】
: 只用了两个bool啊
|
g*********s
发帖数: 1782 | 33 父指针本身也是O(N)的开销。
不带父指针的LCA可以做到T O(N) and S O(N).
带父指针的看似T O(N), S O(1)，算上父指针本身开销，其实复杂度是一样的。
n).
【在 g***s 的大作中提到】
: post-order traverse实际上是用recursive的方式实现了一个栈。额外空间是tree的深
: 度。
: 而且，这个算法，如果两个结点在最右边，那么要遍历玩所有节点。时间复杂度是O(n).
: 而用同时向parent移动找的方式，算法时间是树的深度。
|
g*********e
发帖数: 14401 | 34 would somebody explain question 3?
how is dp used here? |
g***s
发帖数: 3811 | 35 怪我题目没有说好。父指针是题目已经给的。
【在 g*********s 的大作中提到】
: 父指针本身也是O(N)的开销。
: 不带父指针的LCA可以做到T O(N) and S O(N).
: 带父指针的看似T O(N), S O(1)，算上父指针本身开销，其实复杂度是一样的。
:
: n).
|
g***s
发帖数: 3811 | 36 我给出DP公式了。
【在 g*********e 的大作中提到】
: would somebody explain question 3?
: how is dp used here?
|
y***m
发帖数: 7027 | 37 1.1只老鼠1天
joke办法:
1只老鼠每隔1分钟(不是说一天么,就24小时呗)从7瓶子中每瓶中喝一点，记下瓶子先后
次序，如果第二天老鼠死了就按时间推算拿瓶有毒,没死就是剩下一瓶...
2.
p1,p2
while(true){
p1= p1->parent
p2=p2->parent
if(p1=p2) break;
}
【在 g***s 的大作中提到】
: 贡献几道当年google面试题,其实都很经典的题目,但的确是google的面试题。
: １。 ８瓶水，一瓶有毒。老鼠喝了毒水第二天会死去。问用几只老鼠能尽快的找到毒
: 水。
: ２。二叉树给两nodes找最近公共祖先
: ３。给n＊m的字符矩阵。然后给你一个字符串。问是否可以在矩阵中找到他的track。
: track是指从其
: 中一个符出发，可以向四周走，可以重复，可以回头。
: e.g.
: a b
: c d
|
y***m
发帖数: 7027 | 38 类似方法用4只老鼠1天也行吧
1234 A
2345 B
3456 C
4567 D
x drinks 4,5,6,7
y drinks 2,3,6,7
z drinks 1,3,4,5
这里 xy都死了，那67那瓶有毒?
thx!
【在 g***s 的大作中提到】
: mark the bottles with 0..7. giving three rats x,y,z.
: x y z #
: 0 0 0 0
: 0 0 1 1
: 0 1 0 2
: 0 1 1 3
: 1 0 0 4
: 1 0 1 5
: 1 1 0 6
: 1 1 1 7
|
g***s
发帖数: 3811 | 39 2.
你这个只有在同一层才行。这就是为什么要先分别算深度。
【在 y***m 的大作中提到】
: 1.1只老鼠1天
: joke办法:
: 1只老鼠每隔1分钟(不是说一天么,就24小时呗)从7瓶子中每瓶中喝一点，记下瓶子先后
: 次序，如果第二天老鼠死了就按时间推算拿瓶有毒,没死就是剩下一瓶...
: 2.
: p1,p2
: while(true){
: p1= p1->parent
: p2=p2->parent
: if(p1=p2) break;
|
y***m
发帖数: 7027 | 40 老鼠那题不明白，请指教，xy都死了怎么区分6还是7?
thx!
【在 g***s 的大作中提到】
: 2.
: 你这个只有在同一层才行。这就是为什么要先分别算深度。
|
|
|
g***s
发帖数: 3811 | 41 1天的话越少越好。
3只老鼠，有死或者不死两种状态，最多能表达的状态是8.
【在 y***m 的大作中提到】
: 类似方法用4只老鼠1天也行吧
: 1234 A
: 2345 B
: 3456 C
: 4567 D
: x drinks 4,5,6,7
: y drinks 2,3,6,7
: z drinks 1,3,4,5
: 这里 xy都死了，那67那瓶有毒?
: thx!
|
y***m
发帖数: 7027 | 42 那只是二进制吧，xy110是6，但7那瓶有毒也会导致xy死吧?
【在 g***s 的大作中提到】
: 1天的话越少越好。
: 3只老鼠，有死或者不死两种状态，最多能表达的状态是8.
|
S****z
发帖数: 666 | 43 大胆请教初始条件的x,y即x0,y0在哪里？
是不是orig string的最后一个char在Matrix中所有出现过的地方？
【在 g***s 的大作中提到】
: define
: f(x,y,z) x,y means the position in the matrix
: z means the right z-length sub string of orig search string.
: f(x,y,z) true if from x,y, we can find the right z-length sub string of
: orig search string; otherwise false
: t(z) means the z-th char from the right.
: f(x,y,z) =
:
: f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
: f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||
|
S****z
发帖数: 666 | 44 7有毒那都得挂？
【在 y***m 的大作中提到】
: 那只是二进制吧，xy110是6，但7那瓶有毒也会导致xy死吧?
|
y***m
发帖数: 7027 | 45 也是，树结构里应该记录每个节点当前深度吧，then 加个深度平衡计算...
2.
p1,p2,lev1,lev2
while(lev1>lev2){
p1= p1->parent
lev1--
}
while(lev2>lev1){
p2= p2->parent
lev2--
}
while(p1<>p2){
p1= p1->parent
p2=p2->parent
}
【在 g***s 的大作中提到】
: 2.
: 你这个只有在同一层才行。这就是为什么要先分别算深度。
|
y***m
发帖数: 7027 | 46 x drinks 4,5,6,7
y drinks 2,3,6,7
z drinks 1,3,4,5
z都没喝，怎么会挂?
grass好像排错了，ms 可以
x drinks 4,5,6,7
y drinks 2,3,6,7
z drinks 1,3,5,7
【在 S****z 的大作中提到】
: 7有毒那都得挂？
|
g***s
发帖数: 3811 | 47 是的。我的typo。不过，从我给的表，应该能看出z是1，3，5，7.（读对应z的列）
【在 y***m 的大作中提到】
: x drinks 4,5,6,7
: y drinks 2,3,6,7
: z drinks 1,3,4,5
: z都没喝，怎么会挂?
: grass好像排错了，ms 可以
: x drinks 4,5,6,7
: y drinks 2,3,6,7
: z drinks 1,3,5,7
|
g***s
发帖数: 3811 | 48 你这个可以。不过，更简单点，可以f(x,y,0)=true
基本上，你写出递推公式，面试官就知道你会了。
【在 S****z 的大作中提到】
: 大胆请教初始条件的x,y即x0,y0在哪里？
: 是不是orig string的最后一个char在Matrix中所有出现过的地方？
|
z**c
发帖数: 625 | 49
【在 S****z 的大作中提到】
: 大胆请教初始条件的x,y即x0,y0在哪里？
: 是不是orig string的最后一个char在Matrix中所有出现过的地方？
|
z**c
发帖数: 625 | 50 楼主说的是遍历所有的cell吧，所以才有的O(N*M*K)
【在 S****z 的大作中提到】
: 大胆请教初始条件的x,y即x0,y0在哪里？
: 是不是orig string的最后一个char在Matrix中所有出现过的地方？
|
|
|
z**c
发帖数: 625 | 51 多谢分享！
算法是对的，如果加上base case: if (0 == z) return else ...。
我有个问题，这个算法不就是标准的递归吗？DP在哪里？中间结果(sub optimal)存在
哪了？
【在 g***s 的大作中提到】
: define
: f(x,y,z) x,y means the position in the matrix
: z means the right z-length sub string of orig search string.
: f(x,y,z) true if from x,y, we can find the right z-length sub string of
: orig search string; otherwise false
: t(z) means the z-th char from the right.
: f(x,y,z) =
:
: f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
: f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||
|
z**c
发帖数: 625 | 52 多谢分享！
算法是对的，如果加上base case: if (0 == z) return else ...。
我有个问题，这个算法不就是标准的递归吗？DP在哪里？中间结果(sub optimal)存在
哪了？
【在 g***s 的大作中提到】
: define
: f(x,y,z) x,y means the position in the matrix
: z means the right z-length sub string of orig search string.
: f(x,y,z) true if from x,y, we can find the right z-length sub string of
: orig search string; otherwise false
: t(z) means the z-th char from the right.
: f(x,y,z) =
:
: f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
: f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||
|
g***s
发帖数: 3811 | 53 Simple question: do you think f(n) = f(n-1) + f(n-2) is also 标准的递归?
【在 z**c 的大作中提到】
: 多谢分享！
: 算法是对的，如果加上base case: if (0 == z) return else ...。
: 我有个问题，这个算法不就是标准的递归吗？DP在哪里？中间结果(sub optimal)存在
: 哪了？
|
g***s
发帖数: 3811 | 54 我给的是递推公式，他是问DP的初始值如何设。f(x,y,0)=true
【在 z**c 的大作中提到】
: 楼主说的是遍历所有的cell吧，所以才有的O(N*M*K)
|
z**c
发帖数: 625 | 55 是吧，如果用额外空间存中间结果的话，就是dp
【在 g***s 的大作中提到】
: Simple question: do you think f(n) = f(n-1) + f(n-2) is also 标准的递归?
|
s***a
发帖数: 7433 | 56 How about this?
mark the bottles with 0..7. giving three rats x,y,z.
x y z #
0 0 0 0
0 0 1 1
0 1 0 2
0 1 1 3
1 0 0 4
1 0 1 5
1 1 0 6
1 1 1 7
0 means not drinking, 1 means drinking
If all alive, bottle 0 is poison,
If z died, bottle 1,
If y died, bottle 2,
If y,z died, bottle 3,
If x died, bottle 4,
If x,z died, bottle 5
If x,y died, bottle 6
If all died, bottle 7 |
f*******4
发帖数: 1401 | 57 实际实现的时候 建表 然后每次递归的时候看一看值是否已经在里面了 在
里面的话就直接返回了
【在 z**c 的大作中提到】
: 多谢分享！
: 算法是对的，如果加上base case: if (0 == z) return else ...。
: 我有个问题，这个算法不就是标准的递归吗？DP在哪里？中间结果(sub optimal)存在
: 哪了？
|
z**c
发帖数: 625 | 58 哦，我好像明白了，f()是个三维矩阵，我以为是个函数呢
但是这个dp的效率是多少？空间O(NMK)?时间O(NMK)?
【在 f*******4 的大作中提到】
: 实际实现的时候 建表 然后每次递归的时候看一看值是否已经在里面了 在
: 里面的话就直接返回了
|
z**c
发帖数: 625 | 59 哦，我好像明白了，f()是个三维矩阵，我以为是个函数呢
但是这个dp的效率是多少？空间O(NMK)?时间O(NMK)?
【在 f*******4 的大作中提到】
: 实际实现的时候 建表 然后每次递归的时候看一看值是否已经在里面了 在
: 里面的话就直接返回了
|
z**c
发帖数: 625 | 60 哦，我好像明白了，f()是个三维矩阵，我以为是个函数呢
但是这个dp的效率是多少？空间O(NMK)?时间O(NMK)?
【在 f*******4 的大作中提到】
: 实际实现的时候 建表 然后每次递归的时候看一看值是否已经在里面了 在
: 里面的话就直接返回了
|
|
|
z**c
发帖数: 625 | 61 哦，我好像明白了，f()是个三维矩阵，我以为是个函数呢
但是这个dp的效率是多少？空间O(NMK)?时间O(NMK)?
【在 f*******4 的大作中提到】
: 实际实现的时候 建表 然后每次递归的时候看一看值是否已经在里面了 在
: 里面的话就直接返回了
|
f*******4
发帖数: 1401 | 62 对啊 LZ不是说过了么
【在 z**c 的大作中提到】
: 哦，我好像明白了，f()是个三维矩阵，我以为是个函数呢
: 但是这个dp的效率是多少？空间O(NMK)?时间O(NMK)?
|
G****o
发帖数: 155 | 63
【在 g***s 的大作中提到】
: 贡献几道当年google面试题,其实都很经典的题目,但的确是google的面试题。
: １。 ８瓶水，一瓶有毒。老鼠喝了毒水第二天会死去。问用几只老鼠能尽快的找到毒
: 水。
: ２。二叉树给两nodes找最近公共祖先
: ３。给n＊m的字符矩阵。然后给你一个字符串。问是否可以在矩阵中找到他的track。
: track是指从其
: 中一个符出发，可以向四周走，可以重复，可以回头。
: e.g.
: a b
: c d
|
z**c
发帖数: 625 | 64 哈哈，对！ 我没仔细中间的回帖 :(
【在 f*******4 的大作中提到】
: 对啊 LZ不是说过了么
|
b*******y
发帖数: 232 | 65 阿，这个是(7,4)汉明码的验证矩阵阿
【在 g***s 的大作中提到】
: mark the bottles with 0..7. giving three rats x,y,z.
: x y z #
: 0 0 0 0
: 0 0 1 1
: 0 1 0 2
: 0 1 1 3
: 1 0 0 4
: 1 0 1 5
: 1 1 0 6
: 1 1 1 7
|
i*******s
发帖数: 558 | 66 No need to go to DP. If you know the start position in the matrix, it's o(n)
simple scan once, n is the length of string.
【在 g***s 的大作中提到】
: define
: f(x,y,z) x,y means the position in the matrix
: z means the right z-length sub string of orig search string.
: f(x,y,z) true if from x,y, we can find the right z-length sub string of
: orig search string; otherwise false
: t(z) means the z-th char from the right.
: f(x,y,z) =
:
: f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
: f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||
|
h*******n
发帖数: 357 | 67
三只都没死的话，不就是第0瓶有毒。。。
【在 C***y 的大作中提到】
: 如果第0瓶有毒的话？
: 哪只老鼠死？
: 还是你有个附加条件，肯定有瓶是有毒的?
|
g***s
发帖数: 3811 | 68 不觉得能有O(k)的解即使给定你一个点作为开始点。k is the length of string.
o(n)
【在 i*******s 的大作中提到】
: No need to go to DP. If you know the start position in the matrix, it's o(n)
: simple scan once, n is the length of string.
|
i*******s
发帖数: 558 | 69 There IS O(k) solution obviously. If starting point is unknown, then it's O(
m)
+ (k), where m is the number of elements in the matrix.
【在 g***s 的大作中提到】
: 不觉得能有O(k)的解即使给定你一个点作为开始点。k is the length of string.
:
: o(n)
|
g***s
发帖数: 3811 | 70 说来听听。
it's O(
【在 i*******s 的大作中提到】
: There IS O(k) solution obviously. If starting point is unknown, then it's O(
: m)
: + (k), where m is the number of elements in the matrix.
|
|
|
g***s
发帖数: 3811 | 71 肯定不能有O(k)的解.我可以给出反例。
要不就是你理解题目有问题了。贪心在这里是不对的。
it's O(
【在 i*******s 的大作中提到】
: There IS O(k) solution obviously. If starting point is unknown, then it's O(
: m)
: + (k), where m is the number of elements in the matrix.
|
z**c
发帖数: 625 | 72 是O(4^N)吧?
n)
【在 i*******s 的大作中提到】
: No need to go to DP. If you know the start position in the matrix, it's o(n)
: simple scan once, n is the length of string.
|
i*******s
发帖数: 558 | 73 The abcd matrix example shows the matrix elements are unique, so greedy is
fine. Let me know your counter example. The original post doesn't say
replicates in the matrix.
【在 g***s 的大作中提到】
: 肯定不能有O(k)的解.我可以给出反例。
: 要不就是你理解题目有问题了。贪心在这里是不对的。
:
: it's O(
|
g***s
发帖数: 3811 | 74 题目我给的只是一个简单的例子而已。里面当然可以有重复。
给一个例子
n*n, 所有左下半部(包括对角线）全是a，坐标（2，n)是b。右上全是c。
a b c .... c
a a c .... c
a a a c ... c
...
a a a a ....a
字符串是 aaa..ab (n个a）。起点是（1，1).
greedy is
【在 i*******s 的大作中提到】
: The abcd matrix example shows the matrix elements are unique, so greedy is
: fine. Let me know your counter example. The original post doesn't say
: replicates in the matrix.
|
j********x
发帖数: 2330 | 75 这是经典的问题，不是G家发明的。。。
【在 T*o 的大作中提到】
: 原来2是google的题啊，经典题啊。
|
