-
Notifications
You must be signed in to change notification settings - Fork 0
/
38.外观数列.ts
103 lines (101 loc) · 2.47 KB
/
38.外观数列.ts
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*
* @lc app=leetcode.cn id=38 lang=typescript
*
* [38] 外观数列
*
* https://leetcode.cn/problems/count-and-say/description/
*
* algorithms
* Medium (60.33%)
* Likes: 1011
* Dislikes: 0
* Total Accepted: 336.3K
* Total Submissions: 557.4K
* Testcase Example: '1'
*
* 给定一个正整数 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
*
*
*/
// @lc code=start
function countAndSay(n: number): string {
if (n === 1) return '1';
let ans = '1';
for (let i = 2; i <= n; i++) {
let [left, right] = [0, 0];
let temp = '';
while (right < ans.length) {
right += 1;
if (right < ans.length && ans[right] != ans[left]) {
temp += String(right - left) + ans[left];
left = right;
}
}
temp += String(right - left) + ans[left];
ans = temp;
}
return ans;
}
// @lc code=end
countAndSay(2);