MagicalString [source code]

public class MagicalString {
static
/******************************************************************************/
class Solution {
    public int magicalString(int n) {
        if (n <= 0)
            return 0;
        String cur = "2";
        if (n <= 3)
            return 1;
        n -= 3; //n as then number of digits short
        int res = 1;
        while (n > 0) {
            Result next = buildNext(cur, 3 - Character.getNumericValue(cur.charAt(cur.length() - 1)), n);
            n -= next.str.length();
            res += next.numOne;
            cur = next.str;
        }
        return res;
    }

    public Result buildNext(String numAr, int head, int len) {
        StringBuilder sb = new StringBuilder();
        char[] chs = numAr.toCharArray();
        int countOne = 0;
        for (char c : chs) {
            int count = Character.getNumericValue(c);
            for (int i = 0; i < count; i++) {
                sb.append(head);
                if (head == 1)
                    countOne++;
                if (--len == 0)
                    return new Result(sb.toString(), countOne);
            }
            head = 3 - head;
        }
        return new Result(sb.toString(), countOne);
    }

    static class Result {
        String str;
        int numOne;

        public Result(String s, int n) { str = s; numOne = n; }
        public String toString() { return String.format("(\"%s\",%d)", str, numOne); }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MagicalString.Solution tester = new MagicalString.Solution();
        int[] inputs = {
            6, 3,
            7, 4,
            0, 0,
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int n = inputs[2 * i];
            int ans = inputs[1 + 2 * i];
            System.out.println(Printer.separator());
            int output = tester.magicalString(n);
            System.out.println(
                Printer.wrapColor(n, "magenta") +
                " -> " + output +
                Printer.wrapColor(", expected: " + ans, ans == output ? "green" : "red")
                );
        }
    }
}

这个问题看到的第一印象是, 要有一个避免overkill的心思, 因为这里最后要输出的是1的个数, 而不是这个string本身, 所以这个问题最后是有可能出现有一个算法能够less general but faster的, 理论上来说;

想的时间越长越感觉这个题目有什么巧妙的办法, 不需要做出完整的string, 不过暂时有点想不出来; 先尝试用笨办法, 人逻辑来construct string看看;

这个string是可以用一个类似Bottom-Up DP的思路来做出来的, 但是这个DP算法的设计逻辑好像比普通的DP要麻烦很多; 虽然知道了怎么用人逻辑来做这个computation, 但是转化成代码感觉会很麻烦; 这个问题当时读题的时候就感觉有点抖豁, 题目本身太通俗了, 最后往往这样的题目, 在找computation model的时候也格外困难;

最后居然阴差阳错的还是写出来了, 速度是33ms (24%), 不太好; 因为我这个做法实际上是把整个string都build出来了, 所以是有一点overkill的嫌疑的;

我这个做法大概的思路就是分析了人逻辑发现这个string是可以分成一块一块的; 所以用一个变量cur来iterate, 一块一块的向右移动. 一个难点是我们最后这个n可能落在最后一块的中间; 而越到后面的block, 长度会越大, 所以专门重新在最后一个block上再专门来扫一次1, 不太合适; 当然这个问题最后解决起来也不困难, 直接在build函数上稍微修改一下就行了;

虽然我这个解法不是最优解, 不过思考的过程还是很有收获; 我这个解法就是属于, 如果理解了算法本身大意上面的逻辑, 就是设计好怎么实现就行了;

另外注意Empty Case, 这个也是Google的老强项了; 当然, 无论是哪个公司, 只要题目没有给你assertion, 你就有义务检查invalid input;

感觉这个题目还是很有可能有一个pattern解法的, 虽然未必有NimGame那样那么彻底的pattern解法, 但是很大可能会有一个能够利用pattern简化computation的解法;

另外, 这个题目的downvote非常高. 我还没有看discussion的解法, 不过我认为如果是使用这个正经的解法的话, 这个题目还是挺值得训练的啊;

这个是discussion最优解, 思路其实还是有点类似, 最后还是要把整个string都generate出来; 这个算法其实也是一个很聪明的算法, 所以我格外不懂为什么这个问题downvote会这么多;

@shawngao said in Simple Java solution using one array and two pointers:

Algorithm:

1. Create an int array a and initialize the first 3 elements with 1, 2, 2.
2. Create two pointers head and tail. head points to the number which will be used to generate new numbers. tail points to the next empty position to put the new number. Then keep generating new numbers until tail >= n.
3. Need to create the array 1 element more than n to avoid overflow because the last round head might points to a number 2.
4. A trick to flip number back and forth between 1 and 2: num = num ^ 3

public class Solution {  
    public int magicalString(int n) {  
        if (n <= 0) return 0;  
        if (n <= 3) return 1;  

        int[] a = new int[n + 1];  
        a[0] = 1; a[1] = 2; a[2] = 2;  
        int head = 2, tail = 3, num = 1, result = 1;  

        while (tail < n) {  
            for (int i = 0; i < a[head]; i++) {  
                a[tail] = num;  
                if (num == 1 && tail < n) result++;  
                tail++;  
            }  
            num = num ^ 3;  
            head++;  
        }  

        return result;  
    }  
}

他这个算法就是利用了一个快慢指针的思路; 我的做法是一个block一个block的build, 他这个做法是直接一个number一个number的做; 总体来说思路也是对的, 而且实现起来也方便; 时间方面, 我感觉他这个应该比我快一倍; 我的算法应该也是O(N)的时间, 但是是他这个的两倍: 因为我每一个block其实是被扫了两遍的;

另外, 关于flip的一个总结:

@zzg_zzm said in Simple Java solution using one array and two pointers:

To flip x between any two given values x1 and x2, I think using x = x1 + x2 - x is more straightforward (as long as no overflow).

一个类似的做法, 不过naive一点:

@Jerry said in Simple Java solution using one array and two pointers:

My solution is naive: https://en.wikipedia.org/wiki/Kolakoski_sequence
Using a pointer to point the repeat times number. If it is 1, no repeat, if it is 2, add two repeat number to the result list.

1 and 2 are appear one by one, so using num = num ^ 3.

