第四周

Alogrithm

题目—Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

    Input: "babad"
    Output: "bab"
    Note: "aba" is also a valid answer.
Example 2:

    Input: "cbbd"
    Output: "bb"

关键点在于想通回文串的特点是中间两个或者三个字母一定是对称的，所以每个回文串必定是从中间向两边扩散。这样基本思路就在于先找到回文串的中间位置，所以找中间位置的步骤一次从前到后的搜索就搞定了。

答案：


/**
 * Find longest palindrome
 * @param string
 * @return string
 */
std::string Solution::longestPalindrome(std::string s) {
  const char *s_array = s.c_str();
  int len = 1, start = 0;
  for (int i = 0; i < s.length(); ++i) {
    if (i > 0 && s_array[i] == s_array[i - 1]) {
      int testlen = 2;
      int tempstart = i - 1;
      testlen = FindPalindrome(s, testlen, &tempstart);
      if (testlen > len) {
        start = tempstart;
        len = testlen;
      }
    }
    if (i > 1 && s_array[i] == s_array[i - 2]) {
      int testlen = 3, tempstart = i - 2;
      testlen = FindPalindrome(s, testlen, &tempstart);
      if (testlen > len) {
        start = tempstart;
        len = testlen;
      }
    }
  }
  return s.substr(start, len);
}

int Solution::FindPalindrome(const std::string &s,
                             const int templen,
                             int *start) {
  int len = templen;
  while ((*start + len) < s.length() && (*start > 0)) {
    if (s[*start + len] == s[*start - 1]) {
      len += 2;
      --(*start);
    } else break;
  }
  return len;
}

由于中间没有多余的存储，空间复杂度是O(1)，但两个循环，时间复杂度是O(n^2)。

更厉害的Manacher's algorithm（马拉车算法）是一个时间复杂度为O(n)的算法，详见维基百科的Longest palindromic substring - Manacher’s algorithm。(还有一个更多图的讲解)

Tips：

需要注意std::string::substr的定义：string substr (size_t pos = 0, size_t len = npos) const;。其中第二个参数是长度。
循环中容易写各种判断corner case的判断把自己绕进去，要拆分成函数并想清楚基本流程和原理，直观写出流程就好。

Review

Tips

整理了耗子叔的高效学习系列文章的导图和提纲，权当本周的Tips了
左耳听风笔记 - 高效学习系列

最近在天才吧折腾了下自己的笔记本同时换了个新iPad回来，想同步下关于Apple的质保的一些情况：

MacBook:
- MacBook全球联保，如果作为主力开发机，还是比较推荐加一个Apple Care Plus的。自己买了AC+的美版MacBook Pro在近三年时间里免费更换了A、B、C面+屏幕+电池+电源适配器。感觉还是相当值回票价的。
iPad：
- iPad在Apple官方的质保中是只保一年的，但是iPad在中国的官方定义是：苹果便携式电脑。由于是电脑，其享受中国消费者权益保护法的两年主要器件质保。而同时由于Apple对iPad的维修政策是只换不修，所以……在两年内iPad出问题都是可以拿到天才吧去检测下换个同款全新Pad出来的。一年内外唯一的差异是官方认可的一年内换机状况下保修期是重新计算的，而一年外只是换机，质保时间是不重新计算的。

Alogrithm

题目—Longest Palindromic Substring

Review

Tips

Share