力扣00038.外观数列

发表于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 7 分钟
外观数列、字符串、中等

题目描述

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

  • countAndSay(1) = “1”
  • countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221

    第一项是数字 1
    描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 “11”
    描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 “21”
    描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 “1211”
    描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 “111221”
    要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 “3322251” 的描述如下图：

示例 1：

输入：n = 1
输出：”1”
解释：这是一个基本样例。

示例 2：

输入：n = 4
输出：”1211”
解释：
countAndSay(1) = “1”
countAndSay(2) = 读 “1” = 一 个 1 = “11”
countAndSay(3) = 读 “11” = 二 个 1 = “21”
countAndSay(4) = 读 “21” = 一 个 2 + 一 个 1 = “12” + “11” = “1211”

提示：

  • 1 <= n <= 30

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string countAndSay(int n) {
        if (n == 1) {
            return "1";
        } else {
            string prev = countAndSay(n - 1);
            string result = "";
            int count = 1;
            for (size_t i = 0; i < prev.length(); ++i) {
                if (i + 1 < prev.length() && prev[i] == prev[i + 1]) {
                    count++;
                } else {
                    result += to_string(count) + prev[i];
                    count = 1;
                }
            }
            return result;
        }
    }
};

结果

执行用时 : 3 ms, 击败 78.05% 使用 C++ 的用户

内存消耗 : 9.09 MB, 击败 12.48% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        } else {
            String prev = countAndSay(n - 1);
            StringBuilder result = new StringBuilder();
            int count = 1;
            for (int i = 0; i < prev.length(); i++) {
                if (i + 1 < prev.length() && prev.charAt(i) == prev.charAt(i + 1)) {
                    count++;
                } else {
                    result.append(count).append(prev.charAt(i));
                    count = 1;
                }
            }
            return result.toString();
        }
    }
}

结果

执行用时 : 1 ms, 击败 97.05% 使用 Java 的用户

内存消耗 : 40.21 MB, 击败 59.65% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n == 1:
            return "1"
        else:
            prev = self.countAndSay(n - 1)
            result = ""
            count = 1
            for i in range(len(prev)):
                if i + 1 < len(prev) and prev[i] == prev[i + 1]:
                    count += 1
                else:
                    result += str(count) + prev[i]
                    count = 1
            return result

结果

执行用时 : 21 ms, 击败 87.04% 使用 Python 的用户

内存消耗 : 11.59 MB, 击败 91.09% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        else:
            prev = self.countAndSay(n - 1)
            result = ""
            count = 1
            for i in range(len(prev)):
                if i + 1 < len(prev) and prev[i] == prev[i + 1]:
                    count += 1
                else:
                    result += str(count) + prev[i]
                    count = 1
            return result

结果

执行用时 : 45 ms, 击败 81.55% 使用 Python3 的用户

内存消耗 : 16.52 MB, 击败 29.61% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
char* countAndSay(int n) {
    if (n == 1) {
        char* result = malloc(2);
        strcpy(result, "1");
        return result;
    } else {
        char* prev = countAndSay(n - 1);
        int len = strlen(prev);
        char* result = malloc(2 * len + 1);
        int count = 1;
        int index = 0;
        for (int i = 0; i < len; ++i) {
            if (i + 1 < len && prev[i] == prev[i + 1]) {
                count++;
            } else {
                index += sprintf(result + index, "%d%c", count, prev[i]);
                count = 1;
            }
        }
        free(prev);
        return result;
    }
}

结果

执行用时 : 12 ms, 击败 7.90% 使用 C 的用户

内存消耗 : 6.36 MB, 击败 90.88% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public string CountAndSay(int n) {
        if (n == 1) {
            return "1";
        } else {
            string prev = CountAndSay(n - 1);
            System.Text.StringBuilder result = new System.Text.StringBuilder();
            int count = 1;
            for (int i = 0; i < prev.Length; ++i) {
                if (i + 1 < prev.Length && prev[i] == prev[i + 1]) {
                    count++;
                } else {
                    result.Append(count).Append(prev[i]);
                    count = 1;
                }
            }
            return result.ToString();
        }
    }
}

结果

执行用时 : 57 ms, 击败 86.11% 使用 C# 的用户

内存消耗 : 40.65 MB, 击败 51.39% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    if (n === 1) {
        return "1";
    } else {
        var prev = countAndSay(n - 1);
        var result = "";
        var count = 1;
        for (var i = 0; i < prev.length; ++i) {
            if (i + 1 < prev.length && prev[i] === prev[i + 1]) {
                count++;
            } else {
                result += count + prev[i];
                count = 1;
            }
        }
        return result;
    }
};

结果

执行用时 : 64 ms, 击败 66.33% 使用 JavaScript 的用户

内存消耗 : 52.34 MB, 击败 5.01% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function countAndSay(n: number): string {
    if (n === 1) {
        return "1";
    } else {
        const prev: string = countAndSay(n - 1);
        let result: string = "";
        let count: number = 1;
        for (let i: number = 0; i < prev.length; ++i) {
            if (i + 1 < prev.length && prev[i] === prev[i + 1]) {
                count++;
            } else {
                result += count + prev[i];
                count = 1;
            }
        }
        return result;
    }
}

