8000 Add C++ implementation · hiteshmewada/leetcode@c4372d3 · GitHub
[go: up one dir, main page]
Skip to content

Commit c4372d3

Browse files
begeekmyfriendbegeekmyfriend
committed
Add C++ implementation
Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>
1 parent ff9b734 commit c4372d3

File tree

3 files changed

+96
-0
lines changed

3 files changed

+96
-0
lines changed

‎051_n_queens/n_queens.cc

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
vector<vector<string>> solveNQueens(int n) {
8+
vector<vector<string>> res;
9+
vector<int> stack(n);
10+
vector<string> solution(n, string(n, '.'));
11+
dfs(n, 0, stack, solution, res);
12+
return res;
13+
}
14+
15+
private:
16+
void dfs(int n, int row, vector<int>& stack, vector<string>& solution, vector<vector<string>>& res) {
17+
if (row == n) {
18+
res.push_back(solution);
19+
} else {
20+
for (int i = 0; i < n; i++) {
21+
if (row == 0 || !conflict(stack, row, i)) {
22+
solution[row][i] = 'Q';
23+
stack[row] = i;
24+
dfs(n, row + 1, stack, solution, res);
25+
solution[row][i] = '.';
26+
}
27+
}
28+
}
29+
}
30+
31+
bool conflict(vector<int>& stack, int row, int col) {
32+
for (int i = 0; i < row; i++) {
33+
/* If occupied or in one line */
34+
if (col == stack[i] || abs(row - i) == abs(col - stack[i])) {
35+
return true;
36+
}
37+
}
38+
return false;
39+
}
40+
}

‎052_n_queens_ii/n_queens.cc

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
int totalNQueens(int n) {
8+
vector<int> stack(n);
9+
return dfs(n, 0, stack);
10+
}
11+
12+
private:
13+
int dfs(int n, int row, vector<int>& stack) {
14+
int count = 0;
15+
if (row == n) {
16+
return count + 1;
17+
} else {
18+
for (int i = 0; i < n; i++) {
19+
if (row == 0 || !conflict(stack, row, i)) {
20+
stack[row] = i;
21+
count += dfs(n, row + 1, stack);
22+
}
23+
}
24+
return count;
25+
}
26+
}
27+
28+
bool conflict(vector<int>& stack, int row, int col) {
29+
for (int i = 0; i < row; i++) {
30+
/* If occupied or in one line */
31+
if (col == stack[i] || abs(row - i) == abs(col - stack[i])) {
32+
return true;
33+
}
34+
}
35+
return false;
36+
}
37+
}

‎053_maximum_subarray/max_subarray.cc

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
class Solution {
6+
public:
7+
int maxSubArray(vector<int>& nums) {
8+
int sum = 0, max_sum = INT_MIN;
9+
for (int i = 0; i < nums.size(); i++) {
10+
if (sum < 0) {
11+
sum = nums[i];
12+
} else {
13+
sum += nums[i];
14+
}
15+
max_sum = max(sum, max_sum);
16+
}
17+
return max_sum;
18+
}
19+
};

0 commit comments

Comments
 (0)
0