请教L家新面经题，种花 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教L家新面经题，种花

请教L家新面经题，种花# JobHunting - 待字闺中

y*e2015-04-08 07:04

1 楼

题目从一亩看来的：
public boolean canPlaceFlowers(List flowerbed, int numberToPlace)
如果flowerbed当中为true，说明已经栽过花了，附近两个不能再栽花。numberToPlace
代表想再栽多少花到flowerbed里。让return是不是还能栽那么多谢花进去。.
这个应该是说如果flowerbed是true false false false false, 那么在Index = 3种一朵
这题是不是用greedy解就行啊？看到一个可以种花的spot就种, 然后decrement
numberToPlace, 如果到最后numberToPlace > 0，那就不能种。。。
还是需要用DP啊？来一个dp(startPos, flowerLeft), 每一步选择种或者不种？

d*c2015-04-08 07:04

2 楼

这个不就是bad neighbor的变种吗？
比bad neighbor还要简单一点。

numberToPlace
一朵

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

: 题目从一亩看来的：
: public boolean canPlaceFlowers(List flowerbed, int numberToPlace)
: 如果flowerbed当中为true，说明已经栽过花了，附近两个不能再栽花。numberToPlace
: 代表想再栽多少花到flowerbed里。让return是不是还能栽那么多谢花进去。.
: 这个应该是说如果flowerbed是true false false false false, 那么在Index = 3种一朵
: 这题是不是用greedy解就行啊？看到一个可以种花的spot就种, 然后decrement
: numberToPlace, 如果到最后numberToPlace > 0，那就不能种。。。
: 还是需要用DP啊？来一个dp(startPos, flowerLeft), 每一步选择种或者不种？

i*h2015-04-08 07:04

3 楼

bad neighbor是什么题？有link不？

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

: 这个不就是bad neighbor的变种吗？
: 比bad neighbor还要简单一点。
:
: numberToPlace
: 一朵

d*c2015-04-08 07:04

4 楼

leetcode 就有，最近出得，不过最原始的是topcoder。
http://community.topcoder.com/stat?c=problem_statement&pm=2402&

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

: bad neighbor是什么题？有link不？

h*o2015-04-08 07:04

5 楼

就是greedy 这样吧，能种就种，不能种往下找，没感觉有什么tricky的地方

numberToPlace
一朵

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

i*h2015-04-08 07:04

6 楼

多谢

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

: leetcode 就有，最近出得，不过最原始的是topcoder。
: http://community.topcoder.com/stat?c=problem_statement&pm=2402&

y*e2015-04-08 07:04

7 楼

你说的是house robber吧。。。那个是求max，应该上DP的，这个问题问can/can't, 我
觉得用greedy就可以。。不知思路对不对，所以来问问大家。。。

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

: 这个不就是bad neighbor的变种吗？
: 比bad neighbor还要简单一点。
:
: numberToPlace
: 一朵

i*h2015-04-08 07:04

8 楼

用greedy就可以了

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

: 你说的是house robber吧。。。那个是求max，应该上DP的，这个问题问can/can't, 我
: 觉得用greedy就可以。。不知思路对不对，所以来问问大家。。。

b*i2015-04-08 07:04

9 楼

感觉greedy是对的，推理如下：
1. 原始的flowerbed总可以分成一些可以种植的连续的0的区域，比如
[1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0]
这个里面就有四片连续的0的区域可以种植： [0], [0], [0 0 0], [0]
这些是去掉了1旁边的0的。
2. 在连续的0的区域里面种，greedy就是最优的。

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

: 你说的是house robber吧。。。那个是求max，应该上DP的，这个问题问can/can't, 我
: 觉得用greedy就可以。。不知思路对不对，所以来问问大家。。。