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

leetcode 1168 - Optimize Water Distribution in a Village

https://leetcode.com/problems/optimize-water-distribution-in-a-village/

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
class UnionFind {
vector<int> parent;
public:
UnionFind(int n) {
parent.resize(n+1);
for (int i = 0; i <= n; i++)
parent[i] = i;
}

int Find(int i) {
if (parent[i] != i)
parent[i] = Find(parent[i]);
return parent[i];
}

void Union(int i, int j) {
int p1 = Find(i);
int p2 = Find(j);

parent[p1] = p2;
}
};

class Solution {
public:
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
for (int i = 0; i < n; i++)
pipes.push_back({0, i+1, wells[i]});

auto mycomp = [&](const vector<int> &v1, const vector<int> &v2) {
return v1[2] < v2[2];
};
sort(pipes.begin(), pipes.end(), mycomp);

int cost = 0;
UnionFind uf(n);

for (auto edge : pipes) {
if (uf.Find(edge[0]) != uf.Find(edge[1])) {
uf.Union(edge[0], edge[1]);
cost += edge[2];
}
}

return cost;
}
};

leetcode 1219 - Path with Maximum Gold

https://leetcode.com/problems/path-with-maximum-gold/

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
class Solution {
public:
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int row, col;

int getMaximumGold(vector<vector<int>>& grid) {
if (grid.empty()) return 0;

row = grid.size();
col = grid[0].size();

int max_gold = 0;

for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (grid[r][c])
max_gold = max(max_gold, dfs(grid, r, c));
}
}

return max_gold;
}

int dfs(vector<vector<int>> &grid, int i, int j) {
if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0)
return 0;

int tmp = grid[i][j];
grid[i][j] = 0;

int max_gold = 0;

for (const auto &dir : dirs) {
int x = i + dir[0];
int y = j + dir[1];

max_gold = max(max_gold, dfs(grid, x, y));
}

grid[i][j] = tmp;

return max_gold + grid[i][j];
}
};

leetcode 1220 - Count Vowels Permutation

https://leetcode.com/problems/count-vowels-permutation/

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
public:
/*
a: e
e: a i
i: a e o u
o: i u
u: a

e i u -> a
a i -> e
e o -> i
i -> o
i o -> u
*/

unordered_map<char, vector<char>> map;
vector<vector<int>> cache;
int mod;

int get_index(char c) {
string vowel = "aeiou";
for (int i = 0; i < vowel.size(); i++) {
if (c == vowel[i])
return i;
}
return -1;
}

int countVowelPermutation(int n) {
mod = 1e9 + 7;

map['a'] = {'e', 'i', 'u'};
map['e'] = {'a', 'i'};
map['i'] = {'e', 'o'};
map['o'] = {'i'};
map['u'] = {'i', 'o'};

cache.resize(n, vector<int>(5, -1));

string vowel = "aeiou";
int total = 0;

for (char c : vowel)
total = (total + countVowelPermutation(n-1, c)) % mod;

return total;
}

//recursion + memo
int countVowelPermutation(int n, char c) {
int total = 0;
if (n == 0) return 1;

int i = get_index(c);
if (cache[n][i] != -1)
return cache[n][i];

for (char p : map[c]) {
total = (total + countVowelPermutation(n-1, p)) % mod;
}

cache[n][i] = total;
return total;
}

//dp
int countVowelPermutation(int n) {
long count[n+1][5];
int MOD = 1e9 + 7;

for (int i = 0; i < 5; i++)
count[1][i] = 1;

for (int i = 2; i <= n; i++) {
count[i][0] = (count[i-1][1] + count[i-1][2] + count[i-1][4]) % MOD;
count[i][1] = (count[i-1][0] + count[i-1][2]) % MOD;
count[i][2] = (count[i-1][1] + count[i-1][3]) % MOD;
count[i][3] = count[i-1][2];
count[i][4] = (count[i-1][2] + count[i-1][3]) % MOD;
}

int total = 0;
for (int i = 0; i < 5; i++)
total = (total + count[n][i]) % MOD;

return total;
}
};