leetcode 1066 - Campus Bikes II

https://leetcode.com/problems/campus-bikes-ii/

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
class Solution {
public:
int result = INT_MAX;

int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
int size = 1 << bikes.size();
vector<int> dp(size, -1);

return backtrack(workers, bikes, 0, dp, 0);
}

int backtrack(vector<vector<int>>& workers, vector<vector<int>>& bikes,
int i, vector<int> &dp, int used) {
if (i == workers.size()) return 0;

if (dp[used] != -1) return dp[used];

int min_dist = INT_MAX;

for (int p = 0; p < bikes.size(); p++) {
if (used & (1<<p)) continue;

used |= (1<<p);
int dist = backtrack(workers, bikes, i+1, dp, used) + distance(workers[i], bikes[p]);
min_dist = min(min_dist, dist);
used &= ~(1<<p);
}

dp[used] = min_dist;
return min_dist;
}

int distance(vector<int> &worker, vector<int> &bike) {
return abs(worker[0]-bike[0]) + abs(worker[1]-bike[1]);
}
};

leetcode 1057 - Campus Bikes

https://leetcode.com/problems/campus-bikes/

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
43
44
45
46
47
48
49
50
51
class Solution {
public:
struct Distance {
int dist;
int worker;
int bike;

Distance(int d, int w, int b) {
dist = d;
worker = w;
bike = b;
}
};

vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
int size = workers.size();
vector<Distance> dist_array;

for (int i = 0; i < size; i++) {
for (int j = 0; j < bikes.size(); j++) {
int dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
dist_array.push_back(Distance(dist, i, j));
}
}

auto mycomp = [&] (const Distance &d1, const Distance &d2) {
if (d1.dist < d2.dist) return true;
if (d1.dist > d2.dist) return false;
if (d1.worker < d2.worker) return true;
if (d1.worker > d2.worker) return false;
if (d1.bike < d2.bike) return true;
if (d1.bike > d2.bike) return false;

return true;
};

sort(dist_array.begin(), dist_array.end(), mycomp);

vector<int> result(size, -1);
unordered_set<int> used;

for (auto dist : dist_array) {
if (result[dist.worker] == -1 && used.count(dist.bike) == 0) {
result[dist.worker] = dist.bike;
used.insert(dist.bike);
}
}

return result;
}
};

leetcode 1074 - Number of Submatrices That Sum to Target

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/

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
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
int col = matrix[0].size();
int total = 0;

for (int r = 0; r < row; r++) {
vector<int> row_sum(col, 0);

for (int i = r; i < row; i++) {
for (int j = 0; j < col; j++)
row_sum[j] += matrix[i][j];
total += numResult(row_sum, target);
}
}

return total;
}

int numResult(vector<int> &row_sum, int target) {
unordered_map<int, int> map;
int s = 0;
int total = 0;

map[0] = 1;

for (int n : row_sum) {
s += n;

total += map[s - target];
map[s]++;
}

return total;
}
};

leetcode 1088 - Confusing Number II

https://leetcode.com/problems/confusing-number-ii/

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
class Solution {
public:
int confusingNumberII(int N) {
int rotated[] = {0,1,-1,-1,-1,-1,9,-1,8,6};
int next[] = {0,1,6,6,6,6,6,8,8,9};
int total = 0;
int n = 1;

while (n <= N) {
int num1 = n;
int num2 = 0;
unsigned long tmp = 1;

bool valid = true;

while (num1) {
int cur = num1 % 10;
num1 = num1 / 10;

if (rotated[cur] == -1) {
cur = next[cur];
n = num1 * tmp * 10 + cur * tmp;
valid = false;
break;
} else {
num2 = num2 * 10 + rotated[cur];
}

tmp = tmp * 10;
}

if (valid) {
if (num2 != n)
total++;
n++;
}
}

return total;
}
};

leetcode 1091 - Shortest Path in Binary Matrix

https://leetcode.com/problems/shortest-path-in-binary-matrix/

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
43
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int size = grid.size();
if (grid[0][0] == 1 || grid[size-1][size-1] == 1)
return -1;
vector<vector<bool>> visited(size, vector<bool>(size, false));

queue<pair<int,int>> q;
q.push({0,0});
visited[0][0] = true;
int path = 0;

vector<vector<int>> neighbors = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};

while (!q.empty()) {
int len = q.size();

path++;

for (int i = 0; i < len; i++) {
auto p = q.front(); q.pop();

if (p.first == size - 1 && p.second == size - 1)
return path;

for (auto n : neighbors) {
int r = p.first + n[0];
int c = p.second + n[1];

if (r < 0 || r >= size || c < 0 || c >= size || grid[r][c] == 1) continue;

if (grid[r][c] == false) {
grid[r][c] = true;
q.push({r, c});
}
}
}
}

return -1;
}
};

