diff options
Diffstat (limited to 'works/solutions')
145 files changed, 0 insertions, 6130 deletions
diff --git a/works/solutions/.editorconfig b/works/solutions/.editorconfig deleted file mode 100644 index 28365d2..0000000 --- a/works/solutions/.editorconfig +++ /dev/null @@ -1,5 +0,0 @@ -[*.c]
-tab_width = 2
-
-[*.cpp]
-tab_width = 2
diff --git a/works/solutions/.gitignore b/works/solutions/.gitignore deleted file mode 100644 index aab2f3b..0000000 --- a/works/solutions/.gitignore +++ /dev/null @@ -1,9 +0,0 @@ -.vscode
-*.exe
-*.pdb
-*.ilk
-*.obj
-*.exp
-*.lib
-
-.DS_Store
diff --git a/works/solutions/acwing/1204.cpp b/works/solutions/acwing/1204.cpp deleted file mode 100644 index e3e5395..0000000 --- a/works/solutions/acwing/1204.cpp +++ /dev/null @@ -1,31 +0,0 @@ -#include <ios>
-#include <iostream>
-#include <set>
-
-int main() {
- std::ios_base::sync_with_stdio(false);
-
- int repeat;
-
- int n;
- std::cin >> n;
-
- std::set<int> ids;
-
- while (std::cin >> n) {
- auto result = ids.insert(n);
- if (!result.second)
- repeat = n;
- }
-
- auto iter = ids.cbegin();
-
- int last = *iter++;
-
- while (++last == *iter++)
- ;
-
- std::cout << last << ' ' << repeat;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1208.cpp b/works/solutions/acwing/1208.cpp deleted file mode 100644 index 84f60f1..0000000 --- a/works/solutions/acwing/1208.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include <iostream>
-#include <string>
-
-inline void toggle(char &c) { c = c == '*' ? 'o' : '*'; }
-
-int main() {
- std::string original, expected;
- std::cin >> original >> expected;
-
- int size = original.size();
-
- int count = 0;
-
- for (int i = 0; i < size - 1; i++) {
- if (original[i] != expected[i]) {
- count++;
- toggle(original[i + 1]);
- }
- }
-
- std::cout << count;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1209.cpp b/works/solutions/acwing/1209.cpp deleted file mode 100644 index 3f3ff7a..0000000 --- a/works/solutions/acwing/1209.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#include <array>
-#include <iostream>
-#include <vector>
-
-int number;
-int count = 0;
-std::array<bool, 10> used{false};
-std::array<int, 9> current;
-
-int calc(int start, int end) {
- int n = 0;
- for (int i = start; i < end; i++) {
- n *= 10;
- n += current[i];
- }
- return n;
-}
-
-void dfs(int n) {
- if (n == 9) {
- for (int i = 1; i <= 7; i++)
- for (int j = i + 1; j <= 8; j++) {
- int a = calc(0, i);
- int b = calc(i, j);
- int c = calc(j, 9);
- if ((number - a) * b == c) {
- count++;
- }
- }
- return;
- }
-
- for (int i = 1; i <= 9; i++) {
- if (!used[i]) {
- used[i] = true;
- current[n] = i;
- dfs(n + 1);
- used[i] = false;
- }
- }
-}
-
-int main() {
- std::cin >> number;
- dfs(0);
- std::cout << count;
- return 0;
-}
diff --git a/works/solutions/acwing/1210.cpp b/works/solutions/acwing/1210.cpp deleted file mode 100644 index 4c9c0ba..0000000 --- a/works/solutions/acwing/1210.cpp +++ /dev/null @@ -1,37 +0,0 @@ -#include <iostream>
-
-int N;
-int seq[10000];
-
-int main() {
- std::cin >> N;
- for (int i = 0; i < N; i++) {
- std::cin >> seq[i];
- }
-
- int count = N;
-
- for (int start = 0; start < N; start++) {
- int min = seq[start], max = seq[start];
-
- for (int end = start + 1; end < N; end++) {
- int current = seq[end];
-
- if (current > max) {
- max = current;
- }
-
- if (current < min) {
- min = current;
- }
-
- if (max - min == end - start) {
- count++;
- }
- }
- }
-
- std::cout << count;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1211.cpp b/works/solutions/acwing/1211.cpp deleted file mode 100644 index 18c564e..0000000 --- a/works/solutions/acwing/1211.cpp +++ /dev/null @@ -1,38 +0,0 @@ -#include <cmath>
-#include <iostream>
-
-int main() {
- std::ios_base::sync_with_stdio(false);
-
- int n;
- std::cin >> n;
-
- int fever_ant;
- std::cin >> fever_ant;
-
- int fever_position = std::abs(fever_ant);
-
- int left = 0, right = 0;
-
- for (int i = 1; i < n; i++) {
- int ant;
- std::cin >> ant;
- int position = std::abs(ant);
- if (position < fever_position && ant > 0) {
- left++;
- }
- if (position > fever_position && ant < 0) {
- right++;
- }
- }
-
- if (fever_ant < 0 && left == 0) {
- std::cout << 1;
- } else if (fever_ant > 0 && right == 0) {
- std::cout << 1;
- } else {
- std::cout << left + right + 1;
- }
-
- return 0;
-}
diff --git a/works/solutions/acwing/1212.cpp b/works/solutions/acwing/1212.cpp deleted file mode 100644 index e60e993..0000000 --- a/works/solutions/acwing/1212.cpp +++ /dev/null @@ -1,46 +0,0 @@ -#include <iostream>
-
-int n, m, k;
-int v[51][51];
-int f[51][51][14][14]; // row col count max
-const int MOD = 1000000007;
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin >> n >> m >> k;
-
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= m; j++) {
- std::cin >> v[i][j];
- v[i][j]++;
- }
-
- f[1][1][0][0] = 1;
- f[1][1][1][v[1][1]] = 1;
-
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- for (int c = 0; c <= k; c++) {
- for (int m = 0; m <= 13; m++) {
- f[i][j][c][m] = (f[i][j][c][m] + f[i][j - 1][c][m]) % MOD;
- f[i][j][c][m] = (f[i][j][c][m] + f[i - 1][j][c][m]) % MOD;
-
- if (c && v[i][j] == m) {
- for (int max = 0; max < v[i][j]; max++) {
- f[i][j][c][m] = (f[i][j][c][m] + f[i][j - 1][c - 1][max]) % MOD;
- f[i][j][c][m] = (f[i][j][c][m] + f[i - 1][j][c - 1][max]) % MOD;
- }
- }
- }
- }
- }
- }
-
- int result = 0;
- for (int i = 1; i <= 13; i++)
- result = (result + f[n][m][k][i]) % MOD;
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1215.cpp b/works/solutions/acwing/1215.cpp deleted file mode 100644 index d6832b3..0000000 --- a/works/solutions/acwing/1215.cpp +++ /dev/null @@ -1,59 +0,0 @@ -#include <cstring>
-#include <iostream>
-
-const int MAX = 1000010; // Why 1000001 is not ok!?
-
-int n;
-int H[100001];
-int bit[MAX];
-int reverse_pairs[100001];
-
-int lowbit(int x) { return x & -x; }
-
-void add(int x, int y) {
- for (int i = x; i < MAX; i += lowbit(i)) {
- bit[i] += y;
- }
-}
-
-int query(int x) {
- int result = 0;
- for (int i = x; i != 0; i -= lowbit(i)) {
- result += bit[i];
- }
- return result;
-}
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- std::cin >> n;
-
- for (int i = 1; i <= n; i++) {
- std::cin >> H[i];
- H[i]++;
- }
-
- for (int i = 1; i <= n; i++) {
- add(H[i], 1);
- reverse_pairs[i] = i - query(H[i]);
- }
-
- std::memset(bit, 0, sizeof bit);
-
- for (int i = n; i >= 1; i--) {
- add(H[i], 1);
- reverse_pairs[i] += query(H[i] - 1);
- }
-
- long long result = 0;
-
- for (int i = 1; i <= n; i++) {
- result += (1LL + reverse_pairs[i]) * reverse_pairs[i] / 2;
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1216.cpp b/works/solutions/acwing/1216.cpp deleted file mode 100644 index 61d1848..0000000 --- a/works/solutions/acwing/1216.cpp +++ /dev/null @@ -1,19 +0,0 @@ -#include <iostream>
-
-int main() {
- int n;
- std::cin >> n;
-
- int result = n;
-
- while (n >= 3) {
- int exchange = n / 3;
- int rest = n % 3;
- result += exchange;
- n = exchange + rest;
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1217.cpp b/works/solutions/acwing/1217.cpp deleted file mode 100644 index e729547..0000000 --- a/works/solutions/acwing/1217.cpp +++ /dev/null @@ -1,67 +0,0 @@ -#include <cstring>
-#include <iostream>
-
-const int MOD = 1e9 + 7;
-
-int n, m;
-bool conflict_matrix[7][7];
-
-long long f[7];
-long long temp[7];
-
-int back(int x) {
- switch (x) {
- case 1:
- return 4;
- case 2:
- return 5;
- case 3:
- return 6;
- case 4:
- return 1;
- case 5:
- return 2;
- case 6:
- return 3;
- default:
- return 0;
- }
-}
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- std::cin >> n >> m;
-
- for (int i = 0; i < m; i++) {
- int a, b;
- std::cin >> a >> b;
- conflict_matrix[a][b] = true;
- conflict_matrix[b][a] = true;
- }
-
- for (int i = 1; i <= 6; i++)
- f[i] = 4;
-
- for (int c = 2; c <= n; c++) {
- for (int up = 1; up <= 6; up++) {
- for (int down = 1; down <= 6; down++) {
- if (!conflict_matrix[back(down)][up]) {
- temp[up] = (temp[up] + f[down] * 4) % MOD;
- }
- }
- }
- std::memcpy(f, temp, sizeof f);
- std::memset(temp, 0, sizeof temp);
- }
-
- long long result = 0;
- for (int i = 1; i <= 6; i++) {
- result = (result + f[i]) % MOD;
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1219.cpp b/works/solutions/acwing/1219.cpp deleted file mode 100644 index 9538e94..0000000 --- a/works/solutions/acwing/1219.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include <cmath>
-#include <iostream>
-
-int w, m, n;
-
-int row(int x) { return (x - 1) / w; }
-
-int col(int x, int r) {
- int result = (x - 1) % w;
- if (r % 2) {
- result = w - 1 - result;
- }
- return result;
-}
-
-int main() {
- std::cin >> w >> m >> n;
- int m_r = row(m);
- int m_c = col(m, m_r);
- int n_r = row(n);
- int n_c = col(n, n_r);
-
- std::cout << std::abs(m_r - n_r) + std::abs(m_c - n_c);
-
- return 0;
-}
diff --git a/works/solutions/acwing/1220.cpp b/works/solutions/acwing/1220.cpp deleted file mode 100644 index 443ed43..0000000 --- a/works/solutions/acwing/1220.cpp +++ /dev/null @@ -1,65 +0,0 @@ -#include <iostream>
-#include <vector>
-
-const int N = 100010;
-
-struct Node {
- int w;
- std::vector<int> children;
-};
-
-int n;
-Node nodes[N];
-bool visited[N];
-long long contain_root[N];
-long long contain_or_not_contain_root[N];
-
-void dfs(int i) {
- visited[i] = true;
- long long this_contain_root = nodes[i].w;
- long long this_contain_or_not_contain_root = nodes[i].w;
-
- for (auto next : nodes[i].children) {
- if (!visited[next]) {
- dfs(next);
- if (contain_root[next] > 0) {
- this_contain_root += contain_root[next];
- }
- if (contain_or_not_contain_root[next] >
- this_contain_or_not_contain_root) {
- this_contain_or_not_contain_root = contain_or_not_contain_root[next];
- }
- }
- }
-
- if (this_contain_root > this_contain_or_not_contain_root) {
- this_contain_or_not_contain_root = this_contain_root;
- }
-
- contain_root[i] = this_contain_root;
- contain_or_not_contain_root[i] = this_contain_or_not_contain_root;
-}
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- std::cin >> n;
-
- for (int i = 1; i <= n; i++) {
- std::cin >> nodes[i].w;
- }
-
- for (int i = 1; i < n; i++) {
- int a, b;
- std::cin >> a >> b;
- nodes[a].children.push_back(b);
- nodes[b].children.push_back(a);
- }
-
- dfs(1);
-
- std::cout << contain_or_not_contain_root[1];
-
- return 0;
-}
diff --git a/works/solutions/acwing/1221.cpp b/works/solutions/acwing/1221.cpp deleted file mode 100644 index 9ba4229..0000000 --- a/works/solutions/acwing/1221.cpp +++ /dev/null @@ -1,45 +0,0 @@ -#include <cmath>
-#include <iostream>
-
-const int M = 5000010;
-const int SM = std::sqrt(M / 2);
-
-int s[M];
-
-int main() {
- int n;
- std::cin >> n;
-
- for (int i = 0; i <= SM; i++) {
- const int i2 = i * i;
- const int SMB = M - i2;
- for (int j = i; j * j < SMB; j++) {
- const int a = i2 + j * j;
-
- if (s[a] == 0) {
- s[a] = i + 1;
- }
- }
- }
-
- int sm = std::sqrt(n);
-
- for (int a = 0; a <= sm; a++) {
- int as = a * a;
- int bsm = n - 3 * a * a;
- for (int b = a; b * b <= bsm; b++) {
- int bs = b * b + as;
-
- int c = s[n - bs];
-
- if (c != 0) {
- c = c - 1;
- std::cout << a << ' ' << b << ' ' << c << ' '
- << std::sqrt(n - bs - c * c);
- return 0;
- }
- }
- }
-
- return 0;
-}
diff --git a/works/solutions/acwing/1224.cpp b/works/solutions/acwing/1224.cpp deleted file mode 100644 index 8cdd9f0..0000000 --- a/works/solutions/acwing/1224.cpp +++ /dev/null @@ -1,33 +0,0 @@ -#include <iostream> -#include <utility> - -int N; -int x[10010]; - -int main() { - std::ios_base::sync_with_stdio(false); - std::cin.tie(nullptr); - - std::cin >> N; - for (int i = 1; i <= N; i++) { - std::cin >> x[i]; - } - - int result = 0; - - for (int i = 1; i <= N - 1; i++) { - if (x[i] != i) { - for (int j = i + 1; j <= N; j++) { - if (x[j] == i) { - x[j] = x[i]; - result++; - break; - } - } - } - } - - std::cout << result; - - return 0; -} diff --git a/works/solutions/acwing/1226.cpp b/works/solutions/acwing/1226.cpp deleted file mode 100644 index cbfea98..0000000 --- a/works/solutions/acwing/1226.cpp +++ /dev/null @@ -1,55 +0,0 @@ -#include <iostream> - -int gcd(int a, int b) { - if (b == 0) - return a; - return gcd(b, a % b); -} - -int N; -int A[110]; - -const int M = 10000; - -bool f[M + 10]; - -int main() { - std::ios_base::sync_with_stdio(false); - std::cin.tie(nullptr); - - std::cin >> N; - - for (int i = 1; i <= N; i++) { - std::cin >> A[i]; - } - - int a = A[1]; - - for (int i = 2; i <= N; i++) { - a = gcd(a, A[i]); - } - - if (a != 1) { - std::cout << "INF"; - return 0; - } - - f[0] = true; - - for (int i = 1; i <= N; i++) { - for (int w = A[i]; w <= M; w++) { - f[w] = f[w] || f[w - A[i]]; - } - } - - int count = 0; - - for (int i = 1; i <= M; i++) { - if (f[i] == false) - count++; - } - - std::cout << count; - - return 0; -} diff --git a/works/solutions/acwing/1227.cpp b/works/solutions/acwing/1227.cpp deleted file mode 100644 index ff14be2..0000000 --- a/works/solutions/acwing/1227.cpp +++ /dev/null @@ -1,50 +0,0 @@ -#include <iostream> - -const int M = 1e5 + 10; - -int N, K; -int H[M]; -int W[M]; - -bool check(int l) { - if (l == 0) - return true; - - int count = 0; - - for (int i = 1; i <= N; i++) { - count += (H[i] / l) * (W[i] / l); - if (K <= count) { - return true; - } - } - - return false; -} - -int main() { - std::ios_base::sync_with_stdio(false); - std::cin.tie(nullptr); - - std::cin >> N >> K; - - for (int i = 1; i <= N; i++) { - std::cin >> H[i] >> W[i]; - } - - int l = 0, r = M; - - while (l != r) { - int m = l + ((r - l + 1) / 2); - - if (check(m)) { - l = m; - } else { - r = m - 1; - } - } - - std::cout << l; - - return 0; -} diff --git a/works/solutions/acwing/1229.cpp b/works/solutions/acwing/1229.cpp deleted file mode 100644 index e3b16ba..0000000 --- a/works/solutions/acwing/1229.cpp +++ /dev/null @@ -1,106 +0,0 @@ -#include <algorithm>
-#include <cstdio>
-#include <vector>
-
-int ConvertYear(int x) {
- if (x >= 60)
- return 1900 + x;
- return 2000 + x;
-}
-
-bool CheckMonth(int x) {
- if (x <= 0 && x >= 13) {
- return false;
- }
-
- return true;
-}
-
-bool IsLeapYear(int y) {
- if (y == 2000)
- return false;
- if (y % 4)
- return false;
- return true;
-}
-
-int days[] = {0, 31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
-
-bool CheckDay(int day, int month, int year) {
- if (month == 2) {
- const bool leap = IsLeapYear(year);
- if (leap) {
- return day >= 1 && day <= 29;
- } else {
- return day >= 1 && day <= 28;
- }
- }
-
- return day >= 1 && day <= days[month];
-}
-
-struct Date {
- int year;
- int month;
- int day;
-};
-
-bool operator==(const Date &l, const Date &r) {
- return l.year == r.year && l.month == r.month && l.day == r.day;
-}
-
-bool operator<(const Date &l, const Date &r) {
- if (l.year < r.year)
- return true;
- else if (l.year > r.year)
- return false;
- else if (l.month < r.month)
- return true;
- else if (l.month > r.month)
- return false;
- else if (l.day < r.day)
- return true;
- return false;
-}
-
-bool Check(int year, int month, int day, Date *result) {
- if (!CheckMonth(month))
- return false;
- const auto y = ConvertYear(year);
- if (!CheckDay(day, month, y))
- return false;
-
- result->year = y;
- result->month = month;
- result->day = day;
- return true;
-}
-
-int main() {
- std::vector<Date> results;
-
- int a, b, c;
- std::scanf("%d/%d/%d", &a, &b, &c);
-
- Date temp;
- if (Check(a, b, c, &temp)) {
- results.push_back(temp);
- }
-
- if (Check(c, a, b, &temp)) {
- results.push_back(temp);
- }
-
- if (Check(c, b, a, &temp)) {
- results.push_back(temp);
- }
-
- results.erase(std::unique(results.begin(), results.end()), results.end());
- std::sort(results.begin(), results.end());
-
- for (const auto &r : results) {
- std::printf("%d-%02d-%02d\n", r.year, r.month, r.day);
- }
-
- return 0;
-}
diff --git a/works/solutions/acwing/1230.cpp b/works/solutions/acwing/1230.cpp deleted file mode 100644 index 958cbdd..0000000 --- a/works/solutions/acwing/1230.cpp +++ /dev/null @@ -1,36 +0,0 @@ -#include <iostream>
-
-using ll = long long;
-
-const int M = 100010;
-
-int N, K;
-ll p;
-int c[M];
-ll result;
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- std::cin >> N >> K;
-
- c[0] = 1;
-
- for (int i = 1; i <= N; i++) {
- int a;
- std::cin >> a;
-
- p += a;
-
- int r = p % K;
-
- result += c[r];
-
- c[r]++;
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1233.cpp b/works/solutions/acwing/1233.cpp deleted file mode 100644 index 117b2fb..0000000 --- a/works/solutions/acwing/1233.cpp +++ /dev/null @@ -1,69 +0,0 @@ -#include <iostream>
-#include <utility>
-
-const int M = 1010;
-
-int N;
-char map[M][M];
-bool visited[M][M];
-
-int not_sink_count;
-
-const std::pair<int, int> moves[]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
-
-void dfs(int r, int c) {
- if (visited[r][c])
- return;
- if (map[r][c] != '#')
- return;
-
- visited[r][c] = true;
-
- bool sink = false;
-
- for (const auto &move : moves) {
- if (map[r + move.first][c + move.second] == '.') {
- sink = true;
- break;
- }
- }
-
- if (!sink) {
- not_sink_count++;
- }
-
- for (const auto &move : moves) {
- dfs(r + move.first, c + move.second);
- }
-}
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- std::cin >> N;
-
- for (int i = 1; i <= N; i++) {
- for (int j = 1; j <= N; j++) {
- std::cin >> map[i][j];
- }
- }
-
- int result = 0;
-
- for (int i = 1; i <= N; i++) {
- for (int j = 1; j <= N; j++) {
- if (map[i][j] == '#' && !visited[i][j]) {
- dfs(i, j);
- if (not_sink_count == 0) {
- result++;
- }
- not_sink_count = 0;
- }
- }
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1236.cpp b/works/solutions/acwing/1236.cpp deleted file mode 100644 index a89a890..0000000 --- a/works/solutions/acwing/1236.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include <iostream>
-
-const int MAX = 100000;
-const int MM = 100010;
-
-int N;
-
-long long ca[MM];
-long long cb[MM];
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- std::cin >> N;
-
- for (int i = 0; i < N; i++) {
- int a;
- std::cin >> a;
- ca[a]++;
- }
-
- for (int n = 1; n <= MAX; n++) {
- ca[n] = ca[n - 1] + ca[n];
- }
-
- for (int i = 0; i < N; i++) {
- int b;
- std::cin >> b;
- cb[b]++;
- }
-
- for (int n = 1; n <= MAX; n++) {
- cb[n] *= ca[n - 1];
- }
-
- for (int n = 2; n <= MAX; n++) {
- cb[n] = cb[n - 1] + cb[n];
- }
-
- long long result = 0;
-
- for (int i = 0; i < N; i++) {
- int c;
- std::cin >> c;
- if (c >= 2) {
- result += cb[c - 1];
- }
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1237.cpp b/works/solutions/acwing/1237.cpp deleted file mode 100644 index a3b8810..0000000 --- a/works/solutions/acwing/1237.cpp +++ /dev/null @@ -1,49 +0,0 @@ -#include <cmath>
-#include <iostream>
-
-using ll = long long;
-
-int main() {
- ll X, Y;
- std::cin >> X >> Y;
-
- ll result = 0;
-
- if (X == 0 && Y == 0) {
- return 0;
- }
-
- if (std::abs(X) > std::abs(Y) ||
- (std::abs(X) == std::abs(Y) && !(X < 0 && Y < 0))) {
- ll c = std::abs(X);
-
- result += ((c - 1) * 4 + 2) * (c - 1);
-
- if (X > 0) {
- result += (c * 2 - 1) * 2;
- result += c * 2;
- result += (c - Y);
- } else {
- result += (c * 2 - 1);
- result += (Y - (-c + 1));
- }
-
- } else {
- ll c = std::abs(Y);
-
- result += ((c - 1) * 4 + 2) * (c - 1);
-
- if (Y > 0) {
- result += (c * 2 - 1) * 2;
- result += (X - (-c));
- } else {
- result += (c * 2 - 1) * 2;
- result += c * 2 * 2;
- result += c - X;
- }
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1238.cpp b/works/solutions/acwing/1238.cpp deleted file mode 100644 index 2c9d899..0000000 --- a/works/solutions/acwing/1238.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include <iostream>
-#include <map>
-#include <set>
-
-const int M = 100010;
-
-int N, D, K;
-
-std::map<int, std::multiset<int>> vote_map;
-
-bool check(const std::multiset<int> &v) {
- auto iter1 = v.cbegin();
- auto iter2 = v.cbegin();
-
- const auto end = v.cend();
-
- int count = 1;
-
- while (iter2 != end) {
- while (*iter2 - *iter1 >= D) {
- ++iter1;
- count--;
- }
-
- if (count >= K)
- return true;
-
- ++iter2;
- count++;
- }
-
- return false;
-}
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- std::cin >> N >> D >> K;
-
- for (int i = 1; i <= N; i++) {
- int ts, id;
- std::cin >> ts >> id;
- vote_map[id].insert(ts);
- }
-
- int result;
-
- for (const auto &vote : vote_map) {
- if (check(vote.second)) {
- std::cout << vote.first << "\n";
- }
- }
-
- return 0;
-}
diff --git a/works/solutions/acwing/1239.cpp b/works/solutions/acwing/1239.cpp deleted file mode 100644 index c670cd4..0000000 --- a/works/solutions/acwing/1239.cpp +++ /dev/null @@ -1,52 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-int N, K;
-long long A[100010];
-
-long long M = 1000000009;
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- std::cin >> N >> K;
-
- for (int i = 0; i < N; i++) {
- std::cin >> A[i];
- }
-
- std::sort(A, A + N);
-
- long long result = 1;
- int left = 0, right = N - 1;
- long long sign = 1;
- int k = K;
-
- if (k % 2) {
- result = A[N - 1];
- right--;
- k--;
-
- if (result < 0) {
- sign = -1;
- }
- }
-
- while (k) {
- long long x = A[left] * A[left + 1], y = A[right] * A[right - 1];
-
- if (x * sign > y * sign) {
- result = x % M * result % M;
- left += 2;
- } else {
- result = y % M * result % M;
- right -= 2;
- }
- k -= 2;
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1240.cpp b/works/solutions/acwing/1240.cpp deleted file mode 100644 index 8ebae33..0000000 --- a/works/solutions/acwing/1240.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include <iostream>
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- int n;
- std::cin >> n;
-
- int current_count = 0;
- int current_level_count = 1;
- int current_level = 1;
- long long current_sum = 0;
- long long max_sum = -1000000;
- int result = 1;
-
- for (int i = 0; i < n; i++) {
- long long a;
- std::cin >> a;
- current_sum += a;
- current_count++;
-
- if (current_count == current_level_count) {
- if (current_sum > max_sum) {
- max_sum = current_sum;
- result = current_level;
- }
- current_count = 0;
- current_level_count *= 2;
- current_sum = 0;
- current_level++;
- }
- }
-
- if (current_count && current_sum > max_sum) {
- result = current_level;
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1245.cpp b/works/solutions/acwing/1245.cpp deleted file mode 100644 index ba51a8f..0000000 --- a/works/solutions/acwing/1245.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <iostream>
-
-bool check(int n) {
- while (n != 0) {
- int k = n % 10;
- if (k == 2 || k == 0 || k == 1 || k == 9) {
- return true;
- }
- n /= 10;
- }
- return false;
-}
-
-int main() {
- int n;
- std::cin >> n;
-
- long long sum;
-
- for (int i = 1; i <= n; i++) {
- if (check(i)) {
- sum += i;
- }
- }
-
- std::cout << sum;
-
- return 0;
-}
diff --git a/works/solutions/acwing/1246.cpp b/works/solutions/acwing/1246.cpp deleted file mode 100644 index 5c0454c..0000000 --- a/works/solutions/acwing/1246.cpp +++ /dev/null @@ -1,34 +0,0 @@ -#include <algorithm>
-#include <iostream>
-#include <numeric>
-
-int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
-
-int N;
-int A[100010];
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- std::cin >> N;
-
- for (int i = 0; i < N; i++) {
- std::cin >> A[i];
- }
-
- std::sort(A, A + N);
-
- int g = A[1] - A[0];
- for (int i = 1; i < N - 1; i++) {
- g = gcd(g, A[i + 1] - A[i]);
- }
-
- if (g == 0) {
- std::cout << N;
- } else {
- std::cout << (A[N - 1] - A[0]) / g + 1;
- }
-
- return 0;
-}
\ No newline at end of file diff --git a/works/solutions/acwing/1247.cpp b/works/solutions/acwing/1247.cpp deleted file mode 100644 index 1fd4412..0000000 --- a/works/solutions/acwing/1247.cpp +++ /dev/null @@ -1,39 +0,0 @@ -#include <cmath>
-#include <iostream>
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- int N, M;
- std::cin >> N >> M;
-
- long long result = 0;
-
- long long min = 1e9 + 1;
- long long max = -1e9 - 1;
-
- for (int i = 0; i < N + M + 1; i++) {
- long long a;
- std::cin >> a;
- max = std::max(a, max);
- min = std::min(a, min);
- if (M == 0) {
- result += a;
- } else {
- result += std::abs(a);
- }
- }
-
- if (M != 0 && max < 0) {
- result += 2 * max;
- }
-
- if (M != 0 && min > 0) {
- result -= 2 * min;
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/2-2.cpp b/works/solutions/acwing/2-2.cpp deleted file mode 100644 index fb0fb3b..0000000 --- a/works/solutions/acwing/2-2.cpp +++ /dev/null @@ -1,25 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-int N, V;
-int v[1001];
-int w[1001];
-int states[1001];
-
-int main() {
- std::cin >> N >> V;
-
- for (int i = 1; i <= N; i++) {
- std::cin >> v[i] >> w[i];
- }
-
- for (int i = 1; i <= N; i++) {
- for (int j = V; j >= v[i]; j--) {
- states[j] = std::max(states[j], states[j - v[i]] + w[i]);
- }
- }
-
- std::cout << states[V];
-
- return 0;
-}
diff --git a/works/solutions/acwing/2.cpp b/works/solutions/acwing/2.cpp deleted file mode 100644 index 1a75c19..0000000 --- a/works/solutions/acwing/2.cpp +++ /dev/null @@ -1,30 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-int N, V;
-int v[1001];
-int w[1001];
-int states[1001][1001];
-
-int main() {
- std::cin >> N >> V;
-
- for (int i = 1; i <= N; i++) {
- std::cin >> v[i] >> w[i];
- }
-
- for (int i = 1; i <= N; i++) {
- for (int j = V; j >= 0; j--) {
- if (j >= v[i]) {
- states[i][j] =
- std::max(states[i - 1][j], states[i - 1][j - v[i]] + w[i]);
- } else {
- states[i][j] = states[i - 1][j];
- }
- }
- }
-
- std::cout << states[N][V];
-
- return 0;
-}
diff --git a/works/solutions/acwing/2065.cpp b/works/solutions/acwing/2065.cpp deleted file mode 100644 index a0c47c2..0000000 --- a/works/solutions/acwing/2065.cpp +++ /dev/null @@ -1,16 +0,0 @@ -#include <iostream>
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- long long n;
- std::cin >> n;
-
- while (n) {
- std::cout << n << ' ';
- n /= 2;
- }
-
- return 0;
-}
\ No newline at end of file diff --git a/works/solutions/acwing/2066.cpp b/works/solutions/acwing/2066.cpp deleted file mode 100644 index 7a6132b..0000000 --- a/works/solutions/acwing/2066.cpp +++ /dev/null @@ -1,21 +0,0 @@ -#include <cctype>
-#include <iostream>
-
-int main() {
- std::string input;
- std::cin >> input;
- std::string result;
-
- for (int i = 0; i < input.size(); i++) {
- if (std::isalpha(input[i])) {
- result.push_back(input[i]);
- } else {
- int c = input[i] - '1';
- result.append(c, input[i - 1]);
- }
- }
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/2067.cpp b/works/solutions/acwing/2067.cpp deleted file mode 100644 index 3ebd61d..0000000 --- a/works/solutions/acwing/2067.cpp +++ /dev/null @@ -1,22 +0,0 @@ -#include <iostream>
-
-int n, m;
-long long f[31][31];
-
-int main() {
- std::cin >> n >> m;
-
- f[1][1] = 1;
-
- for (int r = 1; r <= n; r++) {
- for (int c = 1; c <= m; c++) {
- if (!(r == 1 && c == 1) && !(r % 2 == 0 && c % 2 == 0)) {
- f[r][c] = f[r - 1][c] + f[r][c - 1];
- }
- }
- }
-
- std::cout << f[n][m];
-
- return 0;
-}
diff --git a/works/solutions/acwing/2068.cpp b/works/solutions/acwing/2068.cpp deleted file mode 100644 index 592f43f..0000000 --- a/works/solutions/acwing/2068.cpp +++ /dev/null @@ -1,57 +0,0 @@ -#include <algorithm>
-#include <cmath>
-#include <cstring>
-#include <iostream>
-
-int n, K;
-int A[100010];
-int c[11][100010];
-long long result;
-
-int CalcDigitCount(int n) {
- int c = 0;
- while (n != 0) {
- c++;
- n /= 10;
- }
- return c;
-}
-
-void work() {
- for (int i = 0; i < n; i++) {
- result += c[CalcDigitCount(A[i])][(K - A[i] % K) % K];
- // Wrong Code I don't know why!
- // int a = A[i];
- // for (int j = 1; j < 11; j++) {
- // a *= 10;
- // a %= K;
- // c[j][a]++;
- // }
- for (int j = 0, power = 1; j < 11; j++) {
- c[j][power * 1ll * A[i] % K]++;
- power = power * 10 % K;
- }
- }
-}
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- std::cin >> n >> K;
-
- for (int i = 0; i < n; i++) {
- std::cin >> A[i];
- }
-
- work();
-
- std::reverse(A, A + n);
- std::memset(c, 0, sizeof c);
-
- work();
-
- std::cout << result;
-
- return 0;
-}
diff --git a/works/solutions/acwing/2069.cpp b/works/solutions/acwing/2069.cpp deleted file mode 100644 index fbfa6d2..0000000 --- a/works/solutions/acwing/2069.cpp +++ /dev/null @@ -1,82 +0,0 @@ -#include <iostream>
-#include <vector>
-
-struct Node {
- int m = 0;
- Node *set;
- Node *left = nullptr;
- Node *right = nullptr;
-
- Node() : set(this) {}
-
- void SetParent(Node *parent, bool l) {
- set = parent;
- l ? parent->left = this : parent->right = this;
- }
-
- Node *GetSetRepresentative() {
- Node *r = this;
- while (r->set != r) {
- r = r->set;
- }
- set = r;
- return set;
- }
-
- bool has_dfs = false;
-
- void Dfs() {
- if (has_dfs)
- return;
- has_dfs = true;
- if (left != nullptr)
- left->Dfs(m);
- if (right != nullptr)
- right->Dfs(m);
- }
-
- void Dfs(int c) {
- m += c;
- if (left != nullptr)
- left->Dfs(m);
- if (right != nullptr)
- right->Dfs(m);
- }
-};
-
-Node nodes[10010];
-
-int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
-
- int n, m;
-
- std::cin >> n >> m;
-
- for (int i = 0; i < m; i++) {
- int operation, a, b;
- std::cin >> operation >> a >> b;
-
- if (operation == 1) {
- auto ra = nodes[a].GetSetRepresentative(),
- rb = nodes[b].GetSetRepresentative();
-
- if (ra != rb) {
- auto node = new Node;
- ra->SetParent(node, true);
- rb->SetParent(node, false);
- }
- } else {
- nodes[a].GetSetRepresentative()->m += b;
- }
- }
-
- for (int i = 1; i <= n; i++) {
- auto &node = nodes[i];
- node.GetSetRepresentative()->Dfs();
- std::cout << node.m << ' ';
- }
-
- return 0;
-}
diff --git a/works/solutions/acwing/3-2.cpp b/works/solutions/acwing/3-2.cpp deleted file mode 100644 index c099838..0000000 --- a/works/solutions/acwing/3-2.cpp +++ /dev/null @@ -1,25 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-int N, V;
-int v[1001];
-int w[1001];
-int states[1001];
-
-int main() {
- std::cin >> N >> V;
-
- for (int i = 1; i <= N; i++) {
- std::cin >> v[i] >> w[i];
- }
-
- for (int i = 1; i <= N; i++) {
- for (int j = v[i]; j <= V; j++) {
- states[j] = std::max(states[j], states[j - v[i]] + w[i]);
- }
- }
-
- std::cout << states[V];
-
- return 0;
-}
diff --git a/works/solutions/acwing/3.cpp b/works/solutions/acwing/3.cpp deleted file mode 100644 index 21bd8dc..0000000 --- a/works/solutions/acwing/3.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-int N, V;
-int v[1001];
-int w[1001];
-int states[1001][1001];
-
-int main() {
- std::cin >> N >> V;
-
- for (int i = 1; i <= N; i++) {
- std::cin >> v[i] >> w[i];
- }
-
- for (int i = 1; i <= N; i++) {
- for (int j = 0; j <= V; j++) {
- if (j >= v[i]) {
- states[i][j] = std::max(states[i - 1][j], states[i][j - v[i]] + w[i]);
- } else {
- states[i][j] = states[i - 1][j];
- }
- }
- }
-
- std::cout << states[N][V];
-
- return 0;
-}
diff --git a/works/solutions/acwing/4.cpp b/works/solutions/acwing/4.cpp deleted file mode 100644 index 3270402..0000000 --- a/works/solutions/acwing/4.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-int N, V;
-int v[101];
-int w[101];
-int s[101];
-int states[101];
-
-void CompletePack(int v, int w) {
- for (int j = v; j <= V; j++) {
- states[j] = std::max(states[j], states[j - v] + w);
- }
-}
-
-void ZeroOnePack(int v, int w) {
- for (int j = V; j >= v; j--) {
- states[j] = std::max(states[j], states[j - v] + w);
- }
-}
-
-int main() {
- std::cin >> N >> V;
-
- for (int i = 1; i <= N; i++) {
- std::cin >> v[i] >> w[i] >> s[i];
- }
-
- for (int i = 1; i <= N; i++) {
- if (v[i] * s[i] >= V) {
- CompletePack(v[i], w[i]);
- } else {
- int k = 1;
- int amount = s[i];
-
- while (k < amount) {
- ZeroOnePack(k * v[i], k * w[i]);
- amount -= k;
- k *= 2;
- }
-
- if (amount != 0) {
- ZeroOnePack(amount * v[i], amount * w[i]);
- }
- }
- }
-
- std::cout << states[V];
-
- return 0;
-}
diff --git a/works/solutions/acwing/5.cpp b/works/solutions/acwing/5.cpp deleted file mode 100644 index a88fba6..0000000 --- a/works/solutions/acwing/5.cpp +++ /dev/null @@ -1,49 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-int N, V;
-int v[1001];
-int w[1001];
-int s[1001];
-int states[2001];
-
-void CompletePack(int v, int w) {
- for (int j = v; j <= V; j++) {
- states[j] = std::max(states[j], states[j - v] + w);
- }
-}
-
-void ZeroOnePack(int v, int w) {
- for (int j = V; j >= v; j--) {
- states[j] = std::max(states[j], states[j - v] + w);
- }
-}
-
-int main() {
- std::cin >> N >> V;
-
- for (int i = 1; i <= N; i++) {
- std::cin >> v[i] >> w[i] >> s[i];
- }
-
- for (int i = 1; i <= N; i++) {
- if (v[i] * s[i] >= V) {
- CompletePack(v[i], w[i]);
- } else {
- int k = 1;
- int amount = s[i];
-
- while (k < amount) {
- ZeroOnePack(k * v[i], k * w[i]);
- amount -= k;
- k *= 2;
- }
-
- ZeroOnePack(amount * v[i], amount * w[i]);
- }
- }
-
- std::cout << states[V];
-
- return 0;
-}
diff --git a/works/solutions/acwing/7.cpp b/works/solutions/acwing/7.cpp deleted file mode 100644 index fcc0fb1..0000000 --- a/works/solutions/acwing/7.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-int N, V;
-int v[1001];
-int w[1001];
-int s[1001];
-int states[1001];
-
-void CompletePack(int v, int w) {
- for (int j = v; j <= V; j++) {
- states[j] = std::max(states[j], states[j - v] + w);
- }
-}
-
-void ZeroOnePack(int v, int w) {
- for (int j = V; j >= v; j--) {
- states[j] = std::max(states[j], states[j - v] + w);
- }
-}
-
-void MultiplePack(int v, int w, int s) {
- int k = 1;
-
- while (k < s) {
- ZeroOnePack(k * v, k * w);
- s -= k;
- k *= 2;
- }
-
- ZeroOnePack(s * v, s * w);
-}
-
-int main() {
- std::cin >> N >> V;
-
- for (int i = 1; i <= N; i++) {
- std::cin >> v[i] >> w[i] >> s[i];
- }
-
- for (int i = 1; i <= N; i++) {
- if (s[i] < 0) {
- ZeroOnePack(v[i], w[i]);
- } else if (s[i] == 0) {
- CompletePack(v[i], w[i]);
- } else {
- MultiplePack(v[i], w[i], s[i]);
- }
- }
-
- std::cout << states[V];
-
- return 0;
-}
diff --git a/works/solutions/acwing/8.cpp b/works/solutions/acwing/8.cpp deleted file mode 100644 index f62d21e..0000000 --- a/works/solutions/acwing/8.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-int N, V, M;
-int v[1001];
-int w[1001];
-int m[1001];
-int states[101][101];
-
-int main() {
- std::cin >> N >> V >> M;
-
- for (int i = 1; i <= N; i++) {
- std::cin >> v[i] >> m[i] >> w[i];
- }
-
- for (int i = 1; i <= N; i++) {
- for (int j = V; j >= v[i]; j--) {
- for (int k = M; k >= m[i]; k--) {
- states[j][k] =
- std::max(states[j][k], states[j - v[i]][k - m[i]] + w[i]);
- }
- }
- }
-
- std::cout << states[V][M];
-
- return 0;
-}
\ No newline at end of file diff --git a/works/solutions/leetcode/2.cpp b/works/solutions/leetcode/2.cpp deleted file mode 100644 index 4cf9c73..0000000 --- a/works/solutions/leetcode/2.cpp +++ /dev/null @@ -1,70 +0,0 @@ -#include <algorithm> -#include <iostream> -#include <set> -#include <queue> - -using std::vector; - -struct P { - int x; - int y; -}; - -struct I { - int x; - int y; - int v; -}; - -P mm[]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; - -class Solution { -public: - vector<vector<int>> bicycleYard(vector<int> &position, - vector<vector<int>> &terrain, - vector<vector<int>> &obstacle) { - std::vector<std::vector<std::set<int>>> visited( - terrain.size(), std::vector<std::set<int>>(terrain.front().size())); - - std::queue<I> q{{position[0], position[1], 1}}; - - bool f = false; - - while (true) { - if (f && q.size() == 1) { - break; - } - f = true; - - I b = q.back(); - q.pop_back(); - - if (b.v <= 0 || visited[b.x][b.y].count(b.v)) { - - } - - visited[b.x][b.y].insert(v); - - for (auto p : mm) { - int nx = x + p.x, ny = y + p.y; - if (nx >= 0 && nx < terrain.size() && ny >= 0 && - ny < terrain.front().size()) { - DFS(v + terrain[x][y] - terrain[nx][ny] - obstacle[nx][ny], nx, ny, - terrain, obstacle, visited); - } - } - } - - vector<vector<int>> result; - - for (int i = 0; i < terrain.size(); i++) { - for (int j = 0; j < obstacle.size(); j++) { - if ((i != position[0] || j != position[1]) && visited[i][j].count(1)) { - result.push_back({i, j}); - } - } - } - - return result; - } -};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/.gitignore b/works/solutions/leetcode/cpp/.gitignore deleted file mode 100644 index d1d85a8..0000000 --- a/works/solutions/leetcode/cpp/.gitignore +++ /dev/null @@ -1,3 +0,0 @@ -*.exe
-*.pdb
-*.ilk
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/10.cpp b/works/solutions/leetcode/cpp/10.cpp deleted file mode 100644 index fbb5586..0000000 --- a/works/solutions/leetcode/cpp/10.cpp +++ /dev/null @@ -1,83 +0,0 @@ -#include <string>
-#include <unordered_map>
-#include <vector>
-
-using std::string;
-
-struct Token {
- explicit Token(char c) : c(c), isAsterisk(false) {}
-
- char c;
- bool isAsterisk;
-};
-
-class Solution {
-public:
- std::vector<Token> tokens_;
- std::string s_;
- std::unordered_map<int, std::unordered_map<int, int>> cache_;
-
- bool isMatch(string s, string p) {
- for (auto c : p) {
- if (c == '*') {
- tokens_.back().isAsterisk = true;
- } else {
- tokens_.push_back(Token{c});
- }
- }
- s_ = s;
-
- return match(0, 0, s_.size(), tokens_.size());
- }
-
- bool cache_match(int s_start, int t_start, int s_length, int t_length) {
- auto cache = cache_[s_start][t_start];
- if (cache < 0) {
- return false;
- } else if (cache > 0) {
- return true;
- } else {
- auto result = match(s_start, t_start, s_length, t_length);
- cache_[s_start][t_start] = result;
- return result;
- }
- }
-
- bool match(int s_start, int t_start, int s_length, int t_length) {
- if (t_start == t_length)
- return s_start == s_length;
-
- const auto &token = tokens_[t_start];
- if (token.isAsterisk) {
- if (cache_match(s_start, t_start + 1, s_length, t_length)) {
- return true;
- }
-
- int s_index = s_start;
- while (s_index < s_length) {
- if (token.c == '.') {
- if (cache_match(s_index + 1, t_start + 1, s_length, t_length))
- return true;
- } else if (token.c == s_[s_index]) {
- if (cache_match(s_index + 1, t_start + 1, s_length, t_length))
- return true;
- } else {
- break;
- }
- s_index++;
- }
-
- return false;
- } else {
- if (token.c == '.') {
- return cache_match(s_start + 1, t_start + 1, s_length, t_length);
- } else {
- if (token.c == s_[s_start]) {
- return cache_match(s_start + 1, t_start + 1, s_length, t_length);
- } else {
- return false;
- }
- }
- }
- }
-};
diff --git a/works/solutions/leetcode/cpp/100.cpp b/works/solutions/leetcode/cpp/100.cpp deleted file mode 100644 index 28448d1..0000000 --- a/works/solutions/leetcode/cpp/100.cpp +++ /dev/null @@ -1,29 +0,0 @@ -struct TreeNode
-{
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode() : val(0), left(nullptr), right(nullptr) {}
- TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
-};
-
-class Solution
-{
-public:
- bool isSameTree(TreeNode *p, TreeNode *q)
- {
- if (p == nullptr)
- {
- if (q == nullptr)
- return true;
- return false;
- }
- else
- {
- if (q == nullptr)
- return false;
- return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
- }
- }
-};
diff --git a/works/solutions/leetcode/cpp/101.cpp b/works/solutions/leetcode/cpp/101.cpp deleted file mode 100644 index a1dad6f..0000000 --- a/works/solutions/leetcode/cpp/101.cpp +++ /dev/null @@ -1,43 +0,0 @@ -#include <cstddef>
-
-struct TreeNode
-{
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode(int x) : val(x), left(NULL), right(NULL) {}
-};
-
-class Solution
-{
-public:
- static bool check(TreeNode *left, TreeNode *right)
- {
- if (left == NULL)
- {
- if (right == NULL)
- return true;
- else
- return false;
- }
- else
- {
- if (right == NULL)
- return false;
- else
- {
- if (left->val != right->val)
- return false;
- return check(left->left, right->right) && check(left->right, right->left);
- }
- }
- }
-
- bool isSymmetric(TreeNode *root)
- {
- if (root == nullptr)
- return true;
-
- return check(root->left, root->right);
- }
-};
diff --git a/works/solutions/leetcode/cpp/1025.cpp b/works/solutions/leetcode/cpp/1025.cpp deleted file mode 100644 index b26ae02..0000000 --- a/works/solutions/leetcode/cpp/1025.cpp +++ /dev/null @@ -1,8 +0,0 @@ -class Solution
-{
-public:
- bool divisorGame(int N)
- {
- return N % 2 == 0;
- }
-};
diff --git a/works/solutions/leetcode/cpp/1051.cpp b/works/solutions/leetcode/cpp/1051.cpp deleted file mode 100644 index 6ded6f5..0000000 --- a/works/solutions/leetcode/cpp/1051.cpp +++ /dev/null @@ -1,33 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int heightChecker(vector<int> &heights)
- {
- vector<int> height_counter(101);
- for (int height : heights)
- {
- height_counter[height]++;
- }
-
- auto iter = heights.cbegin();
-
- int result = 0;
-
- for (int height = 1; height <= 100; height++)
- {
- int height_count = height_counter[height];
- while (height_count > 0)
- {
- if (*iter++ != height)
- result++;
- --height_count;
- }
- }
-
- return result;
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/1052.cpp b/works/solutions/leetcode/cpp/1052.cpp deleted file mode 100644 index 583e217..0000000 --- a/works/solutions/leetcode/cpp/1052.cpp +++ /dev/null @@ -1,47 +0,0 @@ -#include <algorithm>
-// #include <iostream>
-#include <vector>
-
-using std::vector;
-
-class Solution {
-public:
- int maxSatisfied(vector<int> &customers, vector<int> &grumpy, int X) {
- int customer_count = customers.size();
-
- int total_customer_count = 0;
- int total_unsatisfied_customer_count = 0;
-
- for (int i = 0; i < X; i++) {
- total_customer_count += customers[i];
- if (grumpy[i]) {
- total_unsatisfied_customer_count += customers[i];
- }
- }
-
- int current_suppress_customer_count = total_unsatisfied_customer_count;
- int max_suppress_customer_count = total_unsatisfied_customer_count;
-
- for (int i = X; i < customer_count; i++) {
- total_customer_count += customers[i];
- if (grumpy[i]) {
- total_unsatisfied_customer_count += customers[i];
- current_suppress_customer_count += customers[i];
- }
-
- if (grumpy[i - X]) {
- current_suppress_customer_count -= customers[i - X];
- }
-
- max_suppress_customer_count = std::max(max_suppress_customer_count,
- current_suppress_customer_count);
- }
-
- // std::cout << total_customer_count << '\n';
- // std::cout << total_unsatisfied_customer_count << '\n';
- // std::cout << max_suppress_customer_count << '\n';
-
- return total_customer_count - total_unsatisfied_customer_count +
- max_suppress_customer_count;
- }
-};
diff --git a/works/solutions/leetcode/cpp/11.cpp b/works/solutions/leetcode/cpp/11.cpp deleted file mode 100644 index 44a8fd9..0000000 --- a/works/solutions/leetcode/cpp/11.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include <vector>
-#include <algorithm>
-
-using std::vector;
-
-class Solution
-{
-public:
- int maxArea(vector<int> &height)
- {
- auto left = height.cbegin();
- auto right = height.cend();
- --right;
-
- int result = 0;
-
- // although length could be calculated by right - left,
- // but this can be cached in register.
- int length = height.size() - 1;
-
- while (left != right)
- {
- const int left_v = *left;
- const int right_v = *right;
- const int capacity = std::min(left_v, right_v) * length;
- result = std::max(capacity, result);
-
- if (left_v < right_v)
- {
- ++left;
- }
- else
- {
- --right;
- }
-
- length--;
- }
-
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/1144.cpp b/works/solutions/leetcode/cpp/1144.cpp deleted file mode 100644 index e6bf83b..0000000 --- a/works/solutions/leetcode/cpp/1144.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-inline int min(int a, int b)
-{
- return a < b ? a : b;
-}
-
-class Solution
-{
-public:
- int movesToMakeZigzag(vector<int> &nums)
- {
- int size = nums.size();
-
- if (size == 1)
- return 0;
-
- // odd
- int result_odd = 0;
- for (int i = 0; i < size; i += 2)
- {
- int neighber = 1001;
- if (i - 1 >= 0)
- neighber = min(neighber, nums[i - 1]);
- if (i + 1 < size)
- neighber = min(neighber, nums[i + 1]);
- if (nums[i] >= neighber)
- result_odd += nums[i] - neighber + 1;
- }
-
- // even
- int result_even = 0;
- for (int i = 1; i < size; i += 2)
- {
- int neighber = 1001;
- if (i - 1 >= 0)
- neighber = min(neighber, nums[i - 1]);
- if (i + 1 < size)
- neighber = min(neighber, nums[i + 1]);
- if (nums[i] >= neighber)
- result_even += nums[i] - neighber + 1;
- }
-
- return min(result_odd, result_even);
- }
-};
diff --git a/works/solutions/leetcode/cpp/12.cpp b/works/solutions/leetcode/cpp/12.cpp deleted file mode 100644 index e334895..0000000 --- a/works/solutions/leetcode/cpp/12.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include <string>
-
-using std::string;
-
-const char *roman_digits = "IVXLCDM";
-
-class Solution
-{
-public:
- string intToRoman(int num)
- {
- string result;
-
- int current_digit_index = 0;
-
- while (num != 0)
- {
- const int digit = num % 10;
- if (digit == 9)
- {
- result += roman_digits[current_digit_index + 2];
- result += roman_digits[current_digit_index];
- }
- else if (digit <= 8 && digit >= 5)
- {
- for (int i = 0; i < digit - 5; i++)
- {
- result += roman_digits[current_digit_index];
- }
- result += roman_digits[current_digit_index + 1];
- }
- else if (digit == 4)
- {
- result += roman_digits[current_digit_index + 1];
- result += roman_digits[current_digit_index];
- }
- else
- {
- for (int i = 0; i < digit; i++)
- {
- result += roman_digits[current_digit_index];
- }
- }
-
- num /= 10;
- current_digit_index += 2;
- }
-
- return string(result.crbegin(), result.crend());
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/121.cpp b/works/solutions/leetcode/cpp/121.cpp deleted file mode 100644 index 8561fa3..0000000 --- a/works/solutions/leetcode/cpp/121.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int maxProfit(vector<int> &prices)
- {
- if (prices.size() <= 1) return 0;
-
- int result = 0;
- int min = prices.front();
- for (int i = 1; i < prices.size(); i++)
- {
- if (prices[i] - min > result)
- result = prices[i] - min;
- if (prices[i] < min)
- min = prices[i];
- }
-
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/1219.cpp b/works/solutions/leetcode/cpp/1219.cpp deleted file mode 100644 index 5f72206..0000000 --- a/works/solutions/leetcode/cpp/1219.cpp +++ /dev/null @@ -1,64 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- static void dfs(const vector<vector<int>> &grid, bool **visited, int row, int col, int row_max, int col_max, int ¤t, int &max)
- {
- int cell = grid[row][col];
- bool &cell_visited = visited[row][col];
- if (cell == 0 || cell_visited)
- return;
- current += cell;
- cell_visited = true;
-
- if (current > max)
- max = current;
-
- if (row < row_max)
- dfs(grid, visited, row + 1, col, row_max, col_max, current, max);
-
- if (col < col_max)
- dfs(grid, visited, row, col + 1, row_max, col_max, current, max);
-
- if (row > 0)
- dfs(grid, visited, row - 1, col, row_max, col_max, current, max);
-
- if (col > 0)
- dfs(grid, visited, row, col - 1, row_max, col_max, current, max);
-
- cell_visited = false;
- current -= cell;
- }
-
- int getMaximumGold(vector<vector<int>> &grid)
- {
- int row_max = grid.size();
- int col_max = grid.front().size();
-
- bool **visited = new bool *[row_max];
- for (int i = 0; i < row_max; i++)
- {
- visited[i] = new bool[col_max]{false};
- }
-
- int current = 0;
- int max = 0;
-
- for (int row_start = 0; row_start < row_max; row_start++)
- for (int col_start = 0; col_start < col_max; col_start++)
- {
- dfs(grid, visited, row_start, col_start, row_max - 1, col_max - 1, current, max);
- }
-
- for (int i = 0; i < row_max; i++)
- {
- delete[] visited[i];
- }
- delete[] visited;
-
- return max;
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/122.cpp b/works/solutions/leetcode/cpp/122.cpp deleted file mode 100644 index 68cd278..0000000 --- a/works/solutions/leetcode/cpp/122.cpp +++ /dev/null @@ -1,28 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int maxProfit(vector<int> &prices)
- {
- if (prices.size() <= 1)
- return 0;
-
- int day_count = prices.size();
-
- vector<vector<int>> dp(day_count, std::vector<int>(2));
-
- dp[0][0] = 0;
- dp[0][1] = -prices[0];
-
- for (int i = 1; i < day_count; i++)
- {
- dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
- dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
- }
-
- return dp[day_count - 1][0];
- }
-};
diff --git a/works/solutions/leetcode/cpp/123.cpp b/works/solutions/leetcode/cpp/123.cpp deleted file mode 100644 index ecf35c4..0000000 --- a/works/solutions/leetcode/cpp/123.cpp +++ /dev/null @@ -1,34 +0,0 @@ -#include <vector>
-#include <iostream>
-using std::vector;
-
-#include <algorithm>
-
-class Solution
-{
-public:
- // 0 -> after buy for the first time
- // 1 -> after sell for the first time
- // 2 -> after buy for the second time
- // 3 -> after sell for the second time
-
- int maxProfit(vector<int> &prices)
- {
- int day_count = prices.size();
-
- int state_0 = -prices[0];
- int state_1 = 0;
- int state_2 = -prices[0];
- int state_3 = 0;
-
- for (int day = 1; day < day_count; day++)
- {
- state_0 = std::max(state_0, -prices[day]);
- state_1 = std::max(state_1, state_0 + prices[day]);
- state_2 = std::max(state_2, state_1 - prices[day]);
- state_3 = std::max(state_3, state_2 + prices[day]);
- }
-
- return std::max({state_0, state_1, state_2, state_3});
- }
-};
diff --git a/works/solutions/leetcode/cpp/1286.cpp b/works/solutions/leetcode/cpp/1286.cpp deleted file mode 100644 index 1ad0d4e..0000000 --- a/works/solutions/leetcode/cpp/1286.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include <string> - -using std::string; - -#include <vector> - -class CombinationIterator { -public: - string chars; - int char_length; - int combinationLength; - bool has_next = true; - std::vector<int> indices; - - CombinationIterator(string characters, int combinationLength) - : chars(characters), char_length(characters.size()), - combinationLength(combinationLength) { - for (int i = 0; i < combinationLength; i++) { - indices.push_back(i); - } - } - - string next() { - string result; - for (auto index : indices) { - result.push_back(chars[index]); - } - - int count = 1; - while (indices[combinationLength - count] == char_length - count) { - count++; - if (count > combinationLength) { - has_next = false; - return result; - } - } - - indices[combinationLength - count] += 1; - for (int i = combinationLength - count + 1; i < combinationLength; i++) { - indices[i] = indices[i - 1] + 1; - } - - return result; - } - - bool hasNext() { - return has_next; - } -}; - -/** - * Your CombinationIterator object will be instantiated and called as such: - * CombinationIterator* obj = new CombinationIterator(characters, - * combinationLength); string param_1 = obj->next(); bool param_2 = - * obj->hasNext(); - */
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/13.cpp b/works/solutions/leetcode/cpp/13.cpp deleted file mode 100644 index 9b7c5df..0000000 --- a/works/solutions/leetcode/cpp/13.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include <string>
-
-using std::string;
-
-int romanDigitNumber(char romanDigit)
-{
- switch (romanDigit)
- {
- case 'I':
- return 1;
- case 'V':
- return 5;
- case 'X':
- return 10;
- case 'L':
- return 50;
- case 'C':
- return 100;
- case 'D':
- return 500;
- case 'M':
- return 1000;
- };
- return 0;
-}
-
-class Solution
-{
-public:
- int romanToInt(string s)
- {
- int result = 0;
-
- int count = s.size();
-
- for (int i = 0; i < count; i++)
- {
- const char c = s[i];
- int num = romanDigitNumber(c);
- if (i < count - 1)
- {
- const char next = s[i + 1];
- if ((c == 'I' && (next == 'V' || next == 'X')) || (c == 'X' && (next == 'L' || next == 'C')) || (c == 'C') && (next == 'D' || next == 'M'))
- {
- num = -num;
- }
- }
-
- result += num;
- }
-
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/1343.cpp b/works/solutions/leetcode/cpp/1343.cpp deleted file mode 100644 index b300bc7..0000000 --- a/works/solutions/leetcode/cpp/1343.cpp +++ /dev/null @@ -1,40 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int numOfSubarrays(vector<int> &arr, int k, int threshold)
- {
- const auto end = arr.cend();
- auto iter = arr.cbegin();
- auto last_iter = arr.cbegin();
-
- double sum = 0;
-
- int result = 0;
-
- for (int i = 0; i < k; i++)
- {
- sum += *iter++;
- }
-
- while (iter != end)
- {
- if (sum / k >= threshold)
- {
- result++;
- }
- sum -= *last_iter++;
- sum += *iter++;
- }
-
- if (sum / k >= threshold)
- {
- result++;
- }
-
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/1347.cpp b/works/solutions/leetcode/cpp/1347.cpp deleted file mode 100644 index 154a6b5..0000000 --- a/works/solutions/leetcode/cpp/1347.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include <string>
-
-using std::string;
-
-class Solution
-{
-public:
- int minSteps(string s, string t)
- {
- int s_count[26]{0};
- int t_count[26]{0};
-
- for (auto c : s)
- {
- s_count[c - 'a']++;
- }
-
- for (auto c : t)
- {
- t_count[c - 'a']++;
- }
-
- int result = 0;
-
- for (int i = 0; i < 26; i++)
- {
- int a = s_count[i];
- int b = t_count[i];
- if (a > b)
- result += a - b;
- }
-
- return result;
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/1370.cpp b/works/solutions/leetcode/cpp/1370.cpp deleted file mode 100644 index 9741d48..0000000 --- a/works/solutions/leetcode/cpp/1370.cpp +++ /dev/null @@ -1,45 +0,0 @@ -#include <string>
-
-using std::string;
-
-class Solution
-{
-public:
- string sortString(string s)
- {
- int count[26]{0};
-
- for (auto c : s)
- {
- count[c - 'a']++;
- }
-
- int total_count = s.size();
- string result;
-
- while (total_count)
- {
- for (int i = 0; i < 26; i++)
- {
- if (count[i])
- {
- count[i]--;
- total_count--;
- result.push_back(i + 'a');
- }
- }
-
- for (int i = 25; i >= 0; i--)
- {
- if (count[i])
- {
- count[i]--;
- total_count--;
- result.push_back(i + 'a');
- }
- }
- }
-
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/14.cpp b/works/solutions/leetcode/cpp/14.cpp deleted file mode 100644 index 1d07a60..0000000 --- a/works/solutions/leetcode/cpp/14.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include <string>
-#include <vector>
-
-using std::string;
-using std::vector;
-
-class Solution
-{
-public:
- string longestCommonPrefix(vector<string> &strs)
- {
- if (strs.empty())
- return "";
-
- string result;
-
- const auto &first = strs.front();
-
- for (int i = 0; i < first.size(); i++)
- {
- char c = first[i];
-
- for (int j = 1; j < strs.size(); j++)
- {
- if (strs[j][i] != c)
- goto r;
- }
-
- result.push_back(c);
- }
-
- r:
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/147.cpp b/works/solutions/leetcode/cpp/147.cpp deleted file mode 100644 index c741290..0000000 --- a/works/solutions/leetcode/cpp/147.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include <cstddef>
-
-struct ListNode
-{
- int val;
- ListNode *next;
- ListNode(int x) : val(x), next(NULL) {}
-};
-
-class Solution
-{
-public:
- ListNode *insertionSortList(ListNode *head)
- {
- if (head == NULL)
- return NULL;
- if (head->next == NULL)
- return head;
-
- ListNode *next_sort = head->next;
-
- head->next = nullptr;
-
- while (next_sort != nullptr)
- {
- ListNode *current_sort = next_sort;
- next_sort = current_sort->next;
-
- ListNode *prev = nullptr;
- ListNode *current = head;
-
- int i = 0;
-
- while (current != nullptr && current->val < current_sort->val)
- {
- i++;
- prev = current;
- current = current->next;
- }
-
- if (prev == nullptr)
- {
- current_sort->next = head;
- head = current_sort;
- }
- else
- {
- ListNode *prev_next = prev->next;
- prev->next = current_sort;
- current_sort->next = prev_next;
- }
- }
-
- return head;
- }
-};
diff --git a/works/solutions/leetcode/cpp/1470.cpp b/works/solutions/leetcode/cpp/1470.cpp deleted file mode 100644 index 8657dd6..0000000 --- a/works/solutions/leetcode/cpp/1470.cpp +++ /dev/null @@ -1,23 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- vector<int> shuffle(vector<int> &nums, int n)
- {
- vector<int> result;
- result.resize(nums.size());
- auto iter = result.begin();
- auto iter1 = nums.cbegin();
- auto iter2 = nums.cbegin() + n;
- for (int i = 0; i < n; i++)
- {
- *iter++ = *iter1++;
- *iter++ = *iter2++;
- }
-
- return std::move(result);
- }
-};
diff --git a/works/solutions/leetcode/cpp/15.cpp b/works/solutions/leetcode/cpp/15.cpp deleted file mode 100644 index 2b8f6cd..0000000 --- a/works/solutions/leetcode/cpp/15.cpp +++ /dev/null @@ -1,44 +0,0 @@ -#include <iterator> -#include <vector> - -using std::vector; - -#include <algorithm> -#include <set> -#include <unordered_map> -#include <unordered_set> - -bool operator<(const std::vector<int> &l, std::vector<int> &r) { - return std::lexicographical_compare(l.cbegin(), l.cend(), r.cbegin(), - r.cend()); -} - -class Solution { -public: - int ha[100010]{0}; - - vector<vector<int>> threeSum(vector<int> &nums) { - std::set<std::vector<int>> result; - - if (nums.size() < 3) - return {}; - - std::unordered_map<int, int> m; - - for (auto n : nums) { - if (n >= 0) - m[n]++; - } - - for (int i = 0; i < nums.size() - 2; i++) { - for (int j = i + 1; j < nums.size() - 1; j++) { - auto v = -nums[i] - nums[j]; - if (v == 0) { - - } - } - } - - return std::vector<vector<int>>(result.cbegin(), result.cend()); - } -};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/155-2.cpp b/works/solutions/leetcode/cpp/155-2.cpp deleted file mode 100644 index aa07eee..0000000 --- a/works/solutions/leetcode/cpp/155-2.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#include <vector>
-#include <algorithm>
-
-class MinStack
-{
-public:
- /** initialize your data structure here. */
- MinStack()
- {
- // Although I really think this is just a trick for this problem.
- // Leetcode does not give the input size. So I just make a reasonable assumption.
- data_.reserve(10000);
- min_stack_.reserve(10000);
- }
-
- void push(int x)
- {
- data_.push_back(x);
- if (min_stack_.empty())
- {
- min_stack_.push_back(x);
- }
- else
- {
- min_stack_.push_back(std::min(min_stack_.back(), x));
- }
- }
-
- void pop()
- {
- data_.pop_back();
- min_stack_.pop_back();
- }
-
- int top()
- {
- return data_.back();
- }
-
- int getMin()
- {
- return min_stack_.back();
- }
-
-private:
- std::vector<int> data_;
- std::vector<int> min_stack_;
-};
diff --git a/works/solutions/leetcode/cpp/155.cpp b/works/solutions/leetcode/cpp/155.cpp deleted file mode 100644 index 48550be..0000000 --- a/works/solutions/leetcode/cpp/155.cpp +++ /dev/null @@ -1,38 +0,0 @@ -#include <vector>
-#include <set>
-
-class MinStack
-{
-public:
- /** initialize your data structure here. */
- MinStack()
- {
- }
-
- void push(int x)
- {
- data_.push_back(x);
- sorted_data_.insert(x);
- }
-
- void pop()
- {
- const auto v = data_.back();
- data_.pop_back();
- sorted_data_.erase(sorted_data_.find(v));
- }
-
- int top()
- {
- return data_.back();
- }
-
- int getMin()
- {
- return *sorted_data_.cbegin();
- }
-
-private:
- std::vector<int> data_;
- std::multiset<int> sorted_data_;
-};
diff --git a/works/solutions/leetcode/cpp/1609.cpp b/works/solutions/leetcode/cpp/1609.cpp deleted file mode 100644 index e446c0f..0000000 --- a/works/solutions/leetcode/cpp/1609.cpp +++ /dev/null @@ -1,94 +0,0 @@ -struct TreeNode
-{
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode() : val(0), left(nullptr), right(nullptr) {}
- TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
-};
-
-#include <queue>
-
-class Solution
-{
-public:
- bool isEvenOddTree(TreeNode *root)
- {
- if (root == nullptr)
- return true;
- std::queue<TreeNode *> odd_level;
- std::queue<TreeNode *> even_level;
-
- even_level.push(root);
-
- while (true)
- {
- if (!odd_level.empty())
- {
- auto node = odd_level.front();
- odd_level.pop();
- if (node->left)
- even_level.push(node->left);
- if (node->right)
- even_level.push(node->right);
- int last = node->val;
- if (last % 2 != 0)
- return false;
-
- while (!odd_level.empty())
- {
- node = odd_level.front();
- odd_level.pop();
- if (node->left)
- even_level.push(node->left);
- if (node->right)
- even_level.push(node->right);
- int val = node->val;
- if (val % 2 != 0)
- return false;
- if (val >= last)
- return false;
- last = val;
- }
-
- continue;
- }
-
- if (!even_level.empty())
- {
- auto node = even_level.front();
- even_level.pop();
- if (node->left)
- odd_level.push(node->left);
- if (node->right)
- odd_level.push(node->right);
- int last = node->val;
- if (last % 2 == 0)
- return false;
-
- while (!even_level.empty())
- {
- node = even_level.front();
- even_level.pop();
- if (node->left)
- odd_level.push(node->left);
- if (node->right)
- odd_level.push(node->right);
- int val = node->val;
- if (val % 2 == 0)
- return false;
- if (val <= last)
- return false;
- last = val;
- }
-
- continue;
- }
-
- break;
- }
-
- return true;
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/167.cpp b/works/solutions/leetcode/cpp/167.cpp deleted file mode 100644 index 05317b4..0000000 --- a/works/solutions/leetcode/cpp/167.cpp +++ /dev/null @@ -1,28 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- vector<int> twoSum(vector<int> &numbers, int target)
- {
- int left = 0, right = numbers.size() - 1;
- while (true)
- {
- const auto sum = numbers[left] + numbers[right];
- if (sum < target)
- {
- left++;
- }
- else if (sum > target)
- {
- right--;
- }
- else
- {
- return {left + 1, right + 1};
- }
- }
- }
-};
diff --git a/works/solutions/leetcode/cpp/17.04.cpp b/works/solutions/leetcode/cpp/17.04.cpp deleted file mode 100644 index 07ac7ae..0000000 --- a/works/solutions/leetcode/cpp/17.04.cpp +++ /dev/null @@ -1,21 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int missingNumber(vector<int> &nums)
- {
- const int size = nums.size();
- const int sum = size * (size + 1) / 2;
-
- int real_sum = 0;
- for (auto i : nums)
- {
- real_sum += i;
- }
-
- return sum - real_sum;
- }
-};
diff --git a/works/solutions/leetcode/cpp/17.cpp b/works/solutions/leetcode/cpp/17.cpp deleted file mode 100644 index 74e33b4..0000000 --- a/works/solutions/leetcode/cpp/17.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include <string>
-#include <vector>
-
-using std::string;
-using std::vector;
-
-vector<char> c_map[9]{
- {'a', 'b', 'c'},
- {'d', 'e', 'f'},
- {'g', 'h', 'i'},
- {'j', 'k', 'l'},
- {'m', 'n', 'o'},
- {'p', 'q', 'r', 's'},
- {'t', 'u', 'v'},
- {'w', 'x', 'y', 'z'}};
-
-void combine(const string::const_iterator ¤t, const string::const_iterator &end, string &head, vector<string> &result)
-{
- const auto &chars = c_map[(*current) - '2'];
-
- if (current == end)
- {
- for (auto c : chars)
- {
- head.push_back(c);
- result.push_back(head);
- head.pop_back();
- }
- return;
- }
-
- for (auto c : chars)
- {
- head.push_back(c);
- combine(current + 1, end, head, result);
- head.pop_back();
- }
-}
-
-class Solution
-{
-public:
- vector<string> letterCombinations(string digits)
- {
- std::vector<string> result;
-
- if (digits.empty())
- return result;
-
- std::string head;
-
- combine(digits.cbegin(), digits.cend() - 1, head, result);
-
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/198.cpp b/works/solutions/leetcode/cpp/198.cpp deleted file mode 100644 index 4d9d4fc..0000000 --- a/works/solutions/leetcode/cpp/198.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int rob(vector<int> &nums)
- {
- int count = nums.size();
- if (count == 0)
- return 0;
-
- int not_rob_prev = 0;
- int rob_prev = nums.front();
-
- for (int i = 1; i < count; i++)
- {
- int not_rob_prev_cache = not_rob_prev;
- not_rob_prev = std::max(not_rob_prev_cache, rob_prev);
- rob_prev = std::max(not_rob_prev_cache + nums[i], not_rob_prev);
- }
-
- return rob_prev;
- }
-};
diff --git a/works/solutions/leetcode/cpp/2.cpp b/works/solutions/leetcode/cpp/2.cpp deleted file mode 100644 index cb954ae..0000000 --- a/works/solutions/leetcode/cpp/2.cpp +++ /dev/null @@ -1,75 +0,0 @@ -struct ListNode
-{
- int val;
- ListNode *next;
- ListNode(int x) : val(x), next(NULL) {}
-};
-
-class Solution
-{
-public:
- ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
- {
- ListNode *result;
- ListNode *tail;
- int carry = 0;
-
- {
- int sum = l1->val + l2->val;
- if (sum > 9)
- {
- carry = 1;
- sum -= 10;
- }
-
- result = new ListNode(sum);
- tail = result;
-
- l1 = l1->next;
- l2 = l2->next;
- }
-
- while (l1 || l2)
- {
- int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
- if (sum > 9)
- {
- carry = 1;
- sum -= 10;
- }
- else
- {
- carry = 0;
- }
- tail->next = new ListNode(sum);
- tail = tail->next;
-
- if (l1)
- l1 = l1->next;
- if (l2)
- l2 = l2->next;
- }
-
- if (carry)
- {
- tail->next = new ListNode(1);
- }
-
- return result;
- }
-};
-
-int main()
-{
- ListNode *l1 = new ListNode(2);
- l1->next = new ListNode(4);
- l1->next = new ListNode(3);
-
- ListNode *l2 = new ListNode(5);
- l2->next = new ListNode(6);
- l2->next = new ListNode(4);
-
- ListNode *result = Solution{}.addTwoNumbers(l1, l2);
-
- return 0;
-}
diff --git a/works/solutions/leetcode/cpp/20.cpp b/works/solutions/leetcode/cpp/20.cpp deleted file mode 100644 index e994e96..0000000 --- a/works/solutions/leetcode/cpp/20.cpp +++ /dev/null @@ -1,55 +0,0 @@ -#include <string>
-
-using std::string;
-
-#include <stack>
-
-class Solution
-{
-public:
- inline static char get_companion(char c)
- {
- switch (c)
- {
- case ')':
- return '(';
- case ']':
- return '[';
- default:
- return '{';
- }
- }
-
- bool isValid(string s)
- {
- std::stack<char> stack;
-
- for (const auto c : s)
- {
- switch (c)
- {
- case '(':
- case '[':
- case '{':
- {
- stack.push(c);
- break;
- }
- case ')':
- case ']':
- default:
- {
- if (stack.empty())
- return false;
- const auto top = stack.top();
- const char companion = get_companion(c);
- if (top != companion)
- return false;
- stack.pop();
- }
- }
- }
-
- return stack.empty();
- }
-};
diff --git a/works/solutions/leetcode/cpp/203.cpp b/works/solutions/leetcode/cpp/203.cpp deleted file mode 100644 index 0f1bb55..0000000 --- a/works/solutions/leetcode/cpp/203.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#include <cstddef>
-
-struct ListNode
-{
- int val;
- ListNode *next;
- ListNode(int x) : val(x), next(NULL) {}
-};
-
-class Solution
-{
-public:
- ListNode *removeElements(ListNode *head, int val)
- {
- if (head == NULL)
- return NULL;
-
- ListNode *last = NULL;
- ListNode *current = head;
-
- while (current != NULL)
- {
- if (current->val == val)
- {
- if (last == NULL)
- {
- auto temp = current;
- current = current->next;
- head = current;
- delete temp;
- }
- else
- {
- auto temp = current;
- current = current->next;
- last->next = current;
- delete temp;
- }
- }
- else
- {
- last = current;
- current = current->next;
- }
- }
- return head;
- }
-};
diff --git a/works/solutions/leetcode/cpp/213.cpp b/works/solutions/leetcode/cpp/213.cpp deleted file mode 100644 index cd98f67..0000000 --- a/works/solutions/leetcode/cpp/213.cpp +++ /dev/null @@ -1,41 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int rob(vector<int> &nums)
- {
- int count = nums.size();
- if (count == 0)
- return 0;
-
- if (count == 1)
- return nums.front();
-
- int not_rob_prev = 0;
- int rob_prev = nums.front();
- int not_rob_prev_and_not_rob_first = 0;
- int rob_prev_and_not_rob_first = 0;
-
- for (int i = 1; i < count - 1; i++)
- {
- int not_rob_prev_cache = not_rob_prev;
- int not_rob_prev_and_not_rob_first_cache = not_rob_prev_and_not_rob_first;
- not_rob_prev = std::max(not_rob_prev_cache, rob_prev);
- rob_prev = std::max(not_rob_prev_cache + nums[i], not_rob_prev);
- not_rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache, rob_prev_and_not_rob_first);
- rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache + nums[i], not_rob_prev_and_not_rob_first);
- }
-
- // last houst
- {
- int not_rob_prev_and_not_rob_first_cache = not_rob_prev_and_not_rob_first;
- not_rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache, rob_prev_and_not_rob_first);
- rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache + nums[count - 1], not_rob_prev_and_not_rob_first);
- }
-
- return std::max(rob_prev, rob_prev_and_not_rob_first);
- }
-};
diff --git a/works/solutions/leetcode/cpp/22.cpp b/works/solutions/leetcode/cpp/22.cpp deleted file mode 100644 index e9467f1..0000000 --- a/works/solutions/leetcode/cpp/22.cpp +++ /dev/null @@ -1,40 +0,0 @@ -#include <string>
-#include <vector>
-
-using std::string;
-using std::vector;
-
-class Solution
-{
-public:
- static void backtrack(vector<string> &result, string ¤t, int left, int right, int count, int string_length)
- {
- if (current.length() == string_length)
- {
- result.push_back(current);
- return;
- }
-
- if (left < count)
- {
- current.push_back('(');
- backtrack(result, current, left + 1, right, count, string_length);
- current.pop_back();
- }
-
- if (right < left)
- {
- current.push_back(')');
- backtrack(result, current, left, right + 1, count, string_length);
- current.pop_back();
- }
- }
-
- vector<string> generateParenthesis(int n)
- {
- vector<string> result;
- string current;
- backtrack(result, current, 0, 0, n, n * 2);
- return std::move(result);
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/231.cpp b/works/solutions/leetcode/cpp/231.cpp deleted file mode 100644 index 8861e09..0000000 --- a/works/solutions/leetcode/cpp/231.cpp +++ /dev/null @@ -1,10 +0,0 @@ -#include <bitset>
-
-class Solution {
-public:
- bool isPowerOfTwo(int n) {
- if (n <= 0) return false;
- std::bitset<sizeof(n) * 8> bits(n);
- return bits.count() == 1;
- }
-};
diff --git a/works/solutions/leetcode/cpp/26.cpp b/works/solutions/leetcode/cpp/26.cpp deleted file mode 100644 index 3ee4aa7..0000000 --- a/works/solutions/leetcode/cpp/26.cpp +++ /dev/null @@ -1,37 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int removeDuplicates(vector<int> &nums)
- {
- if (nums.empty())
- return 0;
-
- auto iter_head = nums.cbegin();
- auto iter = iter_head + 1;
- int current = nums.front();
- int count = 1;
-
- while (iter != nums.cend())
- {
- const auto v = *iter;
- if (v == current)
- {
- nums.erase(iter);
- iter = iter_head + 1;
- }
- else
- {
- current = v;
- count++;
- iter_head = iter;
- ++iter;
- }
- }
-
- return count;
- }
-};
diff --git a/works/solutions/leetcode/cpp/260-2.cpp b/works/solutions/leetcode/cpp/260-2.cpp deleted file mode 100644 index 336d9e1..0000000 --- a/works/solutions/leetcode/cpp/260-2.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- vector<int> singleNumber(vector<int> &nums)
- {
- int diff = 0;
- for (auto i : nums)
- {
- diff ^= i;
- }
-
- int mask = diff & (-diff);
-
- int result = 0;
- for (auto i : nums)
- {
- result ^= (i & mask) ? i : 0;
- }
-
- return {result, result ^ diff};
- }
-};
diff --git a/works/solutions/leetcode/cpp/260.cpp b/works/solutions/leetcode/cpp/260.cpp deleted file mode 100644 index 5679d52..0000000 --- a/works/solutions/leetcode/cpp/260.cpp +++ /dev/null @@ -1,23 +0,0 @@ -#include <vector>
-#include <unordered_set>
-
-using std::vector;
-
-class Solution
-{
-public:
- vector<int> singleNumber(vector<int> &nums)
- {
- std::unordered_set<int> s;
- for (auto i : nums)
- {
- const auto result = s.find(i);
- if (result == s.cend())
- s.insert(i);
- else
- s.erase(result);
- }
-
- return vector<int>(s.cbegin(), s.cend());
- }
-};
diff --git a/works/solutions/leetcode/cpp/299.cpp b/works/solutions/leetcode/cpp/299.cpp deleted file mode 100644 index 21c09b6..0000000 --- a/works/solutions/leetcode/cpp/299.cpp +++ /dev/null @@ -1,44 +0,0 @@ -#include <string>
-
-using std::string;
-
-class Solution
-{
-public:
- string getHint(string secret, string guess)
- {
- int a = 0;
-
- int secret_digit_count[10] = {0};
-
- auto secret_iter = secret.cbegin();
- auto guess_iter = guess.cbegin();
-
- while (secret_iter != secret.cend())
- {
- auto secret_digit = *secret_iter;
- auto guess_digit = *guess_iter;
-
- secret_digit_count[secret_digit - '0']++;
-
- if (secret_digit == guess_digit)
- a++;
-
- ++secret_iter;
- ++guess_iter;
- }
-
- int b = 0;
- for (auto c : guess)
- {
- auto digit = c - '0';
- if (secret_digit_count[digit])
- {
- b++;
- secret_digit_count[digit]--;
- }
- }
-
- return std::to_string(a) + "A" + std::to_string(b - a) + "B";
- }
-};
diff --git a/works/solutions/leetcode/cpp/303.cpp b/works/solutions/leetcode/cpp/303.cpp deleted file mode 100644 index 06c4ad1..0000000 --- a/works/solutions/leetcode/cpp/303.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class NumArray
-{
-private:
- vector<int> prefix_sums;
-
-public:
- NumArray(vector<int> &nums)
- {
- prefix_sums.push_back(0);
- int sum = 0;
- for (auto num : nums)
- {
- sum += num;
- prefix_sums.push_back(sum);
- }
- }
-
- int sumRange(int i, int j)
- {
- return prefix_sums[j + 1] - prefix_sums[i];
- }
-};
diff --git a/works/solutions/leetcode/cpp/304.cpp b/works/solutions/leetcode/cpp/304.cpp deleted file mode 100644 index ab22281..0000000 --- a/works/solutions/leetcode/cpp/304.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class NumMatrix {
-private:
- std::vector<std::vector<int>> prefix_sum_;
-
-public:
- NumMatrix(vector<vector<int>> &matrix)
- : prefix_sum_(
- matrix.size() + 1,
- std::vector<int>(matrix.empty() ? 1 : matrix.front().size() + 1)) {
- const int row_count = matrix.size();
- const int col_count = matrix.empty() ? 0 : matrix.front().size();
-
- for (int i = 0; i < row_count; i++)
- for (int j = 0; j < col_count; j++) {
- prefix_sum_[i + 1][j + 1] = prefix_sum_[i][j + 1] +
- prefix_sum_[i + 1][j] - prefix_sum_[i][j] +
- matrix[i][j];
- }
- }
-
- int sumRegion(int row1, int col1, int row2, int col2) {
- return prefix_sum_[row1][col1] - prefix_sum_[row2 + 1][col1] -
- prefix_sum_[row1][col2 + 1] + prefix_sum_[row2 + 1][col2 + 1];
- }
-};
-
-/**
- * Your NumMatrix object will be instantiated and called as such:
- * NumMatrix* obj = new NumMatrix(matrix);
- * int param_1 = obj->sumRegion(row1,col1,row2,col2);
- */
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/328.cpp b/works/solutions/leetcode/cpp/328.cpp deleted file mode 100644 index de3ad0b..0000000 --- a/works/solutions/leetcode/cpp/328.cpp +++ /dev/null @@ -1,51 +0,0 @@ -struct ListNode
-{
- int val;
- ListNode *next;
- ListNode() : val(0), next(nullptr) {}
- ListNode(int x) : val(x), next(nullptr) {}
- ListNode(int x, ListNode *next) : val(x), next(next) {}
-};
-
-class Solution
-{
-public:
- ListNode *oddEvenList(ListNode *head)
- {
- if (head == nullptr)
- return nullptr;
-
- if (head->next == nullptr)
- return head;
-
- ListNode *odd_head = head;
- head = head->next;
- ListNode *even_head = head;
- head = head->next;
-
- ListNode *odd_current = odd_head;
- ListNode *even_current = even_head;
-
- bool odd = true;
- while (head != nullptr)
- {
- if (odd)
- {
- odd_current->next = head;
- odd_current = head;
- }
- else
- {
- even_current->next = head;
- even_current = head;
- }
- head = head->next;
- odd = !odd;
- }
-
- odd_current->next = even_head;
- even_current->next = nullptr;
-
- return odd_head;
- }
-};
diff --git a/works/solutions/leetcode/cpp/337.cpp b/works/solutions/leetcode/cpp/337.cpp deleted file mode 100644 index 655a4d0..0000000 --- a/works/solutions/leetcode/cpp/337.cpp +++ /dev/null @@ -1,38 +0,0 @@ -#include <cstddef>
-
-struct TreeNode
-{
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode(int x) : val(x), left(NULL), right(NULL) {}
-};
-
-struct SubTreeResult
-{
- SubTreeResult(int use_root, int not_use_root) : use_root(use_root), not_use_root(not_use_root), max(use_root > not_use_root ? use_root : not_use_root) {}
-
- const int use_root;
- const int not_use_root;
- const int max;
-};
-
-class Solution
-{
-public:
- static SubTreeResult subtree_rob(TreeNode *root)
- {
- SubTreeResult left = root->left != NULL ? subtree_rob(root->left) : SubTreeResult{0, 0};
- SubTreeResult right = root->right != NULL ? subtree_rob(root->right) : SubTreeResult{0, 0};
- const auto use_root_value = root->val + left.not_use_root + right.not_use_root;
- const auto not_use_root_value = left.max + right.max;
- return SubTreeResult{use_root_value, not_use_root_value};
- }
-
- int rob(TreeNode *root)
- {
- if (root == NULL)
- return 0;
- return subtree_rob(root).max;
- }
-};
diff --git a/works/solutions/leetcode/cpp/338.cpp b/works/solutions/leetcode/cpp/338.cpp deleted file mode 100644 index 1758234..0000000 --- a/works/solutions/leetcode/cpp/338.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- vector<int> countBits(int num)
- {
- vector<int> result(num + 1);
- result[0] = 0;
- for (int i = 1; i <= num; i++)
- {
- if (i % 2 == 1)
- {
- result[i] = result[i - 1] + 1;
- }
- else
- {
- result[i] = result[i / 2];
- }
- }
-
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/343.cpp b/works/solutions/leetcode/cpp/343.cpp deleted file mode 100644 index d31f7ce..0000000 --- a/works/solutions/leetcode/cpp/343.cpp +++ /dev/null @@ -1,23 +0,0 @@ -#include <cmath>
-
-class Solution
-{
-public:
- int integerBreak(int n)
- {
- if (n == 2)
- return 1;
- if (n == 3)
- return 2;
-
- if (n % 3 == 1)
- {
- return static_cast<int>(std::pow(3, n / 3 - 1)) * 4;
- }
- else if (n % 3 == 2)
- {
- return static_cast<int>(std::pow(3, n / 3)) * 2;
- }
- return static_cast<int>(std::pow(3, n / 3));
- }
-};
diff --git a/works/solutions/leetcode/cpp/35.cpp b/works/solutions/leetcode/cpp/35.cpp deleted file mode 100644 index 7da26c4..0000000 --- a/works/solutions/leetcode/cpp/35.cpp +++ /dev/null @@ -1,36 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int searchInsert(vector<int> &nums, int target)
- {
- if (nums.empty())
- return 0;
-
- int left_index = 0;
- int right_index = nums.size();
-
- while (left_index != right_index)
- {
- const int middle_index = (left_index + right_index) / 2;
- const int middle_value = nums[middle_index];
- if (target < middle_value)
- {
- right_index = middle_index;
- }
- else if (target > middle_value)
- {
- left_index = middle_index + 1;
- }
- else
- {
- return middle_index;
- }
- }
-
- return left_index;
- }
-};
diff --git a/works/solutions/leetcode/cpp/371.cpp b/works/solutions/leetcode/cpp/371.cpp deleted file mode 100644 index 3a7bc8b..0000000 --- a/works/solutions/leetcode/cpp/371.cpp +++ /dev/null @@ -1,25 +0,0 @@ - -class Solution { -public: - int getSum(int a, int b) { - unsigned x = a, y = b; - - unsigned carry = 0; - - unsigned result = 0; - - for (int i = 0; i < sizeof(int) * 8; i++) { - unsigned mask = 1 << i; - - unsigned n = x & mask ? 1 : 0, m = y & mask ? 1 : 0; - - if (n ^ m ^ carry) { - result |= mask; - } - - carry = n & m || n & carry || m & carry; - } - - return static_cast<int>(result); - } -}; diff --git a/works/solutions/leetcode/cpp/395.cpp b/works/solutions/leetcode/cpp/395.cpp deleted file mode 100644 index d45eee9..0000000 --- a/works/solutions/leetcode/cpp/395.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include <array>
-#include <string>
-
-using std::string;
-
-class Solution {
-public:
- static int dfs(const std::string &s, int start, int end, int k) {
- if (end - start < k) {
- return 0;
- }
-
- std::array<int, 26> counts{0};
-
- for (int i = start; i < end; i++) {
- counts[s[i] - 'a']++;
- }
-
- int max = -1;
-
- for (char c = 'a'; c <= 'z'; c++) {
- int count = counts[c - 'a'];
-
- if (count > 0 && count < k) {
- int sub_start = start;
-
- for (int i = start; i < end; i++) {
- if (s[i] == c) {
- if (sub_start != i) {
- max = std::max(dfs(s, sub_start, i, k), max);
- }
- sub_start = i + 1;
- }
- }
-
- if (sub_start != end) {
- max = std::max(dfs(s, sub_start, end, k), max);
- }
-
- break; // This is vital.
- }
- }
-
- if (max == -1)
- return end - start;
- else
- return max;
- }
-
- int longestSubstring(string s, int k) { return dfs(s, 0, s.size(), k); }
-};
-
-int main() {
- Solution{}.longestSubstring("aaaaaaaaaaaabcdefghijklmnopqrstuvwzyz", 3);
- return 0;
-}
diff --git a/works/solutions/leetcode/cpp/397.cpp b/works/solutions/leetcode/cpp/397.cpp deleted file mode 100644 index bbb61ff..0000000 --- a/works/solutions/leetcode/cpp/397.cpp +++ /dev/null @@ -1,47 +0,0 @@ -class Solution
-{
-public:
- int integerReplacement(int n)
- {
- if (n == 2147483647)
- return 32;
-
- int count = 0;
-
- while (n != 1)
- {
- if (n == 2)
- {
- count += 1;
- break;
- }
- if (n == 3)
- {
- count += 2;
- break;
- }
- if (n % 2 == 0)
- {
- count += 1;
- n /= 2;
- continue;
- }
- if ((n - 1) % 4 == 0)
- {
- count += 3;
- n = (n - 1) / 4;
- continue;
- }
- if ((n + 1) % 4 == 0)
- {
- count += 3;
- n = (n + 1) / 4;
- continue;
- }
- count += 2;
- n = (n - 1) / 2;
- }
-
- return count;
- }
-};
diff --git a/works/solutions/leetcode/cpp/401.cpp b/works/solutions/leetcode/cpp/401.cpp deleted file mode 100644 index 71147f4..0000000 --- a/works/solutions/leetcode/cpp/401.cpp +++ /dev/null @@ -1,57 +0,0 @@ -#include <array>
-#include <string>
-#include <vector>
-
-using std::string;
-using std::vector;
-
-const std::array<int, 4> hour_digits{1, 2, 4, 8};
-const std::array<int, 6> minute_digits{1, 2, 4, 8, 16, 32};
-
-class Solution {
-public:
- template <int max, std::size_t size>
- void dfs(const std::array<int, size> &digits, int total_count, int rest_count,
- int start_index, int value, std::vector<int> &result) {
-
- if (value >= max)
- return;
-
- if (rest_count == 0) {
- result.push_back(value);
- return;
- }
-
- for (int i = start_index; i <= size - rest_count; i++) {
- dfs<max, size>(digits, total_count, rest_count - 1, i + 1,
- value + digits[i], result);
- }
- }
-
- vector<string> readBinaryWatch(int num) {
- vector<string> results;
-
- for (int i = (num > 6 ? num - 6 : 0); i <= (num > 4 ? 4 : num); i++) {
- std::vector<int> hours;
- std::vector<int> minutes;
- if (i == 0)
- hours = {0};
- else
- dfs<12>(hour_digits, i, i, 0, 0, hours);
- if (i == num)
- minutes = {0};
- else
- dfs<60>(minute_digits, num - i, num - i, 0, 0, minutes);
-
- for (auto hour : hours) {
- for (auto minute : minutes) {
- char buffer[6];
- sprintf(buffer, "%d:%02d", hour, minute);
- results.push_back(string(buffer));
- }
- }
- }
-
- return results;
- }
-};
diff --git a/works/solutions/leetcode/cpp/46.cpp b/works/solutions/leetcode/cpp/46.cpp deleted file mode 100644 index bfb3c83..0000000 --- a/works/solutions/leetcode/cpp/46.cpp +++ /dev/null @@ -1,34 +0,0 @@ -#include <vector> - -using std::vector; - -class Solution { -public: - void dfs(const vector<int> &nums, vector<int> ¤t, bool *num_used, - vector<vector<int>> &result) { - if (current.size() == nums.size()) { - result.push_back(current); - return; - } - - for (int i = 0; i < nums.size(); i++) { - if (!num_used[i]) { - num_used[i] = true; - current.push_back(nums[i]); - dfs(nums, current, num_used, result); - current.pop_back(); - num_used[i] = false; - } - } - } - - vector<vector<int>> permute(vector<int> &nums) { - vector<int> current; - vector<vector<int>> result; - bool *num_used = new bool[nums.size()]{false}; - dfs(nums, current, num_used, result); - delete[] num_used; - - return result; - } -}; diff --git a/works/solutions/leetcode/cpp/47.cpp b/works/solutions/leetcode/cpp/47.cpp deleted file mode 100644 index 4a109ea..0000000 --- a/works/solutions/leetcode/cpp/47.cpp +++ /dev/null @@ -1,45 +0,0 @@ -#include <vector> -#include <set> - -using std::vector; - -class Solution { -public: - - void DFS(int length, const std::vector<int>& nums, std::vector<int>& visited, std::vector<int>& current, std::vector<std::vector<int>>& result) { - if (length == 0) { - result.push_back(current); - } - - int used[21] {0}; - - int size = nums.size(); - - for (int i = 0; i < size; i++) { - if (visited[i]) { - continue; - } - - visited[i] = 1; - - int num = nums[i]; - - if (!used[num + 10]) { - current.push_back(nums[i]); - DFS(length - 1, nums, visited, current, result); - current.pop_back(); - used[num + 10] = 1; - } - - visited[i] = 0; - } - } - - vector<vector<int>> permuteUnique(vector<int>& nums) { - std::vector<int> visited(nums.size()); - std::vector<int> current; - std::vector<std::vector<int>> result; - DFS(nums.size(),nums, visited, current, result); - return result; - } -};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/495.cpp b/works/solutions/leetcode/cpp/495.cpp deleted file mode 100644 index c940b0b..0000000 --- a/works/solutions/leetcode/cpp/495.cpp +++ /dev/null @@ -1,37 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int findPoisonedDuration(vector<int> &timeSeries, int duration)
- {
- if (timeSeries.empty())
- return 0;
-
- int total_time = 0;
-
- int start_time = timeSeries.front();
- int expected_end_time = start_time + duration;
-
- for (auto iter = timeSeries.cbegin() + 1; iter != timeSeries.cend(); ++iter)
- {
- const auto this_time = *iter;
- if (this_time <= expected_end_time)
- {
- expected_end_time = this_time + duration;
- }
- else
- {
- total_time += expected_end_time - start_time;
- start_time = this_time;
- expected_end_time = this_time + duration;
- }
- }
-
- total_time += expected_end_time - start_time;
-
- return total_time;
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/5.cpp b/works/solutions/leetcode/cpp/5.cpp deleted file mode 100644 index 6200c4c..0000000 --- a/works/solutions/leetcode/cpp/5.cpp +++ /dev/null @@ -1,104 +0,0 @@ -#include <string>
-
-using std::string;
-
-class Solution
-{
-public:
- void longestWithCenter(const string &s, int length, int index, int *longest_start, int *longest_length_ptr)
- {
- int &longest_length = *longest_length_ptr;
-
- int palindrome_length_odd = index * 2 + 1 <= longest_length || (length - index - 1) * 2 + 1 <= longest_length ? 0 : 1;
- int palindrome_length_even = (index + 1) * 2 <= longest_length || (length - index - 1) * 2 <= longest_length ? 0 : 1;
-
- while (palindrome_length_odd || palindrome_length_even)
- {
- if (palindrome_length_odd)
- {
- int start = index - palindrome_length_odd;
- int end = index + palindrome_length_odd;
- if (start < 0)
- {
- palindrome_length_odd = 0;
- }
- else if (end >= length)
- {
- palindrome_length_odd = 0;
- }
- else
- {
- if (s[start] == s[end])
- {
- int current_length = end - start + 1;
- if (current_length > longest_length)
- {
- *longest_start = start;
- longest_length = current_length;
- }
- palindrome_length_odd++;
- }
- else
- {
- palindrome_length_odd = 0;
- }
- }
- }
-
- if (palindrome_length_even)
- {
- int start = index - palindrome_length_even + 1;
- int end = index + palindrome_length_even;
- if (start < 0)
- {
- palindrome_length_even = 0;
- }
- else if (end >= length)
- {
- palindrome_length_even = 0;
- }
- else
- {
- if (s[start] == s[end])
- {
- int current_length = end - start + 1;
- if (current_length > longest_length)
- {
- *longest_start = start;
- longest_length = current_length;
- }
- palindrome_length_even++;
- }
- else
- {
- palindrome_length_even = 0;
- }
- }
- }
- }
- }
-
- string longestPalindrome(string s)
- {
- if (s.empty())
- return "";
-
- int longest_start = 0;
- int longest_length = 1;
- int length = s.size();
-
- for (int i = 0; i < length; i++)
- {
- longestWithCenter(s, length, i, &longest_start, &longest_length);
- }
-
- return s.substr(longest_start, longest_length);
- }
-};
-
-int main()
-{
- Solution s{};
- s.longestPalindrome("bb");
- return 0;
-}
diff --git a/works/solutions/leetcode/cpp/501.cpp b/works/solutions/leetcode/cpp/501.cpp deleted file mode 100644 index 197ed10..0000000 --- a/works/solutions/leetcode/cpp/501.cpp +++ /dev/null @@ -1,58 +0,0 @@ -#include <cstddef> -#include <vector> - -using std::vector; - -struct TreeNode -{ - int val; - TreeNode *left; - TreeNode *right; - TreeNode(int x) : val(x), left(NULL), right(NULL) {} -}; - -class Solution -{ -public: - void dfs(TreeNode *node, int &last, int &count, int &max_count, vector<int> &result) - { - if (node == nullptr) - return; - - dfs(node->left, last, count, max_count, result); - - auto current = node->val; - if (current == last) - { - count += 1; - } - else - { - count = 1; - } - - if (count == max_count) - { - result.push_back(current); - } - else if (count > max_count) - { - max_count = count; - result.clear(); - result.push_back(current); - } - - last = current; - dfs(node->right, last, count, max_count, result); - } - - vector<int> findMode(TreeNode *root) - { - if (root == nullptr) - return {}; - int last = 0, count = 0, max_count = 0; - vector<int> result; - dfs(root, last, count, max_count, result); - return result; - } -}; diff --git a/works/solutions/leetcode/cpp/526.cpp b/works/solutions/leetcode/cpp/526.cpp deleted file mode 100644 index 19f445f..0000000 --- a/works/solutions/leetcode/cpp/526.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <vector> - -using std::vector; - -class Solution { -public: - void dfs(int N, int index, bool *num_used, int &result) { - if (index > N) { - result += 1; - return; - } - - for (int num = 1; num <= N; num++) { - if (!num_used[num] && (num % index == 0 || index % num == 0)) { - num_used[num] = true; - dfs(N, index + 1, num_used, result); - num_used[num] = false; - } - } - } - - int countArrangement(int N) { - bool *num_used = new bool[N + 1]{false}; - int result = 0; - dfs(N, 1, num_used, result); - delete[] num_used; - return result; - } -}; diff --git a/works/solutions/leetcode/cpp/543.cpp b/works/solutions/leetcode/cpp/543.cpp deleted file mode 100644 index f782521..0000000 --- a/works/solutions/leetcode/cpp/543.cpp +++ /dev/null @@ -1,32 +0,0 @@ -struct TreeNode {
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
-};
-
-#include <algorithm>
-
-class Solution {
-public:
- int diameterOfBinaryTree(TreeNode *root) {
- int max = 0;
- depth(root, max);
- return max;
- }
-
- static int depth(TreeNode *root, int &max) {
- if (root == nullptr)
- return -1;
-
- auto left = depth(root->left, max) + 1;
- auto right = depth(root->right, max) + 1;
-
- auto current_max = left + right;
- if (current_max > max) {
- max = current_max;
- }
-
- return std::max(left, right);
- }
-};
diff --git a/works/solutions/leetcode/cpp/55.cpp b/works/solutions/leetcode/cpp/55.cpp deleted file mode 100644 index d2c2600..0000000 --- a/works/solutions/leetcode/cpp/55.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-#include <algorithm>
-
-class Solution
-{
-public:
- bool canJump(vector<int> &nums)
- {
- int max = 0;
- const int size = nums.size();
- for (int i = 0; i < size; i++)
- {
- if (i <= max)
- {
- max = std::max(max, i + nums[i]);
- if (max >= size - 1)
- return true;
- }
- else
- {
- return false;
- }
- }
- return false;
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/6.cpp b/works/solutions/leetcode/cpp/6.cpp deleted file mode 100644 index f1d947c..0000000 --- a/works/solutions/leetcode/cpp/6.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include <string>
-#include <iostream>
-
-using std::string;
-
-class Solution
-{
-public:
- string convert(string s, int numRows)
- {
- if (numRows == 1)
- return s;
-
- const auto length = s.size();
- const int count_per_group = numRows * 2 - 2;
- string result;
- result.reserve(length);
- for (int row = 0; row < numRows; row++)
- {
- if (row == 0)
- {
- for (int p = 0; p < length; p += count_per_group)
- result += s[p];
- }
- else if (row == numRows - 1)
- {
- for (int p = row; p < length; p += count_per_group)
- result += s[p];
- }
- else
- {
- bool former = true;
- const auto former_gap = count_per_group - row * 2;
- const auto latter_gap = count_per_group - former_gap;
- for (int p = row; p < length; p += (former ? former_gap : latter_gap), former = !former)
- result += s[p];
- }
- }
- return result;
- }
-};
-
-int main()
-{
- Solution s;
-
- auto result1 = s.convert("PAYPALISHIRING", 3);
- auto result2 = s.convert("PAYPALISHIRING", 4);
- std::cout
- << s.convert("A", 1) << '\n'
- << result1 << '\n'
- << "PAHNAPLSIIGYIR\n"
- << result2 << '\n'
- << "PINALSIGYAHRPI\n";
- return 0;
-}
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/60.cpp b/works/solutions/leetcode/cpp/60.cpp deleted file mode 100644 index f090355..0000000 --- a/works/solutions/leetcode/cpp/60.cpp +++ /dev/null @@ -1,44 +0,0 @@ -#include <string>
-#include <vector>
-
-using std::string;
-
-class Solution
-{
-public:
- string getPermutation(int n, int k)
- {
- k--;
-
- string result;
- result.reserve(n);
-
- std::vector<char> nums;
- nums.reserve(n);
-
- for (int i = 1; i <= n; i++)
- {
- nums.push_back(i + '0');
- }
-
- n--;
- int fac = 1;
- for (int i = 2; i <= n; i++)
- {
- fac *= i;
- }
-
- while (n > 0)
- {
- const int index = k / fac;
- k = k % fac;
- result += nums[index];
- nums.erase(nums.cbegin() + index);
- fac /= n--;
- }
-
- result += nums.front();
-
- return result;
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/62.cpp b/works/solutions/leetcode/cpp/62.cpp deleted file mode 100644 index 744a0d3..0000000 --- a/works/solutions/leetcode/cpp/62.cpp +++ /dev/null @@ -1,25 +0,0 @@ -#include <utility>
-
-class Solution
-{
-public:
- // C(m + n - 2, m - 1)
- int uniquePaths(int m, int n)
- {
- if (m < n)
- std::swap(m, n);
-
- long long result = 1;
- for (int i = m; i <= m + n - 2; i++)
- {
- result *= i;
- }
-
- for (int i = 2; i <= n - 1; i++)
- {
- result /= i;
- }
-
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/63.cpp b/works/solutions/leetcode/cpp/63.cpp deleted file mode 100644 index ed07bdc..0000000 --- a/works/solutions/leetcode/cpp/63.cpp +++ /dev/null @@ -1,44 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
- {
- if (obstacleGrid[0][0])
- return 0;
- obstacleGrid[0][0] = 1;
-
- int row = obstacleGrid.size();
- int col = obstacleGrid.front().size();
-
- for (int i = 1; i < row; i++)
- {
- obstacleGrid[i][0] = obstacleGrid[i - 1][0] && !obstacleGrid[i][0] ? 1 : 0;
- }
-
- for (int i = 1; i < col; i++)
- {
- obstacleGrid[0][i] = obstacleGrid[0][i - 1] && !obstacleGrid[0][i] ? 1 : 0;
- }
-
- for (int r = 1; r < row; r++)
- {
- for (int c = 1; c < col; c++)
- {
- if (obstacleGrid[r][c])
- {
- obstacleGrid[r][c] = 0;
- }
- else
- {
- obstacleGrid[r][c] = obstacleGrid[r - 1][c] + obstacleGrid[r][c - 1];
- }
- }
- }
-
- return obstacleGrid[row - 1][col - 1];
- }
-};
diff --git a/works/solutions/leetcode/cpp/639.cpp b/works/solutions/leetcode/cpp/639.cpp deleted file mode 100644 index ead252e..0000000 --- a/works/solutions/leetcode/cpp/639.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include <string> - -using std::string; - -const long long M = 1e9 + 7; - -class Solution { -public: - long long f[100010]{0}; - - int numDecodings(string s) { - f[0] = 1; - if (s.front() == '*') { - f[1] = 9; - } else if (s.front() == '0') { - f[1] = 0; - } else { - f[1] = 1; - } - - for (int i = 2; i <= s.size(); i++) { - char c = s[i - 1], l = s[i - 2]; - if (c == '*') { - f[i] += f[i - 1] * 9; - if (l == '*') { - f[i] += f[i - 2] * 15; - } else if (l == '1') { - f[i] += f[i - 2] * 9; - } else if (l == '2') { - f[i] += f[i - 2] * 6; - } - f[i] %= M; - } else if (c == '0') { - if (l == '1' || l == '2') - f[i] += f[i - 2]; - else if (l == '*') - f[i] += f[i - 2] * 2; - f[i] %= M; - } else { - f[i] += f[i - 1]; - if (l == '*') { - if (c <= '6') - f[i] += f[i - 2] * 2; - else - f[i] += f[i - 2]; - } else if (l == '1') - f[i] += f[i - 2]; - else if (l == '2' && c <= '6') - f[i] += f[i - 2]; - f[i] %= M; - } - } - - return f[s.size()] % M; - } -}; diff --git a/works/solutions/leetcode/cpp/641.cpp b/works/solutions/leetcode/cpp/641.cpp deleted file mode 100644 index 0235797..0000000 --- a/works/solutions/leetcode/cpp/641.cpp +++ /dev/null @@ -1,124 +0,0 @@ -class MyCircularDeque
-{
-private:
- int *data_;
- int *data_end_;
- int *front_;
- int *end_;
-
-public:
- /** Initialize your data structure here. Set the size of the deque to be k. */
- MyCircularDeque(int k)
- {
- data_ = new int[k];
- data_end_ = data_ + k - 1;
- front_ = nullptr;
- end_ = nullptr;
- }
-
- ~MyCircularDeque()
- {
- delete[] data_;
- }
-
- /** Adds an item at the front of Deque. Return true if the operation is successful. */
- bool insertFront(int value)
- {
- if (isFull())
- return false;
- if (front_ == nullptr)
- front_ = end_ = data_;
- else if (front_ == data_)
- front_ = data_end_;
- else
- front_ -= 1;
- *front_ = value;
- return true;
- }
-
- /** Adds an item at the rear of Deque. Return true if the operation is successful. */
- bool insertLast(int value)
- {
- if (isFull())
- return false;
- if (front_ == nullptr)
- front_ = end_ = data_;
- else if (end_ == data_end_)
- end_ = data_;
- else
- end_ += 1;
- *end_ = value;
- return true;
- }
-
- /** Deletes an item from the front of Deque. Return true if the operation is successful. */
- bool deleteFront()
- {
- if (isEmpty())
- return false;
- if (front_ == end_)
- front_ = end_ = nullptr;
- else if (front_ == data_end_)
- front_ = data_;
- else
- front_ += 1;
- return true;
- }
-
- /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
- bool deleteLast()
- {
- if (isEmpty())
- return false;
- if (front_ == end_)
- front_ = end_ = nullptr;
- else if (end_ == data_)
- end_ = data_end_;
- else
- end_ -= 1;
- return true;
- }
-
- /** Get the front item from the deque. */
- int getFront()
- {
- if (isEmpty())
- return -1;
- return *front_;
- }
-
- /** Get the last item from the deque. */
- int getRear()
- {
- if (isEmpty())
- return -1;
- return *end_;
- }
-
- /** Checks whether the circular deque is empty or not. */
- bool isEmpty()
- {
- return front_ == nullptr;
- }
-
- /** Checks whether the circular deque is full or not. */
- bool isFull()
- {
- if (front_ == nullptr)
- return false;
- return (front_ == data_ && end_ == data_end_) || (end_ + 1 == front_);
- }
-};
-
-/**
- * Your MyCircularDeque object will be instantiated and called as such:
- * MyCircularDeque* obj = new MyCircularDeque(k);
- * bool param_1 = obj->insertFront(value);
- * bool param_2 = obj->insertLast(value);
- * bool param_3 = obj->deleteFront();
- * bool param_4 = obj->deleteLast();
- * int param_5 = obj->getFront();
- * int param_6 = obj->getRear();
- * bool param_7 = obj->isEmpty();
- * bool param_8 = obj->isFull();
- */
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/649.cpp b/works/solutions/leetcode/cpp/649.cpp deleted file mode 100644 index ab702d2..0000000 --- a/works/solutions/leetcode/cpp/649.cpp +++ /dev/null @@ -1,67 +0,0 @@ -#include <string>
-
-using std::string;
-
-#include <queue>
-
-class Solution
-{
-public:
- string predictPartyVictory(string senate)
- {
- std::queue<bool> queue;
-
- int r_people = 0;
- int d_people = 0;
- int r_ban = 0;
- int d_ban = 0;
-
- for (auto i = senate.cbegin(); i != senate.cend(); ++i)
- {
- if (*i == 'R')
- {
- r_people += 1;
- queue.push(true);
- }
- else
- {
- d_people += 1;
- queue.push(false);
- }
- }
-
- while (r_people && d_people)
- {
- bool is_r = queue.front();
- queue.pop();
- if (is_r)
- {
- if (d_ban)
- {
- r_people -= 1;
- d_ban -= 1;
- }
- else
- {
- r_ban += 1;
- queue.push(is_r);
- }
- }
- else
- {
- if (r_ban)
- {
- d_people -= 1;
- r_ban -= 1;
- }
- else
- {
- d_ban += 1;
- queue.push(is_r);
- }
- }
- }
-
- return r_people ? "Radiant" : "Dire";
- }
-};
diff --git a/works/solutions/leetcode/cpp/66.cpp b/works/solutions/leetcode/cpp/66.cpp deleted file mode 100644 index 40ce008..0000000 --- a/works/solutions/leetcode/cpp/66.cpp +++ /dev/null @@ -1,34 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- vector<int> plusOne(vector<int> &digits)
- {
- bool carry = true;
- const auto end = digits.rend();
- for (auto iter = digits.rbegin(); carry && iter != end; ++iter)
- {
- auto &digit = *iter;
- digit += 1;
- if (digit == 10)
- {
- digit = 0;
- carry = true;
- }
- else
- {
- carry = false;
- }
- }
-
- if (carry)
- {
- digits.insert(digits.cbegin(), 1);
- }
-
- return digits;
- }
-};
diff --git a/works/solutions/leetcode/cpp/680.cpp b/works/solutions/leetcode/cpp/680.cpp deleted file mode 100644 index 21d150f..0000000 --- a/works/solutions/leetcode/cpp/680.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include <string>
-
-using std::string;
-
-bool strict_palindrome(string::const_iterator left, string::const_iterator right)
-{
- while (left < right)
- {
- if (*left != *right)
- return false;
- ++left;
- --right;
- }
- return true;
-}
-
-class Solution
-{
-public:
- bool validPalindrome(string s)
- {
- string::const_iterator left = s.cbegin();
- string::const_iterator right = s.cend() - 1;
-
- while (left < right)
- {
- if (*left != *right)
- return strict_palindrome(left, right - 1) || strict_palindrome(left + 1, right);
-
- ++left;
- --right;
- }
- return true;
- }
-};
diff --git a/works/solutions/leetcode/cpp/69.c b/works/solutions/leetcode/cpp/69.c deleted file mode 100644 index 9914fff..0000000 --- a/works/solutions/leetcode/cpp/69.c +++ /dev/null @@ -1,14 +0,0 @@ -int mySqrt(int x) {
- long long l = 0, r = x;
-
- while (l != r) {
- long long m = (l + r + 1) / 2;
- if (m * m <= x) {
- l = m;
- } else {
- r = m - 1;
- }
- }
-
- return l;
-}
diff --git a/works/solutions/leetcode/cpp/7.cpp b/works/solutions/leetcode/cpp/7.cpp deleted file mode 100644 index a1a05c1..0000000 --- a/works/solutions/leetcode/cpp/7.cpp +++ /dev/null @@ -1,18 +0,0 @@ -class Solution
-{
-public:
- int reverse(int x)
- {
- int result = 0;
- while (x != 0)
- {
- int digit = x % 10;
- x /= 10;
- if (__builtin_smul_overflow(result, 10, &result))
- return 0;
- if (__builtin_sadd_overflow(result, digit, &result))
- return 0;
- }
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/704.cpp b/works/solutions/leetcode/cpp/704.cpp deleted file mode 100644 index b56a01a..0000000 --- a/works/solutions/leetcode/cpp/704.cpp +++ /dev/null @@ -1,79 +0,0 @@ -#include <vector>
-#include <memory>
-
-class MyHashSet
-{
- static const int max = 100;
-
-private:
- std::unique_ptr<std::vector<int>> data_[max];
-
-public:
- /** Initialize your data structure here. */
- MyHashSet()
- {
- }
-
- void add(int key)
- {
- const auto index = key % max;
- auto &ptr = data_[index];
- if (ptr == nullptr)
- {
- ptr.reset(new std::vector<int>());
- }
-
- auto &v = *ptr;
- for (auto d : v)
- {
- if (d == key)
- return;
- }
-
- v.push_back(key);
- }
-
- void remove(int key)
- {
- const auto index = key % max;
- auto &ptr = data_[index];
- if (ptr == nullptr)
- return;
- auto &v = *ptr;
- const auto end = v.cend();
- for (auto iter = v.cbegin(); iter != end; ++iter)
- {
- if (*iter == key)
- {
- v.erase(iter);
- return;
- }
- }
- }
-
- /** Returns true if this set contains the specified element */
- bool contains(int key)
- {
- const auto index = key % max;
- auto &ptr = data_[index];
- if (ptr == nullptr)
- return false;
-
- const auto &v = *ptr;
- for (auto d : v)
- {
- if (d == key)
- return true;
- }
-
- return false;
- }
-};
-
-/**
- * Your MyHashSet object will be instantiated and called as such:
- * MyHashSet* obj = new MyHashSet();
- * obj->add(key);
- * obj->remove(key);
- * bool param_3 = obj->contains(key);
- */
diff --git a/works/solutions/leetcode/cpp/74.cpp b/works/solutions/leetcode/cpp/74.cpp deleted file mode 100644 index 08560ef..0000000 --- a/works/solutions/leetcode/cpp/74.cpp +++ /dev/null @@ -1,63 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- bool searchMatrix(vector<vector<int>> &matrix, int target)
- {
- if (matrix.empty() || matrix.front().empty())
- return false;
-
- int top_row = 0;
- int bottom_row = matrix.size() - 1;
- while (top_row != bottom_row)
- {
- const int middle_row = (top_row + bottom_row) / 2;
- const int middle_row_p1 = middle_row + 1;
- const int middle_p1_row_front = matrix[middle_row_p1].front();
- if (middle_p1_row_front > target)
- {
- bottom_row = middle_row;
- }
- else if (middle_p1_row_front < target)
- {
- top_row = middle_row_p1;
- }
- else if (middle_p1_row_front == target)
- {
- return true;
- }
- }
-
- const vector<int> &row = matrix[top_row];
-
- if (row.size() == 1)
- {
- return row.front() == target;
- }
-
- int left = 0;
- int right = row.size() - 1;
-
- while (left != right)
- {
- const int middle = (left + right) / 2;
- const int middle_value = row[middle];
- if (middle_value == target)
- {
- return true;
- }
- else if (middle_value < target)
- {
- left = middle + 1;
- }
- else
- {
- right = middle;
- }
- }
- return row[left] == target;
- }
-};
diff --git a/works/solutions/leetcode/cpp/746.cpp b/works/solutions/leetcode/cpp/746.cpp deleted file mode 100644 index 72ffd9f..0000000 --- a/works/solutions/leetcode/cpp/746.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-#include <algorithm>
-
-class Solution
-{
-public:
- int minCostClimbingStairs(vector<int> &cost)
- {
- int count = cost.size();
-
- // Total cost for index i means min cost of stepping through the number i stair,
- // after which you are free to jump two or one stair.
- // total_costs[i] is based on total_costs[i - 2] and total_costs[i - 1].
- // Note:
- // This is not min cost to step above the number i stair, which has no simple dependency
- // relationship because based on whether it steps through the last step there are two situation.
- // However with the restriction of stepping through that last stair, there is a
- // dependency relationship. And we can easily get the final result by comparing total_costs[count - 2]
- // and total_costs[count - 1]. But not just use total_costs[count - 1].
- vector<int> total_costs(count);
-
- total_costs[0] = cost[0];
- total_costs[1] = cost[1];
-
- for (int i = 2; i < count; i++)
- {
- total_costs[i] = std::min(total_costs[i - 2], total_costs[i - 1]) + cost[i];
- }
-
- return std::min(total_costs[count - 2], total_costs[count - 1]);
- }
-};
diff --git a/works/solutions/leetcode/cpp/766-2.cpp b/works/solutions/leetcode/cpp/766-2.cpp deleted file mode 100644 index 79a0cc8..0000000 --- a/works/solutions/leetcode/cpp/766-2.cpp +++ /dev/null @@ -1,20 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution {
-public:
- bool isToeplitzMatrix(vector<vector<int>> &matrix) {
- int row_count = matrix.size();
- int col_count = matrix.front().size();
-
- for (int i = 1; i < row_count; i++) {
- for (int j = 1; j < col_count; j++) {
- if (matrix[i][j] != matrix[i - 1][j - 1])
- return false;
- }
- }
-
- return true;
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/766.cpp b/works/solutions/leetcode/cpp/766.cpp deleted file mode 100644 index 3e8a015..0000000 --- a/works/solutions/leetcode/cpp/766.cpp +++ /dev/null @@ -1,44 +0,0 @@ -#include <algorithm>
-#include <vector>
-
-using std::vector;
-
-class Solution {
-public:
- bool isToeplitzMatrix(vector<vector<int>> &matrix) {
- int row_count = matrix.size();
- int col_count = matrix.front().size();
-
- if (matrix.size() == 1)
- return true;
- if (matrix.front().size() == 1)
- return true;
-
- // offset = col - row
- // max(offset) = row_count - 2
- // min(offset) = -(col_count - 2)
- for (int offset = -(col_count - 2); offset <= (row_count - 2); offset++) {
- int row, col;
- if (offset >= 0) {
- row = offset;
- col = 0;
- } else {
- row = 0;
- col = -offset;
- }
-
- int value = matrix[row][col];
- row++;
- col++;
-
- while (row < row_count && col < col_count) {
- if (matrix[row][col] != value) {
- return false;
- }
- row++;
- col++;
- }
- }
- return true;
- }
-};
diff --git a/works/solutions/leetcode/cpp/77.cpp b/works/solutions/leetcode/cpp/77.cpp deleted file mode 100644 index ec09198..0000000 --- a/works/solutions/leetcode/cpp/77.cpp +++ /dev/null @@ -1,45 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-void combine1(int start, int end, int rest_select_count, vector<int> &head, vector<vector<int>> &result)
-{
- if (rest_select_count == 0)
- {
- for (int i = start; i < end; i++)
- {
- head.push_back(i);
- result.push_back(head);
- head.pop_back();
- }
- return;
- }
-
- for (int i = start; i < end - rest_select_count; i++)
- {
- head.push_back(i);
- combine1(i + 1, end, rest_select_count - 1, head, result);
- head.pop_back();
- }
-}
-
-class Solution
-{
-public:
- vector<vector<int>> combine(int n, int k)
- {
- vector<vector<int>> result;
-
- vector<int> head;
- combine1(1, 1 + n, k - 1, head, result);
-
- return result;
- }
-};
-
-int main()
-{
- Solution s;
- auto result = s.combine(20, 16);
- return 0;
-}
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/832.cpp b/works/solutions/leetcode/cpp/832.cpp deleted file mode 100644 index 000fb94..0000000 --- a/works/solutions/leetcode/cpp/832.cpp +++ /dev/null @@ -1,20 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution {
-public:
- vector<vector<int>> flipAndInvertImage(vector<vector<int>> &A) {
- const int row_count = A.size();
- const int col_count = A.front().size();
- std::vector<std::vector<int>> result(row_count,
- std::vector<int>(col_count));
- for (int i = 0; i < row_count; i++) {
- for (int j = 0; j < col_count; j++) {
- result[i][j] = !A[i][col_count - j - 1];
- }
- }
-
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/86.cpp b/works/solutions/leetcode/cpp/86.cpp deleted file mode 100644 index 1f7568c..0000000 --- a/works/solutions/leetcode/cpp/86.cpp +++ /dev/null @@ -1,80 +0,0 @@ -/**
- * Definition for singly-linked list.
- * struct ListNode {
- * int val;
- * ListNode *next;
- * ListNode(int x) : val(x), next(NULL) {}
- * };
- */
-
-struct ListNode
-{
- int val;
- ListNode *next;
- ListNode(int x) : val(x), next(nullptr) {}
-};
-
-class Solution
-{
-public:
- ListNode *partition(ListNode *head, int x)
- {
- if (head == nullptr)
- return nullptr;
-
- if (head->next == nullptr)
- {
- return head;
- }
-
- ListNode less_list_head(0);
- ListNode greater_list_head(0);
-
- ListNode *less_list_tail = &less_list_head;
- ListNode *greater_list_tail = &greater_list_head;
-
- auto current_head = head;
- auto prev = head;
- auto current = head->next;
- bool less = head->val < x;
-
- while (current != nullptr)
- {
- const bool current_less = (current->val < x);
- if (less != current_less)
- {
- if (less)
- {
- less_list_tail->next = current_head;
- less_list_tail = prev;
- }
- else
- {
- greater_list_tail->next = current_head;
- greater_list_tail = prev;
- }
-
- less = current_less;
- current_head = current;
- }
- prev = current;
- current = current->next;
- }
-
- if (less)
- {
- less_list_tail->next = current_head;
- less_list_tail = prev;
- }
- else
- {
- greater_list_tail->next = current_head;
- greater_list_tail = prev;
- }
-
- less_list_tail->next = greater_list_head.next;
- greater_list_tail->next = nullptr;
-
- return less_list_head.next;
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/865.cpp b/works/solutions/leetcode/cpp/865.cpp deleted file mode 100644 index 8981a02..0000000 --- a/works/solutions/leetcode/cpp/865.cpp +++ /dev/null @@ -1,60 +0,0 @@ -struct TreeNode
-{
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode() : val(0), left(nullptr), right(nullptr) {}
- TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
-};
-
-#include <unordered_set>
-
-class Solution
-{
-public:
- int max_depth = -1;
- std::unordered_set<TreeNode *> deepest_nodes;
-
- void record_depth(TreeNode *root, int depth)
- {
- if (depth > max_depth)
- {
- max_depth = depth;
- deepest_nodes.clear();
- }
-
- if (depth == max_depth)
- deepest_nodes.insert(root);
-
- if (root->left != nullptr)
- record_depth(root->left, depth + 1);
- if (root->right != nullptr)
- record_depth(root->right, depth + 1);
- }
-
- TreeNode *find_common_ancestor(TreeNode *root)
- {
- if (root == nullptr)
- return nullptr;
- if (deepest_nodes.find(root) != deepest_nodes.cend())
- return root;
-
- auto left = find_common_ancestor(root->left);
- auto right = find_common_ancestor(root->right);
-
- if (left != nullptr && right != nullptr)
- return root;
- if (left != nullptr)
- return left;
- if (right != nullptr)
- return right;
- return nullptr;
- }
-
- TreeNode *subtreeWithAllDeepest(TreeNode *root)
- {
- record_depth(root, 0);
- return find_common_ancestor(root);
- }
-};
diff --git a/works/solutions/leetcode/cpp/867.cpp b/works/solutions/leetcode/cpp/867.cpp deleted file mode 100644 index 9efd176..0000000 --- a/works/solutions/leetcode/cpp/867.cpp +++ /dev/null @@ -1,20 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution {
-public:
- vector<vector<int>> transpose(vector<vector<int>> &matrix) {
- const int row_count = matrix.size();
- const int col_count = matrix.front().size();
-
- vector<vector<int>> result(col_count, std::vector<int>(row_count));
-
- for (int i = 0; i < row_count; i++)
- for (int j = 0; j < col_count; j++) {
- result[j][i] = matrix[i][j];
- }
-
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/896.cpp b/works/solutions/leetcode/cpp/896.cpp deleted file mode 100644 index 25bd528..0000000 --- a/works/solutions/leetcode/cpp/896.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-enum Order { Ascend, Descend, Unknown };
-
-class Solution {
-public:
- bool isMonotonic(vector<int> &A) {
- Order order = Unknown;
-
- int count = A.size();
- for (int i = 1; i < count; i++) {
- int last = A[i - 1];
- int current = A[i];
- if (order == Unknown) {
- if (current > last) {
- order = Ascend;
- } else if (current < last) {
- order = Descend;
- }
- } else if (order == Ascend) {
- if (last > current) {
- return false;
- }
- } else {
- if (last < current) {
- return false;
- }
- }
- }
-
- return true;
- }
-};
diff --git a/works/solutions/leetcode/cpp/897.cpp b/works/solutions/leetcode/cpp/897.cpp deleted file mode 100644 index efc9741..0000000 --- a/works/solutions/leetcode/cpp/897.cpp +++ /dev/null @@ -1,37 +0,0 @@ -/**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
- * };
- */
-class Solution {
-public:
- std::vector<TreeNode*> result;
-
- void InOrderTraverse(TreeNode* root) {
- if (root->left != nullptr)
- InOrderTraverse(root->left);
- result.push_back(root);
- if (root->right != nullptr)
- InOrderTraverse(root->right);
- }
-
- TreeNode* increasingBST(TreeNode* root) {
- InOrderTraverse(root);
-
- const auto end = result.end();
- auto iter1 = result.begin();
- auto iter2 = result.begin() + 1;
- for (; iter2 != end; ++iter1, ++iter2) {
- const auto node = *iter1;
- node->left = NULL;
- node->right = *iter2;
- }
- (*iter1)->left = (*iter1)->right = NULL;
-
- return result.front();
- }
-};
diff --git a/works/solutions/leetcode/cpp/917.cpp b/works/solutions/leetcode/cpp/917.cpp deleted file mode 100644 index d01d795..0000000 --- a/works/solutions/leetcode/cpp/917.cpp +++ /dev/null @@ -1,45 +0,0 @@ -#include <string>
-#include <cctype>
-#include <utility>
-
-using std::string;
-
-class Solution
-{
-public:
- string reverseOnlyLetters(string s)
- {
- if (s.empty())
- return s;
-
- auto front = s.rend();
- auto back = s.end();
-
- bool move_front = true;
- while (true)
- {
- if (move_front)
- {
- if (std::isalpha(*--front))
- {
- move_front = false;
- }
- }
- else
- {
- if (std::isalpha(*--back))
- {
- std::swap(*front, *back);
- move_front = true;
- }
- }
-
- if (front.base() == back)
- {
- break;
- }
- }
-
- return s;
- }
-};
diff --git a/works/solutions/leetcode/cpp/96.cpp b/works/solutions/leetcode/cpp/96.cpp deleted file mode 100644 index 3757baa..0000000 --- a/works/solutions/leetcode/cpp/96.cpp +++ /dev/null @@ -1,14 +0,0 @@ -class Solution {
-public:
- // catalan number:
- // f(n) = f(0) * f(n-1) + f(1) * f(n-2) + ... + f(n-1)*f(0)
- // f(n) = 2(2n-1) * f(n-1) / (n+1)
- // f(n) = C(2n, n) / (n+1)
- int numTrees(int n) {
- long long result = 1;
- for (int i = 2; i <= n; i++) {
- result = 2 * (2 * i - 1) * result / (i + 1);
- }
- return result;
- }
-};
diff --git a/works/solutions/leetcode/cpp/965.cpp b/works/solutions/leetcode/cpp/965.cpp deleted file mode 100644 index fd2bff6..0000000 --- a/works/solutions/leetcode/cpp/965.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <cstddef>
-
-struct TreeNode
-{
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode(int x) : val(x), left(NULL), right(NULL) {}
-};
-
-class Solution
-{
-public:
- static bool traverse(TreeNode *root, int val)
- {
- if (root == NULL)
- return true;
- if (root->val != val)
- return false;
- return traverse(root->left, root->val) && traverse(root->right, root->val);
- }
-
- bool isUnivalTree(TreeNode *root)
- {
- if (root == NULL)
- return true;
- return traverse(root, root->val);
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/968.cpp b/works/solutions/leetcode/cpp/968.cpp deleted file mode 100644 index c9e6b24..0000000 --- a/works/solutions/leetcode/cpp/968.cpp +++ /dev/null @@ -1,63 +0,0 @@ -#include <cstddef>
-
-struct TreeNode
-{
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode(int x) : val(x), left(NULL), right(NULL) {}
-};
-
-#include <algorithm>
-
-struct Result
-{
- // root_camera >= root_monitored >= root_not_monitored
- int root_camera;
- int root_monitored;
- int root_not_monitored;
-};
-
-class Solution
-{
-public:
- Result dfs(TreeNode *root)
- {
- if (root->left == nullptr && root->right == nullptr)
- {
- return Result{1, 1, 0};
- }
-
- if (root->left == nullptr || root->right == nullptr)
- {
- TreeNode *child_node = root->left == nullptr ? root->right : root->left;
- Result child = dfs(child_node);
-
- int root_camera = 1 + child.root_not_monitored;
- int root_monitored = std::min({child.root_camera,
- root_camera});
- int root_not_monitored = std::min(child.root_monitored, root_monitored);
-
- return Result{
- root_camera, root_monitored, root_not_monitored};
- }
-
- Result left = dfs(root->left);
- Result right = dfs(root->right);
-
- int root_camera = 1 + left.root_not_monitored + right.root_not_monitored;
- int root_monitored = std::min({left.root_camera + right.root_monitored,
- left.root_monitored + right.root_camera,
- root_camera});
- int root_not_monitored = std::min({left.root_monitored + right.root_monitored, root_monitored});
-
- return Result{
- root_camera, root_monitored, root_not_monitored};
- }
-
- int minCameraCover(TreeNode *root)
- {
- auto result = dfs(root);
- return result.root_monitored;
- }
-};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/976.cpp b/works/solutions/leetcode/cpp/976.cpp deleted file mode 100644 index e306047..0000000 --- a/works/solutions/leetcode/cpp/976.cpp +++ /dev/null @@ -1,23 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-#include <algorithm>
-#include <functional>
-
-class Solution
-{
-public:
- int largestPerimeter(vector<int> &A)
- {
- std::sort(A.begin(), A.end(), std::greater<int>{});
- for (int i = 0; i < A.size() - 2; i++)
- {
- if (A[i] < A[i + 1] + A[i + 2])
- {
- return A[i] + A[i + 1] + A[i + 2];
- }
- }
- return 0;
- }
-};
diff --git a/works/solutions/leetcode/cpp/98.cpp b/works/solutions/leetcode/cpp/98.cpp deleted file mode 100644 index 73cefa0..0000000 --- a/works/solutions/leetcode/cpp/98.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <cstddef> - -struct TreeNode -{ - int val; - TreeNode *left; - TreeNode *right; - TreeNode(int x) : val(x), left(NULL), right(NULL) {} -}; - -#include <limits> - -class Solution -{ -public: - bool dfs(TreeNode *node, long long min, long long max) - { - if (node == nullptr) - return true; - if (node->val <= min || node->val >= max) - return false; - return dfs(node->left, min, node->val) && dfs(node->right, node->val, max); - } - - bool isValidBST(TreeNode *root) - { - return dfs(root, std::numeric_limits<long long>::min(), std::numeric_limits<long long>::max()); - } -}; diff --git a/works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp b/works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp deleted file mode 100644 index dee81ec..0000000 --- a/works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp +++ /dev/null @@ -1,34 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-#include <algorithm>
-
-class Solution
-{
-public:
- int maxValue(vector<vector<int>> &grid)
- {
- int row_count = grid.size();
- int col_count = grid.front().size();
-
- for (int i = 1; i < row_count; i++)
- {
- grid[i][0] = grid[i - 1][0] + grid[i][0];
- }
-
- for (int j = 1; j < col_count; j++)
- {
- grid[0][j] = grid[0][j - 1] + grid[0][j];
- }
-
- for (int i = 1; i < row_count; i++)
- {
- for (int j = 1; j < col_count; j++)
- {
- grid[i][j] = std::max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
- }
- }
- return grid[row_count - 1][col_count - 1];
- }
-};
diff --git a/works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp b/works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp deleted file mode 100644 index 697182d..0000000 --- a/works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp +++ /dev/null @@ -1,46 +0,0 @@ -#include <cstddef>
-
-struct TreeNode
-{
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode(int x) : val(x), left(NULL), right(NULL) {}
-};
-
-#include <vector>
-
-class Solution
-{
-public:
- std::vector<int> current;
-
- int dfs(TreeNode *root, int sum)
- {
- if (root == nullptr)
- return 0;
-
- current.push_back(root->val);
-
- int s = 0;
- int count = 0;
-
- for (auto iter = current.crbegin(); iter != current.crend(); ++iter)
- {
- s += *iter;
- if (s == sum)
- count++;
- }
-
- count += dfs(root->left, sum) + dfs(root->right, sum);
-
- current.pop_back();
-
- return count;
- }
-
- int pathSum(TreeNode *root, int sum)
- {
- return dfs(root, sum);
- }
-};
diff --git a/works/solutions/leetcode/cpp/power-set-lcci.cpp b/works/solutions/leetcode/cpp/power-set-lcci.cpp deleted file mode 100644 index f502e7c..0000000 --- a/works/solutions/leetcode/cpp/power-set-lcci.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <vector> - -using std::vector; - -class Solution { -public: - void dfs(const vector<int> &nums, int index, int size, vector<int> ¤t, - vector<vector<int>> &result) { - if (index == size) { - result.push_back(current); - return; - } - - dfs(nums, index + 1, size, current, result); - - current.push_back(nums[index]); - dfs(nums, index + 1, size, current, result); - current.pop_back(); - } - - vector<vector<int>> subsets(vector<int> &nums) { - vector<int> current; - vector<vector<int>> result; - - dfs(nums, 0 , nums.size(), current, result); - - return result; - } -}; diff --git a/works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp b/works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp deleted file mode 100644 index 1cb3e01..0000000 --- a/works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <vector>
-
-using std::vector;
-
-class Solution
-{
-public:
- int missingNumber(vector<int> &nums)
- {
- if (nums.back() == nums.size() - 1)
- return nums.size();
-
- int low = 0, high = nums.size() - 1;
- while (low != high)
- {
- int middle = (low + high) / 2;
- if (middle == nums[middle])
- {
- low = middle + 1;
- }
- else
- {
- high = middle;
- }
- }
-
- return low;
- }
-};
diff --git a/works/solutions/leetcode/lccup/2021/1.cpp b/works/solutions/leetcode/lccup/2021/1.cpp deleted file mode 100644 index 550da04..0000000 --- a/works/solutions/leetcode/lccup/2021/1.cpp +++ /dev/null @@ -1,27 +0,0 @@ -struct TreeNode { - int val; - TreeNode *left; - TreeNode *right; - TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} -}; - -class Solution { -public: - int visited[1001] {0}; - int result = 0; - - void DFS(TreeNode* r) { - if (!visited[r->val]) { - result += 1; - visited[r->val] = 1; - } - - if (r->left) DFS(r->left); - if (r->right) DFS(r->right); - } - - int numColor(TreeNode* root) { - DFS(root); - return result; - } -};
\ No newline at end of file diff --git a/works/solutions/leetcode/rust/.gitignore b/works/solutions/leetcode/rust/.gitignore deleted file mode 100644 index 8accfa8..0000000 --- a/works/solutions/leetcode/rust/.gitignore +++ /dev/null @@ -1,5 +0,0 @@ -/target
-**/*.rs.bk
-Cargo.lock
-
-.vscode
diff --git a/works/solutions/leetcode/rust/Cargo.toml b/works/solutions/leetcode/rust/Cargo.toml deleted file mode 100644 index a87486e..0000000 --- a/works/solutions/leetcode/rust/Cargo.toml +++ /dev/null @@ -1,9 +0,0 @@ -[package]
-name = "crupest-leetcode"
-version = "0.1.0"
-authors = ["杨宇千 <crupest@outlook.com>"]
-edition = "2018"
-
-# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
-
-[dependencies]
diff --git a/works/solutions/leetcode/rust/src/add_two_numbers.rs b/works/solutions/leetcode/rust/src/add_two_numbers.rs deleted file mode 100644 index d2ca858..0000000 --- a/works/solutions/leetcode/rust/src/add_two_numbers.rs +++ /dev/null @@ -1,160 +0,0 @@ -use super::Solution;
-
-/******************** provided code ********************/
-#[derive(PartialEq, Eq, Clone, Debug)]
-pub struct ListNode {
- pub val: i32,
- pub next: Option<Box<ListNode>>,
-}
-
-impl ListNode {
- #[inline]
- fn new(val: i32) -> Self {
- ListNode { next: None, val }
- }
-}
-
-/******************** my code ********************/
-
-use std::ptr::NonNull;
-
-struct List {
- head: Option<Box<ListNode>>,
- tail: Option<NonNull<Box<ListNode>>>,
-}
-
-impl List {
- fn new() -> List {
- List {
- head: None,
- tail: None,
- }
- }
-
- fn append(&mut self, val: i32) {
- let node = Some(Box::new(ListNode::new(val)));
- unsafe {
- match self.tail {
- None => {
- self.head = node;
- self.tail = Some(NonNull::from(self.head.as_mut().unwrap()));
- }
- Some(mut t) => {
- let last_node = t.as_mut();
- last_node.next = node;
- self.tail = Some(NonNull::from(last_node.next.as_mut().unwrap()));
- }
- }
- }
- }
-
- fn to_result(self) -> Option<Box<ListNode>> {
- self.head
- }
-}
-
-impl Solution {
- pub fn add_two_numbers(
- l1: Option<Box<ListNode>>,
- l2: Option<Box<ListNode>>,
- ) -> Option<Box<ListNode>> {
- let mut l1 = l1;
- let mut l2 = l2;
- let mut result = List::new();
- let mut carry = false;
-
- loop {
- match l1 {
- None => {
- while let Some(v) = l2 {
- let digit = v.val + if carry { 1 } else { 0 };
- carry = digit > 9;
- let digit = digit % 10;
- result.append(digit);
- l2 = v.next;
- }
- break;
- }
- Some(v1) => match l2 {
- None => {
- let digit = v1.val + if carry { 1 } else { 0 };
- carry = digit > 9;
- let digit = digit % 10;
- result.append(digit);
- l1 = v1.next;
- while let Some(v) = l1 {
- let digit = v.val + if carry { 1 } else { 0 };
- carry = digit > 9;
- let digit = digit % 10;
- result.append(digit);
- l1 = v.next;
- }
- break;
- }
- Some(v2) => {
- let digit = v1.val + v2.val + if carry { 1 } else { 0 };
- carry = digit > 9;
- let digit = digit % 10;
- result.append(digit);
- l1 = v1.next;
- l2 = v2.next;
- }
- },
- }
- }
-
- if carry {
- result.append(1);
- }
-
- return result.to_result();
- }
-}
-
-#[cfg(test)]
-mod test {
- use super::{List, ListNode, Solution};
-
- trait IntoList {
- fn into_list(self) -> Option<Box<ListNode>>;
- }
-
- trait IntoVec {
- fn into_vec(self) -> Vec<i32>;
- }
-
- impl IntoList for Vec<i32> {
- fn into_list(self) -> Option<Box<ListNode>> {
- let mut list = List::new();
- for i in self {
- list.append(i);
- }
- list.to_result()
- }
- }
-
- impl IntoVec for Option<Box<ListNode>> {
- fn into_vec(self) -> Vec<i32> {
- let mut result = Vec::new();
- let mut node = self;
- while let Some(v) = node {
- result.push(v.val);
- node = v.next;
- }
- result
- }
- }
-
- #[test]
- fn test() {
- assert_eq!(
- Solution::add_two_numbers(vec![2, 4, 3].into_list(), vec![5, 6, 4].into_list())
- .into_vec(),
- vec![7, 0, 8]
- );
- assert_eq!(
- Solution::add_two_numbers(vec![9, 9, 9].into_list(), vec![1].into_list()).into_vec(),
- vec![0, 0, 0, 1]
- );
- }
-}
diff --git a/works/solutions/leetcode/rust/src/find_median_sorted_arrays.rs b/works/solutions/leetcode/rust/src/find_median_sorted_arrays.rs deleted file mode 100644 index bbc73f9..0000000 --- a/works/solutions/leetcode/rust/src/find_median_sorted_arrays.rs +++ /dev/null @@ -1,101 +0,0 @@ -use super::Solution;
-
-impl Solution {
- pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
- let (len_a, len_b) = (nums1.len(), nums2.len());
- let (a, len_a, b, len_b) = if len_a <= len_b {
- (nums1, len_a, nums2, len_b)
- } else {
- (nums2, len_b, nums1, len_a)
- };
- let index_sum = (a.len() + b.len() + 1) / 2;
- let (mut i_min, mut i_max) = (0, len_a);
-
- while i_min != i_max {
- let i = (i_min + i_max) / 2;
- let j = index_sum - i;
- if j != 0 && a[i] < b[j - 1] {
- i_min = i + 1;
- } else {
- i_max = i;
- }
- }
-
- let i = i_min;
- let j = index_sum - i;
-
- let mut v = vec![];
- if i != 0 {
- v.push(a[i - 1]);
- }
- if j != 0 {
- v.push(b[j - 1]);
- }
- if i != len_a {
- v.push(a[i]);
- }
- if j != len_b {
- v.push(b[j]);
- }
- v.sort_unstable();
-
- if (len_a + len_b) % 2 == 0 {
- match v.len() {
- 2 => (v[0] as f64 + v[1] as f64) / 2.0,
- 3 => {
- if i == 0 {
- (v[0] as f64 + v[1] as f64) / 2.0
- } else {
- (v[1] as f64 + v[2] as f64) / 2.0
- }
- }
- 4 => (v[1] as f64 + v[2] as f64) / 2.0,
- _ => panic!(),
- }
- } else {
- match v.len() {
- 1 | 2 => v[0] as f64,
- 3 => {
- if i == 0 {
- v[0] as f64
- } else {
- v[1] as f64
- }
- }
- 4 => v[1] as f64,
- _ => panic!(),
- }
- }
- }
-}
-
-#[cfg(test)]
-mod tests {
- use super::Solution;
-
- #[test]
- fn test() {
- assert_eq!(Solution::find_median_sorted_arrays(vec![3], vec![]), 3.0);
- assert_eq!(Solution::find_median_sorted_arrays(vec![3], vec![4]), 3.5);
- assert_eq!(
- Solution::find_median_sorted_arrays(vec![3, 4, 5], vec![1, 2, 6]),
- 3.5
- );
- assert_eq!(
- Solution::find_median_sorted_arrays(vec![3, 4], vec![1, 2, 6]),
- 3.0
- );
- assert_eq!(
- Solution::find_median_sorted_arrays(vec![1], vec![2, 3, 4]),
- 2.5
- );
- assert_eq!(
- Solution::find_median_sorted_arrays(vec![4], vec![1, 2, 3, 5]),
- 3.0
- );
- assert_eq!(
- Solution::find_median_sorted_arrays(vec![1, 2, 3], vec![4, 5, 6]),
- 3.5
- );
- }
-}
diff --git a/works/solutions/leetcode/rust/src/length_of_longest_substring.rs b/works/solutions/leetcode/rust/src/length_of_longest_substring.rs deleted file mode 100644 index cbd5e14..0000000 --- a/works/solutions/leetcode/rust/src/length_of_longest_substring.rs +++ /dev/null @@ -1,47 +0,0 @@ -use super::Solution;
-
-impl Solution {
- pub fn length_of_longest_substring(s: String) -> i32 {
- let mut map: [i32; std::u8::MAX as usize] = [-1; std::u8::MAX as usize];
- let mut last_index: i32 = 0;
- let mut result: i32 = 0;
- let bytes = s.as_bytes();
- for (i, c) in bytes.iter().enumerate() {
- let i = i as i32;
- let c = *c as usize;
- let li = map[c];
- if li >= last_index {
- last_index = li + 1;
- map[c] = i;
- } else {
- map[c] = i;
- let length = i - last_index + 1;
- if length > result {
- result = length;
- }
- }
- }
- result
- }
-}
-
-#[cfg(test)]
-mod tests {
- use super::Solution;
-
- #[test]
- fn test() {
- assert_eq!(
- Solution::length_of_longest_substring("abcabcbb".to_string()),
- 3
- );
- assert_eq!(
- Solution::length_of_longest_substring("bbbbb".to_string()),
- 1
- );
- assert_eq!(
- Solution::length_of_longest_substring("pwwkew".to_string()),
- 3
- );
- }
-}
diff --git a/works/solutions/leetcode/rust/src/lib.rs b/works/solutions/leetcode/rust/src/lib.rs deleted file mode 100644 index fc2e8b4..0000000 --- a/works/solutions/leetcode/rust/src/lib.rs +++ /dev/null @@ -1,7 +0,0 @@ -pub mod two_sum;
-pub mod add_two_numbers;
-pub mod length_of_longest_substring;
-pub mod find_median_sorted_arrays;
-pub mod longest_palindrome;
-
-pub struct Solution;
diff --git a/works/solutions/leetcode/rust/src/longest_palindrome.rs b/works/solutions/leetcode/rust/src/longest_palindrome.rs deleted file mode 100644 index 659ffe0..0000000 --- a/works/solutions/leetcode/rust/src/longest_palindrome.rs +++ /dev/null @@ -1,98 +0,0 @@ -use super::Solution;
-
-impl Solution {
- pub fn longest_palindrome(s: String) -> String {
- let bytes = s.as_bytes();
- let len = bytes.len();
-
- return match len {
- 0 => "".to_string(),
- 1 => s,
- _ => {
- let mut max_length = 1;
- let mut result = &bytes[0..1];
-
- for i in 1..len {
- let mut left_iter = bytes[..i].iter().enumerate().rev();
- let mut odd_right_iter = bytes.iter().enumerate().skip(i + 1);
- let mut even_right_iter = bytes.iter().enumerate().skip(i);
- let mut count_odd = true;
- let mut count_even = true;
- while count_odd || count_even {
- match left_iter.next() {
- Some((index_left, left)) => {
- if count_odd {
- match odd_right_iter.next() {
- Some((index_right, right)) => {
- if right == left {
- let length = index_right - index_left + 1;
- if length > max_length {
- max_length = length;
- result = &bytes[index_left..index_right + 1];
- }
- } else {
- count_odd = false;
- }
- }
- None => count_odd = false,
- }
- }
- if count_even {
- match even_right_iter.next() {
- Some((index_right, right)) => {
- if right == left {
- let length = index_right - index_left + 1;
- if length > max_length {
- max_length = length;
- result = &bytes[index_left..index_right + 1];
- }
- } else {
- count_even = false;
- }
- }
- None => count_even = false,
- }
- }
- }
- None => break,
- }
- }
- }
- String::from_utf8(Vec::from(result)).unwrap()
- }
- };
- }
-}
-
-#[cfg(test)]
-mod tests {
- use super::Solution;
-
- #[test]
- fn test() {
- assert_eq!(
- Solution::longest_palindrome("bb".to_string()),
- "bb".to_string()
- );
- assert_eq!(
- Solution::longest_palindrome("abb".to_string()),
- "bb".to_string()
- );
- assert_eq!(
- Solution::longest_palindrome("abbc".to_string()),
- "bb".to_string()
- );
- assert_eq!(
- Solution::longest_palindrome("abccb".to_string()),
- "bccb".to_string()
- );
- assert_eq!(
- Solution::longest_palindrome("abcdcbd".to_string()),
- "bcdcb".to_string()
- );
- assert_eq!(
- Solution::longest_palindrome("aaaabaaa".to_string()),
- "aaabaaa".to_string()
- );
- }
-}
diff --git a/works/solutions/leetcode/rust/src/two_sum.rs b/works/solutions/leetcode/rust/src/two_sum.rs deleted file mode 100644 index 9f400aa..0000000 --- a/works/solutions/leetcode/rust/src/two_sum.rs +++ /dev/null @@ -1,24 +0,0 @@ -use super::Solution;
-
-impl Solution {
- pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
- for (i, v1) in nums.iter().enumerate() {
- for (j, v2) in nums.iter().enumerate().skip(i + 1) {
- if v1 + v2 == target {
- return vec![i as i32, j as i32];
- }
- }
- }
- panic!();
- }
-}
-
-#[cfg(test)]
-mod tests {
- use super::Solution;
-
- #[test]
- pub fn test() {
- assert_eq!(Solution::two_sum(vec![2, 7, 11, 15], 9), vec![0, 1])
- }
-}
\ No newline at end of file diff --git a/works/solutions/leetcode/week/260/1.cpp b/works/solutions/leetcode/week/260/1.cpp deleted file mode 100644 index 4d6c78d..0000000 --- a/works/solutions/leetcode/week/260/1.cpp +++ /dev/null @@ -1,21 +0,0 @@ -#include <vector> - -using std::vector; - -class Solution { -public: - int maximumDifference(vector<int>& nums) { - int result = -1; - - for (int i = 1; i < nums.size(); i++) { - for (int j = 0; j < i; j++) { - int diff = nums[i] - nums[j]; - if (diff > result) { - result = diff; - } - } - } - - return result == 0 ? -1 : result; - } -};
\ No newline at end of file diff --git a/works/solutions/leetcode/week/260/2.cpp b/works/solutions/leetcode/week/260/2.cpp deleted file mode 100644 index 86c4cf2..0000000 --- a/works/solutions/leetcode/week/260/2.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <vector> - -using std::vector; - -#include <iterator> -#include <limits> -#include <numeric> - -class Solution { -public: - long long gridGame(vector<vector<int>> &grid) { - int s = grid.front().size(); - std::vector<long long> row0(grid[0].cbegin(), grid[0].cend()); - std::vector<long long> row1(grid[1].cbegin(), grid[1].cend()); - std::vector<long long> ps0, ps1; - - std::partial_sum(row0.cbegin(), row0.cend(), std::back_inserter(ps0)); - std::partial_sum(row1.cbegin(), row1.cend(), std::back_inserter(ps1)); - - long long r = std::numeric_limits<long long>::max(); - - for (int i = 0; i < s; i++) { - long long c = std::max(ps0.back() - ps0[i], i ? ps1[i - 1] : 0); - r = std::min(r, c); - } - - return r; - } -};
\ No newline at end of file |