结果

执行用时 : 64 ms, 击败 84.00% 使用 TypeScript 的用户

内存消耗 : 52.96 MB, 击败 6.00% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {

    /**
     * @param Integer $n
     * @return String
     */
    function countAndSay($n) {
        if ($n === 1) {
            return "1";
        } else {
            $prev = $this->countAndSay($n - 1);
            $result = "";
            $count = 1;
            for ($i = 0; $i < strlen($prev); ++$i) {
                if ($i + 1 < strlen($prev) && $prev[$i] === $prev[$i + 1]) {
                    $count++;
                } else {
                    $result .= $count . $prev[$i];
                    $count = 1;
                }
            }
            return $result;
        }
    }
}

结果

执行用时 : 7 ms, 击败 87.50% 使用 PHP 的用户

内存消耗 : 20.10 MB, 击败 12.50% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func countAndSay(_ n: Int) -> String {
        if n == 1 {
            return "1"
        } else {
            let prev = countAndSay(n - 1)
            var result = ""
            var count = 1
            for i in 0..<prev.count {
                if i + 1 < prev.count && prev[prev.index(prev.startIndex, offsetBy: i)] == prev[prev.index(prev.startIndex, offsetBy: i + 1)] {
                    count += 1
                } else {
                    result += "\(count)\(prev[prev.index(prev.startIndex, offsetBy: i)])"
                    count = 1
                }
            }
            return result
        }
    }
}

结果

执行用时 : 1663 ms, 击败 10.53% 使用 Swift 的用户

内存消耗 : 14.85 MB, 击败 68.42% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    fun countAndSay(n: Int): String {
        if (n == 1) {
            return "1"
        } else {
            val prev = countAndSay(n - 1)
            var result = ""
            var count = 1
            for (i in 0 until prev.length) {
                if (i + 1 < prev.length && prev[i] == prev[i + 1]) {
                    count++
                } else {
                    result += "$count${prev[i]}"
                    count = 1
                }
            }
            return result
        }
    }
}

结果

执行用时 : 168 ms, 击败 82.35% 使用 Kotlin 的用户

内存消耗 : 36.61 MB, 击败 64.71% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  String countAndSay(int n) {
    if (n == 1) {
      return "1";
    } else {
      String prev = countAndSay(n - 1);
      StringBuffer result = StringBuffer();
      int count = 1;
      for (int i = 0; i < prev.length; ++i) {
        if (i + 1 < prev.length && prev[i] == prev[i + 1]) {
          count++;
        } else {
          result.write("$count${prev[i]}");
          count = 1;
        }
      }
      return result.toString();
    }
  }
}

结果

执行用时 : 291 ms, 击败 -% 使用 Dart 的用户

内存消耗 : 147.80 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func countAndSay(n int) string {
	prev := "1"
	for i := 2; i <= n; i++ {
		var cur strings.Builder
		for j, start := 0, 0; j < len(prev); start = j {
			for j < len(prev) && prev[j] == prev[start] {
				j++
			}
			cur.WriteString(strconv.Itoa(j - start))
			cur.WriteByte(prev[start])
		}
		prev = cur.String()
	}
	return prev
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 2.30 MB, 击败 90.00% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# @param {Integer} n
# @return {String}
def count_and_say(n)
  prev = "1"
  (2..n).each do
    cur = ""
    i, start = 0, 0
    while i < prev.length
      while i < prev.length && prev[i] == prev[start]
        i += 1
      end
      cur += "#{i - start}#{prev[start]}"
      start = i
    end
    prev = cur
  end
  return prev
end

结果

执行用时 : 91 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 210.46 MB, 击败 100.00% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
object Solution {
  def countAndSay(n: Int): String = {
    if (n == 1) {
      "1"
    } else {
      val prev = countAndSay(n - 1)
      val result = new StringBuilder
      var count = 1
      for (i <- 0 until prev.length) {
        if (i + 1 < prev.length && prev(i) == prev(i + 1)) {
          count += 1
        } else {
          result.append(count).append(prev(i))
          count = 1
        }
      }
      result.toString
    }
  }
}

结果

执行用时 : 428 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 52.55 MB, 击败 100.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn count_and_say(n: i32) -> String {
        if n == 1 {
            return "1".to_string();
        } else {
            let prev = Solution::count_and_say(n - 1);
            let mut result = String::new();
            let mut count = 1;
            for i in 0..prev.len() {
                if i + 1 < prev.len() && prev.chars().nth(i).unwrap() == prev.chars().nth(i + 1).unwrap() {
                    count += 1;
                } else {
                    result.push_str(&count.to_string());
                    result.push(prev.chars().nth(i).unwrap());
                    count = 1;
                }
            }
            result
        }
    }
}

结果

执行用时 : 52 ms, 击败 17.65% 使用 Rust 的用户

内存消耗 : 2.07 MB, 击败 58.82% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户