403. Frog Jump

In first place, the solution can be done by recursion and is very straightforward. The tricky part is in line 9 because when gap is less than k, the frog has to jump over the stone as it only has choices of k-1, k and k+1.

1:  class Solution {  
2:  public:  
3:    bool canCross(vector<int>& stones) {  
4:      return canJump(stones, 0, 0);  
5:    }  
6:    bool canJump(vector<int> &stones, int pos, int k) {  
7:      for (int i = pos+1; i < stones.size(); i++) {  
8:        int gap = stones[i] - stones[pos];  
9:        if (gap < k - 1) continue; // the frog has to jump over the stone.  
10:        if (gap > k + 1) return false;  
11:        if (canJump(stones, i, gap, dp)) return true;  
12:      }  
13:      return pos == stones.size()-1;  
14:    }  
15:  };  

However, this solution gets TLE. So the memorization is used.

1:  class Solution {  
2:  public:  
3:    bool canCross(vector<int>& stones) {  
4:      set<pair<int,int>> dp;  
5:      return canJump(stones, 0, 0, dp);  
6:    }  
7:    bool canJump(vector<int> &stones, int pos, int k, set<pair<int,int>> &dp) {  
8:      if (dp.count(make_pair(pos, k))) return false;  
9:      for (int i = pos+1; i < stones.size(); i++) {  
10:        int gap = stones[i] - stones[pos];  
11:        if (gap < k - 1) continue; // the frog has to jump over the stone.  
12:        if (gap > k + 1) { dp.insert(make_pair(pos, k)); return false; }  
13:        if (canJump(stones, i, gap, dp)) { dp.insert(make_pair(pos, k)); return true; }  
14:      }  
15:      return pos == stones.size()-1;  
16:    }  
17:  };  

410. Split Array Largest Sum

I don't have clue in the first place, so I followed the top rated solution.
The idea is the minimized maximum sum among the subarrays must between the largest number in the array and the sum of the total array. So we should think of the binary search.
Once we think about the binary search, we need to find the validation condition. Given the mid number, the condition is invalid if there are more than m subarrays that have sum larger than mid number.

1:  class Solution {  
2:  public:  
3:    int splitArray(vector<int>& nums, int m) {  
4:      long long left = 0, right = 0;  
5:      for (n : nums) {  
6:        left = max(left, (long long)n);  
7:        right += n;  
8:      }  
9:      while (left < right) {  
10:        long long mid = (left + right) / 2;  
11:        if (isValid(nums, m, mid)) right = mid;  
12:        else left = mid + 1;  
13:      }  
14:      return left;  
15:    }  
16:    bool isValid(vector<int> &nums, int m, int maxSum) {  
17:      long long cur = 0;  
18:      int count = 0;  
19:      for (n : nums) {  
20:        cur += n;  
21:        if (cur > maxSum) {  
22:          cur = n, count++;  
23:          // you've got m subarrays that have sum larger than maxSum,  
24:          // so maxSum isn't a minimized sum among these subarrays.  
25:          if (count == m) return false;  
26:        }  
27:      }  
28:      return true;  
29:    }  
30:  };  

404. Sum of Left Leaves

Well, very straightforward solution.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    int sumOfLeftLeaves(TreeNode* root) {  
13:      if (root == NULL) return 0;  
14:      int sum = 0;  
15:      if (isLeaf(root->left)) sum += root->left->val + sumOfLeftLeaves(root->right);  
16:      else sum = sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);  
17:      return sum;  
18:    }  
19:    bool isLeaf(TreeNode *root) {  
20:      if (root == NULL) return false;  
21:      if (root->left == NULL && root->right == NULL) return true;  
22:      return false;  
23:    }  
24:  };  

402. Remove K Digits

I was thinking the K digits must be consecutive but it turns out it's not necessary. So the problem becomes easier. All I need to do is to discard the number that is larger than current number. Line 13 is very trick. Without this line, the code fails the case of ["9", 1]

