108. Convert Sorted Array to Binary Search Tree

Well, not much to say. Pretty straightforward DFS 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:    TreeNode* sortedArrayToBST(vector<int>& nums) {  
13:      int n = nums.size();  
14:      return helper(nums, 0, n-1);  
15:    }  
16:    TreeNode *helper(vector<int> &nums, int s, int e) {  
17:      if (s > e) return NULL;  
18:      int mid = s + (e - s) / 2;  
19:      TreeNode *node = new TreeNode(nums[mid]);  
20:      node->left = helper(nums, s, mid-1);  
21:      node->right = helper(nums, mid+1, e);  
22:      return node;  
23:    }  
24:  };  

339. Nested List Weight Sum

The problem requires a depth so I intuitively think of DFS. And yes, DFS works fine with this problem. The idea is loop through the input list, check if it is an integer. If so, add the integer to the sum. If not, recursively call itself and add the returned value to the sum. After I'm done with the loop, return the sum.

1:  /**  
2:   * // This is the interface that allows for creating nested lists.  
3:   * // You should not implement it, or speculate about its implementation  
4:   * class NestedInteger {  
5:   *  public:  
6:   *   // Return true if this NestedInteger holds a single integer, rather than a nested list.  
7:   *   bool isInteger() const;  
8:   *  
9:   *   // Return the single integer that this NestedInteger holds, if it holds a single integer  
10:   *   // The result is undefined if this NestedInteger holds a nested list  
11:   *   int getInteger() const;  
12:   *  
13:   *   // Return the nested list that this NestedInteger holds, if it holds a nested list  
14:   *   // The result is undefined if this NestedInteger holds a single integer  
15:   *   const vector<NestedInteger> &getList() const;  
16:   * };  
17:   */  
18:  class Solution {  
19:  public:  
20:    int depthSum(vector<NestedInteger>& nestedList) {  
21:      return helper(nestedList, 1);  
22:    }  
23:    int helper(vector<NestedInteger> &nestedList, int d) {  
24:      int sum = 0;  
25:      for (int i = 0; i < nestedList.size(); i++) {  
26:        if (nestedList[i].isInteger()) sum += d * nestedList[i].getInteger();  
27:        else sum += helper(nestedList[i].getList(), d+1);  
28:      }  
29:      return sum;  
30:    }  
31:  };  

113. Path Sum II

Don't forget line 24.

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:    vector<vector<int>> pathSum(TreeNode* root, int sum) {  
13:      vector<vector<int>> res;  
14:      vector<int> sol;  
15:      helper(root, sum, sol, res);  
16:      return res;  
17:    }  
18:    void helper(TreeNode *root, int sum, vector<int> &sol, vector<vector<int>> &res) {  
19:      if (root == NULL) return;  
20:      if (root->left == NULL && root->right == NULL) {  
21:        if (sum == root->val) {  
22:          sol.push_back(root->val);  
23:          res.push_back(sol);  
24:          sol.pop_back();  
25:        }  
26:        return;  
27:      }  
28:      sol.push_back(root->val);  
29:      helper(root->left, sum-root->val, sol, res);  
30:      helper(root->right, sum-root->val, sol, res);  
31:      sol.pop_back();  
32:    }  
33:  };  

124. Binary Tree Maximum Path Sum

The idea is very similar to maximum subarray sum problem where a dp array is used to store the local maximal subarray sum at position i, and a global maximal subarray sum variable is updated as the final result. For this problem, we also need to keep the local maximal path and the global maximal path. The following code is what I did in first place.

However, this piece of code is wrong. The helper function returns not the maximal sum on a path (i.e. left->root, or right->root) but the maximal sum for the whole subtree.

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:  private:  
12:    int maxSum = INT_MIN;  
13:  public:  
14:    int maxPathSum(TreeNode* root) {  
15:      helper(root);  
16:      return maxSum;  
17:    }  
18:    int helper(TreeNode *root) {  
19:      if (root == NULL) return 0;  
20:      int prevMax = helper(root->left);
21:      int postMax = helper(root->right);
22:      int val = max(root->val+prevMax, max(root->val+postMax, max(root->val+prevMax+postMax, root->val)));  
23:      if (root->val > val) val = root->val;  
24:      maxSum = max(val, maxSum);  
25:      return val;  
26:    }  
27:  };  

