diff options
50 files changed, 0 insertions, 1414 deletions
diff --git a/3sum_multiplicity.cpp b/3sum_multiplicity.cpp deleted file mode 100644 index 66f1f2c..0000000 --- a/3sum_multiplicity.cpp +++ /dev/null @@ -1,18 +0,0 @@ -#include <bits/stdc++.h> -using namespace std; - -class Solution { -public: - int threeSumMulti(vector<int> &arr, int target) { - int n = arr.size(), mod = 1e9 + 7, ans = 0; - unordered_map<int, int> m; - for (int i = 0; i < n; i++) { - ans = (ans + m[target - arr[i]]) % mod; - for (int j = 0; j < i; j++) - m[arr[i] + arr[j]]++; - } - return ans; - } -}; - -int main() {} diff --git a/4sum.cpp b/4sum.cpp deleted file mode 100644 index 8ab5fa4..0000000 --- a/4sum.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<vector<int>> fourSum(vector<int> &nums, int target) { - sort(begin(nums), end(nums)); - return kSum(nums, target, 0, 4); - } - - vector<vector<int>> kSum(vector<int> &nums, int target, int start, int k) { - vector<vector<int>> result; - if (start == nums.size()) - return result; - int avgVal = target / k; - if (nums[start] > avgVal || avgVal > nums.back()) - return result; - if (k == 2) - return twoSum(nums, target, start); - for (int i = start; i < nums.size(); ++i) { - if (i == start || nums[i - 1] != nums[i]) { - for (vector<int> &subset : - kSum(nums, static_cast<long>(target) - nums[i], i + 1, k - 1)) { - result.push_back({nums[i]}); - result.back().insert(end(result.back()), begin(subset), end(subset)); - } - } - } - return result; - } - - vector<vector<int>> twoSum(vector<int> &nums, int target, int start) { - vector<vector<int>> result; - int low = start, high = nums.size() - 1; - while (low < high) { - int currSum = nums[low] + nums[high]; - if (currSum < target || (low > start && nums[low] == nums[low - 1])) - ++low; - else if (currSum > target || - (high < nums.size() - 1 && nums[high] == nums[high + 1])) - --high; - else - result.push_back({nums[low++], nums[high--]}); - } - return result; - } -}; - -int main() {} diff --git a/BST_iterator.cpp b/BST_iterator.cpp deleted file mode 100644 index e50c74a..0000000 --- a/BST_iterator.cpp +++ /dev/null @@ -1,22 +0,0 @@ -#include "leetcode.h" - -class BSTIterator { -public: - stack<TreeNode *> s; - BSTIterator(TreeNode *root) { partialOrder(root); } - int next() { - TreeNode *top = s.top(); - s.pop(); - partialOrder(top->right); - return top->val; - } - bool hasNext() { return !s.empty(); } - void partialOrder(TreeNode *root) { - while (root != NULL) { - s.push(root); - root = root->left; - } - } -}; - -int main() {} diff --git a/backspace_string_compare.cpp b/backspace_string_compare.cpp deleted file mode 100644 index 110e469..0000000 --- a/backspace_string_compare.cpp +++ /dev/null @@ -1,36 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - bool backspaceCompare(string s, string t) { - int k = 0, p = 0; - for (int i = 0; i < s.size(); i++) { - if (s[i] == '#') { - k--; - k = max(0, k); - } else { - s[k] = s[i]; - k++; - } - } - for (int i = 0; i < t.size(); i++) { - if (t[i] == '#') { - p--; - p = max(0, p); - } else { - t[p] = t[i]; - p++; - } - } - if (k != p) - return false; - else { - for (int i = 0; i < k; i++) - if (s[i] != t[i]) - return false; - return true; - } - } -}; - -int main() {} diff --git a/baseball_game.cpp b/baseball_game.cpp deleted file mode 100644 index f5d1b35..0000000 --- a/baseball_game.cpp +++ /dev/null @@ -1,30 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int calPoints(vector<string> &ops) { - int val1, val2, ans = 0; - stack<int> s; - for (string i : ops) { - if (i == "C") - s.pop(); - else if (i == "D") - s.push(s.top() * 2); - else if (i == "+") { - val1 = s.top(); - s.pop(); - val2 = s.top(); - s.push(val1); - s.push(val1 + val2); - } else - s.push(stoi(i)); - } - while (s.size() != 0) { - ans += s.top(); - s.pop(); - } - return ans; - } -}; - -int main() {} diff --git a/binary_tree_cameras.cpp b/binary_tree_cameras.cpp deleted file mode 100644 index c73650b..0000000 --- a/binary_tree_cameras.cpp +++ /dev/null @@ -1,28 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int ans; - int minCameraCover(TreeNode *root) { - if (helper(root) == 0) - ans++; - return ans; - } - -private: - int helper(TreeNode *root) { - if (!root) - return 1; - int l = helper(root->left); - int r = helper(root->right); - if (l == 0 || r == 0) { - ans++; - return 2; - } else if (l == 2 || r == 2) - return 1; - else - return 0; - } -}; - -int main() {} diff --git a/bst_to_greater_tree.cpp b/bst_to_greater_tree.cpp deleted file mode 100644 index 293ed81..0000000 --- a/bst_to_greater_tree.cpp +++ /dev/null @@ -1,25 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int currSum; - TreeNode *convertBST(TreeNode *root) { - if (!root) - return root; - currSum = 0; - traverse(root); - return root; - } - -private: - void traverse(TreeNode *node) { - if (node->right) - traverse(node->right); - currSum += node->val; - node->val = currSum; - if (node->left) - traverse(node->left); - } -}; - -int main() {} diff --git a/corresponding_node.cpp b/corresponding_node.cpp deleted file mode 100644 index a5d758e..0000000 --- a/corresponding_node.cpp +++ /dev/null @@ -1,9 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - TreeNode *getTargetCopy(TreeNode *original, TreeNode *clone, - TreeNode *target) {} -}; - -int main() {} diff --git a/critical_connection_network.cpp b/critical_connection_network.cpp deleted file mode 100644 index eeb5f82..0000000 --- a/critical_connection_network.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<vector<int>> criticalConnections(int n, - vector<vector<int>> &connections) { - vector<bool> vi(n, false); - vector<int> disc(n, 0), low(n, 0), parent(n, -1); - vector<vector<int>> g(n, vector<int>()), ans; - for (auto &p : connections) { - g[p.front()].push_back(p.back()); - g[p.back()].push_back(p.front()); - } - for (int i = 0; i < n; ++i) { - if (vi[i]) - continue; - helper(i, vi, disc, low, parent, g, ans); - } - return ans; - } - -private: - void helper(int u, vector<bool> &vi, vector<int> &disc, vector<int> &low, - vector<int> &parent, vector<vector<int>> &g, - vector<vector<int>> &ans) { - static int time = 0; - vi[u] = true; - disc[u] = low[u] = ++time; - for (int i : g[u]) { - if (!vi[i]) { - parent[i] = u; - helper(i, vi, disc, low, parent, g, ans); - low[u] = min(low[u], low[i]); - if (low[i] > disc[u]) - ans.push_back({u, i}); - } else if (i != parent[u]) - low[u] = min(low[u], disc[i]); - } - } -}; - -int main() {} diff --git a/deepest_leaves_sum.cpp b/deepest_leaves_sum.cpp deleted file mode 100644 index bb84f4c..0000000 --- a/deepest_leaves_sum.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int deepestLeavesSum(TreeNode *root) { - int ans = 0, i; - queue<TreeNode *> q; - q.push(root); - while (q.size()) { - for (i = q.size() - 1, ans = 0; i >= 0; --i) { - TreeNode *node = q.front(); - q.pop(); - ans += node->val; - if (node->right) - q.push(node->right); - if (node->left) - q.push(node->left); - } - } - return ans; - } -}; - -int main() {} diff --git a/design_hashmap.cpp b/design_hashmap.cpp deleted file mode 100644 index 6b7ce3d..0000000 --- a/design_hashmap.cpp +++ /dev/null @@ -1,12 +0,0 @@ -#include "leetcode.h" - -class MyHashMap { -public: - int data[1000001]; - MyHashMap() { fill(data, data + 1000000, -1); } - void put(int key, int value) { data[key] = value; } - int get(int key) { return data[key]; } - void remove(int key) { data[key] = -1; } -}; - -int main() {} diff --git a/design_hashset.cpp b/design_hashset.cpp deleted file mode 100644 index 52d1097..0000000 --- a/design_hashset.cpp +++ /dev/null @@ -1,12 +0,0 @@ -#include "leetcode.h" - -class MyHashSet { -public: - vector<bool> ans; - MyHashSet() { ans.resize(1e6 + 1, false); } - void add(int key) { ans[key] = true; } - void remove(int key) { ans[key] = false; } - bool contains(int key) { return ans[key]; } -}; - -int main() {} diff --git a/divide_two_int.cpp b/divide_two_int.cpp deleted file mode 100644 index 6afa1ea..0000000 --- a/divide_two_int.cpp +++ /dev/null @@ -1,23 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int divide(int dividend, int divisor) { - if (dividend == INT_MIN && divisor == -1) - return INT_MAX; - long dvd = labs(dividend), dvs = labs(divisor), ans = 0; - int sign = dividend > 0 ^ divisor > 0 ? -1 : 1; - while (dvd >= dvs) { - long temp = dvs, m = 1; - while (temp << 1 <= dvd) { - temp <<= 1; - m <<= 1; - } - dvd -= temp; - ans += m; - } - return sign * ans; - } -}; - -int main() {} diff --git a/evaluate_division.cpp b/evaluate_division.cpp deleted file mode 100644 index 7bda627..0000000 --- a/evaluate_division.cpp +++ /dev/null @@ -1,63 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<double> calcEquation(vector<vector<string>> &equations, - vector<double> &values, - vector<vector<string>> &queries) { - vector<double> ans; - map<string, double> mp; - map<string, vector<string>> graph; - for (int i = 0; i < equations.size(); i++) { - string u = equations[i][0], v = equations[i][1]; - mp[u + "->" + v] = values[i]; - mp[v + "->" + u] = 1 / values[i]; - graph[u].push_back(v); - graph[v].push_back(u); - } - for (int i = 0; i < queries.size(); i++) { - string start = queries[i][0], end = queries[i][1]; - if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) { - ans.push_back(-1); - } else { - double val = 1; - map<string, int> visited; - bool found = false; - if (start == end) - found = true; - else - dfs(start, end, mp, graph, val, visited, found); - if (found == true) - ans.push_back(val); - else - ans.push_back(-1); - } - } - return ans; - } - -private: - void dfs(string start, string end, map<string, double> &mp, - map<string, vector<string>> &graph, double &val, - map<string, int> &visited, bool &found) { - visited[start] = 1; - if (found == true) - return; - for (auto child : graph[start]) { - if (visited[child] != 1) { - val *= mp[start + "->" + child]; - if (end == child) { - found = true; - return; - } - dfs(child, end, mp, graph, val, visited, found); - if (found == true) - return; - else - val /= mp[start + "->" + child]; - } - } - } -}; - -int main() {} diff --git a/first_last_sorted_array.cpp b/first_last_sorted_array.cpp deleted file mode 100644 index 3f4168a..0000000 --- a/first_last_sorted_array.cpp +++ /dev/null @@ -1,47 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<int> searchRange(vector<int> &nums, int target) { - int s = 0, e = nums.size() - 1; - vector<int> ans(2, -1); - // first position - while (s <= e) { - int m = s + (e - s) / 2; - if (nums[m] < target) - s = m + 1; - else if (nums[m] > target) - e = m - 1; - else { - if (m == s || nums[m] != nums[m - 1]) { - ans[0] = m; - break; - } else { - e = m - 1; - ans[0] = m - 1; - } - } - } - // second position - s = 0, e = nums.size() - 1; - while (s <= e) { - int m = s + (e - s) / 2; - if (nums[m] < target) - s = m + 1; - else if (nums[m] > target) - e = m - 1; - else { - if (m == e || nums[m] != nums[m + 1]) { - ans[1] = m; - break; - } else { - s = m + 1; - ans[1] = m + 1; - } - } - } - return ans; - } -}; - -int main() {} diff --git a/first_missing_pos.cpp b/first_missing_pos.cpp deleted file mode 100644 index 5955ded..0000000 --- a/first_missing_pos.cpp +++ /dev/null @@ -1,17 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int firstMissingPositive(vector<int> &nums) { - int n = nums.size(); - for (int i = 0; i < n; i++) - while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) - swap(nums[i], nums[nums[i] - 1]); - for (int i = 0; i < n; i++) - if (nums[i] != i + 1) - return i + 1; - return n + 1; - } -}; - -int main() {} diff --git a/flatten_nested_iterator.cpp b/flatten_nested_iterator.cpp deleted file mode 100644 index 4a6f93c..0000000 --- a/flatten_nested_iterator.cpp +++ /dev/null @@ -1,33 +0,0 @@ -#include "leetcode.h" - -class NestedIterator { -public: - NestedIterator(vector<NestedInteger> &nestedList) { - int n = nestedList.size(); - for (int i = n - 1; i >= 0; --i) - nodes.push(nestedList[i]); - } - int next() { - int ans = nodes.top().getInteger(); - nodes.pop(); - return ans; - } - bool hasNext() { - while (!nodes.empty()) { - NestedInteger curr = nodes.top(); - if (curr.isInteger()) - return true; - nodes.pop(); - vector<NestedInteger> &adj = curr.getList(); - int n = adj.size(); - for (int i = n - 1; i >= 0; --i) - nodes.push(adj[i]); - } - return false; - } - -private: - stack<NestedInteger> nodes; -}; - -int main() {} diff --git a/game_of_life.cpp b/game_of_life.cpp deleted file mode 100644 index 86c9d53..0000000 --- a/game_of_life.cpp +++ /dev/null @@ -1,37 +0,0 @@ -#include <bits/stdc++.h> -using namespace std; - -class Solution { -public: - void gameOfLife(vector<vector<int>> &board) { - vector<int> waysX = {0, 0, 1, 1, 1, -1, -1, -1}; - vector<int> waysY = {1, -1, 1, -1, 0, 0, 1, -1}; - for (int row = 0; row < board.size(); row++) { - for (int col = 0; col < board[0].size(); col++) { - int live = 0; - for (int i = 0; i < 8; i++) { - int currX = row + waysX[i], currY = col + waysY[i]; - if (isNeighbor(currX, currY, board) && abs(board[currX][currY]) == 1) - live++; - } - if (board[row][col] == 1 && (live < 2 || live > 3)) - board[row][col] = -1; - if (board[row][col] == 0 && live == 3) - board[row][col] = 2; - } - } - for (int row = 0; row < board.size(); row++) - for (int col = 0; col < board[0].size(); col++) - if (board[row][col] >= 1) - board[row][col] = 1; - else - board[row][col] = 0; - } - -private: - bool isNeighbor(int x, int y, vector<vector<int>> &board) { - return (x >= 0 && x < board.size() && y >= 0 && y < board[0].size()); - } -}; - -int main() {} diff --git a/gen_parentheses.cpp b/gen_parentheses.cpp deleted file mode 100644 index 4271beb..0000000 --- a/gen_parentheses.cpp +++ /dev/null @@ -1,21 +0,0 @@ -#include <bits/stdc++.h> -using namespace std; - -class Solution { -public: - vector<string> result; - void helper(int open, int close, int n, string curr) { - if (curr.length() == n * 2) - result.push_back(curr); - if (open < n) - helper(open + 1, close, n, curr + '('); - if (close < open) - helper(open, close + 1, n, curr + ')'); - } - vector<string> generateParenthesis(int n) { - helper(0, 0, n, ""); - return result; - } -}; - -int main() {} diff --git a/graph_bipartite.cpp b/graph_bipartite.cpp deleted file mode 100644 index b37972d..0000000 --- a/graph_bipartite.cpp +++ /dev/null @@ -1,30 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<int> vis, col; - bool isBipartite(vector<vector<int>> &graph) { - int n = graph.size(); - vis.resize(n); - col.resize(n); - for (int i = 0; i < n; i++) - if (vis[i] == 0 && dfs(i, 0, graph) == false) - return false; - return true; - } - -private: - bool dfs(int v, int c, vector<vector<int>> &graph) { - vis[v] = 1; - col[v] = c; - for (int child : graph[v]) - if (vis[child] == 0) { - if (dfs(child, c ^ 1, graph) == false) - return false; - } else if (col[v] == col[child]) - return false; - return true; - } -}; - -int main() {} diff --git a/implement_strstr.cpp b/implement_strstr.cpp deleted file mode 100644 index 4c888c2..0000000 --- a/implement_strstr.cpp +++ /dev/null @@ -1,19 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int strStr(string haystack, string needle) { - int m = haystack.size(), n = needle.size(); - for (int i = 0; i <= m - n; i++) { - int j; - for (j = 0; j < n; j++) - if (haystack[i + j] != needle[j]) - break; - if (j == n) - return i; - } - return -1; - } -}; - -int main() {} diff --git a/increasing_seach_tree.cpp b/increasing_seach_tree.cpp deleted file mode 100644 index cfe97ec..0000000 --- a/increasing_seach_tree.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - TreeNode *increasingBST(TreeNode *root) { - TreeNode *temp; - TreeNode *ans = new TreeNode(); - temp = ans; - inOrder(ans, root); - return temp->right; - } - -private: - void inOrder(TreeNode *&ans, TreeNode *root) { - if (!root) - return; - inOrder(ans, root->left); - ans->right = new TreeNode(root->val); - ans = ans->right; - inOrder(ans, root->right); - } -}; - -int main() {} diff --git a/intersection_2_linked_list.cpp b/intersection_2_linked_list.cpp deleted file mode 100644 index 7477734..0000000 --- a/intersection_2_linked_list.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { - ListNode *p1 = headA; - ListNode *p2 = headB; - if (p1 == NULL || p2 == NULL) - return NULL; - while (p1 != NULL && p2 != NULL && p1 != p2) { - p1 = p1->next; - p2 = p2->next; - if (p1 == p2) - return p1; - if (p1 == NULL) - p1 = headB; - if (p2 == NULL) - p2 = headA; - } - return p1; - } -}; - -int main() {} diff --git a/jump_game2.cpp b/jump_game2.cpp deleted file mode 100644 index 23d2b35..0000000 --- a/jump_game2.cpp +++ /dev/null @@ -1,16 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int jump(vector<int> &nums) { - int n = nums.size(); - vector<int> dp(n, 10001); - dp[n - 1] = 0; - for (int i = n - 2; i >= 0; i--) - for (int jumpLen = 1; jumpLen <= nums[i]; jumpLen++) - dp[i] = min(dp[i], 1 + dp[min(n - 1, i + jumpLen)]); - return dp[0]; - } -}; - -int main() {} diff --git a/kth_smallest_BST.cpp b/kth_smallest_BST.cpp deleted file mode 100644 index 73243d4..0000000 --- a/kth_smallest_BST.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - set<int> s; - int kthSmallest(TreeNode *root, int k) { - traverse(root); - for (auto ans : s) { - k--; - if (!k) - return ans; - } - return 0; - } - -private: - void traverse(TreeNode *root) { - if (!root) - return; - s.insert(root->val); - traverse(root->left); - traverse(root->right); - } -}; - -int main() {} diff --git a/last_stone_weight.cpp b/last_stone_weight.cpp deleted file mode 100644 index c7422db..0000000 --- a/last_stone_weight.cpp +++ /dev/null @@ -1,23 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int lastStoneWeight(vector<int> &stones) { - make_heap(stones.begin(), stones.end()); - while (stones.size() > 1) { - int x = stones.front(); - pop_heap(stones.begin(), stones.end()); - stones.pop_back(); - int y = stones.front(); - pop_heap(stones.begin(), stones.end()); - stones.pop_back(); - if (x == y) - continue; - stones.push_back(x - y); - push_heap(stones.begin(), stones.end()); - } - return stones.size() ? stones.front() : 0; - } -}; - -int main() {} diff --git a/longest_increasing_matrix_path.cpp b/longest_increasing_matrix_path.cpp deleted file mode 100644 index 1ee5b99..0000000 --- a/longest_increasing_matrix_path.cpp +++ /dev/null @@ -1,32 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int longestIncreasingPath(vector<vector<int>> &matrix) { - int rows = matrix.size(), cols = matrix[0].size(); - if (!rows) - return 0; - vector<vector<int>> dp(rows, vector<int>(cols, 0)); - function<int(int, int)> dfs = [&](int x, int y) { - if (dp[x][y]) - return dp[x][y]; - vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; - for (auto &dir : dirs) { - int x2 = x + dir[0], y2 = y + dir[1]; - if (x2 < 0 || x2 >= rows || y2 < 0 || y2 >= cols) - continue; - if (matrix[x2][y2] <= matrix[x][y]) - continue; - dp[x][y] = max(dp[x][y], dfs(x2, y2)); - } - return ++dp[x][y]; - }; - int ans = 0; - for (int i = 0; i < rows; ++i) - for (int j = 0; i < cols; ++j) - ans = max(ans, dfs(i, j)); - return ans; - } -}; - -int main() {} diff --git a/merge_k_lists.cpp b/merge_k_lists.cpp deleted file mode 100644 index 375fb10..0000000 --- a/merge_k_lists.cpp +++ /dev/null @@ -1,36 +0,0 @@ -#include <bits/stdc++.h> -using namespace std; - -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 *mergeKLists(vector<ListNode *> &lists) { - if (lists.size() == 0) - return NULL; - ListNode *head = lists[0]; - for (int i = 1; i < lists.size(); i++) - head = merge(head, lists[i]); - return head; - } - -private: - ListNode *merge(ListNode *list1, ListNode *list2) { - if (!list1) - return list2; - if (!list2) - return list1; - ListNode *head = list1->val <= list2->val ? list1 : list2; - head->next = list1->val <= list2->val ? merge(list1->next, list2) - : merge(list1, list2->next); - return head; - } -}; - -int main() {} diff --git a/merge_lists.cpp b/merge_lists.cpp deleted file mode 100644 index b57bf53..0000000 --- a/merge_lists.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <bits/stdc++.h> -#include <cstddef> - -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 *mergeTwoLists(ListNode *list1, ListNode *list2) { - if (list1 == NULL) - return list2; - if (list2 == NULL) - return list1; - if (list1->val <= list2->val) { - list1->next = mergeTwoLists(list1->next, list2); - return list1; - } else { - list2->next = mergeTwoLists(list1, list2->next); - return list2; - } - } -}; - -int main() {} diff --git a/min_cost_connect_points.cpp b/min_cost_connect_points.cpp deleted file mode 100644 index 09a00c3..0000000 --- a/min_cost_connect_points.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int minCostConnectPoints(vector<vector<int>> &points) { - int n = points.size(); - vector<vector<int>> cost(n, vector<int>(n)); - for (int i = 0; i < n; i++) - for (int j = 0; j < n; j++) - cost[i][j] = - abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]); - int ans = solve(n, cost); - return ans; - } - -private: - int minNode(int n, int keyVal[], bool mstSet[]) { - int mini = INT_MAX; - int miniIdx = -1; - for (int i = 0; i < n; i++) - if (mstSet[i] == false && keyVal[i] < mini) - mini = keyVal[i], miniIdx = i; - return miniIdx; - } - int solve(int n, vector<vector<int>> &city) { - int parent[n], keyVal[n]; - bool mstSet[n]; - for (int i = 0; i < n; i++) { - keyVal[i] = numeric_limits<int>::max(); - mstSet[i] = false; - } - parent[0] = -1; - keyVal[0] = 0; - for (int i = 0; i < n - 1; i++) { - int u = minNode(n, keyVal, mstSet); - mstSet[u] = true; - for (int j = 0; j < n; j++) { - if (city[u][j] && mstSet[j] == false && city[u][j] < keyVal[j]) { - keyVal[j] = city[u][j]; - parent[j] = u; - } - } - } - int cost = 0; - for (int i = 1; i < n; i++) - cost += city[parent[i]][i]; - return cost; - } -}; - -int main() {} diff --git a/multiply_strings.cpp b/multiply_strings.cpp deleted file mode 100644 index 115b85c..0000000 --- a/multiply_strings.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - string multiply(string num1, string num2) { - if (num1 == "0" || num2 == "0") - return "0"; - vector<int> res(num1.size() + num2.size(), 0); - for (int i = num1.size() - 1; i >= 0; i--) { - for (int j = num2.size() - 1; j >= 0; j--) { - res[i + j + 1] += (num1[i] - '0') * (num2[j] - '0'); - res[i + j] += res[i + j + 1] / 10; - res[i + j + 1] %= 10; - } - } - int i = 0; - string ans = ""; - while (res[i] == 0) - i++; - while (i < res.size()) - ans += to_string(res[i++]); - return ans; - } -}; - -int main() {} diff --git a/n_queens.cpp b/n_queens.cpp deleted file mode 100644 index df2457e..0000000 --- a/n_queens.cpp +++ /dev/null @@ -1,43 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<vector<string>> solveNQueens(int n) { - vector<vector<string>> ans; - vector<string> nQueens(n, string(n, '.')); - solve(ans, nQueens, 0, n); - return ans; - } - -private: - void solve(vector<vector<string>> &ans, vector<string> &nQueens, int row, - int &n) { - if (row == n) { - ans.push_back(nQueens); - return; - } - for (int col = 0; col != n; ++col) - if (isValid(nQueens, row, col, n)) { - nQueens[row][col] = 'Q'; - solve(ans, nQueens, row + 1, n); - nQueens[row][col] = '.'; - } - } - bool isValid(vector<string> &nQueens, int row, int col, int &n) { - // check if col had queen - for (int i = 0; i != row; ++i) - if (nQueens[i][col] == 'Q') - return false; - // check if 45deg diagonal had queen - for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) - if (nQueens[i][j] == 'Q') - return false; - // check if 135deg diagonal had queen - for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) - if (nQueens[i][j] == 'Q') - return false; - return true; - } -}; - -int main() {} diff --git a/network_delay_time.cpp b/network_delay_time.cpp deleted file mode 100644 index 7d46995..0000000 --- a/network_delay_time.cpp +++ /dev/null @@ -1,22 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int networkDelayTime(vector<vector<int>> ×, int n, int k) { - vector<int> dist(n + 1, INT_MAX); - dist[k] = 0; - for (int i = 0; i < n; i++) { - for (vector<int> e : times) { - int u = e[0], v = e[1], w = e[2]; - if (dist[u] != INT_MAX && dist[v] > dist[u] + w) - dist[v] = dist[u] + w; - } - } - int maxWait = 0; - for (int i = 1; i <= n; i++) - maxWait = max(maxWait, dist[i]); - return maxWait == INT_MAX ? -1 : maxWait; - } -}; - -int main() {} diff --git a/palindromic_substrings.cpp b/palindromic_substrings.cpp deleted file mode 100644 index 8de80a0..0000000 --- a/palindromic_substrings.cpp +++ /dev/null @@ -1,31 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int countSubstrings(string s) { - this->s = s; - int ans = 0, n = s.size(); - dp.resize(n, vector<int>(n, -1)); - for (int i = 0; i < n; i++) - for (int j = i; j < n; j++) - ans += helper(i, j, s); - return ans; - } - -private: - vector<vector<int>> dp; - // string s = "abc"; - int helper(int l, int r, string s) { - if (l > r || l == r) - return 1; - if (dp[l][r] != -1) - return dp[l][r]; - if (s[l] != s[r]) - return dp[l][r] = 0; - if (helper(l + 1, r - 1, s)) - return dp[l][r] = 1; - return dp[l][r] = 0; - } -}; - -int main() {} diff --git a/populating_right_pointer.cpp b/populating_right_pointer.cpp deleted file mode 100644 index d977321..0000000 --- a/populating_right_pointer.cpp +++ /dev/null @@ -1,32 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - Node *connect(Node *root) { - Node *currParent = root, *baseChild, *currChild, *nextChild; - while (currParent) { - while (currParent->next && !currParent->left && !currParent->right) - currParent = currParent->next; - currChild = baseChild = - currParent->left ? currParent->left : currParent->right; - while (currChild) { - if (currParent->right && currChild != currParent->right) - nextChild = currParent->right; - else { - currParent = currParent->next; - while (currParent && !currParent->left && !currParent->right) - currParent = currParent->next; - nextChild = currParent ? currParent->left ? currParent->left - : currParent->right - : currParent; - } - currChild->next = nextChild; - currChild = nextChild; - } - currParent = baseChild; - } - return root; - } -}; - -int main() {} diff --git a/pow_xn.cpp b/pow_xn.cpp deleted file mode 100644 index f64161f..0000000 --- a/pow_xn.cpp +++ /dev/null @@ -1,20 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - double myPow(double x, int n) { - if (n < 0) - x = 1 / x; - long num = labs(n); - double pow = 1; - while (num) { - if (num & 1) - pow *= x; - x *= x; - num >>= 1; - } - return pow; - } -}; - -int main() {} diff --git a/reconstruct_digit_english.cpp b/reconstruct_digit_english.cpp deleted file mode 100644 index fdc1022..0000000 --- a/reconstruct_digit_english.cpp +++ /dev/null @@ -1,31 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - string originalDigits(string s) { - int fMap[26] = {0}, ans[10] = {0}; - for (char c : s) - fMap[c - 97]++; - for (int i = 0; i < 10; i++) { - int count = fMap[CHARS[i]]; - for (int remain : REM[i]) - fMap[remain] -= count; - ans[DIGITS[i]] = count; - } - string ansStr; - for (int i = 0; i < 10; i++) { - char c = (char)(i + 48); - for (int j = ans[i]; j; j--) - ansStr += c; - } - return ansStr; - } - -private: - const int DIGITS[10] = {0, 2, 4, 6, 8, 5, 7, 3, 9, 1}, - CHARS[10] = {25, 22, 20, 23, 6, 5, 18, 7, 8, 14}; - const vector<vector<int>> REM = {{14}, {14}, {5, 14}, {18, 8}, {8, 7}, - {8}, {}, {}, {}, {}}; -}; - -int main() {} diff --git a/recover_BST.cpp b/recover_BST.cpp deleted file mode 100644 index 9120825..0000000 --- a/recover_BST.cpp +++ /dev/null @@ -1,27 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<pair<TreeNode *, TreeNode *>> vec; - void recoverTree(TreeNode *root) { - inOrder(root); - if (vec.size() == 1) - swap(vec[0].first->val, vec[0].second->val); - if (vec.size() == 2) - swap(vec[0].first->val, vec[1].second->val); - } - -private: - TreeNode *prev = NULL; - void inOrder(TreeNode *root) { - if (!root) - return; - inOrder(root->left); - if (prev && prev->val > root->val) - vec.push_back({prev, root}); - prev = root; - inOrder(root->right); - } -}; - -int main() {} diff --git a/remove_node.cpp b/remove_node.cpp deleted file mode 100644 index 1f79374..0000000 --- a/remove_node.cpp +++ /dev/null @@ -1,31 +0,0 @@ -#include <bits/stdc++.h> -#include <cstddef> -using namespace std; - -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 *removeNthFromEnd(ListNode *head, int n) { - ListNode *temp = head; - for (int i = 0; i < n; i++) - temp = temp->next; - if (temp == NULL) - return head->next; - ListNode *curr = head; - while (temp->next) { - temp = temp->next; - curr = curr->next; - } - curr->next = curr->next->next; - return head; - } -}; - -int main() {} diff --git a/reverse_node_k.cpp b/reverse_node_k.cpp deleted file mode 100644 index e57291a..0000000 --- a/reverse_node_k.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - ListNode *reverseKGroup(ListNode *head, int k) { - ListNode *cursor = head; - for (int i = 0; i < k; i++) { - if (cursor == nullptr) - return head; - cursor = cursor->next; - } - ListNode *curr = head; - ListNode *prev = nullptr; - ListNode *next = nullptr; - for (int i = 0; i < k; i++) { - next = curr->next; - curr->next = prev; - prev = curr; - curr = next; - } - head->next = reverseKGroup(curr, k); - return prev; - } -}; - -int main() {} diff --git a/search_BST.cpp b/search_BST.cpp deleted file mode 100644 index 9d06727..0000000 --- a/search_BST.cpp +++ /dev/null @@ -1,16 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - TreeNode *searchBST(TreeNode *root, int val) { - if (root == NULL) - return NULL; - if (root->val == val) - return root; - if (root->val > val) - return searchBST(root->left, val); - return searchBST(root->right, val); - } -}; - -int main() {} diff --git a/search_insert_pos.cpp b/search_insert_pos.cpp deleted file mode 100644 index f6768a5..0000000 --- a/search_insert_pos.cpp +++ /dev/null @@ -1,20 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int searchInsert(vector<int> &nums, int target) { - int low = 0, high = nums.size() - 1; - while (low <= high) { - int mid = low + (high - low) / 2; - if (nums[mid] == target) - return mid; - else if (nums[mid] > target) - high = mid - 1; - else - low = mid + 1; - } - return low; - } -}; - -int main() {} diff --git a/shift_2d_grid.cpp b/shift_2d_grid.cpp deleted file mode 100644 index b6b06f2..0000000 --- a/shift_2d_grid.cpp +++ /dev/null @@ -1,19 +0,0 @@ -#include <bits/stdc++.h> -using namespace std; - -class Solution { -public: - vector<vector<int>> shiftGrid(vector<vector<int>> &grid, int k) { - int n = grid.size(), m = grid[0].size(); - vector<vector<int>> ans(n, vector<int>(m)); - for (int i = 0; i < n; i++) - for (int j = 0; j < m; j++) { - int newJ = (j + k) % m; - int newI = (i + (j + k) / m) % n; - ans[newI][newJ] = grid[i][j]; - } - return ans; - } -}; - -int main() {} diff --git a/shortest_unsorted_subarray.cpp b/shortest_unsorted_subarray.cpp deleted file mode 100644 index ab56ec6..0000000 --- a/shortest_unsorted_subarray.cpp +++ /dev/null @@ -1,30 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int findUnsortedSubarray(vector<int> &nums) { - int l = -1, r = -1, n = nums.size(); - for (int i = 0; i < n - 1; i++) - if (nums[i] > nums[i + 1]) { - l = i; - break; - } - for (int i = n - 1; i <= 1; i--) - if (nums[i] < nums[i - 1]) { - r = i; - break; - } - if (l == -1) - return 0; - int minI = nums[l], maxI = nums[l]; - for (int i = l; i <= r; i++) { - minI = min(minI, nums[i]); - maxI = max(maxI, nums[i]); - } - l = upper_bound(nums.begin(), nums.begin() + l, minI) - nums.begin(); - r = lower_bound(nums.begin() + r + 1, nums.end(), maxI) - nums.begin(); - return r - l; - } -}; - -int main() {} diff --git a/substring_concentration.cpp b/substring_concentration.cpp deleted file mode 100644 index b989375..0000000 --- a/substring_concentration.cpp +++ /dev/null @@ -1,37 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<int> findSubstring(string s, vector<string> &words) { - int len = words[0].size(), n = words.size(), sSize = s.size(), left, found; - vector<int> result; - unordered_map<string, int> freq, temp; - for (auto word : words) - freq[word]++; - for (int i = 0; i < len; i++) { - temp.clear(); - left = i, found = 0; - for (int j = i; j <= sSize - len; j += len) { - string curr = s.substr(j, len); - if (freq.find(curr) != freq.end()) { - temp[curr]++; - found++; - while (freq[curr] < temp[curr]) { - temp[s.substr(left, len)]--; - found--; - left += len; - } - if (found == n) - result.push_back(left); - } else { - temp.clear(); - found = 0; - left = j + len; - } - } - } - return result; - } -}; - -int main() {} diff --git a/swap_node_pair.cpp b/swap_node_pair.cpp deleted file mode 100644 index b365961..0000000 --- a/swap_node_pair.cpp +++ /dev/null @@ -1,31 +0,0 @@ -#include <bits/stdc++.h> -using namespace std; - -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 *swapPairs(ListNode *head) { - if (!head || !head->next) - return head; - ListNode *temp = new ListNode; - ListNode *prev = temp; - ListNode *curr = head; - while (curr && curr->next) { - prev->next = curr->next; - curr->next = prev->next->next; - prev->next->next = curr; - prev = curr; - curr = curr->next; - } - return temp->next; - } -}; - -int main() {} diff --git a/triangle.cpp b/triangle.cpp deleted file mode 100644 index d7e826b..0000000 --- a/triangle.cpp +++ /dev/null @@ -1,20 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int minimumTotal(vector<vector<int>> &triangle) { - vector<int> ans(triangle.size(), triangle[0][0]); - for (int i = 1; i < triangle.size(); i++) - for (int j = i; j >= 0; j--) { - if (j == 0) - ans[0] += triangle[i][j]; - else if (j == i) - ans[j] = triangle[i][j] + ans[j - 1]; - else - ans[j] = triangle[i][j] + min(ans[j - 1], ans[j]); - } - return *min_element(ans.begin(), ans.end()); - } -}; - -int main() {} diff --git a/trim_binary_tree.cpp b/trim_binary_tree.cpp deleted file mode 100644 index 3f4168a..0000000 --- a/trim_binary_tree.cpp +++ /dev/null @@ -1,47 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<int> searchRange(vector<int> &nums, int target) { - int s = 0, e = nums.size() - 1; - vector<int> ans(2, -1); - // first position - while (s <= e) { - int m = s + (e - s) / 2; - if (nums[m] < target) - s = m + 1; - else if (nums[m] > target) - e = m - 1; - else { - if (m == s || nums[m] != nums[m - 1]) { - ans[0] = m; - break; - } else { - e = m - 1; - ans[0] = m - 1; - } - } - } - // second position - s = 0, e = nums.size() - 1; - while (s <= e) { - int m = s + (e - s) / 2; - if (nums[m] < target) - s = m + 1; - else if (nums[m] > target) - e = m - 1; - else { - if (m == e || nums[m] != nums[m + 1]) { - ans[1] = m; - break; - } else { - s = m + 1; - ans[1] = m + 1; - } - } - } - return ans; - } -}; - -int main() {} diff --git a/underground_system.cpp b/underground_system.cpp deleted file mode 100644 index fd4fbbf..0000000 --- a/underground_system.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include "leetcode.h" - -class UndergroundSystem { -public: - unordered_map<int, pair<string, int>> checkIns; - unordered_map<string, pair<int, int>> routes; - UndergroundSystem() {} - void checkIn(int id, string stationName, int t) { - checkIns[id] = {stationName, t}; - } - void checkOut(int id, string stationName, int t) { - auto [stn, start] = checkIns[id]; - checkIns.erase(id); - string route = stn + "," + stationName; - routes[route].first++; - routes[route].second += t - start; - } - double getAverageTime(string startStation, string endStation) { - auto &[count, sum] = routes[startStation + "," + endStation]; - return (double)sum / count; - } -}; - -int main() {} diff --git a/wildcard_matching.cpp b/wildcard_matching.cpp deleted file mode 100644 index 23a6538..0000000 --- a/wildcard_matching.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - bool isMatch(string s, string p) { - int m = s.length(), n = p.length(); - int i = 0, j = 0, astr = -1, match; - while (i < m) { - if (j < n && p[j] == '*') - match = i, astr = j++; - else if (j < n && (s[i] == p[j] || p[j] == '?')) - i++, j++; - else if (astr >= 0) - i = ++match, j = astr + 1; - else - return false; - } - while (j < n && p[j] == '*') - j++; - return j == n; - } -}; - -int main() {} |