diff options
Diffstat (limited to 'works/solutions/leetcode/cpp')
92 files changed, 3819 insertions, 0 deletions
diff --git a/works/solutions/leetcode/cpp/.gitignore b/works/solutions/leetcode/cpp/.gitignore new file mode 100644 index 0000000..d1d85a8 --- /dev/null +++ b/works/solutions/leetcode/cpp/.gitignore @@ -0,0 +1,3 @@ +*.exe
+*.pdb
+*.ilk
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/10.cpp b/works/solutions/leetcode/cpp/10.cpp new file mode 100644 index 0000000..fbb5586 --- /dev/null +++ b/works/solutions/leetcode/cpp/10.cpp @@ -0,0 +1,83 @@ +#include <string>
+#include <unordered_map>
+#include <vector>
+
+using std::string;
+
+struct Token {
+ explicit Token(char c) : c(c), isAsterisk(false) {}
+
+ char c;
+ bool isAsterisk;
+};
+
+class Solution {
+public:
+ std::vector<Token> tokens_;
+ std::string s_;
+ std::unordered_map<int, std::unordered_map<int, int>> cache_;
+
+ bool isMatch(string s, string p) {
+ for (auto c : p) {
+ if (c == '*') {
+ tokens_.back().isAsterisk = true;
+ } else {
+ tokens_.push_back(Token{c});
+ }
+ }
+ s_ = s;
+
+ return match(0, 0, s_.size(), tokens_.size());
+ }
+
+ bool cache_match(int s_start, int t_start, int s_length, int t_length) {
+ auto cache = cache_[s_start][t_start];
+ if (cache < 0) {
+ return false;
+ } else if (cache > 0) {
+ return true;
+ } else {
+ auto result = match(s_start, t_start, s_length, t_length);
+ cache_[s_start][t_start] = result;
+ return result;
+ }
+ }
+
+ bool match(int s_start, int t_start, int s_length, int t_length) {
+ if (t_start == t_length)
+ return s_start == s_length;
+
+ const auto &token = tokens_[t_start];
+ if (token.isAsterisk) {
+ if (cache_match(s_start, t_start + 1, s_length, t_length)) {
+ return true;
+ }
+
+ int s_index = s_start;
+ while (s_index < s_length) {
+ if (token.c == '.') {
+ if (cache_match(s_index + 1, t_start + 1, s_length, t_length))
+ return true;
+ } else if (token.c == s_[s_index]) {
+ if (cache_match(s_index + 1, t_start + 1, s_length, t_length))
+ return true;
+ } else {
+ break;
+ }
+ s_index++;
+ }
+
+ return false;
+ } else {
+ if (token.c == '.') {
+ return cache_match(s_start + 1, t_start + 1, s_length, t_length);
+ } else {
+ if (token.c == s_[s_start]) {
+ return cache_match(s_start + 1, t_start + 1, s_length, t_length);
+ } else {
+ return false;
+ }
+ }
+ }
+ }
+};
diff --git a/works/solutions/leetcode/cpp/100.cpp b/works/solutions/leetcode/cpp/100.cpp new file mode 100644 index 0000000..28448d1 --- /dev/null +++ b/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/works/solutions/leetcode/cpp/101.cpp b/works/solutions/leetcode/cpp/101.cpp new file mode 100644 index 0000000..a1dad6f --- /dev/null +++ b/works/solutions/leetcode/cpp/101.cpp @@ -0,0 +1,43 @@ +#include <cstddef>
+
+struct TreeNode
+{
+ int val;
+ TreeNode *left;
+ TreeNode *right;
+ TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+};
+
+class Solution
+{
+public:
+ static bool check(TreeNode *left, TreeNode *right)
+ {
+ if (left == NULL)
+ {
+ if (right == NULL)
+ return true;
+ else
+ return false;
+ }
+ else
+ {
+ if (right == NULL)
+ return false;
+ else
+ {
+ if (left->val != right->val)
+ return false;
+ return check(left->left, right->right) && check(left->right, right->left);
+ }
+ }
+ }
+
+ bool isSymmetric(TreeNode *root)
+ {
+ if (root == nullptr)
+ return true;
+
+ return check(root->left, root->right);
+ }
+};
diff --git a/works/solutions/leetcode/cpp/1025.cpp b/works/solutions/leetcode/cpp/1025.cpp new file mode 100644 index 0000000..b26ae02 --- /dev/null +++ b/works/solutions/leetcode/cpp/1025.cpp @@ -0,0 +1,8 @@ +class Solution
+{
+public:
+ bool divisorGame(int N)
+ {
+ return N % 2 == 0;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/1051.cpp b/works/solutions/leetcode/cpp/1051.cpp new file mode 100644 index 0000000..6ded6f5 --- /dev/null +++ b/works/solutions/leetcode/cpp/1051.cpp @@ -0,0 +1,33 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int heightChecker(vector<int> &heights)
+ {
+ vector<int> height_counter(101);
+ for (int height : heights)
+ {
+ height_counter[height]++;
+ }
+
+ auto iter = heights.cbegin();
+
+ int result = 0;
+
+ for (int height = 1; height <= 100; height++)
+ {
+ int height_count = height_counter[height];
+ while (height_count > 0)
+ {
+ if (*iter++ != height)
+ result++;
+ --height_count;
+ }
+ }
+
+ return result;
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/1052.cpp b/works/solutions/leetcode/cpp/1052.cpp new file mode 100644 index 0000000..583e217 --- /dev/null +++ b/works/solutions/leetcode/cpp/1052.cpp @@ -0,0 +1,47 @@ +#include <algorithm>
+// #include <iostream>
+#include <vector>
+
+using std::vector;
+
+class Solution {
+public:
+ int maxSatisfied(vector<int> &customers, vector<int> &grumpy, int X) {
+ int customer_count = customers.size();
+
+ int total_customer_count = 0;
+ int total_unsatisfied_customer_count = 0;
+
+ for (int i = 0; i < X; i++) {
+ total_customer_count += customers[i];
+ if (grumpy[i]) {
+ total_unsatisfied_customer_count += customers[i];
+ }
+ }
+
+ int current_suppress_customer_count = total_unsatisfied_customer_count;
+ int max_suppress_customer_count = total_unsatisfied_customer_count;
+
+ for (int i = X; i < customer_count; i++) {
+ total_customer_count += customers[i];
+ if (grumpy[i]) {
+ total_unsatisfied_customer_count += customers[i];
+ current_suppress_customer_count += customers[i];
+ }
+
+ if (grumpy[i - X]) {
+ current_suppress_customer_count -= customers[i - X];
+ }
+
+ max_suppress_customer_count = std::max(max_suppress_customer_count,
+ current_suppress_customer_count);
+ }
+
+ // std::cout << total_customer_count << '\n';
+ // std::cout << total_unsatisfied_customer_count << '\n';
+ // std::cout << max_suppress_customer_count << '\n';
+
+ return total_customer_count - total_unsatisfied_customer_count +
+ max_suppress_customer_count;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/11.cpp b/works/solutions/leetcode/cpp/11.cpp new file mode 100644 index 0000000..44a8fd9 --- /dev/null +++ b/works/solutions/leetcode/cpp/11.cpp @@ -0,0 +1,42 @@ +#include <vector>
+#include <algorithm>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int maxArea(vector<int> &height)
+ {
+ auto left = height.cbegin();
+ auto right = height.cend();
+ --right;
+
+ int result = 0;
+
+ // although length could be calculated by right - left,
+ // but this can be cached in register.
+ int length = height.size() - 1;
+
+ while (left != right)
+ {
+ const int left_v = *left;
+ const int right_v = *right;
+ const int capacity = std::min(left_v, right_v) * length;
+ result = std::max(capacity, result);
+
+ if (left_v < right_v)
+ {
+ ++left;
+ }
+ else
+ {
+ --right;
+ }
+
+ length--;
+ }
+
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/1144.cpp b/works/solutions/leetcode/cpp/1144.cpp new file mode 100644 index 0000000..e6bf83b --- /dev/null +++ b/works/solutions/leetcode/cpp/1144.cpp @@ -0,0 +1,48 @@ +#include <vector>
+
+using std::vector;
+
+inline int min(int a, int b)
+{
+ return a < b ? a : b;
+}
+
+class Solution
+{
+public:
+ int movesToMakeZigzag(vector<int> &nums)
+ {
+ int size = nums.size();
+
+ if (size == 1)
+ return 0;
+
+ // odd
+ int result_odd = 0;
+ for (int i = 0; i < size; i += 2)
+ {
+ int neighber = 1001;
+ if (i - 1 >= 0)
+ neighber = min(neighber, nums[i - 1]);
+ if (i + 1 < size)
+ neighber = min(neighber, nums[i + 1]);
+ if (nums[i] >= neighber)
+ result_odd += nums[i] - neighber + 1;
+ }
+
+ // even
+ int result_even = 0;
+ for (int i = 1; i < size; i += 2)
+ {
+ int neighber = 1001;
+ if (i - 1 >= 0)
+ neighber = min(neighber, nums[i - 1]);
+ if (i + 1 < size)
+ neighber = min(neighber, nums[i + 1]);
+ if (nums[i] >= neighber)
+ result_even += nums[i] - neighber + 1;
+ }
+
+ return min(result_odd, result_even);
+ }
+};
diff --git a/works/solutions/leetcode/cpp/12.cpp b/works/solutions/leetcode/cpp/12.cpp new file mode 100644 index 0000000..e334895 --- /dev/null +++ b/works/solutions/leetcode/cpp/12.cpp @@ -0,0 +1,51 @@ +#include <string>
+
+using std::string;
+
+const char *roman_digits = "IVXLCDM";
+
+class Solution
+{
+public:
+ string intToRoman(int num)
+ {
+ string result;
+
+ int current_digit_index = 0;
+
+ while (num != 0)
+ {
+ const int digit = num % 10;
+ if (digit == 9)
+ {
+ result += roman_digits[current_digit_index + 2];
+ result += roman_digits[current_digit_index];
+ }
+ else if (digit <= 8 && digit >= 5)
+ {
+ for (int i = 0; i < digit - 5; i++)
+ {
+ result += roman_digits[current_digit_index];
+ }
+ result += roman_digits[current_digit_index + 1];
+ }
+ else if (digit == 4)
+ {
+ result += roman_digits[current_digit_index + 1];
+ result += roman_digits[current_digit_index];
+ }
+ else
+ {
+ for (int i = 0; i < digit; i++)
+ {
+ result += roman_digits[current_digit_index];
+ }
+ }
+
+ num /= 10;
+ current_digit_index += 2;
+ }
+
+ return string(result.crbegin(), result.crend());
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/121.cpp b/works/solutions/leetcode/cpp/121.cpp new file mode 100644 index 0000000..8561fa3 --- /dev/null +++ b/works/solutions/leetcode/cpp/121.cpp @@ -0,0 +1,24 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int maxProfit(vector<int> &prices)
+ {
+ if (prices.size() <= 1) return 0;
+
+ int result = 0;
+ int min = prices.front();
+ for (int i = 1; i < prices.size(); i++)
+ {
+ if (prices[i] - min > result)
+ result = prices[i] - min;
+ if (prices[i] < min)
+ min = prices[i];
+ }
+
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/1219.cpp b/works/solutions/leetcode/cpp/1219.cpp new file mode 100644 index 0000000..5f72206 --- /dev/null +++ b/works/solutions/leetcode/cpp/1219.cpp @@ -0,0 +1,64 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ static void dfs(const vector<vector<int>> &grid, bool **visited, int row, int col, int row_max, int col_max, int ¤t, int &max)
+ {
+ int cell = grid[row][col];
+ bool &cell_visited = visited[row][col];
+ if (cell == 0 || cell_visited)
+ return;
+ current += cell;
+ cell_visited = true;
+
+ if (current > max)
+ max = current;
+
+ if (row < row_max)
+ dfs(grid, visited, row + 1, col, row_max, col_max, current, max);
+
+ if (col < col_max)
+ dfs(grid, visited, row, col + 1, row_max, col_max, current, max);
+
+ if (row > 0)
+ dfs(grid, visited, row - 1, col, row_max, col_max, current, max);
+
+ if (col > 0)
+ dfs(grid, visited, row, col - 1, row_max, col_max, current, max);
+
+ cell_visited = false;
+ current -= cell;
+ }
+
+ int getMaximumGold(vector<vector<int>> &grid)
+ {
+ int row_max = grid.size();
+ int col_max = grid.front().size();
+
+ bool **visited = new bool *[row_max];
+ for (int i = 0; i < row_max; i++)
+ {
+ visited[i] = new bool[col_max]{false};
+ }
+
+ int current = 0;
+ int max = 0;
+
+ for (int row_start = 0; row_start < row_max; row_start++)
+ for (int col_start = 0; col_start < col_max; col_start++)
+ {
+ dfs(grid, visited, row_start, col_start, row_max - 1, col_max - 1, current, max);
+ }
+
+ for (int i = 0; i < row_max; i++)
+ {
+ delete[] visited[i];
+ }
+ delete[] visited;
+
+ return max;
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/122.cpp b/works/solutions/leetcode/cpp/122.cpp new file mode 100644 index 0000000..68cd278 --- /dev/null +++ b/works/solutions/leetcode/cpp/122.cpp @@ -0,0 +1,28 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int maxProfit(vector<int> &prices)
+ {
+ if (prices.size() <= 1)
+ return 0;
+
+ int day_count = prices.size();
+
+ vector<vector<int>> dp(day_count, std::vector<int>(2));
+
+ dp[0][0] = 0;
+ dp[0][1] = -prices[0];
+
+ for (int i = 1; i < day_count; i++)
+ {
+ dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
+ dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
+ }
+
+ return dp[day_count - 1][0];
+ }
+};
diff --git a/works/solutions/leetcode/cpp/123.cpp b/works/solutions/leetcode/cpp/123.cpp new file mode 100644 index 0000000..ecf35c4 --- /dev/null +++ b/works/solutions/leetcode/cpp/123.cpp @@ -0,0 +1,34 @@ +#include <vector>
+#include <iostream>
+using std::vector;
+
+#include <algorithm>
+
+class Solution
+{
+public:
+ // 0 -> after buy for the first time
+ // 1 -> after sell for the first time
+ // 2 -> after buy for the second time
+ // 3 -> after sell for the second time
+
+ int maxProfit(vector<int> &prices)
+ {
+ int day_count = prices.size();
+
+ int state_0 = -prices[0];
+ int state_1 = 0;
+ int state_2 = -prices[0];
+ int state_3 = 0;
+
+ for (int day = 1; day < day_count; day++)
+ {
+ state_0 = std::max(state_0, -prices[day]);
+ state_1 = std::max(state_1, state_0 + prices[day]);
+ state_2 = std::max(state_2, state_1 - prices[day]);
+ state_3 = std::max(state_3, state_2 + prices[day]);
+ }
+
+ return std::max({state_0, state_1, state_2, state_3});
+ }
+};
diff --git a/works/solutions/leetcode/cpp/1286.cpp b/works/solutions/leetcode/cpp/1286.cpp new file mode 100644 index 0000000..1ad0d4e --- /dev/null +++ b/works/solutions/leetcode/cpp/1286.cpp @@ -0,0 +1,56 @@ +#include <string> + +using std::string; + +#include <vector> + +class CombinationIterator { +public: + string chars; + int char_length; + int combinationLength; + bool has_next = true; + std::vector<int> indices; + + CombinationIterator(string characters, int combinationLength) + : chars(characters), char_length(characters.size()), + combinationLength(combinationLength) { + for (int i = 0; i < combinationLength; i++) { + indices.push_back(i); + } + } + + string next() { + string result; + for (auto index : indices) { + result.push_back(chars[index]); + } + + int count = 1; + while (indices[combinationLength - count] == char_length - count) { + count++; + if (count > combinationLength) { + has_next = false; + return result; + } + } + + indices[combinationLength - count] += 1; + for (int i = combinationLength - count + 1; i < combinationLength; i++) { + indices[i] = indices[i - 1] + 1; + } + + return result; + } + + bool hasNext() { + return has_next; + } +}; + +/** + * Your CombinationIterator object will be instantiated and called as such: + * CombinationIterator* obj = new CombinationIterator(characters, + * combinationLength); string param_1 = obj->next(); bool param_2 = + * obj->hasNext(); + */
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/13.cpp b/works/solutions/leetcode/cpp/13.cpp new file mode 100644 index 0000000..9b7c5df --- /dev/null +++ b/works/solutions/leetcode/cpp/13.cpp @@ -0,0 +1,54 @@ +#include <string>
+
+using std::string;
+
+int romanDigitNumber(char romanDigit)
+{
+ switch (romanDigit)
+ {
+ case 'I':
+ return 1;
+ case 'V':
+ return 5;
+ case 'X':
+ return 10;
+ case 'L':
+ return 50;
+ case 'C':
+ return 100;
+ case 'D':
+ return 500;
+ case 'M':
+ return 1000;
+ };
+ return 0;
+}
+
+class Solution
+{
+public:
+ int romanToInt(string s)
+ {
+ int result = 0;
+
+ int count = s.size();
+
+ for (int i = 0; i < count; i++)
+ {
+ const char c = s[i];
+ int num = romanDigitNumber(c);
+ if (i < count - 1)
+ {
+ const char next = s[i + 1];
+ if ((c == 'I' && (next == 'V' || next == 'X')) || (c == 'X' && (next == 'L' || next == 'C')) || (c == 'C') && (next == 'D' || next == 'M'))
+ {
+ num = -num;
+ }
+ }
+
+ result += num;
+ }
+
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/1343.cpp b/works/solutions/leetcode/cpp/1343.cpp new file mode 100644 index 0000000..b300bc7 --- /dev/null +++ b/works/solutions/leetcode/cpp/1343.cpp @@ -0,0 +1,40 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int numOfSubarrays(vector<int> &arr, int k, int threshold)
+ {
+ const auto end = arr.cend();
+ auto iter = arr.cbegin();
+ auto last_iter = arr.cbegin();
+
+ double sum = 0;
+
+ int result = 0;
+
+ for (int i = 0; i < k; i++)
+ {
+ sum += *iter++;
+ }
+
+ while (iter != end)
+ {
+ if (sum / k >= threshold)
+ {
+ result++;
+ }
+ sum -= *last_iter++;
+ sum += *iter++;
+ }
+
+ if (sum / k >= threshold)
+ {
+ result++;
+ }
+
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/1347.cpp b/works/solutions/leetcode/cpp/1347.cpp new file mode 100644 index 0000000..154a6b5 --- /dev/null +++ b/works/solutions/leetcode/cpp/1347.cpp @@ -0,0 +1,35 @@ +#include <string>
+
+using std::string;
+
+class Solution
+{
+public:
+ int minSteps(string s, string t)
+ {
+ int s_count[26]{0};
+ int t_count[26]{0};
+
+ for (auto c : s)
+ {
+ s_count[c - 'a']++;
+ }
+
+ for (auto c : t)
+ {
+ t_count[c - 'a']++;
+ }
+
+ int result = 0;
+
+ for (int i = 0; i < 26; i++)
+ {
+ int a = s_count[i];
+ int b = t_count[i];
+ if (a > b)
+ result += a - b;
+ }
+
+ return result;
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/1370.cpp b/works/solutions/leetcode/cpp/1370.cpp new file mode 100644 index 0000000..9741d48 --- /dev/null +++ b/works/solutions/leetcode/cpp/1370.cpp @@ -0,0 +1,45 @@ +#include <string>
+
+using std::string;
+
+class Solution
+{
+public:
+ string sortString(string s)
+ {
+ int count[26]{0};
+
+ for (auto c : s)
+ {
+ count[c - 'a']++;
+ }
+
+ int total_count = s.size();
+ string result;
+
+ while (total_count)
+ {
+ for (int i = 0; i < 26; i++)
+ {
+ if (count[i])
+ {
+ count[i]--;
+ total_count--;
+ result.push_back(i + 'a');
+ }
+ }
+
+ for (int i = 25; i >= 0; i--)
+ {
+ if (count[i])
+ {
+ count[i]--;
+ total_count--;
+ result.push_back(i + 'a');
+ }
+ }
+ }
+
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/14.cpp b/works/solutions/leetcode/cpp/14.cpp new file mode 100644 index 0000000..1d07a60 --- /dev/null +++ b/works/solutions/leetcode/cpp/14.cpp @@ -0,0 +1,35 @@ +#include <string>
+#include <vector>
+
+using std::string;
+using std::vector;
+
+class Solution
+{
+public:
+ string longestCommonPrefix(vector<string> &strs)
+ {
+ if (strs.empty())
+ return "";
+
+ string result;
+
+ const auto &first = strs.front();
+
+ for (int i = 0; i < first.size(); i++)
+ {
+ char c = first[i];
+
+ for (int j = 1; j < strs.size(); j++)
+ {
+ if (strs[j][i] != c)
+ goto r;
+ }
+
+ result.push_back(c);
+ }
+
+ r:
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/147.cpp b/works/solutions/leetcode/cpp/147.cpp new file mode 100644 index 0000000..c741290 --- /dev/null +++ b/works/solutions/leetcode/cpp/147.cpp @@ -0,0 +1,56 @@ +#include <cstddef>
+
+struct ListNode
+{
+ int val;
+ ListNode *next;
+ ListNode(int x) : val(x), next(NULL) {}
+};
+
+class Solution
+{
+public:
+ ListNode *insertionSortList(ListNode *head)
+ {
+ if (head == NULL)
+ return NULL;
+ if (head->next == NULL)
+ return head;
+
+ ListNode *next_sort = head->next;
+
+ head->next = nullptr;
+
+ while (next_sort != nullptr)
+ {
+ ListNode *current_sort = next_sort;
+ next_sort = current_sort->next;
+
+ ListNode *prev = nullptr;
+ ListNode *current = head;
+
+ int i = 0;
+
+ while (current != nullptr && current->val < current_sort->val)
+ {
+ i++;
+ prev = current;
+ current = current->next;
+ }
+
+ if (prev == nullptr)
+ {
+ current_sort->next = head;
+ head = current_sort;
+ }
+ else
+ {
+ ListNode *prev_next = prev->next;
+ prev->next = current_sort;
+ current_sort->next = prev_next;
+ }
+ }
+
+ return head;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/1470.cpp b/works/solutions/leetcode/cpp/1470.cpp new file mode 100644 index 0000000..8657dd6 --- /dev/null +++ b/works/solutions/leetcode/cpp/1470.cpp @@ -0,0 +1,23 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ vector<int> shuffle(vector<int> &nums, int n)
+ {
+ vector<int> result;
+ result.resize(nums.size());
+ auto iter = result.begin();
+ auto iter1 = nums.cbegin();
+ auto iter2 = nums.cbegin() + n;
+ for (int i = 0; i < n; i++)
+ {
+ *iter++ = *iter1++;
+ *iter++ = *iter2++;
+ }
+
+ return std::move(result);
+ }
+};
diff --git a/works/solutions/leetcode/cpp/15.cpp b/works/solutions/leetcode/cpp/15.cpp new file mode 100644 index 0000000..2b8f6cd --- /dev/null +++ b/works/solutions/leetcode/cpp/15.cpp @@ -0,0 +1,44 @@ +#include <iterator> +#include <vector> + +using std::vector; + +#include <algorithm> +#include <set> +#include <unordered_map> +#include <unordered_set> + +bool operator<(const std::vector<int> &l, std::vector<int> &r) { + return std::lexicographical_compare(l.cbegin(), l.cend(), r.cbegin(), + r.cend()); +} + +class Solution { +public: + int ha[100010]{0}; + + vector<vector<int>> threeSum(vector<int> &nums) { + std::set<std::vector<int>> result; + + if (nums.size() < 3) + return {}; + + std::unordered_map<int, int> m; + + for (auto n : nums) { + if (n >= 0) + m[n]++; + } + + for (int i = 0; i < nums.size() - 2; i++) { + for (int j = i + 1; j < nums.size() - 1; j++) { + auto v = -nums[i] - nums[j]; + if (v == 0) { + + } + } + } + + return std::vector<vector<int>>(result.cbegin(), result.cend()); + } +};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/155-2.cpp b/works/solutions/leetcode/cpp/155-2.cpp new file mode 100644 index 0000000..aa07eee --- /dev/null +++ b/works/solutions/leetcode/cpp/155-2.cpp @@ -0,0 +1,48 @@ +#include <vector>
+#include <algorithm>
+
+class MinStack
+{
+public:
+ /** initialize your data structure here. */
+ MinStack()
+ {
+ // Although I really think this is just a trick for this problem.
+ // Leetcode does not give the input size. So I just make a reasonable assumption.
+ data_.reserve(10000);
+ min_stack_.reserve(10000);
+ }
+
+ void push(int x)
+ {
+ data_.push_back(x);
+ if (min_stack_.empty())
+ {
+ min_stack_.push_back(x);
+ }
+ else
+ {
+ min_stack_.push_back(std::min(min_stack_.back(), x));
+ }
+ }
+
+ void pop()
+ {
+ data_.pop_back();
+ min_stack_.pop_back();
+ }
+
+ int top()
+ {
+ return data_.back();
+ }
+
+ int getMin()
+ {
+ return min_stack_.back();
+ }
+
+private:
+ std::vector<int> data_;
+ std::vector<int> min_stack_;
+};
diff --git a/works/solutions/leetcode/cpp/155.cpp b/works/solutions/leetcode/cpp/155.cpp new file mode 100644 index 0000000..48550be --- /dev/null +++ b/works/solutions/leetcode/cpp/155.cpp @@ -0,0 +1,38 @@ +#include <vector>
+#include <set>
+
+class MinStack
+{
+public:
+ /** initialize your data structure here. */
+ MinStack()
+ {
+ }
+
+ void push(int x)
+ {
+ data_.push_back(x);
+ sorted_data_.insert(x);
+ }
+
+ void pop()
+ {
+ const auto v = data_.back();
+ data_.pop_back();
+ sorted_data_.erase(sorted_data_.find(v));
+ }
+
+ int top()
+ {
+ return data_.back();
+ }
+
+ int getMin()
+ {
+ return *sorted_data_.cbegin();
+ }
+
+private:
+ std::vector<int> data_;
+ std::multiset<int> sorted_data_;
+};
diff --git a/works/solutions/leetcode/cpp/1609.cpp b/works/solutions/leetcode/cpp/1609.cpp new file mode 100644 index 0000000..e446c0f --- /dev/null +++ b/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 <queue>
+
+class Solution
+{
+public:
+ bool isEvenOddTree(TreeNode *root)
+ {
+ if (root == nullptr)
+ return true;
+ std::queue<TreeNode *> odd_level;
+ std::queue<TreeNode *> even_level;
+
+ even_level.push(root);
+
+ while (true)
+ {
+ if (!odd_level.empty())
+ {
+ auto node = odd_level.front();
+ odd_level.pop();
+ if (node->left)
+ even_level.push(node->left);
+ if (node->right)
+ even_level.push(node->right);
+ int last = node->val;
+ if (last % 2 != 0)
+ return false;
+
+ while (!odd_level.empty())
+ {
+ node = odd_level.front();
+ odd_level.pop();
+ if (node->left)
+ even_level.push(node->left);
+ if (node->right)
+ even_level.push(node->right);
+ int val = node->val;
+ if (val % 2 != 0)
+ return false;
+ if (val >= last)
+ return false;
+ last = val;
+ }
+
+ continue;
+ }
+
+ if (!even_level.empty())
+ {
+ auto node = even_level.front();
+ even_level.pop();
+ if (node->left)
+ odd_level.push(node->left);
+ if (node->right)
+ odd_level.push(node->right);
+ int last = node->val;
+ if (last % 2 == 0)
+ return false;
+
+ while (!even_level.empty())
+ {
+ node = even_level.front();
+ even_level.pop();
+ if (node->left)
+ odd_level.push(node->left);
+ if (node->right)
+ odd_level.push(node->right);
+ int val = node->val;
+ if (val % 2 == 0)
+ return false;
+ if (val <= last)
+ return false;
+ last = val;
+ }
+
+ continue;
+ }
+
+ break;
+ }
+
+ return true;
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/167.cpp b/works/solutions/leetcode/cpp/167.cpp new file mode 100644 index 0000000..05317b4 --- /dev/null +++ b/works/solutions/leetcode/cpp/167.cpp @@ -0,0 +1,28 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ vector<int> twoSum(vector<int> &numbers, int target)
+ {
+ int left = 0, right = numbers.size() - 1;
+ while (true)
+ {
+ const auto sum = numbers[left] + numbers[right];
+ if (sum < target)
+ {
+ left++;
+ }
+ else if (sum > target)
+ {
+ right--;
+ }
+ else
+ {
+ return {left + 1, right + 1};
+ }
+ }
+ }
+};
diff --git a/works/solutions/leetcode/cpp/17.04.cpp b/works/solutions/leetcode/cpp/17.04.cpp new file mode 100644 index 0000000..07ac7ae --- /dev/null +++ b/works/solutions/leetcode/cpp/17.04.cpp @@ -0,0 +1,21 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int missingNumber(vector<int> &nums)
+ {
+ const int size = nums.size();
+ const int sum = size * (size + 1) / 2;
+
+ int real_sum = 0;
+ for (auto i : nums)
+ {
+ real_sum += i;
+ }
+
+ return sum - real_sum;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/17.cpp b/works/solutions/leetcode/cpp/17.cpp new file mode 100644 index 0000000..74e33b4 --- /dev/null +++ b/works/solutions/leetcode/cpp/17.cpp @@ -0,0 +1,56 @@ +#include <string>
+#include <vector>
+
+using std::string;
+using std::vector;
+
+vector<char> c_map[9]{
+ {'a', 'b', 'c'},
+ {'d', 'e', 'f'},
+ {'g', 'h', 'i'},
+ {'j', 'k', 'l'},
+ {'m', 'n', 'o'},
+ {'p', 'q', 'r', 's'},
+ {'t', 'u', 'v'},
+ {'w', 'x', 'y', 'z'}};
+
+void combine(const string::const_iterator ¤t, const string::const_iterator &end, string &head, vector<string> &result)
+{
+ const auto &chars = c_map[(*current) - '2'];
+
+ if (current == end)
+ {
+ for (auto c : chars)
+ {
+ head.push_back(c);
+ result.push_back(head);
+ head.pop_back();
+ }
+ return;
+ }
+
+ for (auto c : chars)
+ {
+ head.push_back(c);
+ combine(current + 1, end, head, result);
+ head.pop_back();
+ }
+}
+
+class Solution
+{
+public:
+ vector<string> letterCombinations(string digits)
+ {
+ std::vector<string> result;
+
+ if (digits.empty())
+ return result;
+
+ std::string head;
+
+ combine(digits.cbegin(), digits.cend() - 1, head, result);
+
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/198.cpp b/works/solutions/leetcode/cpp/198.cpp new file mode 100644 index 0000000..4d9d4fc --- /dev/null +++ b/works/solutions/leetcode/cpp/198.cpp @@ -0,0 +1,26 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int rob(vector<int> &nums)
+ {
+ int count = nums.size();
+ if (count == 0)
+ return 0;
+
+ int not_rob_prev = 0;
+ int rob_prev = nums.front();
+
+ for (int i = 1; i < count; i++)
+ {
+ int not_rob_prev_cache = not_rob_prev;
+ not_rob_prev = std::max(not_rob_prev_cache, rob_prev);
+ rob_prev = std::max(not_rob_prev_cache + nums[i], not_rob_prev);
+ }
+
+ return rob_prev;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/2.cpp b/works/solutions/leetcode/cpp/2.cpp new file mode 100644 index 0000000..cb954ae --- /dev/null +++ b/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/works/solutions/leetcode/cpp/20.cpp b/works/solutions/leetcode/cpp/20.cpp new file mode 100644 index 0000000..e994e96 --- /dev/null +++ b/works/solutions/leetcode/cpp/20.cpp @@ -0,0 +1,55 @@ +#include <string>
+
+using std::string;
+
+#include <stack>
+
+class Solution
+{
+public:
+ inline static char get_companion(char c)
+ {
+ switch (c)
+ {
+ case ')':
+ return '(';
+ case ']':
+ return '[';
+ default:
+ return '{';
+ }
+ }
+
+ bool isValid(string s)
+ {
+ std::stack<char> stack;
+
+ for (const auto c : s)
+ {
+ switch (c)
+ {
+ case '(':
+ case '[':
+ case '{':
+ {
+ stack.push(c);
+ break;
+ }
+ case ')':
+ case ']':
+ default:
+ {
+ if (stack.empty())
+ return false;
+ const auto top = stack.top();
+ const char companion = get_companion(c);
+ if (top != companion)
+ return false;
+ stack.pop();
+ }
+ }
+ }
+
+ return stack.empty();
+ }
+};
diff --git a/works/solutions/leetcode/cpp/203.cpp b/works/solutions/leetcode/cpp/203.cpp new file mode 100644 index 0000000..0f1bb55 --- /dev/null +++ b/works/solutions/leetcode/cpp/203.cpp @@ -0,0 +1,48 @@ +#include <cstddef>
+
+struct ListNode
+{
+ int val;
+ ListNode *next;
+ ListNode(int x) : val(x), next(NULL) {}
+};
+
+class Solution
+{
+public:
+ ListNode *removeElements(ListNode *head, int val)
+ {
+ if (head == NULL)
+ return NULL;
+
+ ListNode *last = NULL;
+ ListNode *current = head;
+
+ while (current != NULL)
+ {
+ if (current->val == val)
+ {
+ if (last == NULL)
+ {
+ auto temp = current;
+ current = current->next;
+ head = current;
+ delete temp;
+ }
+ else
+ {
+ auto temp = current;
+ current = current->next;
+ last->next = current;
+ delete temp;
+ }
+ }
+ else
+ {
+ last = current;
+ current = current->next;
+ }
+ }
+ return head;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/213.cpp b/works/solutions/leetcode/cpp/213.cpp new file mode 100644 index 0000000..cd98f67 --- /dev/null +++ b/works/solutions/leetcode/cpp/213.cpp @@ -0,0 +1,41 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int rob(vector<int> &nums)
+ {
+ int count = nums.size();
+ if (count == 0)
+ return 0;
+
+ if (count == 1)
+ return nums.front();
+
+ int not_rob_prev = 0;
+ int rob_prev = nums.front();
+ int not_rob_prev_and_not_rob_first = 0;
+ int rob_prev_and_not_rob_first = 0;
+
+ for (int i = 1; i < count - 1; i++)
+ {
+ int not_rob_prev_cache = not_rob_prev;
+ int not_rob_prev_and_not_rob_first_cache = not_rob_prev_and_not_rob_first;
+ not_rob_prev = std::max(not_rob_prev_cache, rob_prev);
+ rob_prev = std::max(not_rob_prev_cache + nums[i], not_rob_prev);
+ not_rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache, rob_prev_and_not_rob_first);
+ rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache + nums[i], not_rob_prev_and_not_rob_first);
+ }
+
+ // last houst
+ {
+ int not_rob_prev_and_not_rob_first_cache = not_rob_prev_and_not_rob_first;
+ not_rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache, rob_prev_and_not_rob_first);
+ rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache + nums[count - 1], not_rob_prev_and_not_rob_first);
+ }
+
+ return std::max(rob_prev, rob_prev_and_not_rob_first);
+ }
+};
diff --git a/works/solutions/leetcode/cpp/22.cpp b/works/solutions/leetcode/cpp/22.cpp new file mode 100644 index 0000000..e9467f1 --- /dev/null +++ b/works/solutions/leetcode/cpp/22.cpp @@ -0,0 +1,40 @@ +#include <string>
+#include <vector>
+
+using std::string;
+using std::vector;
+
+class Solution
+{
+public:
+ static void backtrack(vector<string> &result, string ¤t, int left, int right, int count, int string_length)
+ {
+ if (current.length() == string_length)
+ {
+ result.push_back(current);
+ return;
+ }
+
+ if (left < count)
+ {
+ current.push_back('(');
+ backtrack(result, current, left + 1, right, count, string_length);
+ current.pop_back();
+ }
+
+ if (right < left)
+ {
+ current.push_back(')');
+ backtrack(result, current, left, right + 1, count, string_length);
+ current.pop_back();
+ }
+ }
+
+ vector<string> generateParenthesis(int n)
+ {
+ vector<string> result;
+ string current;
+ backtrack(result, current, 0, 0, n, n * 2);
+ return std::move(result);
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/231.cpp b/works/solutions/leetcode/cpp/231.cpp new file mode 100644 index 0000000..8861e09 --- /dev/null +++ b/works/solutions/leetcode/cpp/231.cpp @@ -0,0 +1,10 @@ +#include <bitset>
+
+class Solution {
+public:
+ bool isPowerOfTwo(int n) {
+ if (n <= 0) return false;
+ std::bitset<sizeof(n) * 8> bits(n);
+ return bits.count() == 1;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/26.cpp b/works/solutions/leetcode/cpp/26.cpp new file mode 100644 index 0000000..3ee4aa7 --- /dev/null +++ b/works/solutions/leetcode/cpp/26.cpp @@ -0,0 +1,37 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int removeDuplicates(vector<int> &nums)
+ {
+ if (nums.empty())
+ return 0;
+
+ auto iter_head = nums.cbegin();
+ auto iter = iter_head + 1;
+ int current = nums.front();
+ int count = 1;
+
+ while (iter != nums.cend())
+ {
+ const auto v = *iter;
+ if (v == current)
+ {
+ nums.erase(iter);
+ iter = iter_head + 1;
+ }
+ else
+ {
+ current = v;
+ count++;
+ iter_head = iter;
+ ++iter;
+ }
+ }
+
+ return count;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/260-2.cpp b/works/solutions/leetcode/cpp/260-2.cpp new file mode 100644 index 0000000..336d9e1 --- /dev/null +++ b/works/solutions/leetcode/cpp/260-2.cpp @@ -0,0 +1,26 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ vector<int> singleNumber(vector<int> &nums)
+ {
+ int diff = 0;
+ for (auto i : nums)
+ {
+ diff ^= i;
+ }
+
+ int mask = diff & (-diff);
+
+ int result = 0;
+ for (auto i : nums)
+ {
+ result ^= (i & mask) ? i : 0;
+ }
+
+ return {result, result ^ diff};
+ }
+};
diff --git a/works/solutions/leetcode/cpp/260.cpp b/works/solutions/leetcode/cpp/260.cpp new file mode 100644 index 0000000..5679d52 --- /dev/null +++ b/works/solutions/leetcode/cpp/260.cpp @@ -0,0 +1,23 @@ +#include <vector>
+#include <unordered_set>
+
+using std::vector;
+
+class Solution
+{
+public:
+ vector<int> singleNumber(vector<int> &nums)
+ {
+ std::unordered_set<int> s;
+ for (auto i : nums)
+ {
+ const auto result = s.find(i);
+ if (result == s.cend())
+ s.insert(i);
+ else
+ s.erase(result);
+ }
+
+ return vector<int>(s.cbegin(), s.cend());
+ }
+};
diff --git a/works/solutions/leetcode/cpp/299.cpp b/works/solutions/leetcode/cpp/299.cpp new file mode 100644 index 0000000..21c09b6 --- /dev/null +++ b/works/solutions/leetcode/cpp/299.cpp @@ -0,0 +1,44 @@ +#include <string>
+
+using std::string;
+
+class Solution
+{
+public:
+ string getHint(string secret, string guess)
+ {
+ int a = 0;
+
+ int secret_digit_count[10] = {0};
+
+ auto secret_iter = secret.cbegin();
+ auto guess_iter = guess.cbegin();
+
+ while (secret_iter != secret.cend())
+ {
+ auto secret_digit = *secret_iter;
+ auto guess_digit = *guess_iter;
+
+ secret_digit_count[secret_digit - '0']++;
+
+ if (secret_digit == guess_digit)
+ a++;
+
+ ++secret_iter;
+ ++guess_iter;
+ }
+
+ int b = 0;
+ for (auto c : guess)
+ {
+ auto digit = c - '0';
+ if (secret_digit_count[digit])
+ {
+ b++;
+ secret_digit_count[digit]--;
+ }
+ }
+
+ return std::to_string(a) + "A" + std::to_string(b - a) + "B";
+ }
+};
diff --git a/works/solutions/leetcode/cpp/303.cpp b/works/solutions/leetcode/cpp/303.cpp new file mode 100644 index 0000000..06c4ad1 --- /dev/null +++ b/works/solutions/leetcode/cpp/303.cpp @@ -0,0 +1,26 @@ +#include <vector>
+
+using std::vector;
+
+class NumArray
+{
+private:
+ vector<int> prefix_sums;
+
+public:
+ NumArray(vector<int> &nums)
+ {
+ prefix_sums.push_back(0);
+ int sum = 0;
+ for (auto num : nums)
+ {
+ sum += num;
+ prefix_sums.push_back(sum);
+ }
+ }
+
+ int sumRange(int i, int j)
+ {
+ return prefix_sums[j + 1] - prefix_sums[i];
+ }
+};
diff --git a/works/solutions/leetcode/cpp/304.cpp b/works/solutions/leetcode/cpp/304.cpp new file mode 100644 index 0000000..ab22281 --- /dev/null +++ b/works/solutions/leetcode/cpp/304.cpp @@ -0,0 +1,35 @@ +#include <vector>
+
+using std::vector;
+
+class NumMatrix {
+private:
+ std::vector<std::vector<int>> prefix_sum_;
+
+public:
+ NumMatrix(vector<vector<int>> &matrix)
+ : prefix_sum_(
+ matrix.size() + 1,
+ std::vector<int>(matrix.empty() ? 1 : matrix.front().size() + 1)) {
+ const int row_count = matrix.size();
+ const int col_count = matrix.empty() ? 0 : matrix.front().size();
+
+ for (int i = 0; i < row_count; i++)
+ for (int j = 0; j < col_count; j++) {
+ prefix_sum_[i + 1][j + 1] = prefix_sum_[i][j + 1] +
+ prefix_sum_[i + 1][j] - prefix_sum_[i][j] +
+ matrix[i][j];
+ }
+ }
+
+ int sumRegion(int row1, int col1, int row2, int col2) {
+ return prefix_sum_[row1][col1] - prefix_sum_[row2 + 1][col1] -
+ prefix_sum_[row1][col2 + 1] + prefix_sum_[row2 + 1][col2 + 1];
+ }
+};
+
+/**
+ * Your NumMatrix object will be instantiated and called as such:
+ * NumMatrix* obj = new NumMatrix(matrix);
+ * int param_1 = obj->sumRegion(row1,col1,row2,col2);
+ */
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/328.cpp b/works/solutions/leetcode/cpp/328.cpp new file mode 100644 index 0000000..de3ad0b --- /dev/null +++ b/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/works/solutions/leetcode/cpp/337.cpp b/works/solutions/leetcode/cpp/337.cpp new file mode 100644 index 0000000..655a4d0 --- /dev/null +++ b/works/solutions/leetcode/cpp/337.cpp @@ -0,0 +1,38 @@ +#include <cstddef>
+
+struct TreeNode
+{
+ int val;
+ TreeNode *left;
+ TreeNode *right;
+ TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+};
+
+struct SubTreeResult
+{
+ SubTreeResult(int use_root, int not_use_root) : use_root(use_root), not_use_root(not_use_root), max(use_root > not_use_root ? use_root : not_use_root) {}
+
+ const int use_root;
+ const int not_use_root;
+ const int max;
+};
+
+class Solution
+{
+public:
+ static SubTreeResult subtree_rob(TreeNode *root)
+ {
+ SubTreeResult left = root->left != NULL ? subtree_rob(root->left) : SubTreeResult{0, 0};
+ SubTreeResult right = root->right != NULL ? subtree_rob(root->right) : SubTreeResult{0, 0};
+ const auto use_root_value = root->val + left.not_use_root + right.not_use_root;
+ const auto not_use_root_value = left.max + right.max;
+ return SubTreeResult{use_root_value, not_use_root_value};
+ }
+
+ int rob(TreeNode *root)
+ {
+ if (root == NULL)
+ return 0;
+ return subtree_rob(root).max;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/338.cpp b/works/solutions/leetcode/cpp/338.cpp new file mode 100644 index 0000000..1758234 --- /dev/null +++ b/works/solutions/leetcode/cpp/338.cpp @@ -0,0 +1,26 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ vector<int> countBits(int num)
+ {
+ vector<int> result(num + 1);
+ result[0] = 0;
+ for (int i = 1; i <= num; i++)
+ {
+ if (i % 2 == 1)
+ {
+ result[i] = result[i - 1] + 1;
+ }
+ else
+ {
+ result[i] = result[i / 2];
+ }
+ }
+
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/343.cpp b/works/solutions/leetcode/cpp/343.cpp new file mode 100644 index 0000000..d31f7ce --- /dev/null +++ b/works/solutions/leetcode/cpp/343.cpp @@ -0,0 +1,23 @@ +#include <cmath>
+
+class Solution
+{
+public:
+ int integerBreak(int n)
+ {
+ if (n == 2)
+ return 1;
+ if (n == 3)
+ return 2;
+
+ if (n % 3 == 1)
+ {
+ return static_cast<int>(std::pow(3, n / 3 - 1)) * 4;
+ }
+ else if (n % 3 == 2)
+ {
+ return static_cast<int>(std::pow(3, n / 3)) * 2;
+ }
+ return static_cast<int>(std::pow(3, n / 3));
+ }
+};
diff --git a/works/solutions/leetcode/cpp/35.cpp b/works/solutions/leetcode/cpp/35.cpp new file mode 100644 index 0000000..7da26c4 --- /dev/null +++ b/works/solutions/leetcode/cpp/35.cpp @@ -0,0 +1,36 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int searchInsert(vector<int> &nums, int target)
+ {
+ if (nums.empty())
+ return 0;
+
+ int left_index = 0;
+ int right_index = nums.size();
+
+ while (left_index != right_index)
+ {
+ const int middle_index = (left_index + right_index) / 2;
+ const int middle_value = nums[middle_index];
+ if (target < middle_value)
+ {
+ right_index = middle_index;
+ }
+ else if (target > middle_value)
+ {
+ left_index = middle_index + 1;
+ }
+ else
+ {
+ return middle_index;
+ }
+ }
+
+ return left_index;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/371.cpp b/works/solutions/leetcode/cpp/371.cpp new file mode 100644 index 0000000..3a7bc8b --- /dev/null +++ b/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<int>(result); + } +}; diff --git a/works/solutions/leetcode/cpp/395.cpp b/works/solutions/leetcode/cpp/395.cpp new file mode 100644 index 0000000..d45eee9 --- /dev/null +++ b/works/solutions/leetcode/cpp/395.cpp @@ -0,0 +1,56 @@ +#include <array>
+#include <string>
+
+using std::string;
+
+class Solution {
+public:
+ static int dfs(const std::string &s, int start, int end, int k) {
+ if (end - start < k) {
+ return 0;
+ }
+
+ std::array<int, 26> counts{0};
+
+ for (int i = start; i < end; i++) {
+ counts[s[i] - 'a']++;
+ }
+
+ int max = -1;
+
+ for (char c = 'a'; c <= 'z'; c++) {
+ int count = counts[c - 'a'];
+
+ if (count > 0 && count < k) {
+ int sub_start = start;
+
+ for (int i = start; i < end; i++) {
+ if (s[i] == c) {
+ if (sub_start != i) {
+ max = std::max(dfs(s, sub_start, i, k), max);
+ }
+ sub_start = i + 1;
+ }
+ }
+
+ if (sub_start != end) {
+ max = std::max(dfs(s, sub_start, end, k), max);
+ }
+
+ break; // This is vital.
+ }
+ }
+
+ if (max == -1)
+ return end - start;
+ else
+ return max;
+ }
+
+ int longestSubstring(string s, int k) { return dfs(s, 0, s.size(), k); }
+};
+
+int main() {
+ Solution{}.longestSubstring("aaaaaaaaaaaabcdefghijklmnopqrstuvwzyz", 3);
+ return 0;
+}
diff --git a/works/solutions/leetcode/cpp/397.cpp b/works/solutions/leetcode/cpp/397.cpp new file mode 100644 index 0000000..bbb61ff --- /dev/null +++ b/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/works/solutions/leetcode/cpp/401.cpp b/works/solutions/leetcode/cpp/401.cpp new file mode 100644 index 0000000..71147f4 --- /dev/null +++ b/works/solutions/leetcode/cpp/401.cpp @@ -0,0 +1,57 @@ +#include <array>
+#include <string>
+#include <vector>
+
+using std::string;
+using std::vector;
+
+const std::array<int, 4> hour_digits{1, 2, 4, 8};
+const std::array<int, 6> minute_digits{1, 2, 4, 8, 16, 32};
+
+class Solution {
+public:
+ template <int max, std::size_t size>
+ void dfs(const std::array<int, size> &digits, int total_count, int rest_count,
+ int start_index, int value, std::vector<int> &result) {
+
+ if (value >= max)
+ return;
+
+ if (rest_count == 0) {
+ result.push_back(value);
+ return;
+ }
+
+ for (int i = start_index; i <= size - rest_count; i++) {
+ dfs<max, size>(digits, total_count, rest_count - 1, i + 1,
+ value + digits[i], result);
+ }
+ }
+
+ vector<string> readBinaryWatch(int num) {
+ vector<string> results;
+
+ for (int i = (num > 6 ? num - 6 : 0); i <= (num > 4 ? 4 : num); i++) {
+ std::vector<int> hours;
+ std::vector<int> minutes;
+ if (i == 0)
+ hours = {0};
+ else
+ dfs<12>(hour_digits, i, i, 0, 0, hours);
+ if (i == num)
+ minutes = {0};
+ else
+ dfs<60>(minute_digits, num - i, num - i, 0, 0, minutes);
+
+ for (auto hour : hours) {
+ for (auto minute : minutes) {
+ char buffer[6];
+ sprintf(buffer, "%d:%02d", hour, minute);
+ results.push_back(string(buffer));
+ }
+ }
+ }
+
+ return results;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/46.cpp b/works/solutions/leetcode/cpp/46.cpp new file mode 100644 index 0000000..bfb3c83 --- /dev/null +++ b/works/solutions/leetcode/cpp/46.cpp @@ -0,0 +1,34 @@ +#include <vector> + +using std::vector; + +class Solution { +public: + void dfs(const vector<int> &nums, vector<int> ¤t, bool *num_used, + vector<vector<int>> &result) { + if (current.size() == nums.size()) { + result.push_back(current); + return; + } + + for (int i = 0; i < nums.size(); i++) { + if (!num_used[i]) { + num_used[i] = true; + current.push_back(nums[i]); + dfs(nums, current, num_used, result); + current.pop_back(); + num_used[i] = false; + } + } + } + + vector<vector<int>> permute(vector<int> &nums) { + vector<int> current; + vector<vector<int>> result; + bool *num_used = new bool[nums.size()]{false}; + dfs(nums, current, num_used, result); + delete[] num_used; + + return result; + } +}; diff --git a/works/solutions/leetcode/cpp/47.cpp b/works/solutions/leetcode/cpp/47.cpp new file mode 100644 index 0000000..4a109ea --- /dev/null +++ b/works/solutions/leetcode/cpp/47.cpp @@ -0,0 +1,45 @@ +#include <vector> +#include <set> + +using std::vector; + +class Solution { +public: + + void DFS(int length, const std::vector<int>& nums, std::vector<int>& visited, std::vector<int>& current, std::vector<std::vector<int>>& result) { + if (length == 0) { + result.push_back(current); + } + + int used[21] {0}; + + int size = nums.size(); + + for (int i = 0; i < size; i++) { + if (visited[i]) { + continue; + } + + visited[i] = 1; + + int num = nums[i]; + + if (!used[num + 10]) { + current.push_back(nums[i]); + DFS(length - 1, nums, visited, current, result); + current.pop_back(); + used[num + 10] = 1; + } + + visited[i] = 0; + } + } + + vector<vector<int>> permuteUnique(vector<int>& nums) { + std::vector<int> visited(nums.size()); + std::vector<int> current; + std::vector<std::vector<int>> result; + DFS(nums.size(),nums, visited, current, result); + return result; + } +};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/495.cpp b/works/solutions/leetcode/cpp/495.cpp new file mode 100644 index 0000000..c940b0b --- /dev/null +++ b/works/solutions/leetcode/cpp/495.cpp @@ -0,0 +1,37 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int findPoisonedDuration(vector<int> &timeSeries, int duration)
+ {
+ if (timeSeries.empty())
+ return 0;
+
+ int total_time = 0;
+
+ int start_time = timeSeries.front();
+ int expected_end_time = start_time + duration;
+
+ for (auto iter = timeSeries.cbegin() + 1; iter != timeSeries.cend(); ++iter)
+ {
+ const auto this_time = *iter;
+ if (this_time <= expected_end_time)
+ {
+ expected_end_time = this_time + duration;
+ }
+ else
+ {
+ total_time += expected_end_time - start_time;
+ start_time = this_time;
+ expected_end_time = this_time + duration;
+ }
+ }
+
+ total_time += expected_end_time - start_time;
+
+ return total_time;
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/5.cpp b/works/solutions/leetcode/cpp/5.cpp new file mode 100644 index 0000000..6200c4c --- /dev/null +++ b/works/solutions/leetcode/cpp/5.cpp @@ -0,0 +1,104 @@ +#include <string>
+
+using std::string;
+
+class Solution
+{
+public:
+ void longestWithCenter(const string &s, int length, int index, int *longest_start, int *longest_length_ptr)
+ {
+ int &longest_length = *longest_length_ptr;
+
+ int palindrome_length_odd = index * 2 + 1 <= longest_length || (length - index - 1) * 2 + 1 <= longest_length ? 0 : 1;
+ int palindrome_length_even = (index + 1) * 2 <= longest_length || (length - index - 1) * 2 <= longest_length ? 0 : 1;
+
+ while (palindrome_length_odd || palindrome_length_even)
+ {
+ if (palindrome_length_odd)
+ {
+ int start = index - palindrome_length_odd;
+ int end = index + palindrome_length_odd;
+ if (start < 0)
+ {
+ palindrome_length_odd = 0;
+ }
+ else if (end >= length)
+ {
+ palindrome_length_odd = 0;
+ }
+ else
+ {
+ if (s[start] == s[end])
+ {
+ int current_length = end - start + 1;
+ if (current_length > longest_length)
+ {
+ *longest_start = start;
+ longest_length = current_length;
+ }
+ palindrome_length_odd++;
+ }
+ else
+ {
+ palindrome_length_odd = 0;
+ }
+ }
+ }
+
+ if (palindrome_length_even)
+ {
+ int start = index - palindrome_length_even + 1;
+ int end = index + palindrome_length_even;
+ if (start < 0)
+ {
+ palindrome_length_even = 0;
+ }
+ else if (end >= length)
+ {
+ palindrome_length_even = 0;
+ }
+ else
+ {
+ if (s[start] == s[end])
+ {
+ int current_length = end - start + 1;
+ if (current_length > longest_length)
+ {
+ *longest_start = start;
+ longest_length = current_length;
+ }
+ palindrome_length_even++;
+ }
+ else
+ {
+ palindrome_length_even = 0;
+ }
+ }
+ }
+ }
+ }
+
+ string longestPalindrome(string s)
+ {
+ if (s.empty())
+ return "";
+
+ int longest_start = 0;
+ int longest_length = 1;
+ int length = s.size();
+
+ for (int i = 0; i < length; i++)
+ {
+ longestWithCenter(s, length, i, &longest_start, &longest_length);
+ }
+
+ return s.substr(longest_start, longest_length);
+ }
+};
+
+int main()
+{
+ Solution s{};
+ s.longestPalindrome("bb");
+ return 0;
+}
diff --git a/works/solutions/leetcode/cpp/501.cpp b/works/solutions/leetcode/cpp/501.cpp new file mode 100644 index 0000000..197ed10 --- /dev/null +++ b/works/solutions/leetcode/cpp/501.cpp @@ -0,0 +1,58 @@ +#include <cstddef> +#include <vector> + +using std::vector; + +struct TreeNode +{ + int val; + TreeNode *left; + TreeNode *right; + TreeNode(int x) : val(x), left(NULL), right(NULL) {} +}; + +class Solution +{ +public: + void dfs(TreeNode *node, int &last, int &count, int &max_count, vector<int> &result) + { + if (node == nullptr) + return; + + dfs(node->left, last, count, max_count, result); + + auto current = node->val; + if (current == last) + { + count += 1; + } + else + { + count = 1; + } + + if (count == max_count) + { + result.push_back(current); + } + else if (count > max_count) + { + max_count = count; + result.clear(); + result.push_back(current); + } + + last = current; + dfs(node->right, last, count, max_count, result); + } + + vector<int> findMode(TreeNode *root) + { + if (root == nullptr) + return {}; + int last = 0, count = 0, max_count = 0; + vector<int> result; + dfs(root, last, count, max_count, result); + return result; + } +}; diff --git a/works/solutions/leetcode/cpp/526.cpp b/works/solutions/leetcode/cpp/526.cpp new file mode 100644 index 0000000..19f445f --- /dev/null +++ b/works/solutions/leetcode/cpp/526.cpp @@ -0,0 +1,29 @@ +#include <vector> + +using std::vector; + +class Solution { +public: + void dfs(int N, int index, bool *num_used, int &result) { + if (index > N) { + result += 1; + return; + } + + for (int num = 1; num <= N; num++) { + if (!num_used[num] && (num % index == 0 || index % num == 0)) { + num_used[num] = true; + dfs(N, index + 1, num_used, result); + num_used[num] = false; + } + } + } + + int countArrangement(int N) { + bool *num_used = new bool[N + 1]{false}; + int result = 0; + dfs(N, 1, num_used, result); + delete[] num_used; + return result; + } +}; diff --git a/works/solutions/leetcode/cpp/543.cpp b/works/solutions/leetcode/cpp/543.cpp new file mode 100644 index 0000000..f782521 --- /dev/null +++ b/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 <algorithm>
+
+class Solution {
+public:
+ int diameterOfBinaryTree(TreeNode *root) {
+ int max = 0;
+ depth(root, max);
+ return max;
+ }
+
+ static int depth(TreeNode *root, int &max) {
+ if (root == nullptr)
+ return -1;
+
+ auto left = depth(root->left, max) + 1;
+ auto right = depth(root->right, max) + 1;
+
+ auto current_max = left + right;
+ if (current_max > max) {
+ max = current_max;
+ }
+
+ return std::max(left, right);
+ }
+};
diff --git a/works/solutions/leetcode/cpp/55.cpp b/works/solutions/leetcode/cpp/55.cpp new file mode 100644 index 0000000..d2c2600 --- /dev/null +++ b/works/solutions/leetcode/cpp/55.cpp @@ -0,0 +1,29 @@ +#include <vector>
+
+using std::vector;
+
+#include <algorithm>
+
+class Solution
+{
+public:
+ bool canJump(vector<int> &nums)
+ {
+ int max = 0;
+ const int size = nums.size();
+ for (int i = 0; i < size; i++)
+ {
+ if (i <= max)
+ {
+ max = std::max(max, i + nums[i]);
+ if (max >= size - 1)
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ return false;
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/6.cpp b/works/solutions/leetcode/cpp/6.cpp new file mode 100644 index 0000000..f1d947c --- /dev/null +++ b/works/solutions/leetcode/cpp/6.cpp @@ -0,0 +1,56 @@ +#include <string>
+#include <iostream>
+
+using std::string;
+
+class Solution
+{
+public:
+ string convert(string s, int numRows)
+ {
+ if (numRows == 1)
+ return s;
+
+ const auto length = s.size();
+ const int count_per_group = numRows * 2 - 2;
+ string result;
+ result.reserve(length);
+ for (int row = 0; row < numRows; row++)
+ {
+ if (row == 0)
+ {
+ for (int p = 0; p < length; p += count_per_group)
+ result += s[p];
+ }
+ else if (row == numRows - 1)
+ {
+ for (int p = row; p < length; p += count_per_group)
+ result += s[p];
+ }
+ else
+ {
+ bool former = true;
+ const auto former_gap = count_per_group - row * 2;
+ const auto latter_gap = count_per_group - former_gap;
+ for (int p = row; p < length; p += (former ? former_gap : latter_gap), former = !former)
+ result += s[p];
+ }
+ }
+ return result;
+ }
+};
+
+int main()
+{
+ Solution s;
+
+ auto result1 = s.convert("PAYPALISHIRING", 3);
+ auto result2 = s.convert("PAYPALISHIRING", 4);
+ std::cout
+ << s.convert("A", 1) << '\n'
+ << result1 << '\n'
+ << "PAHNAPLSIIGYIR\n"
+ << result2 << '\n'
+ << "PINALSIGYAHRPI\n";
+ return 0;
+}
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/60.cpp b/works/solutions/leetcode/cpp/60.cpp new file mode 100644 index 0000000..f090355 --- /dev/null +++ b/works/solutions/leetcode/cpp/60.cpp @@ -0,0 +1,44 @@ +#include <string>
+#include <vector>
+
+using std::string;
+
+class Solution
+{
+public:
+ string getPermutation(int n, int k)
+ {
+ k--;
+
+ string result;
+ result.reserve(n);
+
+ std::vector<char> nums;
+ nums.reserve(n);
+
+ for (int i = 1; i <= n; i++)
+ {
+ nums.push_back(i + '0');
+ }
+
+ n--;
+ int fac = 1;
+ for (int i = 2; i <= n; i++)
+ {
+ fac *= i;
+ }
+
+ while (n > 0)
+ {
+ const int index = k / fac;
+ k = k % fac;
+ result += nums[index];
+ nums.erase(nums.cbegin() + index);
+ fac /= n--;
+ }
+
+ result += nums.front();
+
+ return result;
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/62.cpp b/works/solutions/leetcode/cpp/62.cpp new file mode 100644 index 0000000..744a0d3 --- /dev/null +++ b/works/solutions/leetcode/cpp/62.cpp @@ -0,0 +1,25 @@ +#include <utility>
+
+class Solution
+{
+public:
+ // C(m + n - 2, m - 1)
+ int uniquePaths(int m, int n)
+ {
+ if (m < n)
+ std::swap(m, n);
+
+ long long result = 1;
+ for (int i = m; i <= m + n - 2; i++)
+ {
+ result *= i;
+ }
+
+ for (int i = 2; i <= n - 1; i++)
+ {
+ result /= i;
+ }
+
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/63.cpp b/works/solutions/leetcode/cpp/63.cpp new file mode 100644 index 0000000..ed07bdc --- /dev/null +++ b/works/solutions/leetcode/cpp/63.cpp @@ -0,0 +1,44 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
+ {
+ if (obstacleGrid[0][0])
+ return 0;
+ obstacleGrid[0][0] = 1;
+
+ int row = obstacleGrid.size();
+ int col = obstacleGrid.front().size();
+
+ for (int i = 1; i < row; i++)
+ {
+ obstacleGrid[i][0] = obstacleGrid[i - 1][0] && !obstacleGrid[i][0] ? 1 : 0;
+ }
+
+ for (int i = 1; i < col; i++)
+ {
+ obstacleGrid[0][i] = obstacleGrid[0][i - 1] && !obstacleGrid[0][i] ? 1 : 0;
+ }
+
+ for (int r = 1; r < row; r++)
+ {
+ for (int c = 1; c < col; c++)
+ {
+ if (obstacleGrid[r][c])
+ {
+ obstacleGrid[r][c] = 0;
+ }
+ else
+ {
+ obstacleGrid[r][c] = obstacleGrid[r - 1][c] + obstacleGrid[r][c - 1];
+ }
+ }
+ }
+
+ return obstacleGrid[row - 1][col - 1];
+ }
+};
diff --git a/works/solutions/leetcode/cpp/639.cpp b/works/solutions/leetcode/cpp/639.cpp new file mode 100644 index 0000000..ead252e --- /dev/null +++ b/works/solutions/leetcode/cpp/639.cpp @@ -0,0 +1,56 @@ +#include <string> + +using std::string; + +const long long M = 1e9 + 7; + +class Solution { +public: + long long f[100010]{0}; + + int numDecodings(string s) { + f[0] = 1; + if (s.front() == '*') { + f[1] = 9; + } else if (s.front() == '0') { + f[1] = 0; + } else { + f[1] = 1; + } + + for (int i = 2; i <= s.size(); i++) { + char c = s[i - 1], l = s[i - 2]; + if (c == '*') { + f[i] += f[i - 1] * 9; + if (l == '*') { + f[i] += f[i - 2] * 15; + } else if (l == '1') { + f[i] += f[i - 2] * 9; + } else if (l == '2') { + f[i] += f[i - 2] * 6; + } + f[i] %= M; + } else if (c == '0') { + if (l == '1' || l == '2') + f[i] += f[i - 2]; + else if (l == '*') + f[i] += f[i - 2] * 2; + f[i] %= M; + } else { + f[i] += f[i - 1]; + if (l == '*') { + if (c <= '6') + f[i] += f[i - 2] * 2; + else + f[i] += f[i - 2]; + } else if (l == '1') + f[i] += f[i - 2]; + else if (l == '2' && c <= '6') + f[i] += f[i - 2]; + f[i] %= M; + } + } + + return f[s.size()] % M; + } +}; diff --git a/works/solutions/leetcode/cpp/641.cpp b/works/solutions/leetcode/cpp/641.cpp new file mode 100644 index 0000000..0235797 --- /dev/null +++ b/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/works/solutions/leetcode/cpp/649.cpp b/works/solutions/leetcode/cpp/649.cpp new file mode 100644 index 0000000..ab702d2 --- /dev/null +++ b/works/solutions/leetcode/cpp/649.cpp @@ -0,0 +1,67 @@ +#include <string>
+
+using std::string;
+
+#include <queue>
+
+class Solution
+{
+public:
+ string predictPartyVictory(string senate)
+ {
+ std::queue<bool> queue;
+
+ int r_people = 0;
+ int d_people = 0;
+ int r_ban = 0;
+ int d_ban = 0;
+
+ for (auto i = senate.cbegin(); i != senate.cend(); ++i)
+ {
+ if (*i == 'R')
+ {
+ r_people += 1;
+ queue.push(true);
+ }
+ else
+ {
+ d_people += 1;
+ queue.push(false);
+ }
+ }
+
+ while (r_people && d_people)
+ {
+ bool is_r = queue.front();
+ queue.pop();
+ if (is_r)
+ {
+ if (d_ban)
+ {
+ r_people -= 1;
+ d_ban -= 1;
+ }
+ else
+ {
+ r_ban += 1;
+ queue.push(is_r);
+ }
+ }
+ else
+ {
+ if (r_ban)
+ {
+ d_people -= 1;
+ r_ban -= 1;
+ }
+ else
+ {
+ d_ban += 1;
+ queue.push(is_r);
+ }
+ }
+ }
+
+ return r_people ? "Radiant" : "Dire";
+ }
+};
diff --git a/works/solutions/leetcode/cpp/66.cpp b/works/solutions/leetcode/cpp/66.cpp new file mode 100644 index 0000000..40ce008 --- /dev/null +++ b/works/solutions/leetcode/cpp/66.cpp @@ -0,0 +1,34 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ vector<int> plusOne(vector<int> &digits)
+ {
+ bool carry = true;
+ const auto end = digits.rend();
+ for (auto iter = digits.rbegin(); carry && iter != end; ++iter)
+ {
+ auto &digit = *iter;
+ digit += 1;
+ if (digit == 10)
+ {
+ digit = 0;
+ carry = true;
+ }
+ else
+ {
+ carry = false;
+ }
+ }
+
+ if (carry)
+ {
+ digits.insert(digits.cbegin(), 1);
+ }
+
+ return digits;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/680.cpp b/works/solutions/leetcode/cpp/680.cpp new file mode 100644 index 0000000..21d150f --- /dev/null +++ b/works/solutions/leetcode/cpp/680.cpp @@ -0,0 +1,35 @@ +#include <string>
+
+using std::string;
+
+bool strict_palindrome(string::const_iterator left, string::const_iterator right)
+{
+ while (left < right)
+ {
+ if (*left != *right)
+ return false;
+ ++left;
+ --right;
+ }
+ return true;
+}
+
+class Solution
+{
+public:
+ bool validPalindrome(string s)
+ {
+ string::const_iterator left = s.cbegin();
+ string::const_iterator right = s.cend() - 1;
+
+ while (left < right)
+ {
+ if (*left != *right)
+ return strict_palindrome(left, right - 1) || strict_palindrome(left + 1, right);
+
+ ++left;
+ --right;
+ }
+ return true;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/69.c b/works/solutions/leetcode/cpp/69.c new file mode 100644 index 0000000..9914fff --- /dev/null +++ b/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/works/solutions/leetcode/cpp/7.cpp b/works/solutions/leetcode/cpp/7.cpp new file mode 100644 index 0000000..a1a05c1 --- /dev/null +++ b/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/works/solutions/leetcode/cpp/704.cpp b/works/solutions/leetcode/cpp/704.cpp new file mode 100644 index 0000000..b56a01a --- /dev/null +++ b/works/solutions/leetcode/cpp/704.cpp @@ -0,0 +1,79 @@ +#include <vector>
+#include <memory>
+
+class MyHashSet
+{
+ static const int max = 100;
+
+private:
+ std::unique_ptr<std::vector<int>> data_[max];
+
+public:
+ /** Initialize your data structure here. */
+ MyHashSet()
+ {
+ }
+
+ void add(int key)
+ {
+ const auto index = key % max;
+ auto &ptr = data_[index];
+ if (ptr == nullptr)
+ {
+ ptr.reset(new std::vector<int>());
+ }
+
+ auto &v = *ptr;
+ for (auto d : v)
+ {
+ if (d == key)
+ return;
+ }
+
+ v.push_back(key);
+ }
+
+ void remove(int key)
+ {
+ const auto index = key % max;
+ auto &ptr = data_[index];
+ if (ptr == nullptr)
+ return;
+ auto &v = *ptr;
+ const auto end = v.cend();
+ for (auto iter = v.cbegin(); iter != end; ++iter)
+ {
+ if (*iter == key)
+ {
+ v.erase(iter);
+ return;
+ }
+ }
+ }
+
+ /** Returns true if this set contains the specified element */
+ bool contains(int key)
+ {
+ const auto index = key % max;
+ auto &ptr = data_[index];
+ if (ptr == nullptr)
+ return false;
+
+ const auto &v = *ptr;
+ for (auto d : v)
+ {
+ if (d == key)
+ return true;
+ }
+
+ return false;
+ }
+};
+
+/**
+ * Your MyHashSet object will be instantiated and called as such:
+ * MyHashSet* obj = new MyHashSet();
+ * obj->add(key);
+ * obj->remove(key);
+ * bool param_3 = obj->contains(key);
+ */
diff --git a/works/solutions/leetcode/cpp/74.cpp b/works/solutions/leetcode/cpp/74.cpp new file mode 100644 index 0000000..08560ef --- /dev/null +++ b/works/solutions/leetcode/cpp/74.cpp @@ -0,0 +1,63 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ bool searchMatrix(vector<vector<int>> &matrix, int target)
+ {
+ if (matrix.empty() || matrix.front().empty())
+ return false;
+
+ int top_row = 0;
+ int bottom_row = matrix.size() - 1;
+ while (top_row != bottom_row)
+ {
+ const int middle_row = (top_row + bottom_row) / 2;
+ const int middle_row_p1 = middle_row + 1;
+ const int middle_p1_row_front = matrix[middle_row_p1].front();
+ if (middle_p1_row_front > target)
+ {
+ bottom_row = middle_row;
+ }
+ else if (middle_p1_row_front < target)
+ {
+ top_row = middle_row_p1;
+ }
+ else if (middle_p1_row_front == target)
+ {
+ return true;
+ }
+ }
+
+ const vector<int> &row = matrix[top_row];
+
+ if (row.size() == 1)
+ {
+ return row.front() == target;
+ }
+
+ int left = 0;
+ int right = row.size() - 1;
+
+ while (left != right)
+ {
+ const int middle = (left + right) / 2;
+ const int middle_value = row[middle];
+ if (middle_value == target)
+ {
+ return true;
+ }
+ else if (middle_value < target)
+ {
+ left = middle + 1;
+ }
+ else
+ {
+ right = middle;
+ }
+ }
+ return row[left] == target;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/746.cpp b/works/solutions/leetcode/cpp/746.cpp new file mode 100644 index 0000000..72ffd9f --- /dev/null +++ b/works/solutions/leetcode/cpp/746.cpp @@ -0,0 +1,35 @@ +#include <vector>
+
+using std::vector;
+
+#include <algorithm>
+
+class Solution
+{
+public:
+ int minCostClimbingStairs(vector<int> &cost)
+ {
+ int count = cost.size();
+
+ // Total cost for index i means min cost of stepping through the number i stair,
+ // after which you are free to jump two or one stair.
+ // total_costs[i] is based on total_costs[i - 2] and total_costs[i - 1].
+ // Note:
+ // This is not min cost to step above the number i stair, which has no simple dependency
+ // relationship because based on whether it steps through the last step there are two situation.
+ // However with the restriction of stepping through that last stair, there is a
+ // dependency relationship. And we can easily get the final result by comparing total_costs[count - 2]
+ // and total_costs[count - 1]. But not just use total_costs[count - 1].
+ vector<int> total_costs(count);
+
+ total_costs[0] = cost[0];
+ total_costs[1] = cost[1];
+
+ for (int i = 2; i < count; i++)
+ {
+ total_costs[i] = std::min(total_costs[i - 2], total_costs[i - 1]) + cost[i];
+ }
+
+ return std::min(total_costs[count - 2], total_costs[count - 1]);
+ }
+};
diff --git a/works/solutions/leetcode/cpp/766-2.cpp b/works/solutions/leetcode/cpp/766-2.cpp new file mode 100644 index 0000000..79a0cc8 --- /dev/null +++ b/works/solutions/leetcode/cpp/766-2.cpp @@ -0,0 +1,20 @@ +#include <vector>
+
+using std::vector;
+
+class Solution {
+public:
+ bool isToeplitzMatrix(vector<vector<int>> &matrix) {
+ int row_count = matrix.size();
+ int col_count = matrix.front().size();
+
+ for (int i = 1; i < row_count; i++) {
+ for (int j = 1; j < col_count; j++) {
+ if (matrix[i][j] != matrix[i - 1][j - 1])
+ return false;
+ }
+ }
+
+ return true;
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/766.cpp b/works/solutions/leetcode/cpp/766.cpp new file mode 100644 index 0000000..3e8a015 --- /dev/null +++ b/works/solutions/leetcode/cpp/766.cpp @@ -0,0 +1,44 @@ +#include <algorithm>
+#include <vector>
+
+using std::vector;
+
+class Solution {
+public:
+ bool isToeplitzMatrix(vector<vector<int>> &matrix) {
+ int row_count = matrix.size();
+ int col_count = matrix.front().size();
+
+ if (matrix.size() == 1)
+ return true;
+ if (matrix.front().size() == 1)
+ return true;
+
+ // offset = col - row
+ // max(offset) = row_count - 2
+ // min(offset) = -(col_count - 2)
+ for (int offset = -(col_count - 2); offset <= (row_count - 2); offset++) {
+ int row, col;
+ if (offset >= 0) {
+ row = offset;
+ col = 0;
+ } else {
+ row = 0;
+ col = -offset;
+ }
+
+ int value = matrix[row][col];
+ row++;
+ col++;
+
+ while (row < row_count && col < col_count) {
+ if (matrix[row][col] != value) {
+ return false;
+ }
+ row++;
+ col++;
+ }
+ }
+ return true;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/77.cpp b/works/solutions/leetcode/cpp/77.cpp new file mode 100644 index 0000000..ec09198 --- /dev/null +++ b/works/solutions/leetcode/cpp/77.cpp @@ -0,0 +1,45 @@ +#include <vector>
+
+using std::vector;
+
+void combine1(int start, int end, int rest_select_count, vector<int> &head, vector<vector<int>> &result)
+{
+ if (rest_select_count == 0)
+ {
+ for (int i = start; i < end; i++)
+ {
+ head.push_back(i);
+ result.push_back(head);
+ head.pop_back();
+ }
+ return;
+ }
+
+ for (int i = start; i < end - rest_select_count; i++)
+ {
+ head.push_back(i);
+ combine1(i + 1, end, rest_select_count - 1, head, result);
+ head.pop_back();
+ }
+}
+
+class Solution
+{
+public:
+ vector<vector<int>> combine(int n, int k)
+ {
+ vector<vector<int>> result;
+
+ vector<int> head;
+ combine1(1, 1 + n, k - 1, head, result);
+
+ return result;
+ }
+};
+
+int main()
+{
+ Solution s;
+ auto result = s.combine(20, 16);
+ return 0;
+}
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/832.cpp b/works/solutions/leetcode/cpp/832.cpp new file mode 100644 index 0000000..000fb94 --- /dev/null +++ b/works/solutions/leetcode/cpp/832.cpp @@ -0,0 +1,20 @@ +#include <vector>
+
+using std::vector;
+
+class Solution {
+public:
+ vector<vector<int>> flipAndInvertImage(vector<vector<int>> &A) {
+ const int row_count = A.size();
+ const int col_count = A.front().size();
+ std::vector<std::vector<int>> result(row_count,
+ std::vector<int>(col_count));
+ for (int i = 0; i < row_count; i++) {
+ for (int j = 0; j < col_count; j++) {
+ result[i][j] = !A[i][col_count - j - 1];
+ }
+ }
+
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/86.cpp b/works/solutions/leetcode/cpp/86.cpp new file mode 100644 index 0000000..1f7568c --- /dev/null +++ b/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/works/solutions/leetcode/cpp/865.cpp b/works/solutions/leetcode/cpp/865.cpp new file mode 100644 index 0000000..8981a02 --- /dev/null +++ b/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 <unordered_set>
+
+class Solution
+{
+public:
+ int max_depth = -1;
+ std::unordered_set<TreeNode *> deepest_nodes;
+
+ void record_depth(TreeNode *root, int depth)
+ {
+ if (depth > max_depth)
+ {
+ max_depth = depth;
+ deepest_nodes.clear();
+ }
+
+ if (depth == max_depth)
+ deepest_nodes.insert(root);
+
+ if (root->left != nullptr)
+ record_depth(root->left, depth + 1);
+ if (root->right != nullptr)
+ record_depth(root->right, depth + 1);
+ }
+
+ TreeNode *find_common_ancestor(TreeNode *root)
+ {
+ if (root == nullptr)
+ return nullptr;
+ if (deepest_nodes.find(root) != deepest_nodes.cend())
+ return root;
+
+ auto left = find_common_ancestor(root->left);
+ auto right = find_common_ancestor(root->right);
+
+ if (left != nullptr && right != nullptr)
+ return root;
+ if (left != nullptr)
+ return left;
+ if (right != nullptr)
+ return right;
+ return nullptr;
+ }
+
+ TreeNode *subtreeWithAllDeepest(TreeNode *root)
+ {
+ record_depth(root, 0);
+ return find_common_ancestor(root);
+ }
+};
diff --git a/works/solutions/leetcode/cpp/867.cpp b/works/solutions/leetcode/cpp/867.cpp new file mode 100644 index 0000000..9efd176 --- /dev/null +++ b/works/solutions/leetcode/cpp/867.cpp @@ -0,0 +1,20 @@ +#include <vector>
+
+using std::vector;
+
+class Solution {
+public:
+ vector<vector<int>> transpose(vector<vector<int>> &matrix) {
+ const int row_count = matrix.size();
+ const int col_count = matrix.front().size();
+
+ vector<vector<int>> result(col_count, std::vector<int>(row_count));
+
+ for (int i = 0; i < row_count; i++)
+ for (int j = 0; j < col_count; j++) {
+ result[j][i] = matrix[i][j];
+ }
+
+ return result;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/896.cpp b/works/solutions/leetcode/cpp/896.cpp new file mode 100644 index 0000000..25bd528 --- /dev/null +++ b/works/solutions/leetcode/cpp/896.cpp @@ -0,0 +1,35 @@ +#include <vector>
+
+using std::vector;
+
+enum Order { Ascend, Descend, Unknown };
+
+class Solution {
+public:
+ bool isMonotonic(vector<int> &A) {
+ Order order = Unknown;
+
+ int count = A.size();
+ for (int i = 1; i < count; i++) {
+ int last = A[i - 1];
+ int current = A[i];
+ if (order == Unknown) {
+ if (current > last) {
+ order = Ascend;
+ } else if (current < last) {
+ order = Descend;
+ }
+ } else if (order == Ascend) {
+ if (last > current) {
+ return false;
+ }
+ } else {
+ if (last < current) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/897.cpp b/works/solutions/leetcode/cpp/897.cpp new file mode 100644 index 0000000..efc9741 --- /dev/null +++ b/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<TreeNode*> result;
+
+ void InOrderTraverse(TreeNode* root) {
+ if (root->left != nullptr)
+ InOrderTraverse(root->left);
+ result.push_back(root);
+ if (root->right != nullptr)
+ InOrderTraverse(root->right);
+ }
+
+ TreeNode* increasingBST(TreeNode* root) {
+ InOrderTraverse(root);
+
+ const auto end = result.end();
+ auto iter1 = result.begin();
+ auto iter2 = result.begin() + 1;
+ for (; iter2 != end; ++iter1, ++iter2) {
+ const auto node = *iter1;
+ node->left = NULL;
+ node->right = *iter2;
+ }
+ (*iter1)->left = (*iter1)->right = NULL;
+
+ return result.front();
+ }
+};
diff --git a/works/solutions/leetcode/cpp/917.cpp b/works/solutions/leetcode/cpp/917.cpp new file mode 100644 index 0000000..d01d795 --- /dev/null +++ b/works/solutions/leetcode/cpp/917.cpp @@ -0,0 +1,45 @@ +#include <string>
+#include <cctype>
+#include <utility>
+
+using std::string;
+
+class Solution
+{
+public:
+ string reverseOnlyLetters(string s)
+ {
+ if (s.empty())
+ return s;
+
+ auto front = s.rend();
+ auto back = s.end();
+
+ bool move_front = true;
+ while (true)
+ {
+ if (move_front)
+ {
+ if (std::isalpha(*--front))
+ {
+ move_front = false;
+ }
+ }
+ else
+ {
+ if (std::isalpha(*--back))
+ {
+ std::swap(*front, *back);
+ move_front = true;
+ }
+ }
+
+ if (front.base() == back)
+ {
+ break;
+ }
+ }
+
+ return s;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/96.cpp b/works/solutions/leetcode/cpp/96.cpp new file mode 100644 index 0000000..3757baa --- /dev/null +++ b/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/works/solutions/leetcode/cpp/965.cpp b/works/solutions/leetcode/cpp/965.cpp new file mode 100644 index 0000000..fd2bff6 --- /dev/null +++ b/works/solutions/leetcode/cpp/965.cpp @@ -0,0 +1,29 @@ +#include <cstddef>
+
+struct TreeNode
+{
+ int val;
+ TreeNode *left;
+ TreeNode *right;
+ TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+};
+
+class Solution
+{
+public:
+ static bool traverse(TreeNode *root, int val)
+ {
+ if (root == NULL)
+ return true;
+ if (root->val != val)
+ return false;
+ return traverse(root->left, root->val) && traverse(root->right, root->val);
+ }
+
+ bool isUnivalTree(TreeNode *root)
+ {
+ if (root == NULL)
+ return true;
+ return traverse(root, root->val);
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/968.cpp b/works/solutions/leetcode/cpp/968.cpp new file mode 100644 index 0000000..c9e6b24 --- /dev/null +++ b/works/solutions/leetcode/cpp/968.cpp @@ -0,0 +1,63 @@ +#include <cstddef>
+
+struct TreeNode
+{
+ int val;
+ TreeNode *left;
+ TreeNode *right;
+ TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+};
+
+#include <algorithm>
+
+struct Result
+{
+ // root_camera >= root_monitored >= root_not_monitored
+ int root_camera;
+ int root_monitored;
+ int root_not_monitored;
+};
+
+class Solution
+{
+public:
+ Result dfs(TreeNode *root)
+ {
+ if (root->left == nullptr && root->right == nullptr)
+ {
+ return Result{1, 1, 0};
+ }
+
+ if (root->left == nullptr || root->right == nullptr)
+ {
+ TreeNode *child_node = root->left == nullptr ? root->right : root->left;
+ Result child = dfs(child_node);
+
+ int root_camera = 1 + child.root_not_monitored;
+ int root_monitored = std::min({child.root_camera,
+ root_camera});
+ int root_not_monitored = std::min(child.root_monitored, root_monitored);
+
+ return Result{
+ root_camera, root_monitored, root_not_monitored};
+ }
+
+ Result left = dfs(root->left);
+ Result right = dfs(root->right);
+
+ int root_camera = 1 + left.root_not_monitored + right.root_not_monitored;
+ int root_monitored = std::min({left.root_camera + right.root_monitored,
+ left.root_monitored + right.root_camera,
+ root_camera});
+ int root_not_monitored = std::min({left.root_monitored + right.root_monitored, root_monitored});
+
+ return Result{
+ root_camera, root_monitored, root_not_monitored};
+ }
+
+ int minCameraCover(TreeNode *root)
+ {
+ auto result = dfs(root);
+ return result.root_monitored;
+ }
+};
\ No newline at end of file diff --git a/works/solutions/leetcode/cpp/976.cpp b/works/solutions/leetcode/cpp/976.cpp new file mode 100644 index 0000000..e306047 --- /dev/null +++ b/works/solutions/leetcode/cpp/976.cpp @@ -0,0 +1,23 @@ +#include <vector>
+
+using std::vector;
+
+#include <algorithm>
+#include <functional>
+
+class Solution
+{
+public:
+ int largestPerimeter(vector<int> &A)
+ {
+ std::sort(A.begin(), A.end(), std::greater<int>{});
+ for (int i = 0; i < A.size() - 2; i++)
+ {
+ if (A[i] < A[i + 1] + A[i + 2])
+ {
+ return A[i] + A[i + 1] + A[i + 2];
+ }
+ }
+ return 0;
+ }
+};
diff --git a/works/solutions/leetcode/cpp/98.cpp b/works/solutions/leetcode/cpp/98.cpp new file mode 100644 index 0000000..73cefa0 --- /dev/null +++ b/works/solutions/leetcode/cpp/98.cpp @@ -0,0 +1,29 @@ +#include <cstddef> + +struct TreeNode +{ + int val; + TreeNode *left; + TreeNode *right; + TreeNode(int x) : val(x), left(NULL), right(NULL) {} +}; + +#include <limits> + +class Solution +{ +public: + bool dfs(TreeNode *node, long long min, long long max) + { + if (node == nullptr) + return true; + if (node->val <= min || node->val >= max) + return false; + return dfs(node->left, min, node->val) && dfs(node->right, node->val, max); + } + + bool isValidBST(TreeNode *root) + { + return dfs(root, std::numeric_limits<long long>::min(), std::numeric_limits<long long>::max()); + } +}; diff --git a/works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp b/works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp new file mode 100644 index 0000000..dee81ec --- /dev/null +++ b/works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp @@ -0,0 +1,34 @@ +#include <vector>
+
+using std::vector;
+
+#include <algorithm>
+
+class Solution
+{
+public:
+ int maxValue(vector<vector<int>> &grid)
+ {
+ int row_count = grid.size();
+ int col_count = grid.front().size();
+
+ for (int i = 1; i < row_count; i++)
+ {
+ grid[i][0] = grid[i - 1][0] + grid[i][0];
+ }
+
+ for (int j = 1; j < col_count; j++)
+ {
+ grid[0][j] = grid[0][j - 1] + grid[0][j];
+ }
+
+ for (int i = 1; i < row_count; i++)
+ {
+ for (int j = 1; j < col_count; j++)
+ {
+ grid[i][j] = std::max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
+ }
+ }
+ return grid[row_count - 1][col_count - 1];
+ }
+};
diff --git a/works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp b/works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp new file mode 100644 index 0000000..697182d --- /dev/null +++ b/works/solutions/leetcode/cpp/paths-with-sums-lcci.cpp @@ -0,0 +1,46 @@ +#include <cstddef>
+
+struct TreeNode
+{
+ int val;
+ TreeNode *left;
+ TreeNode *right;
+ TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+};
+
+#include <vector>
+
+class Solution
+{
+public:
+ std::vector<int> current;
+
+ int dfs(TreeNode *root, int sum)
+ {
+ if (root == nullptr)
+ return 0;
+
+ current.push_back(root->val);
+
+ int s = 0;
+ int count = 0;
+
+ for (auto iter = current.crbegin(); iter != current.crend(); ++iter)
+ {
+ s += *iter;
+ if (s == sum)
+ count++;
+ }
+
+ count += dfs(root->left, sum) + dfs(root->right, sum);
+
+ current.pop_back();
+
+ return count;
+ }
+
+ int pathSum(TreeNode *root, int sum)
+ {
+ return dfs(root, sum);
+ }
+};
diff --git a/works/solutions/leetcode/cpp/power-set-lcci.cpp b/works/solutions/leetcode/cpp/power-set-lcci.cpp new file mode 100644 index 0000000..f502e7c --- /dev/null +++ b/works/solutions/leetcode/cpp/power-set-lcci.cpp @@ -0,0 +1,29 @@ +#include <vector> + +using std::vector; + +class Solution { +public: + void dfs(const vector<int> &nums, int index, int size, vector<int> ¤t, + vector<vector<int>> &result) { + if (index == size) { + result.push_back(current); + return; + } + + dfs(nums, index + 1, size, current, result); + + current.push_back(nums[index]); + dfs(nums, index + 1, size, current, result); + current.pop_back(); + } + + vector<vector<int>> subsets(vector<int> &nums) { + vector<int> current; + vector<vector<int>> result; + + dfs(nums, 0 , nums.size(), current, result); + + return result; + } +}; diff --git a/works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp b/works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp new file mode 100644 index 0000000..1cb3e01 --- /dev/null +++ b/works/solutions/leetcode/cpp/que-shi-de-shu-zi-lcof.cpp @@ -0,0 +1,29 @@ +#include <vector>
+
+using std::vector;
+
+class Solution
+{
+public:
+ int missingNumber(vector<int> &nums)
+ {
+ if (nums.back() == nums.size() - 1)
+ return nums.size();
+
+ int low = 0, high = nums.size() - 1;
+ while (low != high)
+ {
+ int middle = (low + high) / 2;
+ if (middle == nums[middle])
+ {
+ low = middle + 1;
+ }
+ else
+ {
+ high = middle;
+ }
+ }
+
+ return low;
+ }
+};
|