38. 報(bào)數(shù)
描述
報(bào)數(shù)序列是指一個(gè)整數(shù)序列外里，按照其中的整數(shù)的順序進(jìn)行報(bào)數(shù)，得到下一個(gè)數(shù)酝润。
前五項(xiàng)如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
其中：
1 被讀作 "one 1" ("一個(gè)一") , 即 11弓叛。
11 被讀作 "two 1s" ("兩個(gè)一"）, 即 21。
21 被讀作 "one 2", "one 1" （"一個(gè)二" , "一個(gè)一") , 即 1211灾茁。
給定一個(gè)正整數(shù) n 窜觉，輸出報(bào)數(shù)序列的第 n 項(xiàng)。
注意
- 整數(shù)順序?qū)⒈硎緸橐粋€(gè)字符串北专。
示例
示例 1:
輸入: 1
輸出: "1"
示例 2:
輸入: 4
輸出: "1211"
思路
- 題目的邏輯就是要將前一個(gè)數(shù)“讀”出來(lái)竖螃，然后變化成另一個(gè)數(shù)《河啵可以實(shí)現(xiàn)一個(gè)函數(shù)特咆，從前一個(gè)數(shù)推演出另一個(gè)數(shù)，客戶需要第幾個(gè)录粱，就從頭開(kāi)始“讀”就好了腻格。
- 推進(jìn)的過(guò)程就是一個(gè)遍歷的過(guò)程，每次遍歷到一個(gè)新數(shù)時(shí)啥繁，向后計(jì)算其數(shù)量菜职，然后將“數(shù)量”和“數(shù)字”加入到新的字符串中。再將當(dāng)前的Index移到下一個(gè)待“讀”的數(shù)字旗闽。
class Solution_38_01 {
public:
string countAndSay(int n) {
if (n < 1) return "";
string ret = "1";
for (int i = 1; i < n; ++i) {
ret = NextSS(ret);
}
return ret;
}
string NextSS(string str) {
string ret;
int index = 0;
while (index < str.length()) {
char curNum = str[index];
int cnt = 1;
while ((index + cnt) < str.length() && str[index + cnt] == curNum) {
++cnt;
}
index += cnt;
ret.push_back(cnt + '0');
ret.push_back(curNum);
}
return ret;
}
};
// 九章上的一個(gè)實(shí)現(xiàn)
// 利用了StringStream實(shí)現(xiàn)數(shù)字和字符串之間的轉(zhuǎn)換酬核，將上述循環(huán)中的while變?yōu)榱薴or，實(shí)現(xiàn)起來(lái)感覺(jué)更清晰
class Solution_38_02 {
public:
string int_to_string(int j) {
stringstream in;
in << j;
string temp;
in >> temp;
return temp;
}
string genate(string s) {
string now;
int j = 0;
// 這段實(shí)現(xiàn)比自己寫(xiě)的那個(gè)while要清晰适室，以后涉及找到一個(gè)起點(diǎn)嫡意，然后遍歷。然后在跳n個(gè)字符的做法可以參考這個(gè)實(shí)現(xiàn)
for (int i = 0; i < s.size(); i += j) {
for (j = 0; j + i < s.size(); j++) {
if (s[i] != s[i + j]) {
break;
}
}
now = now + int_to_string(j) + s[i];
}
return now;
}
string countAndSay(int n) {
string s("1");
while (--n) {
s = genate(s);
}
return s;
}
};
14. 最長(zhǎng)公共前綴
描述
- 編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴捣辆。
- 如果不存在最長(zhǎng)公共前綴蔬螟，返回空字符串 ""。
示例
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在最長(zhǎng)公共前綴汽畴。
說(shuō)明:
所有輸入只包含小寫(xiě)字母 a-z 旧巾。
思路
- 題目要求的是最長(zhǎng)公共前綴耸序，不是子序列，簡(jiǎn)單一些鲁猩。核心是從頭開(kāi)始依次遍歷vector中對(duì)應(yīng)位置的字符坎怪。
- 避免處理復(fù)雜的邊界，可以優(yōu)先求出最短的序列廓握，然后按照該長(zhǎng)度依次遍歷vector中每個(gè)string對(duì)應(yīng)位置的字符芋忿，相等則將對(duì)應(yīng)字符保留，不相等則退出循環(huán)疾棵。(其實(shí)可以不用管最后的邊界戈钢，因?yàn)樽址詈蟮?\0'，肯定不會(huì)相等是尔，具體可參考實(shí)現(xiàn)二)
class Solution_14_01 {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
string ret("");
int mSize = strs[0].size();
// 找到最短序列
for (string str : strs) {
if (str.size() < mSize) {
mSize = str.size();
}
}
for (int index = 0; index < mSize; ++index) {
char tmp = strs[0][index];
bool match = true;
for (string str : strs) {
if (str[index] != tmp) {
match = false;
break;
}
}
if (!match) break;
ret.push_back(strs[0][index]);
}
return ret;
}
};
// 九章上的實(shí)現(xiàn)殉了。核心思想相同，但更精煉拟枚。
class Solution_14_02 {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) {
return "";
}
string prefix = "";
for (int i = 0; i < strs[0].length(); i++) {
for (int j = 1; j < strs.size(); j++) {
// 這里剛開(kāi)始擔(dān)心strs[j][i]有可能會(huì)越界薪铜，但實(shí)際上字符串最后一個(gè)字符是'\0'，肯定不等恩溅，所以不用去特意求最短的字符串
if (strs[j][i] != strs[0][i]) {
return prefix;
}
}
prefix += strs[0][i];
}
return prefix;
}
};
