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. --- store/works/solutions/leetcode/cpp/.gitignore | 3 + store/works/solutions/leetcode/cpp/10.cpp | 83 ++++++++++++++ store/works/solutions/leetcode/cpp/100.cpp | 29 +++++ store/works/solutions/leetcode/cpp/101.cpp | 43 +++++++ store/works/solutions/leetcode/cpp/1025.cpp | 8 ++ store/works/solutions/leetcode/cpp/1051.cpp | 33 ++++++ store/works/solutions/leetcode/cpp/1052.cpp | 47 ++++++++ store/works/solutions/leetcode/cpp/11.cpp | 42 +++++++ store/works/solutions/leetcode/cpp/1144.cpp | 48 ++++++++ store/works/solutions/leetcode/cpp/12.cpp | 51 +++++++++ store/works/solutions/leetcode/cpp/121.cpp | 24 ++++ store/works/solutions/leetcode/cpp/1219.cpp | 64 +++++++++++ store/works/solutions/leetcode/cpp/122.cpp | 28 +++++ store/works/solutions/leetcode/cpp/123.cpp | 34 ++++++ store/works/solutions/leetcode/cpp/1286.cpp | 56 ++++++++++ store/works/solutions/leetcode/cpp/13.cpp | 54 +++++++++ store/works/solutions/leetcode/cpp/1343.cpp | 40 +++++++ store/works/solutions/leetcode/cpp/1347.cpp | 35 ++++++ store/works/solutions/leetcode/cpp/1370.cpp | 45 ++++++++ store/works/solutions/leetcode/cpp/14.cpp | 35 ++++++ store/works/solutions/leetcode/cpp/147.cpp | 56 ++++++++++ store/works/solutions/leetcode/cpp/1470.cpp | 23 ++++ store/works/solutions/leetcode/cpp/15.cpp | 44 ++++++++ store/works/solutions/leetcode/cpp/155-2.cpp | 48 ++++++++ store/works/solutions/leetcode/cpp/155.cpp | 38 +++++++ store/works/solutions/leetcode/cpp/1609.cpp | 94 ++++++++++++++++ store/works/solutions/leetcode/cpp/167.cpp | 28 +++++ store/works/solutions/leetcode/cpp/17.04.cpp | 21 ++++ store/works/solutions/leetcode/cpp/17.cpp | 56 ++++++++++ store/works/solutions/leetcode/cpp/198.cpp | 26 +++++ store/works/solutions/leetcode/cpp/2.cpp | 75 +++++++++++++ store/works/solutions/leetcode/cpp/20.cpp | 55 +++++++++ store/works/solutions/leetcode/cpp/203.cpp | 48 ++++++++ store/works/solutions/leetcode/cpp/213.cpp | 41 +++++++ store/works/solutions/leetcode/cpp/22.cpp | 40 +++++++ store/works/solutions/leetcode/cpp/231.cpp | 10 ++ store/works/solutions/leetcode/cpp/26.cpp | 37 ++++++ store/works/solutions/leetcode/cpp/260-2.cpp | 26 +++++ store/works/solutions/leetcode/cpp/260.cpp | 23 ++++ store/works/solutions/leetcode/cpp/299.cpp | 44 ++++++++ store/works/solutions/leetcode/cpp/303.cpp | 26 +++++ store/works/solutions/leetcode/cpp/304.cpp | 35 ++++++ store/works/solutions/leetcode/cpp/328.cpp | 51 +++++++++ store/works/solutions/leetcode/cpp/337.cpp | 38 +++++++ store/works/solutions/leetcode/cpp/338.cpp | 26 +++++ store/works/solutions/leetcode/cpp/343.cpp | 23 ++++ store/works/solutions/leetcode/cpp/35.cpp | 36 ++++++ store/works/solutions/leetcode/cpp/371.cpp | 25 +++++ store/works/solutions/leetcode/cpp/395.cpp | 56 ++++++++++ store/works/solutions/leetcode/cpp/397.cpp | 47 ++++++++ store/works/solutions/leetcode/cpp/401.cpp | 57 ++++++++++ store/works/solutions/leetcode/cpp/46.cpp | 34 ++++++ store/works/solutions/leetcode/cpp/47.cpp | 45 ++++++++ store/works/solutions/leetcode/cpp/495.cpp | 37 ++++++ store/works/solutions/leetcode/cpp/5.cpp | 104 +++++++++++++++++ store/works/solutions/leetcode/cpp/501.cpp | 58 ++++++++++ store/works/solutions/leetcode/cpp/526.cpp | 29 +++++ store/works/solutions/leetcode/cpp/543.cpp | 32 ++++++ store/works/solutions/leetcode/cpp/55.cpp | 29 +++++ store/works/solutions/leetcode/cpp/6.cpp | 56 ++++++++++ store/works/solutions/leetcode/cpp/60.cpp | 44 ++++++++ store/works/solutions/leetcode/cpp/62.cpp | 25 +++++ store/works/solutions/leetcode/cpp/63.cpp | 44 ++++++++ store/works/solutions/leetcode/cpp/639.cpp | 56 ++++++++++ store/works/solutions/leetcode/cpp/641.cpp | 124 +++++++++++++++++++++ store/works/solutions/leetcode/cpp/649.cpp | 67 +++++++++++ store/works/solutions/leetcode/cpp/66.cpp | 34 ++++++ store/works/solutions/leetcode/cpp/680.cpp | 35 ++++++ store/works/solutions/leetcode/cpp/69.c | 14 +++ store/works/solutions/leetcode/cpp/7.cpp | 18 +++ store/works/solutions/leetcode/cpp/704.cpp | 79 +++++++++++++ store/works/solutions/leetcode/cpp/74.cpp | 63 +++++++++++ store/works/solutions/leetcode/cpp/746.cpp | 35 ++++++ store/works/solutions/leetcode/cpp/766-2.cpp | 20 ++++ store/works/solutions/leetcode/cpp/766.cpp | 44 ++++++++ store/works/solutions/leetcode/cpp/77.cpp | 45 ++++++++ store/works/solutions/leetcode/cpp/832.cpp | 20 ++++ store/works/solutions/leetcode/cpp/86.cpp | 80 +++++++++++++ store/works/solutions/leetcode/cpp/865.cpp | 60 ++++++++++ store/works/solutions/leetcode/cpp/867.cpp | 20 ++++ store/works/solutions/leetcode/cpp/896.cpp | 35 ++++++ store/works/solutions/leetcode/cpp/897.cpp | 37 ++++++ store/works/solutions/leetcode/cpp/917.cpp | 45 ++++++++ store/works/solutions/leetcode/cpp/96.cpp | 14 +++ store/works/solutions/leetcode/cpp/965.cpp | 29 +++++ store/works/solutions/leetcode/cpp/968.cpp | 63 +++++++++++ store/works/solutions/leetcode/cpp/976.cpp | 23 ++++ store/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 ++++++++ .../solutions/leetcode/cpp/power-set-lcci.cpp | 29 +++++ .../leetcode/cpp/que-shi-de-shu-zi-lcof.cpp | 29 +++++ 92 files changed, 3819 insertions(+) create mode 100644 store/works/solutions/leetcode/cpp/.gitignore create mode 100644 store/works/solutions/leetcode/cpp/10.cpp create mode 100644 store/works/solutions/leetcode/cpp/100.cpp create mode 100644 store/works/solutions/leetcode/cpp/101.cpp create mode 100644 store/works/solutions/leetcode/cpp/1025.cpp create mode 100644 store/works/solutions/leetcode/cpp/1051.cpp create mode 100644 store/works/solutions/leetcode/cpp/1052.cpp create mode 100644 store/works/solutions/leetcode/cpp/11.cpp create mode 100644 store/works/solutions/leetcode/cpp/1144.cpp create mode 100644 store/works/solutions/leetcode/cpp/12.cpp create mode 100644 store/works/solutions/leetcode/cpp/121.cpp create mode 100644 store/works/solutions/leetcode/cpp/1219.cpp create mode 100644 store/works/solutions/leetcode/cpp/122.cpp create mode 100644 store/works/solutions/leetcode/cpp/123.cpp create mode 100644 store/works/solutions/leetcode/cpp/1286.cpp create mode 100644 store/works/solutions/leetcode/cpp/13.cpp create mode 100644 store/works/solutions/leetcode/cpp/1343.cpp create mode 100644 store/works/solutions/leetcode/cpp/1347.cpp create mode 100644 store/works/solutions/leetcode/cpp/1370.cpp create mode 100644 store/works/solutions/leetcode/cpp/14.cpp create mode 100644 store/works/solutions/leetcode/cpp/147.cpp create mode 100644 store/works/solutions/leetcode/cpp/1470.cpp create mode 100644 store/works/solutions/leetcode/cpp/15.cpp create mode 100644 store/works/solutions/leetcode/cpp/155-2.cpp create mode 100644 store/works/solutions/leetcode/cpp/155.cpp create mode 100644 store/works/solutions/leetcode/cpp/1609.cpp create mode 100644 store/works/solutions/leetcode/cpp/167.cpp create mode 100644 store/works/solutions/leetcode/cpp/17.04.cpp create mode 100644 store/works/solutions/leetcode/cpp/17.cpp create mode 100644 store/works/solutions/leetcode/cpp/198.cpp create mode 100644 store/works/solutions/leetcode/cpp/2.cpp create mode 100644 store/works/solutions/leetcode/cpp/20.cpp create mode 100644 store/works/solutions/leetcode/cpp/203.cpp create mode 100644 store/works/solutions/leetcode/cpp/213.cpp create mode 100644 store/works/solutions/leetcode/cpp/22.cpp create mode 100644 store/works/solutions/leetcode/cpp/231.cpp create mode 100644 store/works/solutions/leetcode/cpp/26.cpp create mode 100644 store/works/solutions/leetcode/cpp/260-2.cpp create mode 100644 store/works/solutions/leetcode/cpp/260.cpp create mode 100644 store/works/solutions/leetcode/cpp/299.cpp create mode 100644 store/works/solutions/leetcode/cpp/303.cpp create mode 100644 store/works/solutions/leetcode/cpp/304.cpp create mode 100644 store/works/solutions/leetcode/cpp/328.cpp create mode 100644 store/works/solutions/leetcode/cpp/337.cpp create mode 100644 store/works/solutions/leetcode/cpp/338.cpp create mode 100644 store/works/solutions/leetcode/cpp/343.cpp create mode 100644 store/works/solutions/leetcode/cpp/35.cpp create mode 100644 store/works/solutions/leetcode/cpp/371.cpp create mode 100644 store/works/solutions/leetcode/cpp/395.cpp create mode 100644 store/works/solutions/leetcode/cpp/397.cpp create mode 100644 store/works/solutions/leetcode/cpp/401.cpp create mode 100644 store/works/solutions/leetcode/cpp/46.cpp create mode 100644 store/works/solutions/leetcode/cpp/47.cpp create mode 100644 store/works/solutions/leetcode/cpp/495.cpp create mode 100644 store/works/solutions/leetcode/cpp/5.cpp create mode 100644 store/works/solutions/leetcode/cpp/501.cpp create mode 100644 store/works/solutions/leetcode/cpp/526.cpp create mode 100644 store/works/solutions/leetcode/cpp/543.cpp create mode 100644 store/works/solutions/leetcode/cpp/55.cpp create mode 100644 store/works/solutions/leetcode/cpp/6.cpp create mode 100644 store/works/solutions/leetcode/cpp/60.cpp create mode 100644 store/works/solutions/leetcode/cpp/62.cpp create mode 100644 store/works/solutions/leetcode/cpp/63.cpp create mode 100644 store/works/solutions/leetcode/cpp/639.cpp create mode 100644 store/works/solutions/leetcode/cpp/641.cpp create mode 100644 store/works/solutions/leetcode/cpp/649.cpp create mode 100644 store/works/solutions/leetcode/cpp/66.cpp create mode 100644 store/works/solutions/leetcode/cpp/680.cpp create mode 100644 store/works/solutions/leetcode/cpp/69.c create mode 100644 store/works/solutions/leetcode/cpp/7.cpp create mode 100644 store/works/solutions/leetcode/cpp/704.cpp create mode 100644 store/works/solutions/leetcode/cpp/74.cpp create mode 100644 store/works/solutions/leetcode/cpp/746.cpp create mode 100644 store/works/solutions/leetcode/cpp/766-2.cpp create mode 100644 store/works/solutions/leetcode/cpp/766.cpp create mode 100644 store/works/solutions/leetcode/cpp/77.cpp create mode 100644 store/works/solutions/leetcode/cpp/832.cpp create mode 100644 store/works/solutions/leetcode/cpp/86.cpp create mode 100644 store/works/solutions/leetcode/cpp/865.cpp create mode 100644 store/works/solutions/leetcode/cpp/867.cpp create mode 100644 store/works/solutions/leetcode/cpp/896.cpp create mode 100644 store/works/solutions/leetcode/cpp/897.cpp create mode 100644 store/works/solutions/leetcode/cpp/917.cpp create mode 100644 store/works/solutions/leetcode/cpp/96.cpp create mode 100644 store/works/solutions/leetcode/cpp/965.cpp create mode 100644 store/works/solutions/leetcode/cpp/968.cpp create mode 100644 store/works/solutions/leetcode/cpp/976.cpp create mode 100644 store/works/solutions/leetcode/cpp/98.cpp create mode 100644 store/works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp create mode 100644 store/works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp create mode 100644 store/works/solutions/leetcode/cpp/power-set-lcci.cpp create mode 100644 store/works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp (limited to 'store/works/solutions/leetcode/cpp') diff --git a/store/works/solutions/leetcode/cpp/.gitignore b/store/works/solutions/leetcode/cpp/.gitignore new file mode 100644 index 0000000..d1d85a8 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/.gitignore @@ -0,0 +1,3 @@ +*.exe +*.pdb +*.ilk \ No newline at end of file diff --git a/store/works/solutions/leetcode/cpp/10.cpp b/store/works/solutions/leetcode/cpp/10.cpp new file mode 100644 index 0000000..fbb5586 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/10.cpp @@ -0,0 +1,83 @@ +#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/store/works/solutions/leetcode/cpp/100.cpp b/store/works/solutions/leetcode/cpp/100.cpp new file mode 100644 index 0000000..28448d1 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/100.cpp @@ -0,0 +1,29 @@ +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/store/works/solutions/leetcode/cpp/101.cpp b/store/works/solutions/leetcode/cpp/101.cpp new file mode 100644 index 0000000..a1dad6f --- /dev/null +++ b/store/works/solutions/leetcode/cpp/101.cpp @@ -0,0 +1,43 @@ +#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/store/works/solutions/leetcode/cpp/1025.cpp b/store/works/solutions/leetcode/cpp/1025.cpp new file mode 100644 index 0000000..b26ae02 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1025.cpp @@ -0,0 +1,8 @@ +class Solution +{ +public: + bool divisorGame(int N) + { + return N % 2 == 0; + } +}; diff --git a/store/works/solutions/leetcode/cpp/1051.cpp b/store/works/solutions/leetcode/cpp/1051.cpp new file mode 100644 index 0000000..6ded6f5 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1051.cpp @@ -0,0 +1,33 @@ +#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/store/works/solutions/leetcode/cpp/1052.cpp b/store/works/solutions/leetcode/cpp/1052.cpp new file mode 100644 index 0000000..583e217 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1052.cpp @@ -0,0 +1,47 @@ +#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/store/works/solutions/leetcode/cpp/11.cpp b/store/works/solutions/leetcode/cpp/11.cpp new file mode 100644 index 0000000..44a8fd9 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/11.cpp @@ -0,0 +1,42 @@ +#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/store/works/solutions/leetcode/cpp/1144.cpp b/store/works/solutions/leetcode/cpp/1144.cpp new file mode 100644 index 0000000..e6bf83b --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1144.cpp @@ -0,0 +1,48 @@ +#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/store/works/solutions/leetcode/cpp/12.cpp b/store/works/solutions/leetcode/cpp/12.cpp new file mode 100644 index 0000000..e334895 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/12.cpp @@ -0,0 +1,51 @@ +#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/store/works/solutions/leetcode/cpp/121.cpp b/store/works/solutions/leetcode/cpp/121.cpp new file mode 100644 index 0000000..8561fa3 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/121.cpp @@ -0,0 +1,24 @@ +#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/store/works/solutions/leetcode/cpp/1219.cpp b/store/works/solutions/leetcode/cpp/1219.cpp new file mode 100644 index 0000000..5f72206 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1219.cpp @@ -0,0 +1,64 @@ +#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/store/works/solutions/leetcode/cpp/122.cpp b/store/works/solutions/leetcode/cpp/122.cpp new file mode 100644 index 0000000..68cd278 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/122.cpp @@ -0,0 +1,28 @@ +#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/store/works/solutions/leetcode/cpp/123.cpp b/store/works/solutions/leetcode/cpp/123.cpp new file mode 100644 index 0000000..ecf35c4 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/123.cpp @@ -0,0 +1,34 @@ +#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/store/works/solutions/leetcode/cpp/1286.cpp b/store/works/solutions/leetcode/cpp/1286.cpp new file mode 100644 index 0000000..1ad0d4e --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1286.cpp @@ -0,0 +1,56 @@ +#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/store/works/solutions/leetcode/cpp/13.cpp b/store/works/solutions/leetcode/cpp/13.cpp new file mode 100644 index 0000000..9b7c5df --- /dev/null +++ b/store/works/solutions/leetcode/cpp/13.cpp @@ -0,0 +1,54 @@ +#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/store/works/solutions/leetcode/cpp/1343.cpp b/store/works/solutions/leetcode/cpp/1343.cpp new file mode 100644 index 0000000..b300bc7 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1343.cpp @@ -0,0 +1,40 @@ +#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/store/works/solutions/leetcode/cpp/1347.cpp b/store/works/solutions/leetcode/cpp/1347.cpp new file mode 100644 index 0000000..154a6b5 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1347.cpp @@ -0,0 +1,35 @@ +#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/store/works/solutions/leetcode/cpp/1370.cpp b/store/works/solutions/leetcode/cpp/1370.cpp new file mode 100644 index 0000000..9741d48 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1370.cpp @@ -0,0 +1,45 @@ +#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/store/works/solutions/leetcode/cpp/14.cpp b/store/works/solutions/leetcode/cpp/14.cpp new file mode 100644 index 0000000..1d07a60 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/14.cpp @@ -0,0 +1,35 @@ +#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/store/works/solutions/leetcode/cpp/147.cpp b/store/works/solutions/leetcode/cpp/147.cpp new file mode 100644 index 0000000..c741290 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/147.cpp @@ -0,0 +1,56 @@ +#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/store/works/solutions/leetcode/cpp/1470.cpp b/store/works/solutions/leetcode/cpp/1470.cpp new file mode 100644 index 0000000..8657dd6 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1470.cpp @@ -0,0 +1,23 @@ +#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/store/works/solutions/leetcode/cpp/15.cpp b/store/works/solutions/leetcode/cpp/15.cpp new file mode 100644 index 0000000..2b8f6cd --- /dev/null +++ b/store/works/solutions/leetcode/cpp/15.cpp @@ -0,0 +1,44 @@ +#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/store/works/solutions/leetcode/cpp/155-2.cpp b/store/works/solutions/leetcode/cpp/155-2.cpp new file mode 100644 index 0000000..aa07eee --- /dev/null +++ b/store/works/solutions/leetcode/cpp/155-2.cpp @@ -0,0 +1,48 @@ +#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/store/works/solutions/leetcode/cpp/155.cpp b/store/works/solutions/leetcode/cpp/155.cpp new file mode 100644 index 0000000..48550be --- /dev/null +++ b/store/works/solutions/leetcode/cpp/155.cpp @@ -0,0 +1,38 @@ +#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/store/works/solutions/leetcode/cpp/1609.cpp b/store/works/solutions/leetcode/cpp/1609.cpp new file mode 100644 index 0000000..e446c0f --- /dev/null +++ b/store/works/solutions/leetcode/cpp/1609.cpp @@ -0,0 +1,94 @@ +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/store/works/solutions/leetcode/cpp/167.cpp b/store/works/solutions/leetcode/cpp/167.cpp new file mode 100644 index 0000000..05317b4 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/167.cpp @@ -0,0 +1,28 @@ +#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/store/works/solutions/leetcode/cpp/17.04.cpp b/store/works/solutions/leetcode/cpp/17.04.cpp new file mode 100644 index 0000000..07ac7ae --- /dev/null +++ b/store/works/solutions/leetcode/cpp/17.04.cpp @@ -0,0 +1,21 @@ +#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/store/works/solutions/leetcode/cpp/17.cpp b/store/works/solutions/leetcode/cpp/17.cpp new file mode 100644 index 0000000..74e33b4 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/17.cpp @@ -0,0 +1,56 @@ +#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/store/works/solutions/leetcode/cpp/198.cpp b/store/works/solutions/leetcode/cpp/198.cpp new file mode 100644 index 0000000..4d9d4fc --- /dev/null +++ b/store/works/solutions/leetcode/cpp/198.cpp @@ -0,0 +1,26 @@ +#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/store/works/solutions/leetcode/cpp/2.cpp b/store/works/solutions/leetcode/cpp/2.cpp new file mode 100644 index 0000000..cb954ae --- /dev/null +++ b/store/works/solutions/leetcode/cpp/2.cpp @@ -0,0 +1,75 @@ +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/store/works/solutions/leetcode/cpp/20.cpp b/store/works/solutions/leetcode/cpp/20.cpp new file mode 100644 index 0000000..e994e96 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/20.cpp @@ -0,0 +1,55 @@ +#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/store/works/solutions/leetcode/cpp/203.cpp b/store/works/solutions/leetcode/cpp/203.cpp new file mode 100644 index 0000000..0f1bb55 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/203.cpp @@ -0,0 +1,48 @@ +#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/store/works/solutions/leetcode/cpp/213.cpp b/store/works/solutions/leetcode/cpp/213.cpp new file mode 100644 index 0000000..cd98f67 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/213.cpp @@ -0,0 +1,41 @@ +#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/store/works/solutions/leetcode/cpp/22.cpp b/store/works/solutions/leetcode/cpp/22.cpp new file mode 100644 index 0000000..e9467f1 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/22.cpp @@ -0,0 +1,40 @@ +#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/store/works/solutions/leetcode/cpp/231.cpp b/store/works/solutions/leetcode/cpp/231.cpp new file mode 100644 index 0000000..8861e09 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/231.cpp @@ -0,0 +1,10 @@ +#include + +class Solution { +public: + bool isPowerOfTwo(int n) { + if (n <= 0) return false; + std::bitset bits(n); + return bits.count() == 1; + } +}; diff --git a/store/works/solutions/leetcode/cpp/26.cpp b/store/works/solutions/leetcode/cpp/26.cpp new file mode 100644 index 0000000..3ee4aa7 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/26.cpp @@ -0,0 +1,37 @@ +#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/store/works/solutions/leetcode/cpp/260-2.cpp b/store/works/solutions/leetcode/cpp/260-2.cpp new file mode 100644 index 0000000..336d9e1 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/260-2.cpp @@ -0,0 +1,26 @@ +#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/store/works/solutions/leetcode/cpp/260.cpp b/store/works/solutions/leetcode/cpp/260.cpp new file mode 100644 index 0000000..5679d52 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/260.cpp @@ -0,0 +1,23 @@ +#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/store/works/solutions/leetcode/cpp/299.cpp b/store/works/solutions/leetcode/cpp/299.cpp new file mode 100644 index 0000000..21c09b6 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/299.cpp @@ -0,0 +1,44 @@ +#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/store/works/solutions/leetcode/cpp/303.cpp b/store/works/solutions/leetcode/cpp/303.cpp new file mode 100644 index 0000000..06c4ad1 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/303.cpp @@ -0,0 +1,26 @@ +#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/store/works/solutions/leetcode/cpp/304.cpp b/store/works/solutions/leetcode/cpp/304.cpp new file mode 100644 index 0000000..ab22281 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/304.cpp @@ -0,0 +1,35 @@ +#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/store/works/solutions/leetcode/cpp/328.cpp b/store/works/solutions/leetcode/cpp/328.cpp new file mode 100644 index 0000000..de3ad0b --- /dev/null +++ b/store/works/solutions/leetcode/cpp/328.cpp @@ -0,0 +1,51 @@ +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/store/works/solutions/leetcode/cpp/337.cpp b/store/works/solutions/leetcode/cpp/337.cpp new file mode 100644 index 0000000..655a4d0 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/337.cpp @@ -0,0 +1,38 @@ +#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/store/works/solutions/leetcode/cpp/338.cpp b/store/works/solutions/leetcode/cpp/338.cpp new file mode 100644 index 0000000..1758234 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/338.cpp @@ -0,0 +1,26 @@ +#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/store/works/solutions/leetcode/cpp/343.cpp b/store/works/solutions/leetcode/cpp/343.cpp new file mode 100644 index 0000000..d31f7ce --- /dev/null +++ b/store/works/solutions/leetcode/cpp/343.cpp @@ -0,0 +1,23 @@ +#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/store/works/solutions/leetcode/cpp/35.cpp b/store/works/solutions/leetcode/cpp/35.cpp new file mode 100644 index 0000000..7da26c4 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/35.cpp @@ -0,0 +1,36 @@ +#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/store/works/solutions/leetcode/cpp/371.cpp b/store/works/solutions/leetcode/cpp/371.cpp new file mode 100644 index 0000000..3a7bc8b --- /dev/null +++ b/store/works/solutions/leetcode/cpp/371.cpp @@ -0,0 +1,25 @@ + +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/store/works/solutions/leetcode/cpp/395.cpp b/store/works/solutions/leetcode/cpp/395.cpp new file mode 100644 index 0000000..d45eee9 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/395.cpp @@ -0,0 +1,56 @@ +#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/store/works/solutions/leetcode/cpp/397.cpp b/store/works/solutions/leetcode/cpp/397.cpp new file mode 100644 index 0000000..bbb61ff --- /dev/null +++ b/store/works/solutions/leetcode/cpp/397.cpp @@ -0,0 +1,47 @@ +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/store/works/solutions/leetcode/cpp/401.cpp b/store/works/solutions/leetcode/cpp/401.cpp new file mode 100644 index 0000000..71147f4 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/401.cpp @@ -0,0 +1,57 @@ +#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/store/works/solutions/leetcode/cpp/46.cpp b/store/works/solutions/leetcode/cpp/46.cpp new file mode 100644 index 0000000..bfb3c83 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/46.cpp @@ -0,0 +1,34 @@ +#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/store/works/solutions/leetcode/cpp/47.cpp b/store/works/solutions/leetcode/cpp/47.cpp new file mode 100644 index 0000000..4a109ea --- /dev/null +++ b/store/works/solutions/leetcode/cpp/47.cpp @@ -0,0 +1,45 @@ +#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/store/works/solutions/leetcode/cpp/495.cpp b/store/works/solutions/leetcode/cpp/495.cpp new file mode 100644 index 0000000..c940b0b --- /dev/null +++ b/store/works/solutions/leetcode/cpp/495.cpp @@ -0,0 +1,37 @@ +#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/store/works/solutions/leetcode/cpp/5.cpp b/store/works/solutions/leetcode/cpp/5.cpp new file mode 100644 index 0000000..6200c4c --- /dev/null +++ b/store/works/solutions/leetcode/cpp/5.cpp @@ -0,0 +1,104 @@ +#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/store/works/solutions/leetcode/cpp/501.cpp b/store/works/solutions/leetcode/cpp/501.cpp new file mode 100644 index 0000000..197ed10 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/501.cpp @@ -0,0 +1,58 @@ +#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/store/works/solutions/leetcode/cpp/526.cpp b/store/works/solutions/leetcode/cpp/526.cpp new file mode 100644 index 0000000..19f445f --- /dev/null +++ b/store/works/solutions/leetcode/cpp/526.cpp @@ -0,0 +1,29 @@ +#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/store/works/solutions/leetcode/cpp/543.cpp b/store/works/solutions/leetcode/cpp/543.cpp new file mode 100644 index 0000000..f782521 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/543.cpp @@ -0,0 +1,32 @@ +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/store/works/solutions/leetcode/cpp/55.cpp b/store/works/solutions/leetcode/cpp/55.cpp new file mode 100644 index 0000000..d2c2600 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/55.cpp @@ -0,0 +1,29 @@ +#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/store/works/solutions/leetcode/cpp/6.cpp b/store/works/solutions/leetcode/cpp/6.cpp new file mode 100644 index 0000000..f1d947c --- /dev/null +++ b/store/works/solutions/leetcode/cpp/6.cpp @@ -0,0 +1,56 @@ +#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/store/works/solutions/leetcode/cpp/60.cpp b/store/works/solutions/leetcode/cpp/60.cpp new file mode 100644 index 0000000..f090355 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/60.cpp @@ -0,0 +1,44 @@ +#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/store/works/solutions/leetcode/cpp/62.cpp b/store/works/solutions/leetcode/cpp/62.cpp new file mode 100644 index 0000000..744a0d3 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/62.cpp @@ -0,0 +1,25 @@ +#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/store/works/solutions/leetcode/cpp/63.cpp b/store/works/solutions/leetcode/cpp/63.cpp new file mode 100644 index 0000000..ed07bdc --- /dev/null +++ b/store/works/solutions/leetcode/cpp/63.cpp @@ -0,0 +1,44 @@ +#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/store/works/solutions/leetcode/cpp/639.cpp b/store/works/solutions/leetcode/cpp/639.cpp new file mode 100644 index 0000000..ead252e --- /dev/null +++ b/store/works/solutions/leetcode/cpp/639.cpp @@ -0,0 +1,56 @@ +#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/store/works/solutions/leetcode/cpp/641.cpp b/store/works/solutions/leetcode/cpp/641.cpp new file mode 100644 index 0000000..0235797 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/641.cpp @@ -0,0 +1,124 @@ +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/store/works/solutions/leetcode/cpp/649.cpp b/store/works/solutions/leetcode/cpp/649.cpp new file mode 100644 index 0000000..ab702d2 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/649.cpp @@ -0,0 +1,67 @@ +#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/store/works/solutions/leetcode/cpp/66.cpp b/store/works/solutions/leetcode/cpp/66.cpp new file mode 100644 index 0000000..40ce008 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/66.cpp @@ -0,0 +1,34 @@ +#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/store/works/solutions/leetcode/cpp/680.cpp b/store/works/solutions/leetcode/cpp/680.cpp new file mode 100644 index 0000000..21d150f --- /dev/null +++ b/store/works/solutions/leetcode/cpp/680.cpp @@ -0,0 +1,35 @@ +#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/store/works/solutions/leetcode/cpp/69.c b/store/works/solutions/leetcode/cpp/69.c new file mode 100644 index 0000000..9914fff --- /dev/null +++ b/store/works/solutions/leetcode/cpp/69.c @@ -0,0 +1,14 @@ +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/store/works/solutions/leetcode/cpp/7.cpp b/store/works/solutions/leetcode/cpp/7.cpp new file mode 100644 index 0000000..a1a05c1 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/7.cpp @@ -0,0 +1,18 @@ +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/store/works/solutions/leetcode/cpp/704.cpp b/store/works/solutions/leetcode/cpp/704.cpp new file mode 100644 index 0000000..b56a01a --- /dev/null +++ b/store/works/solutions/leetcode/cpp/704.cpp @@ -0,0 +1,79 @@ +#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/store/works/solutions/leetcode/cpp/74.cpp b/store/works/solutions/leetcode/cpp/74.cpp new file mode 100644 index 0000000..08560ef --- /dev/null +++ b/store/works/solutions/leetcode/cpp/74.cpp @@ -0,0 +1,63 @@ +#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/store/works/solutions/leetcode/cpp/746.cpp b/store/works/solutions/leetcode/cpp/746.cpp new file mode 100644 index 0000000..72ffd9f --- /dev/null +++ b/store/works/solutions/leetcode/cpp/746.cpp @@ -0,0 +1,35 @@ +#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/store/works/solutions/leetcode/cpp/766-2.cpp b/store/works/solutions/leetcode/cpp/766-2.cpp new file mode 100644 index 0000000..79a0cc8 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/766-2.cpp @@ -0,0 +1,20 @@ +#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/store/works/solutions/leetcode/cpp/766.cpp b/store/works/solutions/leetcode/cpp/766.cpp new file mode 100644 index 0000000..3e8a015 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/766.cpp @@ -0,0 +1,44 @@ +#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/store/works/solutions/leetcode/cpp/77.cpp b/store/works/solutions/leetcode/cpp/77.cpp new file mode 100644 index 0000000..ec09198 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/77.cpp @@ -0,0 +1,45 @@ +#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/store/works/solutions/leetcode/cpp/832.cpp b/store/works/solutions/leetcode/cpp/832.cpp new file mode 100644 index 0000000..000fb94 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/832.cpp @@ -0,0 +1,20 @@ +#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/store/works/solutions/leetcode/cpp/86.cpp b/store/works/solutions/leetcode/cpp/86.cpp new file mode 100644 index 0000000..1f7568c --- /dev/null +++ b/store/works/solutions/leetcode/cpp/86.cpp @@ -0,0 +1,80 @@ +/** + * 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/store/works/solutions/leetcode/cpp/865.cpp b/store/works/solutions/leetcode/cpp/865.cpp new file mode 100644 index 0000000..8981a02 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/865.cpp @@ -0,0 +1,60 @@ +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/store/works/solutions/leetcode/cpp/867.cpp b/store/works/solutions/leetcode/cpp/867.cpp new file mode 100644 index 0000000..9efd176 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/867.cpp @@ -0,0 +1,20 @@ +#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/store/works/solutions/leetcode/cpp/896.cpp b/store/works/solutions/leetcode/cpp/896.cpp new file mode 100644 index 0000000..25bd528 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/896.cpp @@ -0,0 +1,35 @@ +#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/store/works/solutions/leetcode/cpp/897.cpp b/store/works/solutions/leetcode/cpp/897.cpp new file mode 100644 index 0000000..efc9741 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/897.cpp @@ -0,0 +1,37 @@ +/** + * 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/store/works/solutions/leetcode/cpp/917.cpp b/store/works/solutions/leetcode/cpp/917.cpp new file mode 100644 index 0000000..d01d795 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/917.cpp @@ -0,0 +1,45 @@ +#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/store/works/solutions/leetcode/cpp/96.cpp b/store/works/solutions/leetcode/cpp/96.cpp new file mode 100644 index 0000000..3757baa --- /dev/null +++ b/store/works/solutions/leetcode/cpp/96.cpp @@ -0,0 +1,14 @@ +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/store/works/solutions/leetcode/cpp/965.cpp b/store/works/solutions/leetcode/cpp/965.cpp new file mode 100644 index 0000000..fd2bff6 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/965.cpp @@ -0,0 +1,29 @@ +#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/store/works/solutions/leetcode/cpp/968.cpp b/store/works/solutions/leetcode/cpp/968.cpp new file mode 100644 index 0000000..c9e6b24 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/968.cpp @@ -0,0 +1,63 @@ +#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/store/works/solutions/leetcode/cpp/976.cpp b/store/works/solutions/leetcode/cpp/976.cpp new file mode 100644 index 0000000..e306047 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/976.cpp @@ -0,0 +1,23 @@ +#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/store/works/solutions/leetcode/cpp/98.cpp b/store/works/solutions/leetcode/cpp/98.cpp new file mode 100644 index 0000000..73cefa0 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/98.cpp @@ -0,0 +1,29 @@ +#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/store/works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp b/store/works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp new file mode 100644 index 0000000..dee81ec --- /dev/null +++ b/store/works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp @@ -0,0 +1,34 @@ +#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/store/works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp b/store/works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp new file mode 100644 index 0000000..697182d --- /dev/null +++ b/store/works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp @@ -0,0 +1,46 @@ +#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/store/works/solutions/leetcode/cpp/power-set-lcci.cpp b/store/works/solutions/leetcode/cpp/power-set-lcci.cpp new file mode 100644 index 0000000..f502e7c --- /dev/null +++ b/store/works/solutions/leetcode/cpp/power-set-lcci.cpp @@ -0,0 +1,29 @@ +#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/store/works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp b/store/works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp new file mode 100644 index 0000000..1cb3e01 --- /dev/null +++ b/store/works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp @@ -0,0 +1,29 @@ +#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