由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 别处看到的g家一个画grid的面试题
相关主题
求解一道面试题 snake sequence问一道面试题目
攒人品,google电话面经一道A家面试题 大家讨论看看
看到个面试题,不会做……一道面试题, 挺难的, 求助
rejected by facebook after 2nd phone interviewG家面试题请教
贡献某公司onsite面经这道面试题如何入手?
G家,A家,E 家, H家, E家面筋,赞人品喽~问一道少见的微软面试题。
leetcode word search问一道面试题
问个Google面题贴点面试题
相关话题的讨论汇总
话题: grid话题: dp话题: lifts话题: cost话题: inner
进入JobHunting版参与讨论
1 (共1页)
r*******h
发帖数: 315
1
画给定行数和列数的grid,每次拿起画笔都是有代价的,墨水也有代价,求画一个grid
的最小成本。
自己思考了一下,DP的问题是无法建立一个转移方程,DFS也有问题,可以重复画多长
一段无法确定。
T******7
发帖数: 1419
2
题目太模糊。
C****t
发帖数: 53
3
Assume # of grid points with odd degrees = D, then the minimum # of lifts =
D//2.
In this case, if you have m*n blocks, the number of odd degree points = 2*(m
-1) + 2*(n-1).
The minimum number of lifts should be m+n-2.
For example, you can draw the (m-1) inner horizontal lines first, next you
can draw the inner n-2 vertical lines, the last draw will be the last inner
vertical line + outer boundary.
Totally # of lifts = (m-1) +(n-2) +1
r*******h
发帖数: 315
4
哪里模糊了?求指明

【在 T******7 的大作中提到】
: 题目太模糊。
l****h
发帖数: 1189
5
墨水也有代价。即意味着有的地方可以重画,而不抬笔,是吗?
r*******h
发帖数: 315
6
赞,确实是个很有启发的思路。可以解决如果不重复画block边的情况下的最小cost,
total_cost = min_lifts * cost_per_lift + (2mn + m + n) * ink_cost_per_unit
问题是如果允许重复画block的边,cost_per_lift又比ink_cost_per_unit大太多的情
况下,最小cost就比较难搞了。

