y*****e
发帖数: 712 | 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*****c
发帖数: 605 | 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*****h
发帖数: 1534 | 3 bad neighbor是什么题？有link不？
【在 d*****c 的大作中提到】
: 这个不就是bad neighbor的变种吗？
: 比bad neighbor还要简单一点。
:
: numberToPlace
: 一朵
|
d*****c
发帖数: 605 | 4 leetcode 就有，最近出得，不过最原始的是topcoder。
http://community.topcoder.com/stat?c=problem_statement&pm=2402&
【在 i*****h 的大作中提到】
: bad neighbor是什么题？有link不？
|
h*********o
发帖数: 230 | 5 就是greedy 这样吧，能种就种，不能种往下找，没感觉有什么tricky的地方
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*****h
发帖数: 1534 | |
y*****e
发帖数: 712 | 7 你说的是house robber吧。。。那个是求max，应该上DP的，这个问题问can/can't, 我
觉得用greedy就可以。。不知思路对不对，所以来问问大家。。。
【在 d*****c 的大作中提到】
: 这个不就是bad neighbor的变种吗？
: 比bad neighbor还要简单一点。
:
: numberToPlace
: 一朵
|
i*****h
发帖数: 1534 | 8 用greedy就可以了
【在 y*****e 的大作中提到】
: 你说的是house robber吧。。。那个是求max，应该上DP的，这个问题问can/can't, 我
: 觉得用greedy就可以。。不知思路对不对，所以来问问大家。。。
|
b******i
发帖数: 914 | 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就可以。。不知思路对不对，所以来问问大家。。。
|
z***m
发帖数: 1602 | 10 我的想法是先用DP求给定长度下，包含最多的1的序列such that 没有相邻的1。
然后看给定的flower bed里面的1是不是多余求出来的的最优值(最多的1)，如果没有就
说明可以再种，否则就不能再种 |
