From dc1f0c4c0096013799416664894c5194dc7e1f52 Mon Sep 17 00:00:00 2001 From: Yuqian Yang Date: Fri, 28 Feb 2025 23:13:39 +0800 Subject: chore(store): move everything to store. --- works/solutions/leetcode/cpp/.gitignore | 3 - works/solutions/leetcode/cpp/10.cpp | 83 -------------- works/solutions/leetcode/cpp/100.cpp | 29 ----- works/solutions/leetcode/cpp/101.cpp | 43 ------- works/solutions/leetcode/cpp/1025.cpp | 8 -- works/solutions/leetcode/cpp/1051.cpp | 33 ------ works/solutions/leetcode/cpp/1052.cpp | 47 -------- works/solutions/leetcode/cpp/11.cpp | 42 ------- works/solutions/leetcode/cpp/1144.cpp | 48 -------- works/solutions/leetcode/cpp/12.cpp | 51 --------- works/solutions/leetcode/cpp/121.cpp | 24 ---- works/solutions/leetcode/cpp/1219.cpp | 64 ----------- works/solutions/leetcode/cpp/122.cpp | 28 ----- works/solutions/leetcode/cpp/123.cpp | 34 ------ works/solutions/leetcode/cpp/1286.cpp | 56 ---------- works/solutions/leetcode/cpp/13.cpp | 54 --------- works/solutions/leetcode/cpp/1343.cpp | 40 ------- works/solutions/leetcode/cpp/1347.cpp | 35 ------ works/solutions/leetcode/cpp/1370.cpp | 45 -------- works/solutions/leetcode/cpp/14.cpp | 35 ------ works/solutions/leetcode/cpp/147.cpp | 56 ---------- works/solutions/leetcode/cpp/1470.cpp | 23 ---- works/solutions/leetcode/cpp/15.cpp | 44 -------- works/solutions/leetcode/cpp/155-2.cpp | 48 -------- works/solutions/leetcode/cpp/155.cpp | 38 ------- works/solutions/leetcode/cpp/1609.cpp | 94 ---------------- works/solutions/leetcode/cpp/167.cpp | 28 ----- works/solutions/leetcode/cpp/17.04.cpp | 21 ---- works/solutions/leetcode/cpp/17.cpp | 56 ---------- works/solutions/leetcode/cpp/198.cpp | 26 ----- works/solutions/leetcode/cpp/2.cpp | 75 ------------- works/solutions/leetcode/cpp/20.cpp | 55 --------- works/solutions/leetcode/cpp/203.cpp | 48 -------- works/solutions/leetcode/cpp/213.cpp | 41 ------- works/solutions/leetcode/cpp/22.cpp | 40 ------- works/solutions/leetcode/cpp/231.cpp | 10 -- works/solutions/leetcode/cpp/26.cpp | 37 ------ works/solutions/leetcode/cpp/260-2.cpp | 26 ----- works/solutions/leetcode/cpp/260.cpp | 23 ---- works/solutions/leetcode/cpp/299.cpp | 44 -------- works/solutions/leetcode/cpp/303.cpp | 26 ----- works/solutions/leetcode/cpp/304.cpp | 35 ------ works/solutions/leetcode/cpp/328.cpp | 51 --------- works/solutions/leetcode/cpp/337.cpp | 38 ------- works/solutions/leetcode/cpp/338.cpp | 26 ----- works/solutions/leetcode/cpp/343.cpp | 23 ---- works/solutions/leetcode/cpp/35.cpp | 36 ------ works/solutions/leetcode/cpp/371.cpp | 25 ----- works/solutions/leetcode/cpp/395.cpp | 56 ---------- works/solutions/leetcode/cpp/397.cpp | 47 -------- works/solutions/leetcode/cpp/401.cpp | 57 ---------- works/solutions/leetcode/cpp/46.cpp | 34 ------ works/solutions/leetcode/cpp/47.cpp | 45 -------- works/solutions/leetcode/cpp/495.cpp | 37 ------ works/solutions/leetcode/cpp/5.cpp | 104 ----------------- works/solutions/leetcode/cpp/501.cpp | 58 ---------- works/solutions/leetcode/cpp/526.cpp | 29 ----- works/solutions/leetcode/cpp/543.cpp | 32 ------ works/solutions/leetcode/cpp/55.cpp | 29 ----- works/solutions/leetcode/cpp/6.cpp | 56 ---------- works/solutions/leetcode/cpp/60.cpp | 44 -------- works/solutions/leetcode/cpp/62.cpp | 25 ----- works/solutions/leetcode/cpp/63.cpp | 44 -------- works/solutions/leetcode/cpp/639.cpp | 56 ---------- works/solutions/leetcode/cpp/641.cpp | 124 --------------------- works/solutions/leetcode/cpp/649.cpp | 67 ----------- works/solutions/leetcode/cpp/66.cpp | 34 ------ works/solutions/leetcode/cpp/680.cpp | 35 ------ works/solutions/leetcode/cpp/69.c | 14 --- works/solutions/leetcode/cpp/7.cpp | 18 --- works/solutions/leetcode/cpp/704.cpp | 79 ------------- works/solutions/leetcode/cpp/74.cpp | 63 ----------- works/solutions/leetcode/cpp/746.cpp | 35 ------ works/solutions/leetcode/cpp/766-2.cpp | 20 ---- works/solutions/leetcode/cpp/766.cpp | 44 -------- works/solutions/leetcode/cpp/77.cpp | 45 -------- works/solutions/leetcode/cpp/832.cpp | 20 ---- works/solutions/leetcode/cpp/86.cpp | 80 ------------- works/solutions/leetcode/cpp/865.cpp | 60 ---------- works/solutions/leetcode/cpp/867.cpp | 20 ---- works/solutions/leetcode/cpp/896.cpp | 35 ------ works/solutions/leetcode/cpp/897.cpp | 37 ------ works/solutions/leetcode/cpp/917.cpp | 45 -------- works/solutions/leetcode/cpp/96.cpp | 14 --- works/solutions/leetcode/cpp/965.cpp | 29 ----- works/solutions/leetcode/cpp/968.cpp | 63 ----------- works/solutions/leetcode/cpp/976.cpp | 23 ---- works/solutions/leetcode/cpp/98.cpp | 29 ----- .../leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp | 34 ------ .../leetcode/cpp/paths-with-sums-lcci.cpp | 46 -------- works/solutions/leetcode/cpp/power-set-lcci.cpp | 29 ----- .../leetcode/cpp/que-shi-de-shu-zi-lcof.cpp | 29 ----- 92 files changed, 3819 deletions(-) delete mode 100644 works/solutions/leetcode/cpp/.gitignore delete mode 100644 works/solutions/leetcode/cpp/10.cpp delete mode 100644 works/solutions/leetcode/cpp/100.cpp delete mode 100644 works/solutions/leetcode/cpp/101.cpp delete mode 100644 works/solutions/leetcode/cpp/1025.cpp delete mode 100644 works/solutions/leetcode/cpp/1051.cpp delete mode 100644 works/solutions/leetcode/cpp/1052.cpp delete mode 100644 works/solutions/leetcode/cpp/11.cpp delete mode 100644 works/solutions/leetcode/cpp/1144.cpp delete mode 100644 works/solutions/leetcode/cpp/12.cpp delete mode 100644 works/solutions/leetcode/cpp/121.cpp delete mode 100644 works/solutions/leetcode/cpp/1219.cpp delete mode 100644 works/solutions/leetcode/cpp/122.cpp delete mode 100644 works/solutions/leetcode/cpp/123.cpp delete mode 100644 works/solutions/leetcode/cpp/1286.cpp delete mode 100644 works/solutions/leetcode/cpp/13.cpp delete mode 100644 works/solutions/leetcode/cpp/1343.cpp delete mode 100644 works/solutions/leetcode/cpp/1347.cpp delete mode 100644 works/solutions/leetcode/cpp/1370.cpp delete mode 100644 works/solutions/leetcode/cpp/14.cpp delete mode 100644 works/solutions/leetcode/cpp/147.cpp delete mode 100644 works/solutions/leetcode/cpp/1470.cpp delete mode 100644 works/solutions/leetcode/cpp/15.cpp delete mode 100644 works/solutions/leetcode/cpp/155-2.cpp delete mode 100644 works/solutions/leetcode/cpp/155.cpp delete mode 100644 works/solutions/leetcode/cpp/1609.cpp delete mode 100644 works/solutions/leetcode/cpp/167.cpp delete mode 100644 works/solutions/leetcode/cpp/17.04.cpp delete mode 100644 works/solutions/leetcode/cpp/17.cpp delete mode 100644 works/solutions/leetcode/cpp/198.cpp delete mode 100644 works/solutions/leetcode/cpp/2.cpp delete mode 100644 works/solutions/leetcode/cpp/20.cpp delete mode 100644 works/solutions/leetcode/cpp/203.cpp delete mode 100644 works/solutions/leetcode/cpp/213.cpp delete mode 100644 works/solutions/leetcode/cpp/22.cpp delete mode 100644 works/solutions/leetcode/cpp/231.cpp delete mode 100644 works/solutions/leetcode/cpp/26.cpp delete mode 100644 works/solutions/leetcode/cpp/260-2.cpp delete mode 100644 works/solutions/leetcode/cpp/260.cpp delete mode 100644 works/solutions/leetcode/cpp/299.cpp delete mode 100644 works/solutions/leetcode/cpp/303.cpp delete mode 100644 works/solutions/leetcode/cpp/304.cpp delete mode 100644 works/solutions/leetcode/cpp/328.cpp delete mode 100644 works/solutions/leetcode/cpp/337.cpp delete mode 100644 works/solutions/leetcode/cpp/338.cpp delete mode 100644 works/solutions/leetcode/cpp/343.cpp delete mode 100644 works/solutions/leetcode/cpp/35.cpp delete mode 100644 works/solutions/leetcode/cpp/371.cpp delete mode 100644 works/solutions/leetcode/cpp/395.cpp delete mode 100644 works/solutions/leetcode/cpp/397.cpp delete mode 100644 works/solutions/leetcode/cpp/401.cpp delete mode 100644 works/solutions/leetcode/cpp/46.cpp delete mode 100644 works/solutions/leetcode/cpp/47.cpp delete mode 100644 works/solutions/leetcode/cpp/495.cpp delete mode 100644 works/solutions/leetcode/cpp/5.cpp delete mode 100644 works/solutions/leetcode/cpp/501.cpp delete mode 100644 works/solutions/leetcode/cpp/526.cpp delete mode 100644 works/solutions/leetcode/cpp/543.cpp delete mode 100644 works/solutions/leetcode/cpp/55.cpp delete mode 100644 works/solutions/leetcode/cpp/6.cpp delete mode 100644 works/solutions/leetcode/cpp/60.cpp delete mode 100644 works/solutions/leetcode/cpp/62.cpp delete mode 100644 works/solutions/leetcode/cpp/63.cpp delete mode 100644 works/solutions/leetcode/cpp/639.cpp delete mode 100644 works/solutions/leetcode/cpp/641.cpp delete mode 100644 works/solutions/leetcode/cpp/649.cpp delete mode 100644 works/solutions/leetcode/cpp/66.cpp delete mode 100644 works/solutions/leetcode/cpp/680.cpp delete mode 100644 works/solutions/leetcode/cpp/69.c delete mode 100644 works/solutions/leetcode/cpp/7.cpp delete mode 100644 works/solutions/leetcode/cpp/704.cpp delete mode 100644 works/solutions/leetcode/cpp/74.cpp delete mode 100644 works/solutions/leetcode/cpp/746.cpp delete mode 100644 works/solutions/leetcode/cpp/766-2.cpp delete mode 100644 works/solutions/leetcode/cpp/766.cpp delete mode 100644 works/solutions/leetcode/cpp/77.cpp delete mode 100644 works/solutions/leetcode/cpp/832.cpp delete mode 100644 works/solutions/leetcode/cpp/86.cpp delete mode 100644 works/solutions/leetcode/cpp/865.cpp delete mode 100644 works/solutions/leetcode/cpp/867.cpp delete mode 100644 works/solutions/leetcode/cpp/896.cpp delete mode 100644 works/solutions/leetcode/cpp/897.cpp delete mode 100644 works/solutions/leetcode/cpp/917.cpp delete mode 100644 works/solutions/leetcode/cpp/96.cpp delete mode 100644 works/solutions/leetcode/cpp/965.cpp delete mode 100644 works/solutions/leetcode/cpp/968.cpp delete mode 100644 works/solutions/leetcode/cpp/976.cpp delete mode 100644 works/solutions/leetcode/cpp/98.cpp delete mode 100644 works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp delete mode 100644 works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp delete mode 100644 works/solutions/leetcode/cpp/power-set-lcci.cpp delete mode 100644 works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp (limited to 'works/solutions/leetcode/cpp') 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 -#include -#include - -using std::string; - -struct Token { - explicit Token(char c) : c(c), isAsterisk(false) {} - - char c; - bool isAsterisk; -}; - -class Solution { -public: - std::vector tokens_; - std::string s_; - std::unordered_map> 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 - -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 - -using std::vector; - -class Solution -{ -public: - int heightChecker(vector &heights) - { - vector 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 -// #include -#include - -using std::vector; - -class Solution { -public: - int maxSatisfied(vector &customers, vector &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 -#include - -using std::vector; - -class Solution -{ -public: - int maxArea(vector &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 - -using std::vector; - -inline int min(int a, int b) -{ - return a < b ? a : b; -} - -class Solution -{ -public: - int movesToMakeZigzag(vector &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 - -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 - -using std::vector; - -class Solution -{ -public: - int maxProfit(vector &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 - -using std::vector; - -class Solution -{ -public: - static void dfs(const vector> &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> &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 - -using std::vector; - -class Solution -{ -public: - int maxProfit(vector &prices) - { - if (prices.size() <= 1) - return 0; - - int day_count = prices.size(); - - vector> dp(day_count, std::vector(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 -#include -using std::vector; - -#include - -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 &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 - -using std::string; - -#include - -class CombinationIterator { -public: - string chars; - int char_length; - int combinationLength; - bool has_next = true; - std::vector 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 - -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 - -using std::vector; - -class Solution -{ -public: - int numOfSubarrays(vector &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 - -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 - -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 -#include - -using std::string; -using std::vector; - -class Solution -{ -public: - string longestCommonPrefix(vector &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 - -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 - -using std::vector; - -class Solution -{ -public: - vector shuffle(vector &nums, int n) - { - vector 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 -#include - -using std::vector; - -#include -#include -#include -#include - -bool operator<(const std::vector &l, std::vector &r) { - return std::lexicographical_compare(l.cbegin(), l.cend(), r.cbegin(), - r.cend()); -} - -class Solution { -public: - int ha[100010]{0}; - - vector> threeSum(vector &nums) { - std::set> result; - - if (nums.size() < 3) - return {}; - - std::unordered_map 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>(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 -#include - -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 data_; - std::vector 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 -#include - -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 data_; - std::multiset 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 - -class Solution -{ -public: - bool isEvenOddTree(TreeNode *root) - { - if (root == nullptr) - return true; - std::queue odd_level; - std::queue 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 - -using std::vector; - -class Solution -{ -public: - vector twoSum(vector &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 - -using std::vector; - -class Solution -{ -public: - int missingNumber(vector &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 -#include - -using std::string; -using std::vector; - -vector 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 &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 letterCombinations(string digits) - { - std::vector 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 - -using std::vector; - -class Solution -{ -public: - int rob(vector &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 - -using std::string; - -#include - -class Solution -{ -public: - inline static char get_companion(char c) - { - switch (c) - { - case ')': - return '('; - case ']': - return '['; - default: - return '{'; - } - } - - bool isValid(string s) - { - std::stack 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 - -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 - -using std::vector; - -class Solution -{ -public: - int rob(vector &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 -#include - -using std::string; -using std::vector; - -class Solution -{ -public: - static void backtrack(vector &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 generateParenthesis(int n) - { - vector 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 - -class Solution { -public: - bool isPowerOfTwo(int n) { - if (n <= 0) return false; - std::bitset 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 - -using std::vector; - -class Solution -{ -public: - int removeDuplicates(vector &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 - -using std::vector; - -class Solution -{ -public: - vector singleNumber(vector &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 -#include - -using std::vector; - -class Solution -{ -public: - vector singleNumber(vector &nums) - { - std::unordered_set s; - for (auto i : nums) - { - const auto result = s.find(i); - if (result == s.cend()) - s.insert(i); - else - s.erase(result); - } - - return vector(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 - -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 - -using std::vector; - -class NumArray -{ -private: - vector prefix_sums; - -public: - NumArray(vector &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 - -using std::vector; - -class NumMatrix { -private: - std::vector> prefix_sum_; - -public: - NumMatrix(vector> &matrix) - : prefix_sum_( - matrix.size() + 1, - std::vector(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 - -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 - -using std::vector; - -class Solution -{ -public: - vector countBits(int num) - { - vector 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 - -class Solution -{ -public: - int integerBreak(int n) - { - if (n == 2) - return 1; - if (n == 3) - return 2; - - if (n % 3 == 1) - { - return static_cast(std::pow(3, n / 3 - 1)) * 4; - } - else if (n % 3 == 2) - { - return static_cast(std::pow(3, n / 3)) * 2; - } - return static_cast(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 - -using std::vector; - -class Solution -{ -public: - int searchInsert(vector &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(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 -#include - -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 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 -#include -#include - -using std::string; -using std::vector; - -const std::array hour_digits{1, 2, 4, 8}; -const std::array minute_digits{1, 2, 4, 8, 16, 32}; - -class Solution { -public: - template - void dfs(const std::array &digits, int total_count, int rest_count, - int start_index, int value, std::vector &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(digits, total_count, rest_count - 1, i + 1, - value + digits[i], result); - } - } - - vector readBinaryWatch(int num) { - vector results; - - for (int i = (num > 6 ? num - 6 : 0); i <= (num > 4 ? 4 : num); i++) { - std::vector hours; - std::vector 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 - -using std::vector; - -class Solution { -public: - void dfs(const vector &nums, vector ¤t, bool *num_used, - vector> &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> permute(vector &nums) { - vector current; - vector> 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 -#include - -using std::vector; - -class Solution { -public: - - void DFS(int length, const std::vector& nums, std::vector& visited, std::vector& current, std::vector>& 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> permuteUnique(vector& nums) { - std::vector visited(nums.size()); - std::vector current; - std::vector> 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 - -using std::vector; - -class Solution -{ -public: - int findPoisonedDuration(vector &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 - -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 -#include - -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 &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 findMode(TreeNode *root) - { - if (root == nullptr) - return {}; - int last = 0, count = 0, max_count = 0; - vector 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 - -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 - -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 - -using std::vector; - -#include - -class Solution -{ -public: - bool canJump(vector &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 -#include - -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 -#include - -using std::string; - -class Solution -{ -public: - string getPermutation(int n, int k) - { - k--; - - string result; - result.reserve(n); - - std::vector 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 - -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 - -using std::vector; - -class Solution -{ -public: - int uniquePathsWithObstacles(vector> &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 - -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 - -using std::string; - -#include - -class Solution -{ -public: - string predictPartyVictory(string senate) - { - std::queue 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 - -using std::vector; - -class Solution -{ -public: - vector plusOne(vector &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 - -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 -#include - -class MyHashSet -{ - static const int max = 100; - -private: - std::unique_ptr> 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()); - } - - 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 - -using std::vector; - -class Solution -{ -public: - bool searchMatrix(vector> &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 &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 - -using std::vector; - -#include - -class Solution -{ -public: - int minCostClimbingStairs(vector &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 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 - -using std::vector; - -class Solution { -public: - bool isToeplitzMatrix(vector> &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 -#include - -using std::vector; - -class Solution { -public: - bool isToeplitzMatrix(vector> &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 - -using std::vector; - -void combine1(int start, int end, int rest_select_count, vector &head, vector> &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> combine(int n, int k) - { - vector> result; - - vector 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 - -using std::vector; - -class Solution { -public: - vector> flipAndInvertImage(vector> &A) { - const int row_count = A.size(); - const int col_count = A.front().size(); - std::vector> result(row_count, - std::vector(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 - -class Solution -{ -public: - int max_depth = -1; - std::unordered_set 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 - -using std::vector; - -class Solution { -public: - vector> transpose(vector> &matrix) { - const int row_count = matrix.size(); - const int col_count = matrix.front().size(); - - vector> result(col_count, std::vector(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 - -using std::vector; - -enum Order { Ascend, Descend, Unknown }; - -class Solution { -public: - bool isMonotonic(vector &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 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 -#include -#include - -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 - -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 - -struct TreeNode -{ - int val; - TreeNode *left; - TreeNode *right; - TreeNode(int x) : val(x), left(NULL), right(NULL) {} -}; - -#include - -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 - -using std::vector; - -#include -#include - -class Solution -{ -public: - int largestPerimeter(vector &A) - { - std::sort(A.begin(), A.end(), std::greater{}); - 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 - -struct TreeNode -{ - int val; - TreeNode *left; - TreeNode *right; - TreeNode(int x) : val(x), left(NULL), right(NULL) {} -}; - -#include - -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::min(), std::numeric_limits::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 - -using std::vector; - -#include - -class Solution -{ -public: - int maxValue(vector> &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 - -struct TreeNode -{ - int val; - TreeNode *left; - TreeNode *right; - TreeNode(int x) : val(x), left(NULL), right(NULL) {} -}; - -#include - -class Solution -{ -public: - std::vector 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 - -using std::vector; - -class Solution { -public: - void dfs(const vector &nums, int index, int size, vector ¤t, - vector> &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> subsets(vector &nums) { - vector current; - vector> 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 - -using std::vector; - -class Solution -{ -public: - int missingNumber(vector &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; - } -}; -- cgit v1.2.3