38. Count and Say

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.

思路:刚开始被这题绕了好久,后来发现就是个循环计数问题。

1 可以被读作 “1个1″, 也就是 11

11可以被读作 “2个1″, 也就是 21

21可以被读作”1个2,1个1″,也就是 1211

依次类推….

大概要解决的问题有2个,如何找到第n次的读数结果,可以拆分为:

  1. 那么对于给定的n,我们要找到第n次结果,那总共就要做n-1次的读数。可以用一个循环来解决
  2. 我们在读每个数的时候,要查下前几位跟后一位是否相同,读数的结果就是: 这个数出现的次数 + 这个数的数值本身。 我们在做的时候需要用指针来判断前后两个数是否相同,并用变量count来记录出现的次数
  1. 每次读完一个数生层的读数结果,要临时保存下来,给下次读数计算使用。 所以我们需要个临时中间变量来保存。
public class Solution {
    public String countAndSay(int n) {
        if (n <= 1) return "1";
        String oldStr = "1";
        for (int i = 0; i < n - 1; i++) {
            int count = 1;
            String tmp = "";
            for (int j = 1; j < oldStr.length() + 1; j++) {
                if (j < oldStr.length() && oldStr.charAt(j) == oldStr.charAt(j - 1)) {
                    count++;
                } else {
                    tmp += String.valueOf(count) + oldStr.charAt(j - 1);
                    count = 1;
                }
            }
            oldStr = tmp;
        }

        return oldStr;
    }
}

几个注意的细节:
1. 读数的时候指针以j-1为主,我们循环的从1 -> oldStr的长度 + 1
2. n<=1的情况都返回"1"

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s