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

leetcode 490 - The Maze

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
class Solution {
public:
vector<vector<int>> get_all_next_pos(vector<vector<int>>& maze, vector<int> &pos) {
vector<vector<int>> all_next_pos;
int n_rows = maze.size(), n_cols = maze[0].size();

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

for (auto dir : dirs) {
int row = pos[0];
int col = pos[1];

while (1) {
if (row < 0 || row >= n_rows || col < 0 || col >= n_cols || maze[row][col] == 1) {
row -= dir[0];
col -= dir[1];

if (row != pos[0] || col != pos[1]) {
all_next_pos.push_back({row, col});
}
break;
}

row += dir[0];
col += dir[1];
}
}

return all_next_pos;
}

int get_index(int n_rows, int row, int col) {
return n_rows * row + col;
}

bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
unordered_set<int> visited;

return dfs(maze, start, destination, visited);
}

bool dfs(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination,
unordered_set<int> &visited) {

if (start == destination)
return true;

int n_rows = maze.size();
int idx = get_index(n_rows, start[0], start[1]);
visited.insert(idx);

bool ret = false;

vector<vector<int>> all_next_pos = get_all_next_pos(maze, start);

for (auto next_pos : all_next_pos) {
int i = get_index(n_rows, next_pos[0], next_pos[1]);
if (visited.count(i))
continue;

if (dfs(maze, next_pos, destination, visited)) {
ret = true;
break;
}
}

return ret;
}
};