Leetcode solutions

Crack_Leetcode.md

刷题专用Gist

Q1.cpp

/* https://leetcode.com/problems/two-sum/ */
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); i++) {
            int key = nums[i] <= (target/2) ? nums[i] : (target-nums[i]);
            // Be careful! Two exactly the same elements will be mapped to the same bin as well!
            if (hashtable.count(key) && (nums[hashtable[key]]+nums[i] == target)) {
                return vector<int>{hashtable[key]+1, i+1};   
            }
            if (!hashtable.count(key)) hashtable[key] = i;
        }
        return vector<int>();
    }
};

Q104.cpp

/* Maximum Depth of Binary Tree */

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
  public:
    int maxDepth(TreeNode* root) {
      if (!root) return 0;
      int left_height = maxDepth(root->left);
      int right_height = maxDepth(root->right);
      return 1 + (left_height > right_height ? left_height : right_height);
    }
};

Q11.cpp

/* https://leetcode.com/problems/container-with-most-water/ */

/* 从首尾两个线开始，找到两个中较短的线，看起他地方有没有比它长的，如果有，看面积会不会变大 */

class Solution {
public:
    int maxArea(vector<int>& height) {
        int front = 0, end = height.size()-1;
        int area = 0;
        while (front < end) {
            area = max(area, (end-front)*min(height[end], height[front]));
            if (height[end] < height[front]) end --;
            else front ++;
        }
        return area;
    }
};

Q115.cpp

/* https://leetcode.com/problems/distinct-subsequences/ */
/* A Good Solution: https://leetcode.com/discuss/50336/4ms-7-lines-c-dp-solution-very-clear-almost-best */
/*
 * A bad but acceptable DP solution. Basically this problem is asking how many ways can you match each character of `t` to `s` with order not changed. 
 * 用一个buffer记录s起始位置和t起始位置之前的Match的方法数量
 */

#define buf(i,j) _buf[(i)*(_tlen)+(j)]
class Solution {
    int *_buf, _tlen;
    int _nd(int sstart, int tstart, string const& s, string const& t) {
        if (sstart >= s.length() || tstart >= t.length()) return 0;
        if (buf(sstart, tstart) != -1) return buf(sstart, tstart);
        int rtn = 0;
        for (int i = sstart; i < s.length(); i++) {
            if (s[i] == t[tstart]) {
                if (tstart == t.length()-1) {
                    rtn += 1;
                } else {
                    rtn += _nd(i+1, tstart+1, s, t);
                }
            }
        }
        buf(sstart, tstart) = rtn;
        return rtn;
    }
public:
    int numDistinct(string s, string t) {
        if (s.length() < t.length()) return 0;
        _buf = new int[s.length()*t.length()];
        _tlen = t.length();
        memset(_buf, 0xff, sizeof(int) * (s.length()*t.length()));
        int rtn = _nd(0, 0, s, t);
        delete [] _buf;
        _buf = NULL;
        _tlen = 0;
        return rtn;
    }
};

Q125.cpp

/* https://leetcode.com/problems/valid-palindrome/ */
/* 循环终止条件！边界！注意看题！ */

class Solution {
public:
    bool isPalindrome(string s) {
        int front = 0, end = s.length() - 1;
        while (front < end) {
            while (!isalpha(s[front]) && !isdigit(s[front]) && front < end) front ++;
            while (!isalpha(s[end]) && !isdigit(s[end]) && end > front) end--;
            if (tolower(s[front]) != tolower(s[end])) return false;
            front ++;
            end --;
        }
        return true;
    }
};

Q147.cpp

/* https://leetcode.com/problems/insertion-sort-list/ */
/* 又是一道看似简单的题，里面坑还是挺多的 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode node(INT_MIN), *nodeptr = &node;
        node.next = head;
        ListNode * next = NULL;;
        for (auto curr = head; curr != NULL; curr = next) { // 这个地方如果直接curr=curr->next会被坑，因为curr->next在后面会被更新。。。
            ListNode * prev = nodeptr;
            next = curr->next;
            for (auto ptr = node.next; ptr != curr; ptr = ptr->next) { // ptr = node.next，如果写成了ptr=head就惨了，因为head可能指向的并不是起点
                if (ptr->val <= curr->val) {
                    prev = ptr;
                    continue;
                }
                prev->next = curr;
                curr->next = ptr;
                while (ptr->next != curr) ptr = ptr->next; // 一定记得要更新curr之前那个节点的下一个节点到curr的next
                ptr->next = next;
                break;
            }
        }
        return node.next;
    }
};

Q148.cpp

/* https://leetcode.com/problems/sort-list/ */

