0841-0850

841. Keys and Rooms $\star\star$

842. Split Array into Fibonacci Sequence $\star\star$

843. Guess the Word $\star\star\star$

844. Backspace String Compare $\star$

845. Longest Mountain in Array $\star\star$

846. Hand of Straights $\star\star$

847. Shortest Path Visiting All Nodes $\star\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
class Solution {
 public:
  int shortestPathLength(vector<vector<int>>& graph) {
    const int n = graph.size();
    const int goal = (1 << n) - 1;

    int ans = 0;
    queue<pair<int, int>> q;
    vector<vector<int>> visited(n, vector<int>(1 << n));

    for (int i = 0; i < graph.size(); ++i) q.push({i, 1 << i});

    while (!q.empty()) {
      int s = q.size();
      while (s--) {
        auto p = q.front();
        q.pop();
        int node = p.first;
        int state = p.second;
        if (state == goal) return ans;
        if (visited[node][state]) continue;
        visited[node][state] = 1;
        for (int next : graph[node]) q.push({next, state | (1 << next)});
      }
      ++ans;
    }

    return -1;
  }
};

848. Shifting Letters $\star\star$

849. Maximize Distance to Closest Person $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int maxDistToClosest(vector<int>& seats) {
    const int n = seats.size();

    int ans = 0;
    int j = -1;

    for (int i = 0; i < n; ++i)
      if (seats[i] == 1) {
        ans = j == -1 ? i : max(ans, (i - j) / 2);
        j = i;
      }

    return max(ans, n - j - 1);
  }
};

850. Rectangle Area II $\star\star\star$