333. Largest BST Subtree

I can use the way that "98. Validate Binary Search Tree" does to validate if the root is a valid BST root. If it is, then just count the node in the BST. Otherwise, do the same to its left subtree and right 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:  public:  
12:    int largestBSTSubtree(TreeNode* root) {  
13:      if (root == NULL) return 0;  
14:      if (root->left == NULL && root->right == NULL) return 1;  
15:      if (isValidBST(root, NULL, NULL)) return count(root);  
16:      return max(largestBSTSubtree(root->left), largestBSTSubtree(root->right));  
17:    }  
18:    bool isValidBST(TreeNode *root, TreeNode *pre, TreeNode *suc) {  
19:      if (root == NULL) return true;  
20:      if (pre && root->val <= pre->val) return false;  
21:      if (suc && root->val >= suc->val) return false;  
22:      return isValidBST(root->left, pre, root) && isValidBST(root->right, root, suc);  
23:    }  
24:    int count(TreeNode *root) {  
25:      if (root == NULL) return 0;  
26:      if (root->left == NULL && root->right == NULL) return 1;  
27:      return 1 + count(root->left) + count(root->right);  
28:    }  
29:  };  

The solution above is a top-down one. The top rated solution which follows a down-top way runs at O(n) time since each node only need to be visited once. Will investigate later.

372. Super Pow

I don’t have any clue. This is completely a math problem. I have to follow the top rated solution.

1:  class Solution {  
2:  private:  
3:    const int k = 1337;  
4:    int powmod(int a, int b) {  
5:      // (a^b)%k = (a^(b-1)*a)%k = (a^(b-1)%k)*(a%k)%k  
6:      int res = 1;  
7:      a %= k;  
8:      for (int i = 0; i < b; i++) {  
9:        res = res * a % k;  
10:      }  
11:      return res;  
12:    }  
13:  public:  
14:    int superPow(int a, vector<int>& b) {  
15:      // ab % k = (a%k)(b%k)%k  
16:      // a^123 % k = (a^120*a^3) % k = (a^120%k)(a^3%k)%k  
17:      if (b.empty()) return 1;  
18:      int last = b.back();  
19:      b.pop_back();  
20:      return powmod(superPow(a, b), 10) * powmod(a, last) % k;  
21:    }  
22:  };  

63. Unique Paths II

Same solution with problem “62. Unique Paths”. The only difference is the initial state.

1:  class Solution {  
2:  public:  
3:    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {  
4:      int rows = obstacleGrid.size();  
5:      if (rows == 0) return 0;  
6:      int cols = obstacleGrid[0].size();  
7:      vector<vector<int>> dp(rows, vector<int>(cols, 0));  
8:      for (int j = 0; j < cols; j++) {  
9:        if (obstacleGrid[0][j] == 1) break;  
10:        dp[0][j] = 1;  
11:      }  
12:      for (int i = 0; i < rows; i++) {  
13:        if (obstacleGrid[i][0] == 1) break;  
14:        dp[i][0] = 1;  
15:      }  
16:      for (int i = 1; i < rows; i++) {  
17:        for (int j = 1; j < cols; j++) {  
18:          if (obstacleGrid[i][j] == 0) {  
19:            dp[i][j] = dp[i-1][j]+dp[i][j-1];  
20:          }  
21:        }  
22:      }  
23:      return dp[rows-1][cols-1];  
24:    }  
25:  };  

267. Palindrome Permutation I

The trick here as the hint says is we only need to track the first half string. So we need to count the number for the first half string. Also, we need to keep the middle character if the string has an odd length. And finally, we need to use hashtable to store each character’s count. After that, the problem becomes a classic backtracking permutation problem.

I used vector as hash table in first place. But I got TLE. I guess it’s too cost to check for 256 characters every time. Also when doing unordered_map, the iterator it in the loop “for (auto it : mp)” is a copy not the real iterator itself. So if you update this copy, it doesn’t change the content of the unordered_map at all. So we need to do either “for (auto &it : mp)” or “for (auto it=mp.begin(); it != mp.end(); i++)”.

