The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1
is read off as "one 1"
or 11
.11
is read off as "two 1s"
or 21
.21
is read off as "one 2
, then one 1"
or 1211
.Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
题意是
n=1时输出字符串1;
n=2时,数上次字符串中的数值个数,因为上次字符串有1个1,所以输出11;
n=3时,由于上次字符是11,有2个1,所 以输出21;
n=4时,由于上次字符串是21,有1个2和1个1,所以输出1211。
依次类推,写个countAndSay(n)函数返回字符串。
A:
public class Solution { public String countAndSay(int n) { // recursively if (n == 1) { return "1"; } else { String lastStr = countAndSay(n - 1); StringBuffer buf = new StringBuffer(); // use two pointer to check int slowRunner = 0, fastRunner; while (slowRunner < lastStr.length()) { fastRunner = slowRunner; while (fastRunner < lastStr.length()) { if (lastStr.charAt(fastRunner) == lastStr .charAt(slowRunner)) { fastRunner++; }else{ break; } } // now fastRunner point to the next value that //either != slowRunner, or exceed array boundary buf.append( fastRunner-slowRunner); buf.append( lastStr.charAt(slowRunner)); slowRunner = fastRunner; } return buf.toString(); } } }
Mistakes:
1: 当 update fastRunner的时候,当值与slowRunner 不相等的时候,我们要break 该while Loop。 ------------ 开始,就SB, 没有加上。
2:
Learned:
----------------------第一遍是递归调用--------第二遍是-------------DP 建立--------------
public class Solution { public String countAndSay(int n) { // assume n >=1 String lastStr = "1"; StringBuffer buf; for (int i = 2; i <= n; i++) { // DP calculate each layer buf = new StringBuffer(); for (int j = 0; j < lastStr.length(); j++) { char curCh = lastStr.charAt(j); int count = 1; while (j + 1 < lastStr.length() && lastStr.charAt(j + 1) == curCh) { count++; j++; } buf.append("" + count + curCh); } lastStr = buf.toString(); } return lastStr; } }
public class Solution { public String countAndSay(int n) { String res = "1"; for(int i =0; i<n-1;i++) res = helper(res); return res; } private String helper(String str){ StringBuffer buf = new StringBuffer(); int i = 0; while(i<str.length()){ int len=1; while(i+1<str.length() && str.charAt(i)==str.charAt(i+1)){ len++; i++; } buf.append(""+len+str.charAt(i)); i++; } return buf.toString(); } }
No comments:
Post a Comment