38. 報數(shù)

描述

報數(shù)序列是指一個整數(shù)序列，按照其中的整數(shù)的順序進行報數(shù)，得到下一個數(shù)。

前五項如下：
  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221
其中：
  1 被讀作  "one 1"  ("一個一") , 即 11。
  11 被讀作 "two 1s" ("兩個一"）, 即 21。
  21 被讀作 "one 2",  "one 1" （"一個二" ,  "一個一") , 即 1211。
給定一個正整數(shù) n ，輸出報數(shù)序列的第 n 項。

注意

• 整數(shù)順序?qū)⒈硎緸橐粋€字符串。

示例

示例 1:
  輸入: 1
  輸出: "1"

示例 2:
  輸入: 4
  輸出: "1211"

思路

1. 題目的邏輯就是要將前一個數(shù)“讀”出來，然后變化成另一個數(shù)?？梢詫崿F(xiàn)一個函數(shù)，從前一個數(shù)推演出另一個數(shù)，客戶需要第幾個，就從頭開始“讀”就好了。
2. 推進的過程就是一個遍歷的過程，每次遍歷到一個新數(shù)時，向后計算其數(shù)量，然后將“數(shù)量”和“數(shù)字”加入到新的字符串中。再將當(dāng)前的Index移到下一個待“讀”的數(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;
  }
};

// 九章上的一個實現(xiàn)
// 利用了StringStream實現(xiàn)數(shù)字和字符串之間的轉(zhuǎn)換，將上述循環(huán)中的while變?yōu)榱薴or，實現(xiàn)起來感覺更清晰
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;
    // 這段實現(xiàn)比自己寫的那個while要清晰，以后涉及找到一個起點，然后遍歷。然后在跳n個字符的做法可以參考這個實現(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. 最長公共前綴

描述

• 編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。
• 如果不存在最長公共前綴，返回空字符串 ""。

示例

示例 1:
  輸入: ["flower","flow","flight"]
  輸出: "fl"

示例 2:
  輸入: ["dog","racecar","car"]
  輸出: ""
  解釋: 輸入不存在最長公共前綴。

說明:
  所有輸入只包含小寫字母 a-z 。

思路

1. 題目要求的是最長公共前綴，不是子序列，簡單一些。核心是從頭開始依次遍歷vector中對應(yīng)位置的字符。
2. 避免處理復(fù)雜的邊界，可以優(yōu)先求出最短的序列，然后按照該長度依次遍歷vector中每個string對應(yīng)位置的字符，相等則將對應(yīng)字符保留，不相等則退出循環(huán)。(其實可以不用管最后的邊界，因為字符串最后的'\0'，肯定不會相等，具體可參考實現(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;
  }
};

// 九章上的實現(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++) {
        // 這里剛開始擔(dān)心strs[j][i]有可能會越界，但實際上字符串最后一個字符是'\0'，肯定不等，所以不用去特意求最短的字符串
        if (strs[j][i] != strs[0][i]) {
          return prefix;
        }
      }
      prefix += strs[0][i];
    }
    return prefix;
  }
};