LeetCode 38：Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     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 where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

这个题目审题都要研究半天，还google翻译了下，大概意思就是要不停输出前一个字符串中“字符次数” + “字符”拼凑起来的字符串，说的更简单一点：

n = 1，s = “1”

n = 2，上一次s = 1个”1”，因此s = “11″

n = 3，上一次s = 2个“1”，因此s = “21”

n = 4，上一次s = 1个“2” + 1个“1”，因此s = “1211”

n = 5，上一次n = 1个“1” + 1个“2” + 2个“1”，因此s = “111221”

其实除了n=1的时候，s有个初值之外，n > 1的时候，计算过程和n没啥关系，但n决定的是从n=1开始计算的次数

 

大致流程：

1：当n = 1时，s = “1″

2：遍历s，当now == last，count++，这样就一直累加last字符的次数

3：遍历s，当now != last，这时候就可以append一个str(count) + last了，比如21，当now=“1”的时候，str(count) + last = “12”这个就可以计算出来了，并且新的last = now，因为当前已经遍历到了”1”，因此count = 1，这样进入下一轮循环

Python大概代码如下

#!/usr/bin/env python3

# -*- coding: utf-8 -*-
# Time : 2019/9/8 12:01 下午
# Auth : lihui
# File : leetcode.py

class Solution:
    """
    1.     1
    2.     11
    3.     21
    4.     1211
    5.     111221
    """
    def countAndSay(self, n: int) -> str:
        s = "1"
        if n == 1:
            return s
        while n > 1:
            last, count = s[0], 0
            ss = ""

            # s  = 21
            # ss = 1211
            for now in s:
                if now == last:
                    count += 1
                else:
                    # 当前字符和前一个字符不一样
                    # 1：前面一个字符的数目此刻截止，合并一次
                    ss += str(count) + last
                    # 2：已经遍历到now了，因此前一个字符赋值为now，并且已经有一次了，count = 1
                    last, count = now, 1

            ss += str(count) + last
            s = ss
            n -= 1

        return s

Java照搬

package com.lihuia.leetcode;

/**
 * Copyright (C), 2018-2019
 * FileName: ThirtyEight
 * Author:   lihui
 * Date:     2019-09-08
 */

public class ThirtyEight {

    public String countAndSay(int n) {
        String s = "1";
        if (n == 1) {
            return s;
        }

        for (int i = 0; i < n - 1; i++) {
            char last = s.charAt(0);
            int count = 0;
            String ss = "";
            
            for (char now : s.toCharArray()) {
                if (now == last) {
                    count++;
                } else {
                    ss += String.valueOf(count) + last;
                    last = now;
                    count = 1;
                }
            }
            ss += String.valueOf(count) + last;
            s = ss;
        }
        System.out.println(s);
        return s;
    }
}

else里的count = 1不能丢弃，这里的意思是遍历到当前now字符，因此出现了一次，赋值为1，假如前面一个last出现多次，count很大了，所以必须赋值为1，如果前面last出现一次，那此时count才不会出现问题