0051-0060

51. N-Queens $\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
31
32
33
class Solution {
 public:
  vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> ans;
    vector<string> board(n, string(n, '.'));
    vector<bool> cols(n, false);
    vector<bool> diag1(2 * n - 1, false);
    vector<bool> diag2(2 * n - 1, false);

    dfs(0, cols, diag1, diag2, board, ans);

    return ans;
  }

 private:
  void dfs(int y, vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2,
           vector<string>& board, vector<vector<string>>& ans) {
    if (y == cols.size()) {
      ans.push_back(board);
      return;
    }

    for (int x = 0; x < cols.size(); ++x) {
      if (!cols[x] && !diag1[x + y] && !diag2[x - y + cols.size() - 1]) {
        board[y][x] = 'Q';
        cols[x] = diag1[x + y] = diag2[x - y + cols.size() - 1] = true;
        dfs(y + 1, cols, diag1, diag2, board, ans);
        cols[x] = diag1[x + y] = diag2[x - y + cols.size() - 1] = false;
        board[y][x] = '.';
      }
    }
  }
};

52. N-Queens II $\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 totalNQueens(int n) {
    int ans = 0;
    vector<bool> cols(n, false);
    vector<bool> diag1(2 * n - 1, false);
    vector<bool> diag2(2 * n - 1, false);

    dfs(0, cols, diag1, diag2, ans);

    return ans;
  }

 private:
  void dfs(int y, vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2,
           int& ans) {
    if (y == cols.size()) {
      ++ans;
      return;
    }

    for (int x = 0; x < cols.size(); ++x) {
      if (!cols[x] && !diag1[x + y] && !diag2[x - y + cols.size() - 1]) {
        cols[x] = diag1[x + y] = diag2[x - y + cols.size() - 1] = true;
        dfs(y + 1, cols, diag1, diag2, ans);
        cols[x] = diag1[x + y] = diag2[x - y + cols.size() - 1] = false;
      }
    }
  }
};

53. Maximum Subarray $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    int ans = INT_MIN;
    int sum = 0;

    for (int num : nums) {
      sum += num;
      ans = max(ans, sum);
      sum = max(sum, 0);
    }

    return ans;
  }
};

54. Spiral Matrix $\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
class Solution {
 public:
  vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if (matrix.empty()) return {};

    vector<int> ans;
    int r1 = 0;
    int c1 = 0;
    int r2 = matrix.size() - 1;
    int c2 = matrix[0].size() - 1;

    while (r1 <= r2 && c1 <= c2) {
      for (int c = c1; c <= c2; ++c) ans.push_back(matrix[r1][c]);
      for (int r = r1 + 1; r <= r2; ++r) ans.push_back(matrix[r][c2]);
      if (r1 < r2 && c1 < c2) {
        for (int c = c2 - 1; c > c1; --c) ans.push_back(matrix[r2][c]);
        for (int r = r2; r > r1; --r) ans.push_back(matrix[r][c1]);
      }
      ++r1;
      ++c1;
      --r2;
      --c2;
    }

    return ans;
  }
};

55. Jump Game $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  bool canJump(vector<int>& nums) {
    int goal = nums.size() - 1;

    for (int i = goal; i >= 0; --i)
      if (i + nums[i] >= goal) goal = i;

    return goal == 0;
  }
};

56. Merge Intervals $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> ans;

    sort(intervals.begin(), intervals.end(), compare);

    for (vector<int>& interval : intervals) {
      if (ans.empty() || ans.back()[1] < interval[0])
        ans.push_back(interval);
      else
        ans.back()[1] = max(ans.back()[1], interval[1]);
    }

    return ans;
  }

 private:
  bool static compare(const vector<int>& a, const vector<int>& b) {
    return a[0] < b[0];
  }
};

57. Insert Interval $\star\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:
  vector<vector<int>> insert(vector<vector<int>>& intervals,
                             vector<int>& newInterval) {
    vector<vector<int>> ans;

    auto it = intervals.begin();
    for (; it != intervals.end(); ++it)
      if ((*it)[0] >= newInterval[0]) break;
    intervals.insert(it, newInterval);

    for (vector<int>& interval : intervals) {
      if (ans.empty() || interval[0] > ans.back()[1])
        ans.push_back(interval);
      else
        ans.back()[1] = max(ans.back()[1], interval[1]);
    }

    return ans;
  }
};

58. Length of Last Word $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int lengthOfLastWord(string s) {
    int ans = 0;
    int i = s.size() - 1;

    while (i >= 0 && s[i] == ' ') --i;
    while (i >= 0 && s[i] != ' ') {
      --i;
      ++ans;
    }

    return ans;
  }
};

59. Spiral Matrix II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> ans(n, vector<int>(n));
    int count = 1;

    for (int min = 0, max = n - min - 1; min < n / 2; ++min, --max) {
      for (int i = min; i < max; ++i) ans[min][i] = count++;
      for (int i = min; i < max; ++i) ans[i][max] = count++;
      for (int i = max; i > min; --i) ans[max][i] = count++;
      for (int i = max; i > min; --i) ans[i][min] = count++;
    }

    if (n & 1) ans[n / 2][n / 2] = count;

    return ans;
  }
};

60. Permutation Sequence $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  string getPermutation(int n, int k) {
    string ans;
    vector<int> nums(n);
    vector<int> fact(n, 1);

    for (int i = 0; i < n; ++i) nums[i] = i + 1;
    for (int i = 1; i < n; ++i) fact[i] = fact[i - 1] * i;

    --k;

    for (int i = n; i >= 1; --i) {
      int j = k / fact[i - 1];
      k %= fact[i - 1];
      ans.append(to_string(nums[j]));
      nums.erase(nums.begin() + j);
    }

    return ans;
  }
};