[算法Rust,Go,Python,JS实现)]LeetCode之38-报数

题目：

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
1 被读作  "one 1"  ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

思路

下一项是上一项的解释，如
[0]:1
[1]:1个1 表述字符串："11"
[2]:2个1 表述字符串："21"
[3]:1个2和1个1 表述字符串："1211"
....依次类推
这提比较有意思

Rust实现

use std::char::from_digit;
impl Solution {
    pub fn count_and_say(n: i32) -> String {
        if n == 1 {
            return "1".to_string();
        } else {
            let mut rvecs = vec![];
            let str = &*(Solution::count_and_say(n-1));
            let mut vecs = vec![];
            let mut count:u32 = 1;
            for char in str.chars() {
                vecs.push(char);
            }
            for i in 0..vecs.len() {
                if i+1 < vecs.len() && vecs[i] == vecs[i+1]{
                    count += 1;
                } else {
                    rvecs.push(from_digit(count, 10).unwrap());
                    rvecs.push(vecs[i]);
                    count = 1;
                }
            }
            return rvecs.iter().collect();
        }
    }
}

Go实现

func countAndSay(n int) string {
	if n == 1 {
		return "1"
	} else {
		str := countAndSay(n-1)
		count := 1
		res := ""
		for i:=0;i<len(str);i++ {
			if i+1<len(str)&&str[i]==str[i+1]{
				count ++
			} else {
			   res = res + strconv.Itoa(count)+string(str[i])
			   // 重置
			   count = 1
			}
		}
		return res
	}
}

Python实现

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        else:
            st = self.countAndSay(n-1)
            count = 1
            res = ""
            for i in range(0, len(st)):
                if i+1 < len(st) and st[i] == st[i+1]:
                    count += 1
                else:
                    res = res+ str(count)+str(st[i])
                    count = 1 
        return res

JavaScript实现

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
   if(n == 1) {
       return "1"
   } else {
       let str = countAndSay(n-1);
       let count = 1;
       let res = "";
       for (let i = 0;i < str.length;i++) {
           if (str[i] == str[i+1]) {
               count ++
           } else {
               res = res+count + str[i]
               count = 1
           }
       }
       return res
   }
};

效果

源码下载地址：

源码下载地址