CanPlaceFlowers [source code]

public class CanPlaceFlowers {
static
/******************************************************************************/
public class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i : flowerbed) sb.append(i);
        String str = sb.toString();
        String[] runs = str.split("1");
        if (flowerbed[0] == 0) runs[0] += "0";
        if (flowerbed[flowerbed.length - 1] == 0) runs[runs.length - 1] += "0";
        int[] runLens = new int[runs.length];
        for (int i = 0; i < runs.length; i++) {
            int len = runs[i].length();
            if (len == 0) continue;
            runLens[i] = len - 2 <= 0 ? 0 : ((len - 2 - 1) / 2 + 1) ; //可以简化, 不过这样写提醒自己逻辑
        }
        int sum = 0;
        for (int i : runLens) sum += i;
        return n <= sum;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        CanPlaceFlowers.Solution tester = new CanPlaceFlowers.Solution();
        int[][] inputs = {
            {1,0,0,0,0,1}, {2}, {0},
            {1,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1}, {7}, {0},
            {1,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1}, {5}, {1},
            {1,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1}, {6}, {1},
            {0,0,1,0,1}, {1}, {1},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[] flowerbed = inputs[3 * i];
            int n = inputs[1 + 3 * i][0];
            boolean expected = inputs[2 + 3 * i][0] == 1;
            Printer.openColor("magenta");
            System.out.print(Printer.array(flowerbed) + " AND " + n);
            Printer.closeColor();
            boolean res = tester.canPlaceFlowers(flowerbed, n);
            System.out.print(" -> " + res);
            Printer.openColor(res == expected ? "green" : "red");
            System.out.println(", expected : " + expected);
        }
    }
}

数0run 的话我这里还是先用 string 做一个, 然后后面 ver2尝试用数组做一下;

这里有一个小坑:

java> "100001".split("1")  
java.lang.String[] res2 = ["", "0000"]

这个在开头居然会split出来一个空的, 所以可以看到split并不是一个像你想象中那么好用的随心所欲的那种split, 而是把这个seperator当做是一个休止符一样的东西: 一旦碰到它, 立刻处理之前的run, 所以这里第一个1之前才会有一个empty run;

Problem Description

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True
Example 2:
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False
Note:
The input array won't violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won't exceed the input array size.
Difficulty:Easy
Total Accepted:9.3K
Total Submissions:31.1K
Contributor: fallcreek
Companies
linkedin
Related Topics
array
Similar Questions
Teemo Attacking