資訊專(zhuān)欄INFORMATION COLUMN
摘要：遞歸解法復(fù)雜度時(shí)間空間遞歸棧思路該序列又叫做外觀(guān)序列，無(wú)論如何我們都得將前一個(gè)序列元素算出來(lái)，才能計(jì)算后一個(gè)序列元素。當(dāng)遞歸至的時(shí)候返回初始數(shù)字。另外，比如初始數(shù)字，第一次變成了，我們可以發(fā)現(xiàn)大于的數(shù)都只會(huì)一個(gè)一個(gè)出現(xiàn)了。
Count And Say
遞歸解法 復(fù)雜度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.
時(shí)間 O(N!) 空間 O(N) 遞歸棧
思路該序列又叫做外觀(guān)序列，無(wú)論如何我們都得將前一個(gè)序列元素算出來(lái)，才能計(jì)算后一個(gè)序列元素。當(dāng)遞歸至0的時(shí)候返回初始數(shù)字1。
代碼public class Solution {
public String countAndSay(int n) {
// 遞歸盡頭返回空或者1
if(n == 0) return "";
if(n == 1) return "1";
// 計(jì)算出上一個(gè)字符串
String s = countAndSay(n - 1);
StringBuilder sb = new StringBuilder();
// 通過(guò)記錄上次的字符來(lái)判斷是否重復(fù)
char last = s.charAt(0);
int cnt = 1;
for(int i = 1; i < s.length(); i++){
// 如果重復(fù)則計(jì)數(shù)器加1
if(s.charAt(i) == last){
cnt++;
} else {
// 否則添加上一個(gè)字符，并重置計(jì)數(shù)器為1
sb.append(cnt);
sb.append(last);
last = s.charAt(i);
cnt = 1;
}
}
// 最后記得把最后一個(gè)字符加上
sb.append(cnt);
sb.append(last);
return sb.toString();
}
}
迭代解法
復(fù)雜度
時(shí)間 O(N!) 空間 O(N) 字符長(zhǎng)度
思路將遞歸換成了循環(huán)而已。
代碼public class Solution {
public String countAndSay(int n) {
if(n == 0) return "";
String s = "1";
for(int j = 1; j < n; j++){
StringBuilder sb = new StringBuilder();
char last = s.charAt(0);
int cnt = 1;
for(int i = 1; i < s.length(); i++){
if(s.charAt(i) == last){
cnt++;
} else {
sb.append(cnt);
sb.append(last);
last = s.charAt(i);
cnt = 1;
}
}
sb.append(cnt);
sb.append(last);
s = sb.toString();
}
return s;
}
}
后續(xù) Follow Up
Q：該序列有什么特點(diǎn)？
A：該序列最大的數(shù)不超過(guò)3，除非初始的數(shù)字大于3
Q: 對(duì)于101這種數(shù)字如何解讀？
A：因?yàn)?0后面只有1個(gè)（奇數(shù)）數(shù)字，所以不可能是1個(gè)0，肯定是10個(gè)1.
Q: 如果有三位數(shù)，比如200個(gè)1，表示成2001時(shí)怎么辦？
A: 其實(shí)我們可以發(fā)現(xiàn)，除了第一次生成的數(shù)以外，以后再也不可能有200個(gè)連續(xù)的同一個(gè)數(shù)，所以這種情況只可能發(fā)生在第一次count and say，特殊處理一下就好了。另外，比如初始數(shù)字9991999，第一次變成了391139，我們可以發(fā)現(xiàn)大于3的數(shù)都只會(huì)一個(gè)一個(gè)出現(xiàn)了。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64675.html
摘要：反轉(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. The...
摘要：而讀起來(lái)是兩個(gè)，所以第三個(gè)字符串就應(yīng)當(dāng)是。同理第四個(gè)字符串是一個(gè)一個(gè)，因此是。依次類(lèi)推而我們的目的是，對(duì)于輸入的正整數(shù)，我們要給出第個(gè)字符串是什么。這里采用了是為了減少內(nèi)存的開(kāi)銷(xiāo)。解法設(shè)置初始字符串將重新賦值當(dāng)前字符字符計(jì)數(shù) 題目詳情 The count-and-say sequence is the sequence of integers with the first five t...
摘要：題目要求英文的題目有點(diǎn)繞口，所以去網(wǎng)上找了一下題目的意思。題目的核心邏輯在于將口語(yǔ)化的數(shù)數(shù)字轉(zhuǎn)化為字符串。 題目要求 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...
Problem Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Note:The array siz...
摘要：在線(xiàn)網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線(xiàn)網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
閱讀 2597·2021-10-19 11:41
閱讀 2432·2021-09-01 10:32
閱讀 3388·2019-08-29 15:21
閱讀 1772·2019-08-29 12:20
閱讀 1175·2019-08-29 12:13
閱讀 614·2019-08-26 12:24
閱讀 2529·2019-08-26 10:26
閱讀 846·2019-08-23 18:40