    public int magicalString(int n) {  
      List<Integer> nums = new ArrayList();  
      nums.add(1);  
      nums.add(2);  
      nums.add(2);  
      int repIndex = 2, i = 3, num = 1, res = 0;  
      while(i < n){  
         int repeat = nums.get(repIndex);  
         repIndex++;  
         if(repeat == 1) {  
             addOne(nums, num);  
             i++;  
         } else {  
             addTwo(nums, num);  
             i += 2;  
         }  
         num ^= 3;  
      }  

      for(i = 0; i < n; i++){  
        if(nums.get(i) == 1) res++;    
      }  
      return res;  
    }  

    void addOne(List<Integer> nums, int num){  
      nums.add(num);        
    }  

    void addTwo(List<Integer> nums, int num){  
      nums.add(num);    
      nums.add(num);   
    }

这个是另外一个跟这个思路非常类似的解法:

public int magicalString(int n) {  
    StringBuilder magic = new StringBuilder("1221121221221121122");  
    int pt1 = 12, pt2 = magic.length(), count = 0; //initiate pointers  
    //generate sequence directly  
    while(magic.length() < n){  
        if(magic.charAt(pt1) == '1'){  
            if(magic.charAt(pt2-1) == '1') magic.append(2);  
            else magic.append(1);  
            pt2++;  
        }else{ //==2  
            if(magic.charAt(pt2-1) == '1') magic.append(22);  
            else magic.append(11);  
            pt2+=2;  
        }  
        pt1++;  
    }  
    for(int i=0;i<n;i++)  
        if(magic.charAt(i)=='1') count++;  
    return count;  
}

关于这个magical string的唯一性:

@zzg_zzm said in Simple Java solution using one array and two pointers:

@jh2016 said in Simple Java solution using one array and two pointers:

why must start 1,2,2?

I wonder whether there is magical string start from 2,2,1,1,2,1,2,2...

I got your point. Actually, the magic string S is uniquely determined by only the first char S[0] (either '1' or '2'). Either case gives a well defined problem, but they are "logically" duplicated problem, so OJ just simply picked the case S[0] = 1 to define as magic string. The method to solve "the other" magic string will be duplicated anyway.

Hopefully, it will help.

我一开始以为, 是开头的三个122才能够唯一定义这个string, 不过看他这里写了之后想了一下, 好像只要第一个就行了: 如果第一个是2, 这个是很自然的; 如果第一个是1, 其实也是很自然的, 虽然这个1 count的是自己, 但是根据交替的规律, 下一个肯定是2(如果是1, 那么[0]就不可能是1: 没有count完);

另外, 上面那个算法, 其实对于最后一个run, 也就是最后一个count如果全部generate出来之后超过n的情况是怎么处理的? 是在count 1的时候加了一个tail < n的条件, 这样假如最后一个count非常大, 那么其实是浪费了很多时间做无用功的. 另外一个做法是这样:

public class Solution {  
    public int magicalString(int n) {  
        if (n <= 0) {  
            return 0;  
        }  
        if (n <= 3) {  
            return 1;  
        }  

        int[] a = new int[n];  
        a[0] = 1; a[1] = 2; a[2] = 2;  
        int head = 2, tail = 3, num = 1, result = 1;  
        while (tail < n) {  
            for (int i = 0; i < a[head] && tail < n; i++) {  
                a[tail] = num;  
                if (num == 1) {  
                    result++;  
                }  
                tail++;  
            }  
            num = num ^ 3;  
            head++;  
        }  

        return result;  
    }  
}

这样, 在generate最后一个count的时候, 如果我们还没有generate完就已经到达n了, 直接停止就行了;

另外他们这一路快慢指针的思路虽然比我的快一倍, 但是他们的空间复杂度很差. 我的方法因为不维护整个string(一定程度上, 相比于他们的这个做法, 有一点avoid overkill的意思了?), 最后空间复杂度要好很多;

一个减少了nested loop的做法:

@Pharmacist-Hwang said in Simple Java solution using one array and two pointers:

Good post, I like the idea to represent the characters with int array, and flip between 1 and 2 with XOR. x = x1 + x2 - x is also very good idea.

As I want to avoid the nested loop, I used the algorithm below:

int magicalNaive (int n) {  
        string magical;  
        magical.append("122");  
        char next = '1';  
        // the position in magical that act as a recurrence count   
        int cntIdx = 2;  
        int cnt = 2;  
        // '1' count in magical string   
        int ret = 1;  
        for (int i = 3; i < n; i++) {  
            if (cnt == 0) {  
                cnt = magical[++cntIdx] - '0';  
                next = next == '1' ? '2' : '1';  
            }  

            // push in next to magical top   
            ret += next == '1';  

            magical.push_back (next);  
            cnt--;  
        }  

        return n < 1 ? 0 : ret;  
    }

大体思路是一样的, cnt变量每一个iteration都在更新, 只有cnt到0的时候, 我们才重新fetch一个新的count(移动慢指针);

有一个问题, 我自己的这个解法, 虽然不维护完整的string, 但是空间复杂度是多少? 一个简单的分析是, O(N/2), 因为每一个string最多(WorstCase)可能是上一个string的两倍长度, 所以就类似一个BST, 最后一个string就类似于BST里面leaf level的node的个数, 是N/2; 但是感觉这个bound好像并不是特别tight?

这个是Stefan写的一个非常复杂的解法, 他认为这个解法的空间复杂度是lgN:

public class Solution {  

