Short Python using queue


  • 2

    Since how many current "1" or "2" depends on previous number in S, we can use a queue to get the corresponding information we need. Every time we update S, we update queue as well.

    Updated: based @StefanPochmann 's idea, we can only use an index to indict current number of value we need.

    class Solution(object):
        def magicalString(self, n):
            """
            :type n: int
            :rtype: int
            """
            S = [1,2,2]
            idx = 2
            while len(S) < n:
                S += S[idx] * [(3 - S[-1])]
                idx += 1
            return S[:n].count(1)
    

    Old version:

    class Solution(object):
        def magicalString(self, n):
            """
            :type n: int
            :rtype: int
            """
            queue = collections.deque([2])
            S = [1,2,2]
            while len(S) < n:
                k = queue.popleft()
                tmp = 3 - S[-1]
                for i in range(k):
                    S.append(tmp)
                    queue.append(tmp)
            return S[:n].count(1)
    

  • 3

    Good idea, using a list of ints instead of a string. Makes working with the digits easier. No need for the additional queue, though:

    def magicalString(self, n):
        S = [1, 2, 2]
        i = 2
        while len(S) < n:
            S += S[i] * [3 - S[-1]]
            i += 1
        return S[:n].count(1)
    

    Or if we don't mind being a bit wasteful:

    def magicalString(self, n):
        S = [1, 2, 2]
        for i in range(2, n):
            S += S[i] * [3 - S[-1]]
        return S[:n].count(1)

  • 0

    @StefanPochmann You're right. Quite excited to read your comment actually. It is the 6th month since I decided to learn CS myself and I always learned a lot from your post. Hope someday I can be as good as you, :)


  • -1
    S

    @StefanPochmann I am learning CS ,too. But I have difficulty in solving the problem like this one. I fail to find the trick. How can I improve myself.


Log in to reply
 

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