Beat 91% Java solution


  • 1

    Thanks to the paper that @StefanPochmann mentioned in his post. Just as Stefan said, all we need is the graph in page 3. It's really impressive.

    Below is the code beating 91% in Java, well, I first time wanted to write a recursive solution, but ended with stackoverflow.

    public int magicalString(int n) {
            if (n == 0) return 0;
            if (n <= 3) return 1;
            
            int[] arr = new int[n + 1];
            arr[0] = 1; arr[1] = 2; arr[2] = 2;
            
            int head = 2, tail = 3, val = 1, count = 1;
            while (tail < n) {
                if (val == 1) count += arr[head];
                for (int i = 0; i < arr[head]; i++) {
                    arr[tail++] = val;
                }
                head++;
                val ^= 3;
            }
            if (arr[n] == 1) count--;
            return count;
        }
    

  • 0

    This doesn't really have anything to do with that paper or my post, though. They're about solving this with only O(log n) space in a different way. What you're doing is just the standard O(n) space solution.


  • 0

    @StefanPochmann Well, actually I get the idea of solving this question from the graph of that paper... I know your post is about O(logn) space, but what I meant is just the relationship between 1s and 2s I got from that graph.

    When I first saw this question, actually I have no idea how to do it, and I don't want to search for the right answers from other posts directly, so I read the paper you mentioned. That's all. So this has something to do with that paper, maybe not as advanced as your thought.


  • 0

    Ah, ok.

    Anyway... would be interesting to see an O(log n) space solution in languages other than Python. Maybe in Java it could be done nicely with streams?


  • 0

    @StefanPochmann Maybe... I am more than happy to see your Java O(logn) solution... :)

    You know more about Java than me actually :/


  • 1

  • 0

    @StefanPochmann Nice job, man!


Log in to reply
 

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