1:  class Solution {  
2:  public:  
3:    string removeKdigits(string num, int k) {  
4:      string res = "";  
5:      int n = num.size(), sz = n-k;  
6:      for (c : num) {  
7:        while (k && !res.empty() && res.back() > c) {  
8:          res.pop_back();  
9:          k--;  
10:        }  
11:        res += c;  
12:      }  
13:      res.resize(sz);  
14:      int i = 0;  
15:      while (!res.empty() && res[i] == '0') i++;  
16:      res = res.substr(i);  
17:      return res.empty() ? "0" : res;  
18:    }  
19:  };  

417. Pacific Atlantic Water Flow

We should start from the boundary of the matrix to see if they can reach the other ocean. So it is a typical DSF problem. For DSF problem, we need to have a visited matrix. The trick here is right on the visited matrix. The value in visited matrix is no long bool now. It should use bit to represent the ocean. We can have 0b01 to be pacific and 0b10 to be atlantic. So only when visited becomes 0b11, we know the element is able to reach both oceans.

1:  class Solution {  
2:  private:  
3:    int rows, cols;  
4:    vector<pair<int,int>> res;  
5:    vector<vector<int>> visited;  
6:    vector<pair<int,int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
7:  public:  
8:    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {  
9:      if (matrix.empty()) return res;  
10:      rows = matrix.size(), cols = matrix[0].size();  
11:      visited = vector<vector<int>>(rows, vector<int>(cols, 0));  
12:      for (int i = 0; i < rows; i++) {  
13:        dfs(matrix, i, 0, INT_MIN, 1); // 1 is pacific  
14:        dfs(matrix, i, cols-1, INT_MIN, 2); // 2 is atlatic  
15:      }  
16:      for (int j = 0; j < cols; j++) {  
17:        dfs(matrix, 0, j, INT_MIN, 1);  
18:        dfs(matrix, rows-1, j, INT_MIN, 2);  
19:      }  
20:      return res;  
21:    }  
22:    void dfs(vector<vector<int>> &matrix, int i, int j, int prev, int ocean) {  
23:      if (i<0||j<0||i==rows||j==cols||matrix[i][j]<prev||(visited[i][j]&ocean)==ocean) return;  
24:      visited[i][j] |= ocean;  
25:      if (visited[i][j] == 3) res.push_back(make_pair(i, j));  
26:      for (int d = 0; d < dir.size(); d++) {  
27:        int ii = i + dir[d].first;  
28:        int jj = j + dir[d].second;  
29:        dfs(matrix, ii, jj, matrix[i][j], visited[i][j]);  
30:      }  
31:    }  
32:  };  

407. Trapping Rain Water II

