0001-0010

1. Two Sum $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    const int n1 = nums1.size();
    const int n2 = nums2.size();

    if (n1 > n2) return findMedianSortedArrays(nums2, nums1);

    int l = 0;
    int r = n1;

    while (l <= r) {
      int partition1 = l + (r - l) / 2;
      int partition2 = (n1 + n2 + 1) / 2 - partition1;
      int maxLeft1 = partition1 == 0 ? INT_MIN : nums1[partition1 - 1];
      int maxLeft2 = partition2 == 0 ? INT_MIN : nums2[partition2 - 1];
      int minRight1 = partition1 == n1 ? INT_MAX : nums1[partition1];
      int minRight2 = partition2 == n2 ? INT_MAX : nums2[partition2];
      if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
        return (n1 + n2) % 2 == 0
                   ? (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) * 0.5
                   : max(maxLeft1, maxLeft2);
      else if (maxLeft1 > minRight2)
        r = partition1 - 1;
      else
        l = partition1 + 1;
    }

    throw;
  }
};

5. Longest Palindromic Substring $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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));
  }
};