/* merge-sort。我一开始的做法没有实际上把左半边和右半边断开（左半边的最后一个元素不是NULL，而是右半边的某一个元素），然后因为忽视了循环终止条件，导致死循环 */

/* 断开连接的版本 */
class Solution {
public:
    ListNode* sortList(ListNode* begin) {
        if (begin == NULL) return NULL;
        if (begin->next == NULL) return begin;
        ListNode *head, *mid, *tail;
        head = mid = tail = begin;
        while (tail != NULL && tail->next != NULL && tail->next->next != NULL) {
            tail = tail->next->next;
            mid = mid->next;
        }
        auto tmp = mid->next;
        mid->next = NULL;
        ListNode * first = sortList(begin);
        ListNode * second = sortList(tmp);
        ListNode tmpHead(0), *tmpHeadPtr = &tmpHead;
        while (first != NULL && second != NULL) {
            if (first->val < second->val) {
                tmpHeadPtr->next = first;
                first = first->next;
            } else {
                tmpHeadPtr->next = second;
                second = second->next;
            }
            tmpHeadPtr = tmpHeadPtr->next;
        }
        if (first != NULL) {
            tmpHeadPtr->next = first;
        } else {
            tmpHeadPtr->next = second;
        }
        
        return tmpHead.next;
    }
};

/* 保持连接的版本 */
class Solution {
    ListNode* sortList(ListNode* begin, ListNode* end) {
        if (begin->next == end) return begin;
        ListNode *head, *mid, *tail;
        head = mid = tail = begin;
        while (tail != end && tail->next != end && tail->next->next != end) {
            tail = tail->next->next;
            mid = mid->next;
        }
        auto fend = mid->next; // 这里需要把这个mid->next保存下来，因为后面要用这个值来作为左半边Linklist的尾。如果不保存，而是使用mid->next来判断，因为mid->next可能在右半边排序的时候被修改，会导致死循环
        ListNode * first = sortList(begin, fend);
        ListNode * second = sortList(fend, end);
        ListNode tmpHead(0), *tmpHeadPtr = &tmpHead;
        while (first != fend && second != end) {
            if (first->val < second->val) {
                tmpHeadPtr->next = first;
                first = first->next;
            } else {
                tmpHeadPtr->next = second;
                second = second->next;
            }
            tmpHeadPtr = tmpHeadPtr->next;
        }
        if (first != fend) {
            tmpHeadPtr->next = first;
            while (first->next != fend) {
                first = first->next;
            }
            first->next = end;
        } else {
            tmpHeadPtr->next = second;
        }
        
        return tmpHead.next;
    }
public:
    ListNode* sortList(ListNode* head) {
        if (head == NULL) return NULL;
        return sortList(head, NULL);
    }
};

Q169.md

[https://leetcode.com/problems/majority-element/]

这个题还挺tricky的。其实直接用hashmap也可以做，但是有space O(1) time O(n)的算法。整体想法就是majority的元素个数肯定比剩下所有元素的总和还要多，如果我们维护一个candidate的元素和其目前出现的数量，遇到与其相同的数量加一，否则减一。当其数量变成零的时候用其他元素替换掉，那么这个candidate最后一定会是我们要的那个Majority。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int answer = nums[0], counter = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == answer) counter++;
            else {
                if (counter == 0) {
                    answer = nums[i];
                    counter = 1;
                } else {
                    counter--;
                }
            }
        }
        return answer;
    }
};

Q190.cpp

/*https://leetcode.com/problems/reverse-bits/*/

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t rtn = 0;
        for (int i = 0; i < 32; i++) {
            rtn = rtn<<1|(n&0x1);
            n = n>>1;
        }
        return rtn;
    }
};

Q191.cpp

/* https://leetcode.com/problems/number-of-1-bits/ */
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int counter = 0;
        for (int i = 0; i < 32; i++) {
            counter += n&0x1;
            n = n>>1;
        }
        return counter;
    }
};

Q20.cpp

