Java Two Solutions: String-Based(Slow) and Array-Based(fast)


  • 0

    The solution in the editorial article does something essentially like counting 000 runs.

    The two solutions I used can both be extended to solve a broader category of problems: paragraph splitting, or run counting. Although for this particular problem, they are not the optimal solutions, since they do use extra space.

    In this problem, we just have to go 1pass, and find the all the consecutive 0 runs, then process each run's length to get the number of flowers such a run can support:

    1. for 0 and 00, supports no flowers. for 000 and 0000, we subtract 2 from the len, and we can calculate the number of flowers supported:
    len - 2 <= 0 -> no flowers
    len - 2 == 1 -> 1 flower
    len - 2 == 2 -> 1 flower
    len - 2 == 3 -> 2 flowers
    len - 2 == 4 -> 2 flowers
    ...
    
    1. for a zero at the head or end of the whole bed, we add one to len since they are like spots where we have an open end, which is just a 0 on the other side. For example: [0]01 and 10[0]01 supports the same number of flowers and the bracketed 0 are actually equivalent.

    In the code below I do not try to reduce the verbosity but feel free to do so if you are into that.

    String-based version (not fast, 28ms@20170715)

    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;
        }
    }
    

    Array-based version (same speed as the editorial solution (without the premature exit test) 12ms@20170715)

    public class Solution {
        public boolean canPlaceFlowers(int[] flowerbed, int n) {        
            int sum = 0, run = 0, len = flowerbed.length;
            boolean inRun = true;
            for (int i = 0; i < len; i++) {
                if (inRun && flowerbed[i] == 1) {
                    sum += run - 2 <= 0 ? 0 : ((run - 2 - 1) / 2 + 1);
                    run = 0;
                } else if (!inRun && flowerbed[i] == 0) {
                    run++;
                    inRun = true;
                } else if (inRun && flowerbed[i] == 0) {
                    run++;
                    if (i == 0) run++;
                    if (i == len - 1) {
                        run++;
                        sum += run - 2 <= 0 ? 0 : ((run - 2 - 1) / 2 + 1);
                    }
                } 
            }
            return n <= sum;
        }
    }
    

    This array-based solution can be extended to solve most problems that requires paragraph delimiting.

    Hope this more or less helps.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.