I don't have any clue to solve the problem. I have to follow the top rated solution. The idea behind is
(1) Use minimum heap to store the height for most outer boarder and scan from the lowest height.
(2) For the top height in the heap (h1), we need to record the lowest height (it's the maxH in the code). (Why? Because it is the lowest height in the most out boundary, we expect it to grow only. If there is any height lower than current lowest height, it has trapped water.) If it has neighbor with lower height (h2), then the neighbor must be able to hold water (maxH - h2). Why? Because at this time the boundary has been updated and maxH is the lowest height so far, please see step (3).
(3) Mark the neighbor as visited and push it to the heap. Since the neighbor has been visited, the boundary is updated.
(4) repeat (2) - (3) until heap becomes empty.

1:  class Solution {  
2:  public:  
3:    int trapRainWater(vector<vector<int>>& heightMap) {  
4:      if (heightMap.empty()) return 0;  
5:      int rows = heightMap.size(), cols = heightMap[0].size();  
6:      priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;  
7:      vector<vector<bool>> visited(rows, vector<bool>(cols, false));  
8:      for (int i = 0; i < rows; i++) {  
9:        for (int j = 0; j < cols; j++) {  
10:          if (i == 0 || i == rows-1 || j == 0 || j == cols-1) {  
11:            q.push(make_pair(heightMap[i][j], i*cols+j));  
12:            visited[i][j] = true;  
13:          }  
14:        }  
15:      }  
16:      vector<pair<int,int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
17:      int res = 0, maxH = INT_MIN;  
18:      while (!q.empty()) {  
19:        int height = q.top().first;  
20:        int i = q.top().second / cols, j = q.top().second % cols;  
21:        q.pop();  
22:        maxH = max(maxH, height);  
23:        for (int d = 0; d < dir.size(); d++) {  
24:          int ii = i + dir[d].first;  
25:          int jj = j + dir[d].second;  
26:          if (ii < 0 || jj < 0 || ii == rows || jj == cols || visited[ii][jj]) continue;  
27:          visited[ii][jj] = true;  
28:          if (heightMap[ii][jj] < maxH) res += maxH - heightMap[ii][jj];  
29:          q.push(make_pair(heightMap[ii][jj], ii*cols+jj));  
30:        }  
31:      }  
32:      return res;  
33:    }  
34:  };  

409. Longest Palindrome

Very straightforward solution. Count the frequency for characters in the input string. If a character appears even times, it must be a part of palindrome. On the other hand, if a character appears odd times, then we want to add (odd times - 1). In the end, if there is odd time character, the return value should be added one.

1:  class Solution {  
2:  public:  
3:    int longestPalindrome(string s) {  
4:      unordered_map<char, int> mp;  
5:      for (c : s) mp[c]++;  
6:      int res = 0, odd = 0;  
7:      for (auto it : mp) {  
8:        if (it.second & 1) { res += it.second - 1, odd = 1; }  
9:        else res += it.second;  
10:      }  
11:      return res + odd;  
12:    }  
13:  };  

408. Valid Word Abbreviation

No trick. Pretty straightforward solution. Note when return, we need to check if we've reached both ends of word and it abbreviation.

1:  class Solution {  
2:  public:  
3:    bool validWordAbbreviation(string word, string abbr) {  
4:      int i = 0, j = 0;  
5:      while (i < word.size() && j < abbr.size()) {  
6:        if (!isNum(abbr[j])) {  
7:          if (word[i++] != abbr[j++]) return false;  
8:        } else {  
9:          if (abbr[j] == '0') return false;  
10:          int l = 0;  
11:          while (j < abbr.size() && isNum(abbr[j])) {  
12:            l = l * 10 + abbr[j++] - '0';  
13:          }  
14:          i += l;  
15:        }  
16:      }  
17:      return i == word.size() && j == abbr.size();  
18:    }  
19:    bool isNum(char c) {  
20:      return c >= '0' && c <= '9';  
21:    }  
22:  };  

399. Evaluate Division

I don't have clue to solve the problem. I followed one of the top rated solutions.
The idea is that each equation is a link of graph with value as weight on the link. Note the graph should be directed because given a/b=x it's easy to get b/a=1/x. Therefore, for a query a/c, it is to find a valid path that connects node a and c.

For example, a / b = 3.0, b / c = 2.0, the graph looks like:
a <==> b <==> c. So for query, a/c, the path exists and the value is 3.0 * 2.0 = 6.0. On the other hand, for query c/a, the path also exists and the value is 1 / 3* 1 / 2 = 1 / 6.

The path can be find by DFS. Note, to avoid loop, i.e. a / b * b / a = 1, we need to have a set to cache the visited node.

1:  class Solution {  
2:  public:  
3:    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {  
4:      unordered_map<string, unordered_map<string, double>> mp;  
5:      for (int i = 0; i < equations.size(); i++) {  
6:        mp[equations[i].first].insert(make_pair(equations[i].second, values[i]));  
7:        mp[equations[i].second].insert(make_pair(equations[i].first, 1 / values[i]));  
8:      }  
9:      vector<double> res;  
10:      for (auto q : queries) {  
11:        unordered_set<string> s;  
12:        double tmp = check(mp, q.first, q.second, s);  
13:        if (tmp) res.push_back(tmp);  
14:        else res.push_back(-1);  
15:      }  
16:      return res;  
17:    }  
18:    double check(unordered_map<string, unordered_map<string, double>> &mp, string up, string down, unordered_set<string> &s) {  
19:      if (mp[up].find(down) != mp[up].end()) return mp[up][down];  
20:      for (auto it : mp[up]) {  
21:        if (s.find(it.first) == s.end()) {  
22:          s.insert(it.first);  
23:          double tmp = check(mp, it.first, down, s);  
24:          if (tmp) return it.second * tmp;  
25:        }  
26:      }  
27:      return 0;  
28:    }  
29:  };  

400. Nth Digit

The solution consists of three steps:
- find the length of number that the Nth digit comes from
- find the number that contains Nth digit
- find the Nth digit

Note the variable "count" must be long because "count *= 10" could make it overflow.

1:  class Solution {  
2:  public:  
3:    int findNthDigit(int n) {  
4:      int len = 1;  
5:      long count = 9;  
6:      int start = 1;  
7:      while (n > len * count) {  
8:        n -= len * count;  
9:        len++;  
10:        count *= 10;  
11:        start *= 10;  
12:      }  
13:      start += (n - 1) / len;  
14:      string s = to_string(start);  
15:      return s[(n-1) % len] - '0';  
16:    }  
17:  };  

389. Find the Difference

The naive way is to sort the two strings and find the different character. The code is very straightforward.

1:  class Solution {  
2:  public:  
3:    char findTheDifference(string s, string t) {  
4:      sort(s.begin(), s.end());  
5:      sort(t.begin(), t.end());  
6:      int i = 0;  
7:      for (; i < s.size(); i++) {  
8:        if (s[i] != t[i]) break;  
9:      }  
10:      return t[i];  
11:    }  
12:  };  

However, this problem is actually equivalent to the problem of "136. Single Number".

1:  class Solution {  
2:  public:  
3:    char findTheDifference(string s, string t) {  
4:      char res = 0;  
5:      for (c : s) res ^= c;  
6:      for (c : t) res ^= c;  
7:      return res;  
8:    }  
9:  };  

401. Binary Watch

The idea behind is to enumerate all possible combinations and count the bit of 1. If the bits number matches the input, then output the time.

1:  class Solution {  
2:  public:  
3:    vector<string> readBinaryWatch(int num) {  
4:      vector<string> res;  
5:      for (int h = 0; h < 12; h++) {  
6:        for (int m = 0; m < 60; m++) {  
7:          if (countBits((h << 6) | m) == num) {  
8:            res.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));  
9:          }  
10:        }  
11:      }  
12:      return res;  
13:    }  
14:    int countBits(int n) {  
15:      int count = 0;  
16:      while (n) {  
17:        n &= n-1;  
18:        count++;  
19:      }  
20:      return count;  
21:    }  
22:  };  

