Share my Java Solution Using LinkedList/Deque


  • 0
    J

    I view the problem like this:
    1 2 2 1 1 2 1 2 2
    1 22 11 2 1 22 1 22 11

    After the third element there is no overlap between the first line and second line.
    So we can maintain a deque so that the first element will decide how many times(1 or 2) to add the new element and the last element will decide which element to be added(3 - last).
    Here is the code:

    public class Solution {
        public int magicalString(int n) {
            if(n <= 0) return 0;
            if(n<=3) return 1;
            int ret = 1;
            LinkedList<Integer> q = new LinkedList<Integer>();
            n-=2;
            q.offer(2);
            while(n>1){
                int nextNum = 3 - q.getLast();
                int t = q.poll();
                while(t>0 && n>1){
                    q.offer(nextNum);
                    n--;t--;
                    if(nextNum == 1) ret+=1;
                }
            }
            return ret;
        }
    }
    

Log in to reply
 

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