Count and Say (E)
題目
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.
題意
定義一組數字序列為：每一個數字序列都是對上一個數字序列的“描述”，如第一個序列為“1”，第二個序列為“11”(描述第一個序列中有1個1)，第三個序列為“21”(描述第二個序列中有2個1)，第四個序列為“1211”(描述第三個序列中有1個2、1個1)……要求回傳第n個序列，
思路
創建一個next(String s)方法來根據上一個序列計算下一個序列，為了避免多次重復的計算，用一個List來保存各個序列，
代碼實作
Java
class Solution {
// 保存計算過的序列，避免重復運算
private List<String> list = new ArrayList<>();
public String countAndSay(int n) {
// 首先找是否已經計算過對應的值
if (n <= list.size()) {
return list.get(n - 1);
}
// 尚未計算對應值，則從已有的最后一個序列開始計算到指定序列
while (list.size() < n) {
String s = list.size() == 0 ? null : list.get(list.size() - 1); // 注意沒有一個已計算的情況
list.add(next(s));
}
return list.get(n - 1);
}
private String next(String s) {
// 特殊情況，計算第一個序列
if (s == null) {
return "1";
}
StringBuilder sb = new StringBuilder();
int count = 1;
for (int i = 0; i < s.length(); i++) {
if (i > 0) {
if (s.charAt(i) == s.charAt(i - 1)) {
count++;
} else {
sb.append(count);
sb.append(s.charAt(i - 1));
count = 1;
}
}
}
sb.append(count);
sb.append(s.charAt(s.length() - 1));
return sb.toString();
}
}
JavaScript
/**
* @param {number} n
* @return {string}
*/
var countAndSay = function (n) {
let count = 1
let s = '1'
while (count !== n) {
let times = 1
let t = ''
for (let i = 1; i < s.length; i++) {
if (s[i] === s[i - 1]) {
times++
} else {
t += times + '' + s[i - 1]
times = 1
}
}
t += times + '' + s[s.length - 1]
s = t
count++
}
return s
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/38876.html
標籤：其他
上一篇：思科路由重分發