1.25 Google 加面跪经

import java.lang.Math; // headers MUST be above the first class
import java.util.*;

// one class needs to have a main() method
public class HelloWorld
{
  // arguments are passed using the text field below this editor
  public static void main(String[] args)
  {
    OtherClass o=new OtherClass();
    for(int i=1;i<10;i++){
      System.out.println(o.generateMagicString(i));
  }
  }
}

// you can add other public classes to this editor in any order
public class OtherClass
{
  public String generateMagicString(int len){
    String result="1";
    int currentCount=0;
    int countingPosition=0;
    while(result.length()<len){
      char count=result.charAt(currentCount);
      char countingChar=result.charAt(countingPosition);
      if(count=='1'){
              if(countingChar=='1')
          result+='2';
        else
          result+='1';
        countingPosition++;
      }
      else{
        result+=countingChar;
        if(countingChar=='1')
          result+='2';
        else
          result+='1';
        countingPosition+=2;
      }
      currentCount++;
      
    }
    return result;
  }
}

zhan8803705 发表于 2016-10-5 22:59
你的code有bug，会生成 “12221.....” 而不是"1221....."

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

这段代码对于len >= 4的情况生成的都是1221..., 请实际运行一下. 注意res先被设为'12\0\0\0...', 然后从index=1开始写两个2(也就是会重写已经存在于res[1]处的2, 而并非在res[1]后面加两个2), 于是res就变成'122\0\0...'; 然后就会接着写1-> '12211...'

没想到这个题最近有这么多大神讨论和贡献代码，如果大家觉得lz描述的不太清楚的话可以参考11垅的附件，是一模一样的题～

    public String get_magic_string(int len) {
        int cur = 2;
        if (len < 1) return "";
        String rst = "122";
        int p = 1;
        while (cur <= len) {
            if (rst.charAt(p + 1) == '1' && rst.charAt(cur) == '1') {
                rst += '2';
                cur++;
            } else if (rst.charAt(p + 1) == '1' && rst.charAt(cur) == '2') {
                rst += '1';
                cur++;
            }

            if (rst.charAt(p + 1) == '2' && rst.charAt(cur) == '1') {
                rst += "22";
                cur += 2;
            } else if (rst.charAt(p + 1) == '2' && rst.charAt(cur) == '2') {
                rst += "11";
                cur += 2;
            }


            p++;

        }


        return rst.substring(0, len);
    }

我测试一下20个元素的没错， 我把前三个固定了，从第四个开始生成

stellari 发表于 2016-10-7 05:36
这段代码对于len >= 4的情况生成的都是1221..., 请实际运行一下. 注意res先被设为'12\0\0\0...', 然后从i ...

你这个方法前两位必须是12开头吧，但实际上11111和22222也是magic string

syjohnson 发表于 2016-11-1 03:29
你这个方法前两位必须是12开头吧，但实际上11111和22222也是magic string

请看某楼附件中给出的原题，其中对magic string是这样定义的：The string is magical because because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string S itself.

换句话说，原string如果有X个连续的1或2，count string在相应位置上的值就必须是X。要想原stirng=count string，那么count string中也只能是1或2，换句话说原string中同一数字不可能连续出现超过2次。所以1111...和2222...都不可能是magic string。

stellari 发表于 2016-11-1 11:24
请看某楼附件中给出的原题，其中对magic string是这样定义的：The string is magical because because co ...

怪我不严谨，不过你那个反向构建string的思路真心点赞