筆者按照目錄刷題绍载，對(duì)于每一道題，力爭(zhēng)使用效率最高（時(shí)間復(fù)雜度最低）的算法，并全部通過(guò)C++代碼實(shí)現(xiàn)AC。(文中計(jì)算的復(fù)雜度都是最壞情況復(fù)雜度)
因?yàn)榭紤]到大部分讀者已經(jīng)在Leetcode瀏覽過(guò)題目了摄闸，所以每道題都按照 解題思路 -> 實(shí)現(xiàn)代碼 -> 問(wèn)題描述 的順序進(jìn)行講解。
(筆者目前已刷 40 題妹萨，已更新解法 10 題年枕，最近一段時(shí)間會(huì)頻繁更新)可以點(diǎn)擊下方鏈接，直達(dá)gitbook：
https://codernie.gitbooks.io/leetcode-solutions/content/
也歡迎大家關(guān)注我的微信公眾號(hào)(大雄的學(xué)習(xí)人生)乎完，有問(wèn)題可以隨時(shí)后臺(tái)回復(fù)我熏兄，多多探討。

1. Two Sum 【easy】

解題思路：

**暴力解法 **O(N^2)：

嵌套兩層循環(huán)：第一層：i 從 0 到 n - 2；第二層：j 從 i + 1 到 n - 1摩桶；判斷 nums[i] + nums[j] == target 桥状，如果成立則是正確答案

map解法 O(N*logN)：

從 0 到 n - 1 依次遍歷，利用map存放每一個(gè)數(shù)值的下標(biāo)典格，在map中尋找是否有使（nums[i] + x == target）成立的x的存在岛宦，如果存在則返回i和它的下標(biāo)（即myMap[ target - nums[i] ])。

復(fù)雜度分析：因?yàn)橹槐闅v了一次數(shù)組耍缴，map每次的查詢的時(shí)間復(fù)雜度為O(logN)所以整體復(fù)雜度為O(N*logN)、如果這里使用hash_map可以將查詢復(fù)雜度降低到O(1)挽霉，從而使得整體復(fù)雜度為O(N)防嗡，但是hash_map不是標(biāo)準(zhǔn)的C++庫(kù)，所以這里沒(méi)有使用侠坎。

實(shí)現(xiàn)代碼：

// 1. Two Sum
vector<int> twoSum(vector<int>& nums, int target) {
  map<int, int> myMap;
  vector<int> result;
  for (int i = 0; i < nums.size(); i++) {
    if (myMap.find(target - nums[i]) == myMap.end()) {
      myMap[nums[i]] = i;
    } else {
      result = {myMap[target - nums[i]], i};
      break;
    }
  }
  return result;
}

問(wèn)題描述：

Given an array of integers, return **indices **of the two numbers such that they add up to a specific target.

You may assume that each input would have _**exactly **_one solution, and you may not use the_same_element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

2. Add Two Numbers【medium】

解題思路：

從左到右遍歷鏈表蚁趁，依次相加，每一個(gè)位置生成一個(gè)新的結(jié)點(diǎn)即可实胸。

時(shí)間復(fù)雜度：O( max( len(l1), len(l2) ) )

考慮邊界條件：

1.進(jìn)位的的處理：carry表示進(jìn)位他嫡，當(dāng)最后一位還有進(jìn)位時(shí)，即使 l1 和 l2 均為NULL的情況下庐完，還需要生成一個(gè)新的結(jié)點(diǎn)钢属，所以while的條件中加入了 carry != 0 判斷項(xiàng)。

2.返回頭結(jié)點(diǎn)：當(dāng)頭結(jié)點(diǎn)為NULL的時(shí)候記錄頭結(jié)點(diǎn)门躯，并且讓p等于頭結(jié)點(diǎn)淆党；后續(xù)情況讓 p->next 等于新的結(jié)點(diǎn)，并讓 p 指向 p->next讶凉。

實(shí)現(xiàn)代碼：

// 2. Add Two Numbers
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  ListNode *head = NULL, *p;
  int carry = 0, sum;
  while (l1 != NULL || l2 != NULL || carry != 0) {
    sum = 0;
    if (l1 != NULL) {
      sum += l1->val;
      l1 = l1->next;
    }
    if (l2 != NULL) {
      sum += l2->val;
      l2 = l2->next;
    }
    sum += carry;
    carry = sum / 10;
    sum %= 10;
    ListNode *newNode = new ListNode(sum);
    if (head == NULL) {
      head = newNode;
      p = newNode;
    } else {
      p->next = newNode;   
      p = p->next;
    }
  }
  return head;
}

