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];
}
};

leetcode 1145 - Binary Tree Coloring Game

https://leetcode.com/problems/binary-tree-coloring-game/

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
class Solution {
public:
bool btreeGameWinningMove(TreeNode* root, int n, int x) {
TreeNode *node = find(root, x);
int left = count(node->left);
int right = count(node->right);
int parent = n - (left + right + 1);

if (left > right + parent + 1 || right > left + parent + 1 || parent > left + right + 1)
return true;
return false;
}

TreeNode *find(TreeNode *root, int x) {
if (!root || root->val == x) return root;

TreeNode *found = find(root->left, x);
if (!found)
found = find(root->right, x);
return found;
}

int count(TreeNode *root) {
if (!root) return 0;

return count(root->left) + count(root->right) + 1;
}
};

leetcode 1231 - Divide Chocolate

https://leetcode.com/problems/divide-chocolate/

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 maximizeSweetness(vector<int>& sweetness, int K) {
int left = 1, right = 0;

for (int s : sweetness)
right += s;

while (left <= right) {
int mid = left + (right - left) / 2;

if (valid(sweetness, K, mid))
left = mid + 1;
else
right = mid - 1;
}

return left - 1;
}

bool valid(vector<int> &sweetness, int K, int m) {
int count = 0;
int total = 0;

for (int s : sweetness) {
total += s;
if (total >= m) {
if (++count > K)
return true;
total = 0;
}
}

return false;
}
};

leetcode 1155 - Number of Dice Rolls With Target Sum

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

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
class Solution {
public:
vector<vector<int>> cached;
int mod = 1e9 + 7;

//up down
int numRollsToTarget0(int d, int f, int target) {
cached.resize(d+1, vector<int>(target+1, -1));

return recursive(f, d, target);
}

int recursive(int f, int d, int target) {
int total = 0;

if (d <= 0 || target <= 0) {
if (target == 0 && d == 0)
return 1;
return 0;
}

if (cached[d][target] != -1)
return cached[d][target];

for (int i = 1; i <= f; i++) {
total = (total + recursive(f, d-1, target-i)) % mod;
}

cached[d][target] = total;

return total;
}

//bottom up
int numRollsToTarget(int d, int f, int target) {
int dp[d+1][target+1];

dp[0][0] = 1;
for (int t = 1; t <= target; t++)
dp[0][t] = 0;

for (int i = 1; i <= d; i++) {
for (int t = 0; t <= target; t++) {
dp[i][t] = 0;
for (int j = 1; j <= f; j++) {
if (t - j >= 0)
dp[i][t] = (dp[i][t] + dp[i-1][t-j]) % mod;
}
}
}

return dp[d][target];
}
};