Magical String

字符串里有神奇性质的真多。这个是类似于count and say的一个字符串，这类字符串都有个特性，都是‘0’ 与‘1’构成的字符串。

• 这道题可以以“122”为seed，生成字符串。

• 开始时p＝2，“122”＝＝》“122（11）”；p＋＋后再次指向1，“12211”＝＝》“122112”

• 每次新加的数字和上一次不同，取决于末尾元素。

• 数量取决于p的值。

public class Solution {
    public int magicalString(int n) {
        StringBuilder sb = new StringBuilder("122");
        int p = 2;
        while(sb.length()<n){
            char c = sb.charAt(p++);
            int count = (int)(c-'0');
            c = sb.charAt(sb.length()-1)=='1'?'2':'1';
            for(int j=0;j<count;j++) sb.append(c);
        }
        int ans = 0;char[] arr = sb.substring(0,n).toString().toCharArray();
        for(char c : arr)
            ans+=c=='1'?1:0;
        return ans;
    }
}

Count and Say

很类似的一道题，建立一个get next的函数，用最直观的逻辑就可以。

1.     1
2.     11
3.     21
4.     1211
5.     111221

public class Solution {
    public String countAndSay(int n) {
        if(n<=0) {
        return "";
        }
        String nowStr = "1";
        for(int i=1;i<n;i++)
            nowStr = getNext(nowStr);
        return nowStr;
    }

    public String getNext(String str){
        int count = 0; StringBuilder sb = new StringBuilder();
        for(int i=0;i<str.length();i++){
            count++;
            if(i+1==str.length() || str.charAt(i)!=str.charAt(i+1)){ //key point: i+1==str.length() reach to end
                sb.append(count).append(str.charAt(i));
                //if(i+1<str.length())
                    count = 0;
            }
        }
        return sb.toString();
    }
}

Number of Digit One

一开始撸了一个DFS，一边生成字符串一边统计字符，注意起始位为0的数字只能用于生成下一轮数字，不能用于统计，36/40后TLE

public class Solution {
    int count = 0;
    public int countDigitOne(int n) {
        if(n<=0) return 0;
        String s = n+"";
        dfs(0, s, "", 0);
        return count;
    }

    public void dfs(int start, String s, String cur, int curCount){
        //System.out.println(cur+ " " + curCount);
        if(start==s.length()){
            if(cur.compareTo(s)<=0&&cur.charAt(0)!='0')
                count+=curCount;
            return;
        }
        if(cur.length()>0 && cur.charAt(0)!='0') count+=curCount;
        for(int i=0;i<=9;i++){
            if(i==1)
                dfs(start+1, s, i+cur, curCount+1);
            else
                dfs(start+1, s, i+cur, curCount);
        }
    }
}

数学推倒每位有多少个1，和一些corner case，得到的解。

public class Solution {
    public int countDigitOne(int n) {
  int count = 0;

  for (long k = 1; k <= n; k *= 10) {
    long r = n / k, m = n % k;
    // sum up the count of ones on every place k
    count += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
  }

  return count;
}
}

Keyboard Row

大水题，注意arraylist转string[]的时候需要ans.toArray(new String[0])声明类型。