leetcode 224 - Basic Calculator

https://leetcode.com/problems/basic-calculator/

Convert Infix Expression to Post-Fix Expression: https://condor.depaul.edu/ichu/csc415/notes/notes9/Infix.htm

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public:
int calculate(string s) {
vector<string> postfix = infix_to_postfix(s);
stack<int> stk;
int result;

for (auto e : postfix) {
if (e == "+" || e == "-") {
int op1 = stk.top(); stk.pop();
int op2 = stk.top(); stk.pop();

if (e == "+")
result = op2 + op1;
else
result = op2 - op1;
stk.push(result);
} else
stk.push(stoi(e));
}

return stk.top();
}

vector<string> infix_to_postfix(string &s) {
vector<string> postfix;
stack<char> stk;
char e;
bool last_is_digit = false;

for (char c : s) {
switch (c) {
case '(':
stk.push(c);
last_is_digit = false;
break;
case ')':
case '+':
case '-':
while (!stk.empty()) {
e = stk.top();
if (e == '(')
break;
postfix.push_back(string(1,e));
stk.pop();
}
if (c == ')')
stk.pop();
else
stk.push(c);
last_is_digit = false;
break;
case ' ':
last_is_digit = false;
break;
default:
if (last_is_digit)
postfix.back().push_back(c);
else
postfix.push_back(string(1,c));
last_is_digit = true;
break;
}
}

while (!stk.empty()) {
e = stk.top(); stk.pop();
if (e == '(') break;
postfix.push_back(string(1, e));
}

return postfix;
}
};

leetcode 1087 - Brace Expansion

https://leetcode.com/problems/brace-expansion/

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
class Solution {
public:
vector<string> all_result;

vector<string> expand(string S) {
string result;
recursive(S, result, 0);
sort(all_result.begin(), all_result.end());

return all_result;
}

void recursive(string &S, string &result, int i) {
if (i == S.size()) {
all_result.push_back(result);
return;
}

if (S[i] == '{') {
string tmp;

i++;
while (S[i] != '}') {
if (S[i] != ',')
tmp.push_back(S[i]);
i++;
}

i++;
for (char c : tmp) {
result.push_back(c);
recursive(S, result, i);
result.pop_back();
}
} else {
result.push_back(S[i]);
recursive(S, result, i+1);
result.pop_back();
}
}
};

leetcode 1110 - Delete Nodes And Return Forest

https://leetcode.com/problems/delete-nodes-and-return-forest/

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
class Solution {
public:
unordered_set<int> set_to_delete;
vector<TreeNode *> result;

vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
for (int i : to_delete)
set_to_delete.insert(i);

delNode(root, true);
return result;
}

TreeNode *delNode(TreeNode *root, bool parent_deleted) {
if (!root) return NULL;

if (set_to_delete.count(root->val)) {
delNode(root->left, true);
delNode(root->right, true);
return NULL;
} else {
root->left = delNode(root->left, false);
root->right = delNode(root->right, false);
if (parent_deleted)
result.push_back(root);
return root;
}
}
};

leetcode 1122 - Relative Sort Array

https://leetcode.com/problems/relative-sort-array/

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
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
unordered_set<int> set;
unordered_map<int, int> map;

for (int n : arr2)
set.insert(n);

int len = arr1.size();
int j = len - 1;

for (int i = len - 1; i >= 0; i--) {
int n = arr1[i];

if (set.count(n) == 0)
arr1[j--] = n;
else {
map[n]++;
}
}

int i = 0;
for (int n : arr2) {
int count = map[n];

while (count-- > 0)
arr1[i++] = n;
}

sort(arr1.begin() + i, arr1.end());

return arr1;
}
};

leetcode 1143 - Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
/*
abcdexab
xcyeza

dp[i][j] =
1. max(dp[i-1][j], dp[i][j-1]), text1[i] != test2[j]
2. dp[i-1][j-1] + 1, text1[i] == test2[j]

dp[0][j] = 0
dp[i][0] = 0
*/
//2D array
int longestCommonSubsequence_2D_array(string text1, string text2) {
int len1 = text1.size(), len2 = text2.size();
int dp[len1+1][len2+1];

for (int i = 0; i <= len1; i++)
dp[i][0] = 0;
for (int j = 0; j <= len2; j++)
dp[0][j] = 0;

for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (text1[i-1] == text2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}

return dp[len1][len2];
}

//1D array
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.size(), len2 = text2.size();
vector<int> dp(len2+1, 0);

for (int i = 1; i <= len1; i++) {
vector<int> tmp = dp;
for (int j = 1; j <= len2; j++) {
if (text1[i-1] == text2[j-1])
tmp[j] = dp[j-1] + 1;
else {
tmp[j] = max(dp[j], tmp[j-1]);
}
}

dp = tmp;
}

return dp[len2];
}
};