/* https://leetcode.com/problems/valid-parentheses/ */
class Solution {
  inline char sympair(char c) {
    if (c == '}') return '{';
    if (c == ']') return '[';
    if (c == ')') return '(';
    return 0;
  }
  public:
    bool isValid(string s) {
      stack<char> stk;
      for (auto iter = s.begin(); iter != s.end(); iter++) {
        switch(*iter) {
          case '{':
          case '[':
          case '(':
            stk.push(*iter);
            break;
          case '}':
          case ']':
          case ')':
            if (stk.empty() || stk.top() != sympair(*iter)) {
              return false;
            } else {
              stk.pop();
            }
            break;
        }
      }
      return stk.empty();
    }
};

Q200.cpp

/*https://leetcode.com/problems/number-of-islands/*/
/*Union-find，注意下标和merge的条件*/
class Solution {
    vector<int> union_find;
    int trace_root(int target) {
        if (union_find[target] < 0) return target;
        int parent = union_find[target];
        while (union_find[parent] >= 0) parent = union_find[parent];
        union_find[target] = parent;
        return parent;
    }
    void merge_union(int merge_to, int merge_from) {
        int p1 = trace_root(merge_from);
        int p2 = trace_root(merge_to);
        if (p1 == p2) return;
        union_find[p1] = p2;
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) return 0;
        union_find = vector<int>(grid.size() * grid[0].size(), -1);
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == '0') {
                    union_find[i*grid[0].size()+j] = 0; // 不要算错下标
                    continue;
                }
                if (i-1 >= 0 && grid[i-1][j] == '1' && grid[i][j] == '1') merge_union((i-1)*grid[0].size()+j, i*grid[0].size()+j);
                if (j-1 >= 0 && grid[i][j-1] == '1' && grid[i][j] == '1') merge_union(i*grid[0].size()+j-1, i*grid[0].size()+j);
            }
        }
        int result = 0;
        for (int n : union_find) {
            if (n < 0) result++;
        }
        return result;
    }
};

Q203.cpp

/* https://leetcode.com/problems/remove-linked-list-elements/ */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  public:
    ListNode* removeElements(ListNode* head, int val) {
      if (!head) return NULL;
      while (head) {
        if (head->val == val) {
          head = head->next;
        } else {
          break; // 第一次提交时忘了写这个。。。
        }
      }
      if (!head) return NULL; // 需要再次检查head是否为空
      ListNode * prev = head, * curr = prev->next;
      while (curr) {
        if (curr->val == val) {
          prev->next = curr->next;
        } else {
          prev = curr;
        }
        curr = curr->next;
      }
      return head;
    }
};

Q21.cpp

/* https://leetcode.com/problems/merge-two-sorted-lists/ */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode node(0), *head = &node;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                head->next = l1;
                l1 = l1->next;
            } else {
                head->next = l2;
                l2 = l2->next;
            }
            head = head->next;
        }
        if (l1) head->next = l1;
        else head->next = l2;
        return node.next;
    }
};

Q217.cpp

/* https://leetcode.com/problems/contains-duplicate/ */
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if (nums.size() == 0) return false;
        sort(nums.begin(), nums.end());
        for (auto iter = nums.begin()+1; iter != nums.end(); iter++) {
            if (*iter == *(iter-1)) return true;
        }
        
        return false;
    }
};

Q229.md

[https://leetcode.com/submissions/detail/43216705/]

这道题跟Q169是差不多的，考虑最多会有两个majority的candidate，如果一个数字是majority的话，那么它的个数应该比其他非majority的个数的总和还要多，所以思路与Q169类似。因为我们可能有两个candidate，所以维护四个变量分别记录majority candidate和num。最后需要遍历一遍所有的数字确定选择的candidate是正确的。

class Solution {
public:
    vector<int> majorityElement(vector<int> const& nums) {
        if (nums.empty()) return vector<int>();
        if (nums.size() == 1) return nums;
        int tmp = 1;
        while (nums[tmp] == nums[tmp-1]) tmp++;
        int candidate1 = nums[0], candidate2 = nums[tmp], num1 = tmp, num2 = 1;
        for (int i = tmp+1; i < nums.size(); i++) {
            if (nums[i] == candidate1) {
                num1++;
            } else if (nums[i] == candidate2) {
                num2++;
            } else {
                if (num1 == 0) {
                    num1 = 1;
                    candidate1 = nums[i];
                } else if (num2 == 0) {
                    num2 = 1;
                    candidate2 = nums[i];
                } else {
                    num1--;
                    num2--;
                }
            }
        }
        num1 = 0;
        num2 = 0;
        for (int n : nums) {
            if (n == candidate1) num1++;
            else if (n==candidate2) num2++;
        }
        vector<int> v;
        if (num1>(int)(nums.size()/3)) v.push_back(candidate1);
        if (num2>(int)(nums.size()/3)) v.push_back(candidate2);
        return v;
    }
};

Q231.cpp

/* https://leetcode.com/problems/power-of-two/ */

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        int c = 0;
        while (n) {
            c += n&0x1;
            n>>=1;
        }
        return c == 1;
    }
};

