419. Battleships in a Board

The key to solve this problem is the following two conditions:

- Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.

- At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

So the problem becomes something similar to counting islands where islands here is 'X's surrounded by '.'.

1:  class Solution {  
2:  public:  
3:    int countBattleships(vector<vector<char>>& board) {  
4:      int count = 0;  
5:      for (int i = 0; i < board.size(); i++) {  
6:        for (int j = 0; j < board[0].size(); j++) {  
7:          if (board[i][j] == 'X' && (i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X')) count++;  
8:        }  
9:      }  
10:      return count;  
11:    }  
12:  };  

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:  };