[Leetcode] Count and Say 數(shù)個(gè)數(shù)

whjin 發(fā)布于2019-08-14 12:30 / 2176人閱讀

摘要：反轉(zhuǎn)字符法復(fù)雜度時(shí)間空間思路因?yàn)閿?shù)字不好從前向后遍歷每一位要先統(tǒng)計(jì)一共有多少位，比較麻煩，所以我們直接從后向前計(jì)數(shù)，最后把結(jié)果倒置就行了。

Count Consecutive Digits in Integer

Count consecutive digits and say it. For example, return 132341 if input is 1112224. There are three 1s, three 2s and one 4.

反轉(zhuǎn)字符法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

因?yàn)閿?shù)字不好從前向后遍歷每一位（要先統(tǒng)計(jì)一共有多少位，比較麻煩），所以我們直接從后向前計(jì)數(shù)，最后把結(jié)果倒置就行了。

注意

退出循環(huán)后還要額外執(zhí)行一次append，將最后的連續(xù)數(shù)字補(bǔ)齊

代碼

public String countAndSay(int n) {
    if(n <= 0) return "";
    int last = n % 10, cnt = 1;
    n = n / 10;
    StringBuilder sb = new StringBuilder();
    while(n > 0){
        int digit = n % 10;
        if(digit == last){
            cnt++;
        } else {
            sb.append(cnt);
            sb.append(last);
            cnt = 1;
            last = digit;
        }
        n = n / 10;
    }
    sb.append(cnt);
    sb.append(last);
    sb.reverse();
    return sb.toString();
}

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.

遞歸法 復(fù)雜度

時(shí)間 O(N) 空間 O(N) 遞歸棧空間

思路

因?yàn)榈趎個(gè)數(shù)count and say的結(jié)果是基于第n-1個(gè)數(shù)的，我們可以用遞歸解決這個(gè)問(wèn)題。

代碼

public class Solution {
    public String countAndSay(int n) {
        if(n == 0){
            return "";
        }
        if(n == 1){
            return "1";
        }
        String s = countAndSay(n-1);
        char last = s.charAt(0);
        int cnt = 1;
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i)==last){
                cnt++;
            } else {
                sb.append(cnt);
                sb.append(last);
                cnt = 1;
                last = s.charAt(i);
            }
        }
        sb.append(cnt);
        sb.append(last);
        return sb.toString();
    }
}