Straightforward Java Solution with explanation


  • 1

    The method is quite simple using two points:

    1, create a boolean[] and initialize the first three(the reason initializing first three is to avoid tail and head overlap)
    2, if tail is 2, add two identical item which is different from current head
    3, if tail is 1, add 1 different.
    4, since it is 1 or 2, just use boolean (1: true, 2: false) to replace int
    

    Here is the code:

    public class Solution {
        public int magicalString(int n) {
            // o(n)
            if (n == 0) return 0;
            if (n < 3) return 1;
            int head = 3;
            int tail = 2;
            boolean[] nums = new boolean[n];
            //1:true 2: false
            nums[0] = true;
            nums[1] = false;
            nums[2] = false;
            int res = 0;
            while (head < n) {
                if (!nums[tail]) {
                    nums[head] = !nums[head-1];
                    head++;
                    if (head < n) {
                        nums[head] = nums[head-1];
                        head++;
                    }
                } else {
                    nums[head] = !nums[head-1];
                    head++;
                }
                tail++;
            }
            for(boolean b: nums) {
                if (b) res++;
            }
            return res;
        }
    }
    

  • 0
    R

    Awesome solution! If you use a temp variable and increment it when the value - num[head] is true then the last step to traverse is not required and the algorithm becomes faster.


Log in to reply
 

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