0221-0230

221. Maximal Square $\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
class Solution {
 public:
  int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.empty()) return 0;

    const int m = matrix.size();
    const int n = matrix[0].size();

    vector<int> dp(n);
    int max = 0;
    int prev = 0;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        int temp = dp[j];
        dp[j] = (i == 0 || j == 0 || matrix[i][j] == '0')
                    ? matrix[i][j] - '0'
                    : min(dp[j], min(dp[j - 1], prev)) + 1;
        max = std::max(max, dp[j]);
        prev = temp;
      }

    return max * max;
  }
};

222. Count Complete Tree Nodes $\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:
  int countNodes(TreeNode* root) {
    if (!root) return 0;

    int ans = 0;

    queue<TreeNode*> queue;
    queue.push(root);

    while (!queue.empty()) {
      ++ans;
      TreeNode* node = queue.front();
      queue.pop();
      if (node->left) queue.push(node->left);
      if (node->right) queue.push(node->right);
    }

    return ans;
  }
};

223. Rectangle Area $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
 public:
  int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
    long x = max(A, E) < min(C, G) ? (min(C, G) - max(A, E)) : 0;
    long y = max(B, F) < min(D, H) ? (min(D, H) - max(B, F)) : 0;

    return (long)(C - A) * (long)(D - B) + (long)(G - E) * (long)(H - F) -
           x * y;
  }
};

224. Basic Calculator $\star\star\star$

225. Implement Stack using Queues $\star$

226. Invert Binary Tree $\star$

227. Basic Calculator II $\star\star$

228. Summary Ranges $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  vector<string> summaryRanges(vector<int>& nums) {
    vector<string> ans;

    for (int i = 0; i < nums.size(); ++i) {
      int begin = nums[i];
      while (i < nums.size() - 1 && nums[i] == nums[i + 1] - 1) ++i;
      int end = nums[i];
      if (begin == end)
        ans.push_back(to_string(begin));
      else
        ans.push_back(to_string(begin) + "->" + to_string(end));
    }

    return ans;
  }
};

229. Majority Element II $\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
class Solution {
 public:
  vector<int> majorityElement(vector<int>& nums) {
    vector<int> ans;
    int ans1 = 0;
    int ans2 = 1;
    int count1 = 0;
    int count2 = 0;

    for (int num : nums) {
      if (num == ans1)
        ++count1;
      else if (num == ans2)
        ++count2;
      else if (count1 == 0) {
        ans1 = num;
        ++count1;
      } else if (count2 == 0) {
        ans2 = num;
        ++count2;
      } else {
        --count1;
        --count2;
      }
    }

    count1 = 0;
    count2 = 0;

    for (int num : nums) {
      if (num == ans1)
        ++count1;
      else if (num == ans2)
        ++count2;
    }

    if (count1 > nums.size() / 3) ans.push_back(ans1);
    if (count2 > nums.size() / 3) ans.push_back(ans2);

    return ans;
  }
};

230. Kth Smallest Element in a BST $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int kthSmallest(TreeNode* root, int k) {
    vector<int> nums;

    inorder(root, nums);

    return nums[k - 1];
  }

 private:
  void inorder(TreeNode* root, vector<int>& nums) {
    if (!root) return;

    inorder(root->left, nums);
    nums.push_back(root->val);
    inorder(root->right, nums);
  }
};