406. Queue Reconstruction by Height

I don't have clue to solve the problem in first place. I followed the top rated solution.
- sort the array by the height in descending order and if heights are the same then sort by the k number in ascending order.
- create an empty array and insert into kth position the sorted people one by one.

1:  class Solution {  
2:  public:  
3:    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {  
4:      auto comp = [](pair<int, int> &p1, pair<int, int> &p2) {  
5:        return (p1.first > p2.first) || (p1.first == p2.first && p1.second < p2.second);  
6:      };  
7:      sort(people.begin(), people.end(), comp);  
8:      vector<pair<int, int>> res;  
9:      for (auto p : people) {  
10:        res.insert(res.begin() + p.second, p);  
11:      }  
12:      return res;  
13:    }  
14:  };  

394. Decode String

One way to solve the problem is DFS. But the trick is the input index. The index must be reference (or pointer) because it should be continuous to the function call in the stack.

1:  class Solution {  
2:  public:  
3:    string decodeString(string s) {  
4:      int i = 0;  
5:      return helper(s, i);  
6:    }  
7:    string helper(string s, int &i) {  
8:      string res;  
9:      while (i < s.size() && s[i] != ']') {  
10:        if (!isDigit(s[i])) res += s[i++];  
11:        else {  
12:          int n = 0;  
13:          while (i < s.size() && isDigit(s[i])) n = n * 10 + s[i++] - '0';  
14:          i++; // '['  
15:          string t = helper(s, i);  
16:          i++; // ']'  
17:          for (int j = 0; j < n; j++) res += t;  
18:        }  
19:      }  
20:      return res;  
21:    }  
22:    bool isDigit(char c) {  
23:      return c >= '0' && c <= '9';  
24:    }  
25:  };  