1:  class Solution {  
2:  public:  
3:    vector<string> generatePalindromes(string s) {  
4:      unordered_map<char, int> mp;  
5:      vector<string> res;  
6:      for (int i = 0; i < s.size(); i++) {  
7:        mp[s[i]]++;  
8:      }  
9:      int odd = 0, len = 0;  
10:      string mid = "";  
11:      for (auto it = mp.begin(); it != mp.end(); it++) {  
12:        if (it->second & 1) { odd++; mid += it->first; }  
13:        it->second /= 2;  
14:        len += it->second;  
15:      }  
16:      if (odd > 1) return res;  
17:      gen(mp, len, mid, "", res);  
18:      return res;  
19:    }  
20:    void gen(unordered_map<char, int> &mp, int len, string &mid, string s, vector<string> &res) {  
21:      if (s.size() == len) {  
22:        string r = s;  
23:        reverse(r.begin(), r.end());  
24:        res.push_back(s+mid+r);  
25:        return;  
26:      }  
27:      for (auto it = mp.begin(); it != mp.end(); it++) {  
28:        if (it->second > 0) {  
29:          it->second--;  
30:          gen(mp, len, mid, s+it->first, res);  
31:          it->second++;  
32:        }  
33:      }  
34:    }  
35:  };  

161. One Edit Distance

I was thinking of DP, but it turns out quite straightforward. See the comments in the code.

1:  class Solution {  
2:  public:  
3:    bool isOneEditDistance(string s, string t) {  
4:      int ns = s.size();  
5:      int nt = t.size();  
6:      int n = min(ns, nt);  
7:      for (int i = 0; i < n; i++) {  
8:        if (s[i] != t[i]) {  
9:          if (ns == nt) return s.substr(i+1) == t.substr(i+1); // replace s[i] with t[i]  
10:          else if (ns < nt) return s.substr(i) == t.substr(i+1); // delete t[i]  
11:          else return s.substr(i+1) == t.substr(i); // delete s[i]  
12:        }  
13:      }  
14:      return abs(ns-nt) == 1; // one character long otherwise two strings are equal.  
15:    }  
16:  };  

227. Basic Calculator II

The difference with problem "224. Basic Calculator" is that this problem contains '*' and '/' operator but no parenthesis. We can use stack to solve this problem. Stack stores all the numbers that need to sum up. So when we meet '+', we simply push the number into stack. When we meet '-', we simply push the negative number into the stack. When we meet '*' or '/' which has high priority, we only need to pop the top number out of the stack, operate on it and push it back to stack. With this operation, the stack will store all the numbers that need to sum up only.

1:  class Solution {  
2:  public:  
3:    int calculate(string s) {  
4:      char sign = '+';  
5:      int num = 0;  
6:      stack<int> stk;  
7:      for (int i = 0; i < s.size(); i++) {  
8:        if (s[i] >= '0' && s[i] <= '9') {  
9:          num = num*10+s[i]-'0';  
10:        }  
11:        if (((s[i] < '0' || s[i] > '9') && (s[i] != ' ')) || i == s.size()-1) {  
12:          if (sign == '+') stk.push(num);  
13:          else if (sign == '-') stk.push(-num);  
14:          else if (sign == '*') {num *= stk.top(); stk.pop(); stk.push(num);}  
15:          else if (sign == '/') {num = stk.top()/num; stk.pop(); stk.push(num);}  
16:          sign = s[i];  
17:          num = 0;  
18:        }  
19:      }  
20:      int res = 0;  
21:      while (!stk.empty()) {  
22:        res += stk.top();  
23:        stk.pop();  
24:      }  
25:      return res;  
26:    }  
27:  };  

88. Merge Sorted Array

The tricky part is we need to start from the end of arrays such that the largest will be allocated in the end.

1:  class Solution {  
2:  public:  
3:    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {  
4:      int i = m-1;  
5:      int j = n-1;  
6:      int k = m+n-1;  
7:      while (i >= 0 && j >= 0) {  
8:        if (nums1[i] > nums2[j]) {  
9:          nums1[k--] = nums1[i--];  
10:        } else {  
11:          nums1[k--] = nums2[j--];  
12:        }  
13:      }  
14:      while (j >= 0) nums1[k--] = nums2[j--];  
15:    }  
16:  };