So I modified the code and eventually got the right 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:  private:  
12:    int maxSum = INT_MIN;  
13:  public:  
14:    int maxPathSum(TreeNode* root) {  
15:      helper(root);  
16:      return maxSum;  
17:    }  
18:    int helper(TreeNode *root) {  
19:      if (root == NULL) return 0;  
20:      int prevMax = helper(root->left);  
21:      int postMax = helper(root->right);  
22:      int val = max(root->val+prevMax, max(root->val+postMax, max(root->val+prevMax+postMax, root->val)));  
23:      maxSum = max(val, maxSum);  
24:      return max(root->val+prevMax, max(root->val+postMax, root->val));  
25:    }  
26:  };  

322. Coin Change

This is a classic dynamic programming problem. If you don't know the problem before, it will be tricky. Let dp[i] be the minimal change for amount i. We should try from 1 to the target amount such that should a coin amount be less or equal to i, dp[i] = min(dp[i], dp[i-coins[j]]+1), i.e. the minimal change for amount i will be the minimal change at i-coins[j] plus 1.

1:  class Solution {  
2:  public:  
3:    int coinChange(vector<int>& coins, int amount) {  
4:      vector<int> dp(amount+1, INT_MAX-1);  
5:      dp[0] = 0;  
6:      for (int i = 1; i <= amount; i++) {  
7:        for (int j = 0; j < coins.size(); j++) {  
8:          if (coins[j] <= i) {  
9:            dp[i] = min(dp[i], dp[i-coins[j]]+1);  
10:          }  
11:        }  
12:      }  
13:      return dp[amount] == INT_MAX-1 ? -1 : dp[amount];  
14:    }  
15:  };  

167. Two Sum II - Input array is sorted

Not much to say. An easy two pointers solution with O(N) running time. Of course, it can be solved by binary search but it may cost NlogN running time.

1:  class Solution {  
2:  public:  
3:    vector<int> twoSum(vector<int>& numbers, int target) {  
4:      int l = 0, r = numbers.size()-1;  
5:      while (l < r) {  
6:        int sum = numbers[l] + numbers[r];  
7:        if (sum == target) break;  
8:        else if (sum < target) l++;  
9:        else r--;  
10:      }  
11:      return vector<int>{l+1, r+1};  
12:    }  
13:  };  

379. Design Phone Directory

I was thinking to build up a hash table for every number in the construction function. However, it turns out too costly. Actually, I only needs to have two arrays, with one storing numbers and another storing used tag. The idea behind is that we really don't have to care about the order of number that we dispensed and even who got the number. So don't think over too much. It's a very simple design.

1:  class PhoneDirectory {  
2:  private:  
3:    vector<int> numbers;  
4:    vector<bool> used;  
5:    int front;  
6:    int maxNumbers;  
7:  public:  
8:    /** Initialize your data structure here  
9:      @param maxNumbers - The maximum numbers that can be stored in the phone directory. */  
10:    PhoneDirectory(int maxNumbers) {  
11:      this->maxNumbers = maxNumbers;  
12:      numbers = vector<int>(maxNumbers, 0);  
13:      used = vector<bool>(maxNumbers, false);  
14:      front = 0;  
15:      for (int i = 0; i < maxNumbers; i++) {  
16:        numbers[i] = i;  
17:      }  
18:    }  
19:    /** Provide a number which is not assigned to anyone.  
20:      @return - Return an available number. Return -1 if none is available. */  
21:    int get() {  
22:      if (front == maxNumbers) return -1;  
23:      int ret = numbers[front++];  
24:      used[ret] = true;  
25:      return ret;  
26:    }  
27:    /** Check if a number is available or not. */  
28:    bool check(int number) {  
29:      if (number < 0 || number > maxNumbers-1) return false;  
30:      return !used[number];  
31:    }  
32:    /** Recycle or release a number. */  
33:    void release(int number) {  
34:      if (number >= 0 && number < maxNumbers && used[number]) {  
35:        numbers[--front] = number;  
36:        used[number] = false;  
37:      }  
38:    }  
39:  };  
40:  /**  
41:   * Your PhoneDirectory object will be instantiated and called as such:  
42:   * PhoneDirectory obj = new PhoneDirectory(maxNumbers);  
43:   * int param_1 = obj.get();  
44:   * bool param_2 = obj.check(number);  
45:   * obj.release(number);  
46:   */