/* 更好的方法 */
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0 && !(n&(n-1));
    }
};

Q237.cpp

/* Delete Node in a Linked List */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/* 删除节点需要获知prev节点，在无法获知的情况下通过将next节点值覆盖当前节点的方法，构造当前节点为next节点的prev节点，从而删除next节点 */
class Solution {
  public:
    void deleteNode(ListNode* node) {
      if (!node) return;
      ListNode* next = node->next;
      node->val = next->val;
      node->next = next->next;
    }
};

Q283.cpp

/* https://leetcode.com/problems/move-zeroes/ */
/* 思路就是把所有的非零的都移动到数列前面来 */
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int front = 0, curr = 0;
        while (curr < nums.size()) {
            if (nums[curr] != 0) nums[front++] = nums[curr];
            curr++;
        }
        while (front < nums.size()) {
            nums[front++] = 0;
        }
    }
};

Q29.md

https://leetcode.com/problems/divide-two-integers/

这道题有很多边界情况需要考虑比较的坑。如果图省事的话可以将输入变量类型改为long long，我没试过，理论上应该可以直接过，因为大部分边界情况都是在处理各种越界。

1. 这道题可以考虑将除数按位左移或者被除数按位右移，可问题在于按位左移会导致int类型溢出，所以必须采用右移的方法
2. 很容易理解的是如果除数是INT_MIN，那么除非被除数也是INT_MIN，否则结果一定是0（向0取整）
3. 如果被除数是INT_MIN的话，这里有很多种情况
4. 如果除数是-1那么结果就是-INT_MIN，越界，直接返回INT_MAX
5. 如果除数不是-1，那么，因为在后面的逻辑里面我的做法是将除数和被除数都取绝对值，然后利用正整数来计算。可是如果被除数是INT_MIN的话，绝对值还是INT_MIN，因为越界了，所以这里有一个trick，就是看到第15行，tmpDividend += tmpDivisor，这句话会使得结果比（两个整数全是正数的情况下）正确结果少1（因为我们确定tmpDivisor是个正数，是divisor的绝对值）

#define c_abs(x) (((x)<0)?(-x):(x))
class Solution {
  public:
    int divide(int dividend, int divisor) {
      if (divisor == 0) return INT_MAX;
      int negative = (dividend & 0x80000000) ^ (divisor & 0x80000000);
      int tmpDividend = dividend;
      int tmpDivisor = c_abs(divisor);
      if (divisor == INT_MIN) {
        if (dividend == INT_MIN) return 1;
        else return 0;
      }
      if (dividend == INT_MIN) {
        if (divisor == -1) return INT_MAX;
        tmpDividend += tmpDivisor;
      }

      int remain = c_abs(tmpDividend);
      if (remain < tmpDivisor) {
        if (dividend == INT_MIN) {
          if (negative) return -1;
          return 1;
        }
        else return 0;
      }
      int result = 0;
      while (remain >= tmpDivisor) {
        int step = 0;
        while ((remain >> step) >= tmpDivisor) step++;
        result += 1 << (step-1);
        remain -= (tmpDivisor << (step - 1));
      }
      if (dividend == INT_MIN) result++;
      if (negative) result = ~result + 1; //-result
      return result;
    }
};

Q42.cpp

/* https://leetcode.com/problems/trapping-rain-water/ */

/* 通过观察我们可以发现其实包含墙壁和水在内整个是一个凸多边形。我们从最底层开始，看这个多边形在每一层是从左边哪里开始，到右边哪里结束，由此可以获得整个多边形的面积。然后整个多边形的面积减去墙的面积（墙的面积可以通过对数组直接求和得到）就可以得到水的面积。我们使用front和back两个指针，这两个指针相遇的时候循环结束。 */