問(wèn)題描述：

You are given two non-empty linked lists representing two non-negative integers. The digits are stored inreverse orderand each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

3. Longest Substring Without Repeating Characters【medium】

解題思路：

**暴力解法 **O(N^3)：

從每個(gè)點(diǎn)遍歷染乌、依次遍歷這個(gè)點(diǎn)后的每一個(gè)點(diǎn)、通過(guò)遍歷該點(diǎn)之前的點(diǎn)判斷該點(diǎn)是否出現(xiàn)過(guò)懂讯。聽(tīng)上去有點(diǎn)拗口荷憋，代碼在下方，這個(gè)暴力方法Leetcode也可以AC褐望，但是不推薦使用勒庄。

頭尾標(biāo)記法 O(N*logN)：

頭標(biāo)記指向當(dāng)前最長(zhǎng)無(wú)重復(fù)字符串的頭部，尾標(biāo)記指向其尾部譬挚。通過(guò)一個(gè) map 來(lái)記錄出現(xiàn)過(guò)的字符最后出現(xiàn)的位置锅铅。

依次遍歷數(shù)組，如果當(dāng)前字符已出現(xiàn)過(guò)减宣，則讓頭標(biāo)記指向其最后出現(xiàn)過(guò)的位置的后一個(gè)位置盐须。然后每次通過(guò)頭、尾標(biāo)記計(jì)算當(dāng)前無(wú)重復(fù)字符串的長(zhǎng)度漆腌，并與已知最大值作比較贼邓。這里查詢map的復(fù)雜度為 O(logN)阶冈，遍歷的復(fù)雜度為 O(N)，因此整體復(fù)雜度為 O(N*logN)塑径。如果這里使用hash_map可以將查詢復(fù)雜度降低到O(1)女坑，從而使得整體復(fù)雜度為O(N)，但是hash_map不是標(biāo)準(zhǔn)的C++庫(kù)统舀，所以這里沒(méi)有使用匆骗。

實(shí)現(xiàn)代碼：

// 3. Longest Substring Without Repeating Characters
// 暴力解法
int lengthOfLongestSubstring_bruteForce(string s) {
  int res = 0, sum;
  for (int i = s.size() - 1; i >= 0; i--) {
    sum = 1;
    for (int j = i - 1; j >= 0; j--) {
      bool flag = true;
      for (int k = i; k > j; k--) {
        if (s[j] == s[k]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        sum++;
      } else {
        break;
      }
    }
    res = max(res, sum);
  }
  return res;      
}
// 頭尾標(biāo)記法
int lengthOfLongestSubstring(string s) {
  map<char, int> myMap;
  int res = 0;
  for (int i = 0, j = 0; j < s.size(); j++){
    if (myMap.find(s[j]) != myMap.end()) {
      i = max(i, myMap[s[j]] + 1);
    }
    myMap[s[j]] = j;
    res = max(res, j - i + 1);
  }
  return res;
}

問(wèn)題描述：

Given a string, find the length of thelongest substringwithout repeating characters.

Examples:

Given"abcabcbb", the answer is"abc", which the length is 3.

Given"bbbbb", the answer is"b", with the length of 1.

Given"pwwkew", the answer is"wke", with the length of 3. Note that the answer must be asubstring,"pwke"is asubsequenceand not a substring.

4. Median of Two Sorted Arrays【hard】

解題思路：

這道題咋一看像二分查找，但是仔細(xì)看題誉简，發(fā)現(xiàn)有兩個(gè)有序數(shù)組碉就，而且不是讓我們找一個(gè)特定的數(shù)，而是要找兩個(gè)數(shù)組合并后的中位數(shù)闷串，這樣一看就比較難了瓮钥，也難怪歸類為hard類別。這道題除了一下介紹的二分查找法烹吵，還有兩個(gè)數(shù)組分別進(jìn)行二分查找的方法碉熄，不過(guò)代碼量相對(duì)更多(也可能是因?yàn)楣P者水平不夠?qū)е麓a量過(guò)大)，而且看了下面的二分查找法后肋拔，感嘆于該算法作者的腦洞锈津，所以在這里只介紹該種方法。