393. UTF-8 Validation

The idea is count bytes first and validate the following bytes.

1:  class Solution {  
2:  public:  
3:    bool validUtf8(vector<int>& data) {  
4:      int c = 0;  
5:      for (int d : data) {  
6:        if (c == 0) {  
7:          if ((d >> 7) == 0) c = 0;  
8:          else if ((d >> 5) == 0b110) c = 1;  
9:          else if ((d >> 4) == 0b1110) c = 2;  
10:          else if ((d >> 3) == 0b11110) c = 3;  
11:          else return false;  
12:        } else {  
13:          if ((d >> 6) != 0b10) return false;  
14:          c--;  
15:        }  
16:      }  
17:      return c == 0;  
18:    }  
19:  };  

388. Longest Absolute File Path

This problem has long long description and the file path is very confusing at the first glance. However, if you read the path carefully, you'll find that '\t' indicates the depth of a directory or file and '\n' indicates the end of the directory or file. Also you should notice that the file in the path appears one by one, so the solution becomes to have an array to store the length for each depth and once reaches a file, compute the total length to the file. After computing a file, everything can be reset to start finding a new file.

1:  class Solution {  
2:  public:  
3:    int lengthLongestPath(string input) {  
4:      int maxL = 0, l = 1, len = 0;  
5:      bool isFile = false;  
6:      vector<int> level(1, 0);  
7:      for (int i = 0; i < input.size(); i++) {  
8:        while (input[i] == '\t') {  
9:          l++, i++;  
10:        }  
11:        while (input[i] != '\n' && i < input.size()) {  
12:          if (input[i] == '.') isFile = true;  
13:          len++, i++;  
14:        }  
15:        if (isFile) {  
16:          maxL = max(maxL, level[l-1]+len);  
17:        } else {  
18:          if (l == level.size()) level.push_back(level[l-1]+len+1);  
19:          else level[l] = level[l-1] + len + 1;  
20:        }  
21:        len = 0, l = 1, isFile = false;  
22:      }  
23:      return maxL;  
24:    }  
25:  };  

67. Add Binary

Very straightforward solution. I think the little challenge is the make the code clean and clever.

1:  class Solution {  
2:  public:  
3:    string addBinary(string a, string b) {  
4:      string s = "";  
5:      int c = 0, i = a.size()-1, j = b.size()-1;  
6:      while (i >= 0 || j >= 0 || c == 1) {  
7:        c += i >= 0 ? a[i--] - '0' : 0;  
8:        c += j >= 0 ? b[j--] - '0' : 0;  
9:        char t = c % 2 + '0';  
10:        s = t + s;  
11:        c /= 2;  
12:      }  
13:      return s;  
14:    }  
15:  };  

283. Move Zeroes

Simple two pointers problem. We can have two pointers i and j. i is pointing to the next element in the array to check and j is pointing to the first 0 position. So for example [0, 0, 0, 1, 2]
1st round, i = 0, j = 0: 0, 0, 0, 1, 2
2nd round, i = 1, j = 0: 0, 0, 0, 1, 2
3rd round, i = 2, j = 0: 0, 0, 0, 1, 2
4th round, i = 3, j = 0: 1, 0, 0, 0, 2
5th round, i = 4, j = 1, 1, 2, 0, 0, 0

Another example, [1, 0, 3]
1st round, i = 0, j = 0: 1, 0, 3
2nd round, i = 1, j = 1: 1, 0, 3
3rd round, i = 2, j = 1: 1, 3, 0

1:  class Solution {  
2:  public:  
3:    void moveZeroes(vector<int>& nums) {  
4:      int i = 0, j = 0;  
5:      while (i < nums.size()) {  
6:        if (nums[i] == 0) {  
7:          i++;  
8:        } else {  
9:          swap(nums[i++], nums[j++]);  
10:        }  
11:      }  
12:    }  
13:  };