class Solution {
  public:
    int trap(vector<int>& height) {
        if (height.size() < 1) return 0;
      size_t front = 0, back = height.size()-1;
      int size = 0, level = 1;
      while (front < back) {
        if (height[front] >= level) {
          if (height[back] >= level) {
            size += back - front + 1;
            level ++;
          } else {
            back --;
          }
        } else {
          front ++;
        }
      }
      if (height[front] >= level) {
        size += height[front] - level + 1;
      }
      int sum = 0;
      for (vector<int>::iterator iter = height.begin(); iter != height.end(); iter ++) {
        sum += *iter;
      }
      return size - sum;
    }
};

Q48.cpp

/* https://leetcode.com/problems/rotate-image/ */
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int start = 0, end = matrix.size() - 1;
        while (start < end) {
        /* 下面的for的判断条件是什么？注意啊！ */
            for (int j = 0; j < end-start; j++) {
                int tmp = matrix[start][start+j];
                matrix[start][start+j] = matrix[end-j][start];
                matrix[end-j][start] = matrix[end][end-j];
                matrix[end][end-j] = matrix[start+j][end];
                matrix[start+j][end] = tmp;
            }
            start ++;
            end --;
        }
    }
};

Q58.cpp

/* https://leetcode.com/problems/length-of-last-word/ */

class Solution {
public:
    int lengthOfLastWord(string s) {
        int end = s.length() - 1;
        int counter = 0;
        while (!isalpha(s[end]) && end >= 0) end --;
        for (int i = end; i >= 0 && isalpha(s[i]); i--, counter++);
        return counter;
    }
};

Q6.cpp

/* https://leetcode.com/problems/zigzag-conversion/ */
/* This is a Naive solution */

class Solution {
public:
    string convert(string s, int numRows) {
      if (numRows == 1) return s;
      if (numRows == 0) return "";
        vector<vector<char> > lines(numRows);
        
        int idx = 0, step = -1;
        for (auto iter = s.begin(); iter != s.end(); iter++) {
            if (idx == numRows) {
              idx = numRows - 2;
              step = -1;
            } else if (idx == -1) {
              idx = 1;
              step = 1;
            }
            lines[idx].push_back(*iter);
            idx += step;
        }
        string result;
        for (int i = 0; i < lines.size(); i++) {
            for (int j = 0; j < lines[i].size(); j++) {
                result.push_back(lines[i][j]);
            }
        }
        return result;
    }
};

Q60.md

https://leetcode.com/problems/permutation-sequence/

事实上排列数abcd的编号其实就是：(a-1)*3!+(b'-1)*2!+(c'-1)*1!+1，其中b'、c'指代的并不是数字本身，而是当去掉了排在其前面的所有数字之后，该数字处在剩下所有数字当中的位置。

这个题有两个地方需要注意一下：

1. size_t ptr = (k - sum - 1) / fac;：如果恰巧整除，我们是不希望更换curr指向的数字的，所以k-sum-1使得整除时ptr的值不会变动
2. while (sum < (k - 1)) {：因为一开始说道最后需要+1

class Solution {
  inline int factorial(int n) {
    int r = 1;
    while (n) r *= n--;
    return r;
  }
  public:
  string getPermutation(int n, int k) {
    int numbers[] = {1,2,3,4,5,6,7,8,9};
    int sum = 0;
    size_t curr = 0;
    while (sum < (k - 1)) {
      int fac = factorial(n-curr-1);
      size_t ptr = (k - sum - 1) / fac;
      swap(numbers[curr], numbers[curr + ptr]);
      sort(numbers + curr + 1, numbers + n);
      sum += ptr * fac;
      curr++;
    }
    char out[10] = {0}; // 10字节，因为如果输出为9位的话，需要第10位是0，否则字符串没有结束符
    for (int i = 0; i < n; i++) {
      out[i] = '0' + numbers[i];
    }
    return out;
  }
};

Q67.cpp

/* https://leetcode.com/problems/add-binary/ */
class Solution {
public:
    string addBinary(string a, string b) {
        string longer, shorter, rtn;
        if (a.length() < b.length()) {
            longer = b;
            shorter = a;
        } else {
            longer = a;
            shorter = b;
        }
        int carry = 0;
        for (auto siter = shorter.rbegin(), liter = longer.rbegin(); liter != longer.rend(); liter++) {
            int sdigit;
            if (siter != shorter.rend()) {
                sdigit = *siter - '0';
                siter ++;
            } else {
                sdigit = 0;
            }
            int ldigit = *liter - '0', digit = 0;
            int result = sdigit + ldigit + carry;
            digit = result & 1;
            if (result > 1) {
                carry = 1;
            } else {
                carry = 0;
            }
            rtn.insert(0,1,'0'+digit);
        }
        if (carry) {
            rtn.insert(0,1,'0'+carry);
        }
        return rtn;
    }
};

Q75.cpp

/* https://leetcode.com/problems/sort-colors/ */
/* 主要想法就是三个指针，一个指向左边第一个不是0的位置，另一个指向右边第一个不是2的位置 */

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int red = 0, white = 0, blue = nums.size()-1;
        while (white <= blue) { // 循环终止条件是小于等于，因为blue实际指的是一个未被访问的节点，这个点也需要被测试一下
            if (nums[white] == 0) {
                swap(nums[white], nums[red]);
                red++;
                white++; // red指向的值只有可能是1，因为red始终<=white，也就是说，red指向的值一定是被white访问过了，如果这个值是0那么就早已经更新到之前red的位置了，如果是2那么早就更新给blue了
            } else if (nums[white] == 2) {
                swap(nums[white], nums[blue]);
                blue--;
            } else {
                white++;
            }
        }
    }
};