暴力方法 O((m + n)*log(m + n))：

將兩個(gè)數(shù)組合并只损，然后進(jìn)行快排一姿，中間的數(shù)即中位數(shù)。由于題目說(shuō)了復(fù)雜度不能超過(guò)O(log(m + n))跃惫，所以這個(gè)方法當(dāng)然回Time Limit Excess叮叹，所以我們得探究一種更高效的解法。

二分查找法 O(log(min(m, n)))：

首先分別把兩個(gè)數(shù)組分成兩邊爆存，大概為下面這種形式：(A表示nums1蛉顽， B表示nums2)

          left_part          |        right_part
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

因?yàn)橛行驍?shù)列的性質(zhì)，我們知道只要我們滿足以下兩個(gè)條件先较，我們就可以找到中位數(shù)了：

條件一：len(A_left) + len(B_left) = len(A_right) + len(B_right)

條件二：max[A_left, B_left] <= min[A_right, B_right]

為了使問(wèn)題簡(jiǎn)單化携冤，我們先只考慮 m + n 為偶數(shù)的情況下，只要滿足上述兩個(gè)條件闲勺，我們的中位數(shù)就等于左邊的最大值加上右邊的最小值除以二曾棕。

為了滿足條件一，我們只要令** i + j == m + n - i - j (+ 1)**即可（這里加一是為了之后考慮 m + n 為奇數(shù)的情況）

而為了滿足條件二菜循，根據(jù)有序數(shù)組的性質(zhì)翘地，我們知道只需要滿足 **A[i - 1] <= B[j] 且 B[j - 1] <= A[i] **即可。

接下來(lái)開(kāi)始我們的算法探究：

假設(shè)我們首先隨機(jī)選擇一個(gè) i (這里 0 <= i < m)，所以我們根據(jù)條件一衙耕，可以求得 j = (m + n + 1) / 2 - i昧穿；

為了滿足條件二，我們開(kāi)始分別比較 A[i - 1] 與 B[j] 和 B[j - 1] 與 A[i]：

不難知道可能會(huì)有四種情況：

• A[i - 1] <= B[j] 且 B[j - 1] <= A[i] ：這不正是我們要找的 i 嗎橙喘？可以直接返回答案
• A[i - 1] > B[j] 且 B[j - 1] > A[i] ：根據(jù)有序數(shù)列的性質(zhì)时鸵，再利用反證法不難證明這種情況不可能存在
• A[i - 1] <= B[j] 且 B[j - 1] > A[i]：為了使情況更加接近我們的答案，也就是情況1厅瞎。也就是要使 B[j - 1] <= A[i]饰潜，因?yàn)楝F(xiàn)在 B[j - 1] > A[i]，所以我們要想辦法縮小 B[j - 1]磁奖，擴(kuò)大A[i]囊拜，所以當(dāng)然是讓我們的 i 增大，否則情況會(huì)越來(lái)越遠(yuǎn)離我們的正確答案比搭。
• A[i - 1] > B[j] 且 B[j - 1] <= A[i]：與情況3恰恰相反，這里我們應(yīng)該縮小我們的 i南誊。

那我們?nèi)绾慰s小和擴(kuò)大我們的 i 呢身诺，那就是采用二分查找的方式啦，首先將 i 置為數(shù)組A的中間下標(biāo)抄囚，如果需要增大霉赡，則把其設(shè)為上半?yún)^(qū)的中間下標(biāo)，反之則設(shè)為下半?yún)^(qū)的中間下標(biāo)幔托，所以這種搜索方式的時(shí)間復(fù)雜度和二分查找的時(shí)間復(fù)雜度一樣穴亏，為了使時(shí)間復(fù)雜度盡量的小，我們使A成為長(zhǎng)度更小的那個(gè)數(shù)組重挑，如果初始A比B長(zhǎng)嗓化，我們則交換它們的位置。

考慮邊界條件：

1.如果不存在滿足條件二的情況會(huì)怎么樣呢谬哀？也就是 i 走到了數(shù)組A的盡頭刺覆，依舊沒(méi)法滿足條件二，這個(gè)時(shí)候我們不難知道如果 i 走到數(shù)組A的最左端史煎，那么它一定是在不斷地經(jīng)歷情況4谦屑，而這時(shí) A[0] > B[j]，那么我們不難知道這時(shí)left_part的最大值就是B[j - 1]篇梭；反之我們也可以推出 i 到了A的最右端氢橙、j 到了B的最左端或者最右端的情況。

