0881-0890

881. Boats to Save People $\star\star$

882. Reachable Nodes In Subdivided Graph $\star\star\star$

883. Projection Area of 3D Shapes $\star$

884. Uncommon Words from Two Sentences $\star$

885. Spiral Matrix III $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
    vector<vector<int>> ans = {{r0, c0}};
    int x = 0;
    int y = 1;

    for (int i = 0; ans.size() < R * C; ++i) {
      for (int j = 0; j < i / 2 + 1; ++j) {
        r0 += x;
        c0 += y;
        if (0 <= r0 && r0 < R && 0 <= c0 && c0 < C) ans.push_back({r0, c0});
      }
      swap(x, y);
      y *= -1;
    }

    return ans;
  }
};

886. Possible Bipartition $\star\star$

887. Super Egg Drop $\star\star\star$

888. Fair Candy Swap $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
    int diff = (accumulate(A.begin(), A.end(), 0) -
                accumulate(B.begin(), B.end(), 0)) /
               2;
    unordered_set<int> set(B.begin(), B.end());

    for (int a : A)
      if (set.count(a - diff)) return {a, a - diff};

    throw;
  }
};

889. Construct Binary Tree from Preorder and Postorder Traversal $\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
class Solution {
 public:
  TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
    return helper(0, 0, pre.size(), pre, post);
  }

 private:
  TreeNode* helper(int i, int j, int n, vector<int>& pre, vector<int>& post) {
    if (n == 0) return NULL;

    TreeNode* root = new TreeNode(pre[i]);
    if (n == 1) return root;

    int k = j;
    while (post[k] != pre[i + 1]) ++k;
    int l = k - j + 1;

    root->left = helper(i + 1, j, l, pre, post);
    root->right = helper(i + l + 1, j + l, n - l - 1, pre, post);

    return root;
  }
};

890. Find and Replace Pattern $\star\star$