38. Count And Say 问题

题目描述

这个 count&say 问题其实没什么难的。
简单说一下就是统计出现的频率。
“11122334” ==> “31222314”
就是说3个1，2个2，2个3，1个4。

自己的方法

从逻辑上来说就是向后遍历，然后比较和后面的元素是否一样，如果一样就 count++， 不一样就直接统计输出；最后一个元素需要特殊考虑一下。

但是问题是，这里最终结果长度是不确定的，一开始想的是用 List<Character> 来存结果，但是这样来说最后是要有类型转换的。最后的类型转换就挺麻烦的。
涉及 List 转换到 Array，使用 List 中的 toArray() 方法，该方法的构造参数接收一个 array 的对象 。

List<String> list =  new ArrayList<>();
String res = list.toArray(new String[list.size()])
// list.toArray() 方法后面

代码

package String;

// 38. Count And Say 可以看到下面的例子，实际上就是在统计每一种出现的频率
//   整体来说这个逻辑是比较简单的，就是一些API不是很熟悉，主要是一些类型转换什么的，所以这个题目用 java 写起来显得比较慢，如果用python的话肯定写的很快。
//      所以这也是为什么要用 java 来做题目的原因，边做边学吧。
// 1.     1
// 2.     11
// 3.     21
// 4.     1211
// 5.     111221
// 6.     312211
// 7.     13112221
// 8.     1113213211
// 9.     31131211131221
//10.     13211311123113112211


import java.util.ArrayList;
import java.util.List;

public class CountAndSay {
    public String countAndSay(int n) {
        String res;
        if (n == 1)
            return "1";
        if (n==2)
            return "11";
        res = "11";
        for (int i = 3; i <= n; i++) {
            res = count(res);
        }
        return res;
    }

    /**
     * 从上一代到下一代的函数，输入是上一代的 字符串，输出是下一代的字符串
     *
     * @param s
     * @return
     */
    public String count(String s) {
        String res;
        List<Character> ele = new ArrayList<Character>();
        char arr[] = s.toCharArray();
        int count = 1;
        for (int i = 0; i < arr.length; i++) {
            if (i == arr.length - 1) {
                // 对于最后一个元素的特殊处理
                if (arr[i] == arr[i - 1]) {
                    ele.add(new Character((char) (count + 48)));
                    ele.add(new Character(arr[i]));
                } else {
                    ele.add('1');
                    ele.add(new Character(arr[i]));
                }
            } else {
                if (arr[i] == arr[i + 1]) {
                    count++;
                    continue;
                } else {
                    ele.add(new Character((char) (count + 48)));  //  这里的类型转换，JVM会自动将其当做 asc2码，所以要加一个 48
                    ele.add(new Character(arr[i]));
                    count = 1; // 计数复位
                }
            }

        }
        StringBuilder stringBuilder = new StringBuilder();
        for (Character e : ele) {
            stringBuilder.append(e);
        }
        res = new String(stringBuilder);
        return res;
    }

    public static void main(String args[]) {
        int a = 4;
        CountAndSay c = new CountAndSay();

        System.out.println(c.countAndSay(10));
    }
}

更好的方法

可以用 StringBuilder 对象来完成字符拼接成字符串的工作。而且 StringBuilder 可以向其中添加整数等非char类型的元素。
同时，遍历String的时候，可以从第一个向后遍历，这样就不用考虑最后一个元素的特殊情况，只需要在遍历结束后将Count 和 最后 一个元素 也加入。使得代码简洁了许多。

public String countAndSay(int n) {
    if(n<=0)
        return "";
    String curRes = "1";
    int start = 1;//从1开始算
    while(start < n){
        StringBuilder res = new StringBuilder();
        int count = 1;
        for(int j=1;j<curRes.length();j++){
            if(curRes.charAt(j)==curRes.charAt(j-1))
                count++;
            else{
                res.append(count);
                res.append(curRes.charAt(j-1));
                count = 1;
            }
        }
        res.append(count);
        res.append(curRes.charAt(curRes.length()-1));
        curRes = res.toString();
        start++;
    }
    return curRes;
}