2.m + n 為奇數(shù)恬偷。這個(gè)時(shí)候我們不難推出 left_part 的最大值就是中位數(shù)悍手。

3.A或B為空數(shù)組，因?yàn)楫?dāng)數(shù)組空的時(shí)候無(wú)法對(duì)數(shù)組進(jìn)行下標(biāo)訪問(wèn)，所以我們?cè)谶M(jìn)行二分查找前就應(yīng)該對(duì)該情況進(jìn)行特殊處理谓苟，處理方式也是很簡(jiǎn)單的啦官脓。

實(shí)現(xiàn)代碼：

// 4. Median of Two Sorted Arrays
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  // 使得 nums1 短于 nums2
  int m = nums1.size();
  int n = nums2.size();
  if (m > n) {
    vector<int> temp = nums1;
    nums1 = nums2;
    nums2 = temp;
    m = m + n;
    n = m - n;
    m = m - n;
  }
  // 考慮數(shù)組長(zhǎng)度為0的邊界情況
  if (m == 0) {
    if (n == 0) {
      return 0;
    } else {
      if (n % 2 == 1) {
        return nums2[n / 2];
      } else {
        return (double)(nums2[n / 2] + nums2[n / 2 - 1]) / 2;
      }
    }
  }
  int iMin = 0, iMax = m, sizeSum = (m + n + 1) / 2, i, j;
  while (iMin <= iMax) {
    i = (iMax + iMin) / 2;
    j = sizeSum - i;
    if (nums2[j - 1] > nums1[i] && i < iMax) {
      iMin = i + 1;
    } else if (nums1[i - 1] > nums2[j] && i > iMin) {
      iMax = i - 1;
    } else {
      int maxLeft, minRight;
      if (i == 0) {
        maxLeft = nums2[j - 1];
      } else if (j == 0) {
        maxLeft = nums1[i - 1];
      } else {
        maxLeft = max(nums1[i - 1], nums2[j - 1]);
      }
      if ((m + n) % 2 == 1) {
        return maxLeft;
      }
      if (i == m) {
        minRight = nums2[j];
      } else if (j == n) {
        minRight = nums1[i];
      } else {
        minRight = min(nums1[i], nums2[j]);
      }
      return (double)(maxLeft + minRight) / 2;
    }
  }
  return 0;
}

問(wèn)題描述：

There are two sorted arrays **nums1 **and **nums2 **of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

5. Longest Palindromic Substring【medium】

解題思路：

暴力解法 O(N^3)：

字符串有 n(n-1)/2 個(gè)子串，對(duì)每個(gè)子串進(jìn)行檢測(cè)涝焙，看其是否是回文子串卑笨。因此復(fù)雜度為 O(N^3)。

從字符串中間開(kāi)始擴(kuò)展 O(N^2)：

把字符串的每個(gè)點(diǎn)分別當(dāng)成回文子串的中間點(diǎn)仑撞，開(kāi)始往兩端擴(kuò)展赤兴，不斷檢測(cè)，直到兩端不相等為止隧哮。因此復(fù)雜度為 O(N^2)桶良。

動(dòng)態(tài)規(guī)劃 O(N^2)：

用 dp[i][j] 表示下標(biāo)為 i 開(kāi)頭 j 結(jié)尾的子串是否是回文子串。

轉(zhuǎn)移方程：dp[i][j] = (dp[i + 1][j - 1] && s[i] == s[j]) 【含義：當(dāng)且僅當(dāng)子串首尾兩端相等沮翔，且去除首尾兩端依舊是回文串時(shí)陨帆，該子串才會(huì)是回文串】

初始條件：對(duì)于每個(gè)長(zhǎng)度為1的子串 dp[i][i] 都為回文串；對(duì)于每個(gè)長(zhǎng)度為2的子串 dp[i][i + 1]采蚀，當(dāng)其首尾兩端相等時(shí)疲牵，其為回文串，否則不是榆鼠。

實(shí)現(xiàn)代碼：