Q9.cpp

// [https://leetcode.com/problems/palindrome-number/]

// A good solution: [https://leetcode.com/discuss/63070/accepted-c-solution]

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int largest = 1, smallest = 10;
        while (largest < 1000000000 && x / (largest * 10) > 0) largest *= 10;
        while (largest >= smallest) {
            int ldigit = (largest == 1000000000 ? x/largest : x%(largest*10)/largest);
            int rdigit = x%smallest/(smallest/10);
            if (ldigit != rdigit) return false;
            smallest *= 10;
            largest /= 10;
        }
        return true;
    }
};

Q91.md

题目：[https://leetcode.com/problems/decode-ways/]

我对这道题第一种思路是递归的考虑这个问题：对于字符串s可能的组成方式M其实M(s) = M(s.substr(1))+M(s.substr(2))，前提条件是s的前两位构成有效的字母，即>=10且<=26。在这种递归当中我们可以发现，很多操作是重复的。比如M(s.substr(1)) = M(s.substr(2))+M(s.substr(3))，这里M(s.substr(2))的计算就重复了，所以我们把这些重复操作cache起来。在下面的代码当中，我是用了hashtable，但事实上通过一个普通的数组也可以完成cache的任务。

class Solution {
    unordered_map<string, int> table;
public:
    int numDecodings(string s) {
        if (s.empty()) return 0;
        if (s[0] == '0') return 0;
        if (s.length() == 1) return 1;
        if (table.count(s)) return table[s];
        if (atoi(s.substr(0,2).c_str()) <= 26) {
            if (s.length() == 2) return 1+numDecodings(s.substr(1));
            table[s] = numDecodings(s.substr(2)) + numDecodings(s.substr(1));
        } else {
            table[s] = numDecodings(s.substr(1));
        }
        return table[s];
    }
};

在Leetcode上面，上述方法12ms，而且空间复杂度O(n)。我看到许多网友做到了4ms，空间复杂度O(1)，便仔细考虑了一下，得到下面的解法。

想法其实比较简单，但是应看代码可能会比较难懂，解释一下。

对于abcdefg这七个数字来说，如果我们只拿出abc，会发现其实M(c) = M(a) + M(b)，什么意思呢？其实就是，如果我们有三个数字，那么这三个数字能够组成的字母排列其实就是前两个数字能组成的排列加上在后两个数字（bc）为有效字母的情况下第一个数字的排列。

我觉得我解释不清楚了，这里有一个回答：[http://stackoverflow.com/questions/20342462/review-an-answer-decode-ways]

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0' || s.empty()) return 0;
        if (s.length() == 1) return 1;
        
        int chars_ahead_2, chars_ahead_1, result;
        chars_ahead_2 = 1;
        chars_ahead_1 = (atoi(s.substr(0,2).c_str()) <= 26 ? 1 : 0) + (s[1] != '0' ? 1 : 0);
        result = chars_ahead_1;
        for (int i = 2; i < s.length(); i++) {
            result = 0;
            if (s[i] != '0') result = chars_ahead_1;
            int tmp = atoi(s.substr(i-1, 2).c_str());
            if (tmp <= 26 && tmp >=10) result += chars_ahead_2;
            chars_ahead_2 = chars_ahead_1;
            chars_ahead_1 = result;
        }
        return result;
    }
};