    public int magicalString(int n) {  
        if (n == 0) return 0;  
        int ones = 1;  
        n -= 2;  
        Lakoski lakoski = new Lakoski();  
        while (n-- > 0)  
            if (lakoski.next() == 1)  
                ones++;  
        return ones;  
    }  

    private class Lakoski {  
        private int number = 2;  
        private boolean again = false;  
        private Lakoski source;  
        int next() {  
            if (again)  
                again = false;  
            else if (source == null)  
                source = new Lakoski();  
            else {  
                number ^= 3;  
                again = source.next() == 2;  
            }  
            return number;  
        }  
    }  
}

这个版本是他已经改进过的版本(跳过了最开始的两个element), 他一开始没有改进过的版本太慢了; 这个改进版本最后达到的速度是19ms, 算是不错的了;

这个是他个人的解释和未改进版本:

@StefanPochmann said in O(log n) space Java:

Based on my Python solution. Here I use a helper class giving me the Kolakoski sequence (that's its name) one element at a time with its next method. It has the first three elements hard-coded, and after that, it uses another instance of the sequence to iterate further. That other instance does the same, so it might eventually use yet another instance. And so on, O(log n) nested Kolakoski objects iterating in parallel at different speeds as needed. Takes O(log n) space and O(n) time.

public class Solution {  

    public int magicalString(int n) {  
        Kolakoski kolakoski = new Kolakoski();  
        int ones = 0;  
        while (n-- > 0)  
            if (kolakoski.next() == 1)  
                ones++;  
        return ones;  
    }  

    private class Kolakoski {  
        private int[] queue = {1, 2, 2};  
        private int first = 0, last = 2;  
        private Kolakoski source;  
        int next() {  
            if (first > last) {  
                if (source == null) {  
                    source = new Kolakoski();  
                    source.next();  
                    source.next();  
                }  
                int output = queue[last % 3] ^ 3;  
                for (int k = source.next(); k > 0; k--)  
                    queue[++last % 3] = output;  
            }  
            return queue[first++ % 3];  
        }  
    }  
}

他这个算法的根据好像是一个什么paper, 这个paper的出处在他的Python解法的帖子里面有;

我刚开始看到他标题提到空间节省的时候, 以为他用的是类似我的方法, 但是看了一下, 好像不太像?

这个算法相当复杂, 尤其是未改进版本, 看了好久还是有点看不懂;

首先看一下他这个class, 大概意思就是一个类似LinkedList的结构, 所以自己打草稿画图的时候, visual可以就画的跟LinkedList那种结构有点类似:

(2,F) -> (1,T) -> ...

括号(node)里面写的就是instance var(except for the pointer);

画了几个trace还是有点看不懂, 暂时不看了;

又重新瞄了一眼他之前提到的那个paper, 好像知道了一点意思; 等有时间看这个paper之后再来看这个算法到底是什么意思;

Problem Description

A magical string S consists of only '1' and '2' and obeys the following rules:

The string S is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string S itself.

The first few elements of string S is the following: S = "1221121221221121122……"

If we group the consecutive '1's and '2's in S, it will be:

1 22 11 2 1 22 1 22 11 2 11 22 ......

and the occurrences of '1's or '2's in each group are:

1 2 2 1 1 2 1 2 2 1 2 2 ......

You can see that the occurrence sequence above is the S itself.

Given an integer N as input, return the number of '1's in the first N number in the magical string S.

Note: N will not exceed 100,000.

Example 1:

Input: 6  
Output: 3  
Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.

Difficulty:Medium
Total Accepted:9.5K
Total Submissions:20.8K
Contributor: DonaldTrump
Companies
google