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

leetcode 1170 - Compare Strings by Frequency of the Smallest Character

https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character

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
class Solution {
public:
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
vector<int> freq;

for (auto w : words) {
freq.push_back(getFreq(w));
}

sort(freq.begin(), freq.end());

vector<int> result;
for (auto q : queries) {
int f = getFreq(q);

int i = binary_search(freq, f);
result.push_back(freq.size() - i);
}

return result;
}

int getFreq(string &str) {
int freq[256] = {0};

int smallest = INT_MAX;
for (char c : str) {
freq[c]++;
smallest = min(smallest, (int)c);
}

return freq[smallest];
}

int binary_search(vector<int> &freq, int f) {
int left = 0, right = freq.size() - 1;

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

if (f >= freq[mid])
left = mid + 1;
else
right = mid - 1;
}

return left;
}
};

leetcode 1210 - Minimum Moves to Reach Target with Rotations

https://leetcode.com/problems/minimum-moves-to-reach-target-with-rotations

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
class Solution {
public:
enum {
HORIZONTAL,
VERTICAL
};

struct Position {
int x1, y1, x2, y2;
vector<vector<int>> *grid;
int size;

Position(int a, int b, int c, int d, vector<vector<int>> *g) {
x1 = a; y1 = b; x2 = c; y2 = d;
grid = g;
size = g->size();
}

Position() {
}

int direction() {
return x1 == x2 ? HORIZONTAL : VERTICAL;
}

int end() {
return x1 == size - 1 && x2 == size - 1 && y1 == size - 2 && y2 == size - 1;
}

int valid() {
if (x1 == -1 || y1 == -1 || x2 == -1 || y2 == -1 || x1 >= size || x2 >= size || y1 >= size || y2 >= size)
return 0;
return (*grid)[x1][y1] != 1 && (*grid)[x2][y2] != 1;
}

Position go_right() {
Position tmp(x1, y1+1, x2, y2+1, grid);
if (tmp.valid())
return tmp;

return Position(-1, -1, -1, -1, grid);
}

Position go_down() {
Position tmp(x1+1, y1, x2+1, y2, grid);
if (tmp.valid())
return tmp;

return Position(-1, -1, -1, -1, grid);
}

Position rotate_clockwise() {
if (direction() == HORIZONTAL && go_down().valid()) {
Position tmp(x1, y1, x1+1, y1, grid);
if (tmp.valid())
return tmp;
}

return Position(-1, -1, -1, -1, grid);
}

Position rotate_counterclockwise() {
if (direction() == VERTICAL && go_right().valid()) {
Position tmp(x1, y1, x1, y1+1, grid);
if (tmp.valid())
return tmp;
}

return Position(-1, -1, -1, -1, grid);
}

string key() {
return to_string(x1) + "-" + to_string(y1) + "-" + to_string(x2) + "-" + to_string(y2);
}
};

void handle_it(Position &pos, queue<Position> &q, unordered_set<string> &visited) {
if (!pos.valid()) return;

string key = pos.key();
if (visited.count(key) == 0) {
visited.insert(key);
q.push(pos);
}
}

int minimumMoves(vector<vector<int>>& grid) {
queue<Position> q;
unordered_set<string> visited;

if (grid.empty()) return 0;

Position cur(0, 0, 0, 1, &grid);
q.push(cur);

int step = 0;

while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
cur = q.front(); q.pop();
if (cur.end())
return step;

Position tmp;

tmp = cur.go_right();
handle_it(tmp, q, visited);

tmp = cur.go_down();
handle_it(tmp, q, visited);

tmp = cur.rotate_clockwise();
handle_it(tmp, q, visited);

tmp = cur.rotate_counterclockwise();
handle_it(tmp, q, visited);
}

step++;
}

return -1;
}
};

leetcode 1209 - Remove All Adjacent Duplicates in String II

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-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
class Solution {
public:
string removeDuplicates(string s, int k) {
stack<pair<char, int>> stk;

for (char c : s) {
if (stk.empty() || stk.top().first != c)
stk.push({c, 1});
else {
auto p = stk.top(); stk.pop();
stk.push({p.first, p.second + 1});
}

auto p = stk.top();
if (p.second == k) {
stk.pop();
}
}

string result;

while (!stk.empty()) {
auto p = stk.top(); stk.pop();
result.append(p.second, p.first);
}

reverse(result.begin(), result.end());

return result;
}
};

leetcode 1208 - Get Equal Substrings Within Budget

https://leetcode.com/problems/get-equal-substrings-within-budget

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 equalSubstring_v1(string s, string t, int maxCost) {
int length = s.size();
int cost[length][length+1];
int max_len = 0;

for (int i = 0; i < length; i++)
cost[i][0] = 0;

for (int len = 1; len <= length; len++) {
for (int i = 0; i <= length - len; i++) {
int j = i + len - 1;
cost[i][len] = cost[i][len-1] + abs(s[j] - t[j]);
if (cost[i][len] <= maxCost)
max_len = max(max_len, len);
}
}

return max_len;
}

int equalSubstring(string s, string t, int maxCost) {
int max_len = 0;
int cost = 0;
int left = 0;

for (int right = 0; right < s.size(); right++) {
cost += abs(s[right] - t[right]);

while (left <= right && cost > maxCost) {
cost -= abs(s[left] - t[left]);
left++;
}

max_len = max(max_len, right - left + 1);
}

return max_len;
}
};