

0001-0010

1. Two Sum $\star$

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;

    for (int i = 0; i < nums.size(); ++i) {
      if (map.count(nums[i])) return {map[nums[i]], i};
      map[target - nums[i]] = i;
    }

    throw;
  }
};

2. Add Two Numbers $\star\star$

class Solution {
 public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    int carry = 0;

    while (carry || l1 || l2) {
      carry += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
      curr->next = new ListNode(carry % 10);
      curr = curr->next;
      carry /= 10;
      if (l1) l1 = l1->next;
      if (l2) l2 = l2->next;
    }

    return dummy.next;
  }
};

3. Longest Substring Without Repeating Characters $\star\star$

class Solution {
 public:
  int lengthOfLongestSubstring(string s) {
    int ans = 0;
    unordered_map<char, int> map;

    int j = 0;
    for (int i = 0; i < s.size(); ++i) {
      char c = s[i];
      if (map.count(c)) j = max(j, map[c]);
      ans = max(ans, i - j + 1);
      map[c] = i + 1;
    }

    return ans;
  }
};

4. Median of Two Sorted Arrays $\star\star\star$

• 2个sorted数组，取第K大的数
• 用left_k，right_k（left_k + 1）的trick解决奇偶长度的问题
• 每次取第k/2位置的元素val1，val2比较，如果val1 < val2，则有k/2可以排除了，arr1起点+ k/2，递归查找第k-k/2大的数

class Solution {
  public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
      int lk = (nums1.size() + nums2.size() + 1) / 2;
      int rk = (nums1.size() + nums2.size() + 2) / 2;
      double lret = findKth(nums1, 0, nums2, 0, lk);
      double rret = findKth(nums1, 0, nums2, 0, rk);
      return (lret + rret) / 2;
    }
    double findKth(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
      if (i >= nums1.size()) {
        return nums2[j+k-1];
      }
      if (j >= nums2.size()) {
        return nums1[i+k-1];
      }
      if (k == 1) {
        return min(nums1[i], nums2[j]);
      }

      int val1 = (i+k/2-1 < nums1.size()) ? nums1[i+k/2-1] : INT_MAX;
      int val2 = (j+k/2-1 < nums2.size()) ? nums2[j+k/2-1] : INT_MAX;

      if (val1 < val2) {
        return findKth(nums1, i+k/2, nums2, j, k-k/2);
      } else {
        return findKth(nums1, i, nums2, j+k/2, k-k/2);
      }
    }
};

5. Longest Palindromic Substring $\star\star$

class Solution {
 public:
  string longestPalindrome(string s) {
    const int length = s.length() * 2 + 3;

    // Manacher's Algorithm
    string T(length, '#');
    T[0] = '$';
    T[length - 1] = '@';
    for (int i = 2; i < length - 2; i += 2) T[i] = s[i / 2 - 1];

    int center = 1;
    int right = 1;
    vector<int> P(length, 0);

    for (int i = 1; i < length - 1; ++i) {
      int mirr = 2 * center - i;
      if (i < right) P[i] = min(P[mirr], right - i);
      while (T[i + P[i] + 1] == T[i - P[i] - 1]) ++P[i];
      if (i + P[i] > right) {
        center = i;
        right = i + P[i];
      }
    }

    // find max and the center;
    int max = 0;
    int c = 0;
    for (int i = 0; i < length; ++i)
      if (P[i] > max) {
        max = P[i];
        c = i;
      }

    // omit '#' and get the string desired
    string ans(max, '#');
    int i = 0;
    for (int j = c - max + 1; j < c + max; j += 2) {
      ans[i] = T[j];
      ++i;
    }

    return ans;
  }
};

6. ZigZag Conversion $\star\star$

class Solution {
 public:
  string convert(string s, int numRows) {
    string ans(s);
    vector<vector<char>> rows(numRows);
    int k = 0;
    int direction = (numRows == 1) - 1;

    for (char c : s) {
      rows[k].push_back(c);
      if (k == 0 || k == numRows - 1) direction *= -1;
      k += direction;
    }

    k = 0;
    for (int i = 0; i < numRows; ++i)
      for (int j = 0; j < rows[i].size(); ++j) ans[k++] = rows[i][j];

    return ans;
  }
};

7. Reverse Integer $\star$

class Solution {
 public:
  int reverse(int x) {
    long ans = 0;

    while (x) {
      ans = ans * 10 + x % 10;
      x /= 10;
    }

    if (ans < INT_MIN || ans > INT_MAX) return 0;
    return ans;
  }
};

8. String to Integer (atoi) $\star\star$

class Solution {
 public:
  int myAtoi(string str) {
    long long ans = 0;
    bool isNegative = false;
    int j = 0;

    while (j < str.size() && str[j] == ' ') ++j;
    if (j == str.size()) return 0;
    if (str[j] == '-') {
      isNegative = true;
      ++j;
    } else if (str[j] == '+') {
      ++j;
    }

    for (int i = j; i < str.size(); ++i) {
      if (str[i] < '0' || str[i] > '9')
        break;
      else {
        ans = ans * 10 + (str[i] - '0');
        if (isNegative && -ans <= INT_MIN) return INT_MIN;
        if (!isNegative && ans >= INT_MAX) return INT_MAX;
      }
    }

    return isNegative ? -ans : ans;
  }
};

9. Palindrome Number $\star$

class Solution {
 public:
  bool isPalindrome(int x) {
    if (x < 0) return false;

    long ans = 0;
    int y = x;

    while (y) {
      ans = ans * 10 + y % 10;
      y /= 10;
    }

    return ans == x;
  }
};

10. Regular Expression Matching $\star\star\star$

class Solution {
 public:
  bool isMatch(string s, string p) {
    if (p.empty()) return s.empty();

    bool isFirstMatch = (!s.empty() && (p[0] == s[0] || p[0] == '.'));

    if (p.length() >= 2 && p[1] == '*')
      return (isMatch(s, p.substr(2)) ||
              (isFirstMatch && isMatch(s.substr(1), p)));
    return isFirstMatch && isMatch(s.substr(1), p.substr(1));
  }
};