LeetCodeDay10

38. 报数

描述

报数序列是指一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。

前五项如下：
  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221
其中：
  1 被读作  "one 1"  ("一个一") , 即 11。
  11 被读作 "two 1s" ("两个一"）, 即 21。
  21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。
给定一个正整数 n ，输出报数序列的第 n 项。

注意

• 整数顺序将表示为一个字符串。

示例

示例 1:
  输入: 1
  输出: "1"

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

思路

1. 题目的逻辑就是要将前一个数“读”出来，然后变化成另一个数。可以实现一个函数，从前一个数推演出另一个数，客户需要第几个，就从头开始“读”就好了。
2. 推进的过程就是一个遍历的过程，每次遍历到一个新数时，向后计算其数量，然后将“数量”和“数字”加入到新的字符串中。再将当前的Index移到下一个待“读”的数字。

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;
  }
};

// 九章上的一个实现
// 利用了StringStream实现数字和字符串之间的转换，将上述循环中的while变为了for，实现起来感觉更清晰
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;
    // 这段实现比自己写的那个while要清晰，以后涉及找到一个起点，然后遍历。然后在跳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. 最长公共前缀

描述

• 编写一个函数来查找字符串数组中的最长公共前缀。
• 如果不存在最长公共前缀，返回空字符串 ""。

示例

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

示例 2:
  输入: ["dog","racecar","car"]
  输出: ""
  解释: 输入不存在最长公共前缀。

说明:
  所有输入只包含小写字母 a-z 。

思路

1. 题目要求的是最长公共前缀，不是子序列，简单一些。核心是从头开始依次遍历vector中对应位置的字符。
2. 避免处理复杂的边界，可以优先求出最短的序列，然后按照该长度依次遍历vector中每个string对应位置的字符，相等则将对应字符保留，不相等则退出循环。(其实可以不用管最后的边界，因为字符串最后的'\0'，肯定不会相等，具体可参考实现二)

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;
  }
};

// 九章上的实现。核心思想相同，但更精炼。
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++) {
        // 这里刚开始担心strs[j][i]有可能会越界，但实际上字符串最后一个字符是'\0'，肯定不等，所以不用去特意求最短的字符串
        if (strs[j][i] != strs[0][i]) {
          return prefix;
        }
      }
      prefix += strs[0][i];
    }
    return prefix;
  }
};