=
(m
inner

【在 C****t 的大作中提到】
: Assume # of grid points with odd degrees = D, then the minimum # of lifts =
: D//2.
: In this case, if you have m*n blocks, the number of odd degree points = 2*(m
: -1) + 2*(n-1).
: The minimum number of lifts should be m+n-2.
: For example, you can draw the (m-1) inner horizontal lines first, next you
: can draw the inner n-2 vertical lines, the last draw will be the last inner
: vertical line + outer boundary.
: Totally # of lifts = (m-1) +(n-2) +1

r*******h
发帖数: 315
7
对的,感觉这里也是难点所在,无法简单的标记visited来做backtracking

【在 l****h 的大作中提到】
: 墨水也有代价。即意味着有的地方可以重画,而不抬笔,是吗?
v********o
发帖数: 67
8
在重画cell一条边的cost比抬笔cost低的情况下,可以选择用重画来代替抬笔。
首先考虑把整幅图的四条边界间隔性地重画一遍(每隔一个边界cell重画一条边),这样
就可以整张图中所有点都变成偶度数了。
然后想到一笔画问题可以接受一对奇度数点,还可以留一个cell边不重画,这样总共是
(2(m-1)+2(n-1))÷2-1 = m+n-3次重画,与所需的最小抬笔次数持平。
考虑到每次不得不抬笔的时候至少需要一次重画来挽回,而上面正好达到这一点,这样
是不是就是最小cost了呢?

【在 r*******h 的大作中提到】
: 赞,确实是个很有启发的思路。可以解决如果不重复画block边的情况下的最小cost,
: total_cost = min_lifts * cost_per_lift + (2mn + m + n) * ink_cost_per_unit
: 问题是如果允许重复画block的边,cost_per_lift又比ink_cost_per_unit大太多的情
: 况下,最小cost就比较难搞了。
:
: =
: (m
: inner

b***e
发帖数: 1419
9
这是中国邮路问题的推广。如果提笔的cost 是无穷大的话就退化成中国邮路问题了。

grid

【在 r*******h 的大作中提到】
: 画给定行数和列数的grid,每次拿起画笔都是有代价的,墨水也有代价,求画一个grid
: 的最小成本。
: 自己思考了一下,DP的问题是无法建立一个转移方程,DFS也有问题,可以重复画多长
: 一段无法确定。

r*******h
发帖数: 315
10
谢谢启发。3楼给出的是多笔画无重复的最小成本方案,而你提到的中国邮路问题解决
了一笔画可能有重复的最小成本方案。这两个值可以看作最终答案的上界和下界,对于
有些grid来说,可能存在多笔画有重复的最小成本解。

【在 b***e 的大作中提到】
: 这是中国邮路问题的推广。如果提笔的cost 是无穷大的话就退化成中国邮路问题了。
:
: grid

r*******h
发帖数: 315
11
你的思路有点类似9楼提到的中国邮路问题的无向图解法,需要选择重画的边,不过标
准的解法是找出所有奇度数的点,建立连通图,然后找到可以到达所有点的最小成本边
的集合,这也就是解决一笔画可能会重复的最小代价方案。

【在 v********o 的大作中提到】
: 在重画cell一条边的cost比抬笔cost低的情况下,可以选择用重画来代替抬笔。
: 首先考虑把整幅图的四条边界间隔性地重画一遍(每隔一个边界cell重画一条边),这样
: 就可以整张图中所有点都变成偶度数了。
: 然后想到一笔画问题可以接受一对奇度数点,还可以留一个cell边不重画,这样总共是
: (2(m-1)+2(n-1))÷2-1 = m+n-3次重画,与所需的最小抬笔次数持平。
: 考虑到每次不得不抬笔的时候至少需要一次重画来挽回,而上面正好达到这一点,这样
: 是不是就是最小cost了呢?

C****t
发帖数: 53
12
It is hard to see the relationship between dp(i,j) and dp(x, y) 0<=x<=i, 0<
=y<= j.
Or it might be not feasible to use DP.
s**i
发帖数: 220
13
瞎猜一下:
1) init state:
grid[1,1] = ?;
grid[2,1] = ?;
grid[1,2] = ?;
grid[2,2] = ?;
2) state transfering:
grid[m, n] = min{grid[m-1,n]+Line[m], grid[m, n-1]+line[n],grid[m-1,n-1] +
out border }
l****h
发帖数: 1189
14
感觉似乎不是DP问题。
这个可以往回走的。比如抬笔代价很大的情况,可以有回走的情况。除非能证明所有回
走的情况都可以在代价相同或更小的情况下被前走替代。

【在 s**i 的大作中提到】
: 瞎猜一下:
: 1) init state:
: grid[1,1] = ?;
: grid[2,1] = ?;
: grid[1,2] = ?;
: grid[2,2] = ?;
: 2) state transfering:
: grid[m, n] = min{grid[m-1,n]+Line[m], grid[m, n-1]+line[n],grid[m-1,n-1] +
: out border }

1 (共1页)
进入JobHunting版参与讨论
相关主题
贴点面试题贡献某公司onsite面经
请教一道面试题,判断迷宫有没有解G家,A家,E 家, H家, E家面筋,赞人品喽~
问一道算法题leetcode word search
google 一题问个Google面题
求解一道面试题 snake sequence问一道面试题目
攒人品,google电话面经一道A家面试题 大家讨论看看
看到个面试题,不会做……一道面试题, 挺难的, 求助
rejected by facebook after 2nd phone interviewG家面试题请教
相关话题的讨论汇总
话题: grid话题: dp话题: lifts话题: cost话题: inner