// 5. Longest Palindromic Substring (動(dòng)態(tài)規(guī)劃)
string longestPalindrome(string s) {
  int length = s.size();
  if (length == 0) return s;
  int resI = 0, resJ = 0;
  bool dp[length + 1][length + 1];
  for (int i = 0; i <= length; i++)
    dp[i][i] = true;
  for (int i = 0; i < length; i++) {
    if (s[i] == s[i + 1]) {
      dp[i][i + 1] = true;
      if (resJ - resI < 1) {
        resI = i;
        resJ = i + 1;
      }
    } else {
      dp[i][i + 1] = false;
    }
  }
  for (int gap = 2; gap < length; gap++) {
    for (int i = 0; i + gap < length; i++) {
      int j = i + gap;
      if (s[i] == s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        if (resJ - resI < j - i) {
          resI = i;
          resJ = j;
        }
      } else {
        dp[i][j] = false;
      }
    }
  }
  return s.substr(resI, resJ - resI + 1);
}

問(wèn)題描述：

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"

6. ZigZag Conversion【medium】

解題思路：

這道題倒沒(méi)有特別的方法纲爸，就按照題目意思來(lái)模擬 Z 字形即可，用一個(gè)字符串?dāng)?shù)組來(lái)存放每一行的字符串妆够，最后進(jìn)行拼接即可识啦。

考慮邊界條件：

當(dāng)numRows等于1的時(shí)候，因?yàn)閜oint無(wú)法增加也無(wú)法減小神妹，所以沒(méi)辦法共用后面的代碼颓哮，考慮到numRows等于1的時(shí)候，答案就是原字符串灾螃，所以這里直接返回s即可题翻。

實(shí)現(xiàn)代碼：

// 6. ZigZag Conversion
string convert(string s, int numRows) {
  if (numRows == 1) return s;
  string res;
  bool shouldIncrease = true;
  string strArr[numRows];
  int point = 0;
  for (char c : s) {
    strArr[point] += c;
    if (point == numRows - 1) {
      shouldIncrease = false;
    } else if (point == 0) {
      shouldIncrease = true;
    }
    if (shouldIncrease) {
      point++;
    } else {
      point--;
    }
  }
  for (string str: strArr) {
    res += str;
  }
  return res;
}

問(wèn)題描述：

The string"PAYPALISHIRING"is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line:"PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"

Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

7. Reverse Integer【easy】

解題思路：

挨個(gè)遍歷，不斷把末位數(shù)賦給新的值即可腰鬼。

考慮邊界條件：

當(dāng)結(jié)果溢出時(shí)返回0嵌赠，所以為了不讓中間值溢出，采用 long 類型來(lái)保存結(jié)果熄赡。

實(shí)現(xiàn)代碼：

// 7. Reverse Integer
int reverse(int x) {
  long result = 0, longX = abs((long)x);
  while (longX > 0) {
    result = result * 10 + longX % 10;
    longX /= 10;
  }
  result = (x > 0) ? result : -result;
  if (result > INT32_MAX || result < INT32_MIN) {
    return 0;
  } else {
    return (int)result;
  }
}

