1.25 Google 加面跪经

farm 发表于 2016-1-27 05:44
想问一下，你是怎么在HackerRank上看到这道题的啊？
HackerRank的题目可以搜么？还是只能是random的chal ...

之前我朋友參加的challenge，找我支援的時候看到的。應該還是搜得到，剛剛試過，Google: "hackerrank magic string"就找得到了

这题好难，求hint

是不是可以从她给出的Magic string 开始结合count string继续生成？ query 不就是遍历吗？难道有trick？

问题生成的速度比原串要慢，怎么能生成下去啊。。。。

生成倒是不难。如果已生成长为len的序列，query也不难。但是，如果follow up是问你在不生成magic序列的情况下，仅用O(1)时间（或者最起码是sublinear时间）完成query，有没有可能做出来呢？

补一个生成magic string的代码：

string getMagicString(int len) {
    string res(len, '1');
    if (len < 2) return res;
    res[1] = '2';

    int iCount = 1, iStr = 1; // Pointers in the 'count' and 'string' sequence
    char curChar = '2', nextChar = '1';
    while (iStr < len) {
        int count = res[iCount++] - '0'; // Get the current count;
        for (int i = 0; i < count; ++i) { // Append to the ‘string’ sequence
            res[iStr++] = curChar;
            if (iStr == len) break;
        }
        swap(curChar, nextChar);    // Flip the current character, e.g. '1'->'2'
    }
    return res;
}

Good code 如果可以用extra memory的话 生成magic string 同时就建一个count array。但是我觉得Magic string 本身就是count 不知道怎么用这个特性。

stellari 发表于 2016-1-27 19:58
生成倒是不难。如果已生成长为len的序列，query也不难。但是，如果follow up是问你在不生成magic序列的情况 ...

懂了，反过来generate。。。思维定势了。。。谢谢

stellari 发表于 2016-1-27 19:58
生成倒是不难。如果已生成长为len的序列，query也不难。但是，如果follow up是问你在不生成magic序列的情况 ...

leetcode discussion区的大神们居然都在混一亩三分地...

stellari 发表于 2016-1-27 19:58
生成倒是不难。如果已生成长为len的序列，query也不难。但是，如果follow up是问你在不生成magic序列的情况 ...

你的code有bug，会生成 “12221.....” 而不是"1221....."

前三个字符应该要特别处理