問(wèn)題描述：

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [?2^31, 2^31 ? 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

8. String to Integer (atoi)【medium】

解題思路：

遍歷字符串然后進(jìn)行分情況討論：（ isInit 表示數(shù)字是否已經(jīng)開(kāi)始姜挺，通過(guò) isInit 的值判斷是否為開(kāi)頭，如果為 true 表示不是開(kāi)頭）

(1) 空格：如果為開(kāi)頭空格則continue彼硫，否則跳出循環(huán)

(2) 正負(fù)號(hào)：如果為開(kāi)頭正負(fù)號(hào)則設(shè)置isNeg的值炊豪，否則跳出循環(huán)

(3) 數(shù)字：將 isInit 置為true凌箕，累加結(jié)果

(4) 其他符號(hào)：跳出循環(huán)

考慮邊界條件：

當(dāng)結(jié)果溢出時(shí)根據(jù)正負(fù)返回 INT32_MAX 或者 INT32_MIN，所以為了不讓中間值溢出词渤，采用 long 類型來(lái)保存結(jié)果牵舱。

實(shí)現(xiàn)代碼：

// 8. String to Integer (atoi)
int myAtoi(string str) {
  long result = 0;
  bool isInit = false;
  bool isNeg = false;
  for (char c : str) {
    if (c == ' ') {
      if (isInit) {
        break;
      } else {
        continue;
      }
    } else if (c == '-' || c == '+') {
      if (!isInit) {
        isInit = true;
      } else {
        break;
      }
      isNeg = (c == '-');
    } else if (c >= 48 && c <= 57) {
      isInit = true;
      result = result * 10 + (c - 48);
      if (result > INT32_MAX) { 
        return isNeg ? INT32_MIN : INT32_MAX;
      }
    } else {
      break;
    }
  }      
  return (int)(isNeg ? -result : result);
}

問(wèn)題描述：

Implementatoiwhich converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

• Only the space character' 'is considered as whitespace character.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [?2^31, 2^31 ? 1]. If the numerical value is out of the range of representable values, INT_MAX (2^31 ? 1) or INT_MIN (?2^31) is returned.

Example 1:

Input: "42"
Output: 42

Example 2:

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (?231) is returned.

9. Palindrome Number【medium】

解題思路：

利用第七題的代碼，將數(shù)字反轉(zhuǎn)缺虐，判斷與原數(shù)字是否相等即可芜壁，這里考慮到負(fù)數(shù)全部都不是回文數(shù)字，所以直接返回false高氮。

實(shí)現(xiàn)代碼：

// 9. Palindrome Number
int reverse(int x) {
  long result = 0, longX = abs((long)x);
  while (longX > 0) {
    result = result * 10 + longX % 10;
    longX /= 10;
  }
  result = (x > 0) ? result : -result;
  if (result > INT32_MAX || result < INT32_MIN) {
    return 0;
  } else {
    return (int)result;
  }
}
bool isPalindrome(int x) {
  if (x < 0) {
    return false;
  } else {
    return (x == reverse(x));
  }
}

問(wèn)題描述：

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

10. Regular Expression Matching【hard】

解題思路：

動(dòng)態(tài)規(guī)劃思想解答這道題：

用 dp[i][j] 表示 s 的前 i 個(gè)字符組成的字符串和 p 的 前 j 個(gè)字符組成的字符串是否匹配慧妄。

轉(zhuǎn)移方程：

當(dāng) p[j - 1] == '*' 時(shí)：因?yàn)?* 可以表示匹配零位或者多位，正則匹配這里要做貪心考慮剪芍，分三種情況塞淹，只要其中一種滿足即為true：

• 匹配零位：則 dp[i][j] = dp[i][j - 2]
• 匹配一位：則 dp[i][j] = dp[i - 1][j - 2] && (滿足最后一位匹配)
• 匹配多位：則一位一位匹配，dp[i][j] = dp[i - 1][j] && (滿足最后一位匹配)

當(dāng) p[j - 1] != '*' 時(shí)罪裹，dp[i][j] 當(dāng)且僅當(dāng) dp[i - 1][j - 1]為true時(shí)饱普，并且最后一位匹配成功時(shí)，才為true状共。

初始狀態(tài)：

顯然费彼，當(dāng) s 不為空，p 為空的時(shí)候dp[i][j] = false口芍；

其次，當(dāng) s 為空雇卷，p不為空的時(shí)候鬓椭，考慮到 * 可以匹配零位，所以利用狀態(tài)轉(zhuǎn)移方程判斷其是否應(yīng)該為true关划。

實(shí)現(xiàn)代碼：

// 10. Regular Expression Matching
bool isMatch(string s, string p) {
  int n = s.size();
  int m = p.size();
  // initial
  bool dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      dp[i][j] = false;
    }
  }
  // start
  dp[0][0] = true;
  for (int i = 1; i < n + 1; i++) {
    dp[i][0] = false;
  }
  for (int j = 1; j < m + 1; j++) {
    if (j % 2 == 0) {
      dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
    } else {
      dp[0][j] = false;
    }
  }
  // trans
  bool compare;
  for (int i = 1; i < n + 1; i++) {
    for (int j = 1; j < m + 1; j++) {
      if (p[j - 1] != '*') {
        dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
      } else {
        compare = (s[i - 1] == p[j - 2] || p[j - 2] == '.');
        dp[i][j] = dp[i][j - 2] || (dp[i - 1][j - 2] && compare) || (dp[i - 1][j] && compare);
      }
    }
  }
  return dp[n][m];
}

問(wèn)題描述：

Given an input string (s) and a pattern (p), implement regular expression matching with support for'.'and'*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover theentireinput string (not partial).

Note:

• scould be empty and contains only lowercase lettersa-z
• pcould be empty and contains only lowercase lettersa-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false