Programming
Leetcode Programming Skills study plan list I
- Day 1 Array
- Day 2 Operator
- Day 3 Conditional Statements
- Day 4 Loop
- Day 5 Function
- Day 6 Array
- Day 7 Array
- Day 8 String
- Day 9 String
- Day 10 Linked List & Tree
- Day 11 Containers & Libraries
- Day 12 Class & Object
class Solution {
public:
int countOdds(int low, int high) {
int total = (high - low) >> 1;
if (low & 1 or high & 1) total++;
return total;
}
};
class Solution {
public:
double average(vector<int>& salary) {
int min_salary = salary[0], max_salary = salary[0];
double total = 0;
for (int amt : salary){
min_salary = min(min_salary, amt);
max_salary = max(max_salary, amt);
total = total + amt;
}
return (total - min_salary - max_salary) / (salary.size() - 2);
}
};
class Solution {
public:
int hammingWeight(uint32_t n) {
int nbits = 0;
while (n){
nbits += n & 1;
n >>= 1;
}
return nbits;
}
};
class Solution {
public:
int subtractProductAndSum(int n) {
int accum_prod=1, accum_sum=0, digit;
while (n){
digit = n % 10;
n = n / 10;
accum_prod *= digit;
accum_sum += digit;
}
return accum_prod - accum_sum;
}
};
class Solution {
public:
int largestPerimeter(vector<int>& nums) {
sort(nums.begin(), nums.end(), [](int i, int j)->bool {return j < i;});
int result = 0;
for (int i=0; i < nums.size() - 2; i++) {
if (nums[i] < nums[i+1] + nums[i+2]) {
result = nums[i] + nums[i+1] + nums[i+2];
break;
}
}
return result;
}
};
class Solution {
public:
int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
int min_dist = INT_MAX, nearest_point_idx=-1;
auto manhattan_dist = [](int x1, int y1, int x2, int y2) -> int {
return abs(y2 - y1) + abs(x2 - x1);
};
for (int i = 0; i < points.size(); i++) {
auto point = points[i];
if (point[0] == x or point[1] == y) {
int dist = manhattan_dist(point[0], point[1], x, y);
if (dist < min_dist) {
min_dist = dist;
nearest_point_idx = i;
}
}
}
return nearest_point_idx;
}
};
class Solution {
public:
int arraySign(vector<int>& nums) {
int sign = 1;
for (auto num: nums) {
if (num == 0) return 0;
else if (num > 0) sign *= 1;
else sign *= -1;
}
return sign;
}
};
class Solution {
public:
bool canMakeArithmeticProgression(vector<int>& arr) {
set<int> nums;
int min_val = arr[0], max_val = arr[0];
for (auto num: arr) {
min_val = min(min_val, num);
max_val = max(max_val, num);
nums.insert(num);
}
if (max_val == min_val) return true;
if ((max_val - min_val) % (arr.size() - 1)) return false;
int delta = (max_val - min_val) / (arr.size() - 1);
for (int curr = min_val; curr + delta <= max_val; curr += delta) {
if (not nums.count(curr)) return false;
}
return true;
}
};
class Solution {
public:
bool isHappy(int n) {
set<int> seen;
while (not seen.count(n)) {
seen.insert(n);
int m = 0, d;
while (n > 0) {
d = n % 10;
m += d * d;
n /= 10;
}
n = m;
}
return n == 1;
}
};
class Solution {
public:
bool areAlmostEqual(string s1, string s2) {
char c11, c12, c21, c22;
int num_diff = 0;
for (int i = 0; i < s1.size(); i++){
if (s1[i] != s2[i]) {
num_diff++;
if (num_diff == 1) {
c11 = s1[i];
c21 = s2[i];
}
if (num_diff == 2) {
c12 = s1[i];
c22 = s2[i];
}
}
if (num_diff > 2) return false;
}
if (num_diff == 0) return true;
if (num_diff == 1) return false;
return (c11 == c22 and c21 == c12);
}
};
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> result;
if (root == nullptr) return result;
stack<Node*> s;
s.push(root);
while (not s.empty()) {
auto node = s.top();
s.pop();
result.push_back(node->val);
for (int i=node->children.size()-1; i >= 0; i--) {
s.push(node->children[i]);
}
}
return result;
}
};
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> map;
stack<int> s;
vector<int> result;
for (auto num: nums2) {
while (not s.empty() and s.top() < num) {
map[s.top()] = num;
s.pop();
}
s.push(num);
}
for (auto num: nums1) {
if (not map.count(num)) result.push_back(-1);
else result.push_back(map[num]);
}
return result;
}
};
class Solution {
public:
bool checkStraightLine(vector<vector<int>>& coordinates) {
int x1 = coordinates[0][0], y1 = coordinates[0][1];
int x2 = coordinates[1][0], y2 = coordinates[1][1];
if (x1 == x2) {
for (auto point: coordinates) {
if (point[0] != x1) return false;
}
} else {
double slope, intercept;
slope = (y2 - y1) * 1.0 / (x2 - x1);
intercept = y1 - x1 * slope;
for (auto point: coordinates) {
int expected_y = slope * point[0] + intercept;
if (expected_y != point[1]) return false;
}
}
return true;
}
};
class Solution {
public:
int sumOddLengthSubarrays(vector<int>& arr) {
int total = 0, n = arr.size();
for (int i = 0; i < n; ++i) {
total += arr[i] * (((i + 1) * (n - i) + 1) / 2);
}
return total;
}
};
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int l = 0, r = 0;
while (r < nums.size()) {
while (r < nums.size() and nums[r] == 0) r++;
if (r < nums.size()) swap(nums[l], nums[r]);
l++;
r++;
}
}
};
class Solution {
public:
int maximumWealth(vector<vector<int>>& accounts) {
int max_wealth=accounts[0][0];
for (auto account: accounts) {
int total = accumulate(account.begin(), account.end(), 0);
max_wealth = max(max_wealth, total);
}
return max_wealth;
}
};
class Solution {
public:
int diagonalSum(vector<vector<int>>& mat) {
int total=0, r, c, n=mat.size();
r = 0, c = 0;
while (0 <= r and r < n and 0 <= c and c < n) {
total += mat[r++][c++];
}
r = 0, c = n - 1;
while (0 <= r and r < n and 0 <= c and c < n) {
total += mat[r++][c--];
}
if (n % 2) total -= mat[n / 2][n / 2];
return total;
}
};
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
int nrow=mat.size(), ncol=mat[0].size(), i=0;
if (nrow * ncol != r * c) return mat;
vector<vector<int>> result(r);
while (i < r * c) {
int val = mat[i/ncol][i%ncol];
result[i/c].push_back(val);
i++;
}
return result;
}
};
class Solution {
public:
string mergeAlternately(string word1, string word2) {
string merged;
auto it1 = word1.begin(), it2 = word2.begin();
while (it1 < word1.end() or it2 < word2.end()) {
if (it1 < word1.end()) merged.push_back(*it1++);
if (it2 < word2.end()) merged.push_back(*it2++);
}
return merged;
}
};
class Solution {
public:
string interpret(string command) {
string result;
for (auto i=0; i < command.size(); ) {
if (command[i] == 'G') {
result += 'G';
i += 1;
} else if (command.compare(i, 2, "()") == 0) {
result += 'o';
i += 2;
} else {
result += "al";
i += 4;
}
}
return result;
}
};
class Solution {
public:
char findTheDifference(string s, string t) {
char diff=0;
for (auto c: s) diff ^= c;
for (auto c: t) diff ^= c;
return diff;
}
};
class Solution {
public:
string toLowerCase(string s) {
for (int i=0; i < s.size(); i++) {
if (s[i] >= 'A' and s[i] <= 'Z') s[i] += 32;
}
return s;
}
};
class Solution {
public:
string freqAlphabets(string s) {
string result;
int i = 0;
while (i < s.size()) {
if (i + 2 < s.size() and s[i+2] == '#') {
result.push_back('j' + stoi(s.substr(i, 2)) - 10);
i += 3;
} else {
result.push_back('a' + stoi(s.substr(i, 1)) - 1);
i++;
}
}
return result;
}
};
class Solution {
public:
bool is_ordered(string& w1, string&w2, unordered_map<char, int>& rank) {
for (int i=0; i < min(w1.size(), w2.size()); i++) {
if (rank[w1[i]] < rank[w2[i]]) return true;
if (rank[w1[i]] > rank[w2[i]]) return false;
}
return w1.size() <= w2.size();
}
bool isAlienSorted(vector<string>& words, string order) {
unordered_map<char, int> rank;
for (int i=0; i < order.size(); i++) {
rank[order[i]] = i;
}
for (int i=0; i < words.size() -1; i++) {
if (not is_ordered(words[i], words[i+1], rank)) return false;
}
return true;
}
};
class Solution {
public:
int getDecimalValue(ListNode* head) {
int val = 0;
while (head != nullptr) {
val <<= 1;
val += head->val;
head = head->next;
}
return val;
}
};
class Solution {
public:
ListNode* middleNode(ListNode* head) {
auto slow=head, fast=head;
while (fast and fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
if (not root) return 0;
int max_depth = 0;
stack<pair<TreeNode*, int>> s;
s.push({root, 1});
while (not s.empty()) {
auto node = s.top();
s.pop();
max_depth = max(max_depth, node.second);
if (node.first->left) s.push({node.first->left, node.second + 1});
if (node.first->right) s.push({node.first->right, node.second + 1});
}
return max_depth;
}
};
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
int total=0;
stack<pair<TreeNode*, int>> s;
s.push({root, 0});
while (not s.empty()) {
auto p = s.top(); s.pop();
TreeNode* node = p.first;
int is_left = p.second;
if (is_left and not (node->left or node->right)) {
total += node->val;
}
if (node->left) s.push({node->left, 1});
if (node->right) s.push({node->right, 0});
}
return total;
}
};
#include <bit>
class Solution {
public:
vector<int> sortByBits(vector<int>& arr) {
sort(
arr.begin(),
arr.end(),
[](int a, int b) -> bool {
int a_bits = __popcount(a), b_bits = __popcount(b);
if (a_bits == b_bits) return a < b;
return a_bits < b_bits;
}
);
return arr;
}
};
class MyQueue {
stack<int> instack;
stack<int> outstack;
public:
MyQueue() {}
void push(int x) { instack.push(x); }
int pop() {
shuffle();
int val = outstack.top();
outstack.pop();
return val;
}
void shuffle() {
if (outstack.empty()) {
while (instack.size()) {
int val = instack.top();
instack.pop();
outstack.push(val);
}
}
}
int peek() {
shuffle();
return outstack.top();
}
bool empty() { return instack.size() + outstack.size() == 0;}
};
class Solution {
public:
bool isAnagram(string s, string t) {
unordered_map<char, int> char_freq;
for (char c: s) {
if (char_freq.count(c)) char_freq[c]++;
else char_freq[c] = 1;
}
for (char c: t) {
if (not char_freq.count(c)) return false;
else {
char_freq[c]--;
if (char_freq[c] == 0) char_freq.erase(c);
}
}
return char_freq.size() == 0;
}
};
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
set<int> m;
for (int num:nums) {
if (m.count(num)) return true;
m.insert(num);
}
return false;
}
};
class ParkingSystem {
private:
vector<int> car_counts;
public:
ParkingSystem(int big, int medium, int small) {
car_counts = {big, medium, small};
}
bool addCar(int carType) {
return --car_counts[carType-1] >= 0;
}
};
class NumArray {
private:
vector<int> prefix_sum;
public:
NumArray(vector<int>& nums) {
prefix_sum = {0};
int accum = 0;
for (auto num: nums) {
accum += num;
prefix_sum.push_back(accum);
}
}
int sumRange(int left, int right) {
return prefix_sum[right + 1] - prefix_sum[left];
}
};
Leetcode Programming Skills study plan list II
- Day 1
- Day 2
- Day 3
- Day 4
- Day 5
- Day 6
- Day 7
- Day 8
- Day 9
- Day 10
- Day 11
- Day 12
- Day 13
- Day 14
- Day 15
- Day 16
- Day 17
- Day 18
- Day 19
- Day 20
class Solution {
public:
bool isMonotonic(vector<int>& nums) {
bool asc=true, dsc=true;
for (int i=0; i<nums.size()-1; i++){
if (nums[i+1] > nums[i]) dsc=false;
if (nums[i+1] < nums[i]) asc=false;
}
return asc or dsc;
}
};
class Solution {
private:
vector<int> table(string p) {
int m = p.size();
vector<int> lps = {0, 0};
int j = 0;
for (int i = 1; i < m; i++) {
while (j and p[i] != p[j]) j = lps[j];
if (p[i] == p[j]) j++;
lps.push_back(j);
}
return lps;
}
int match(string s, string p) {
int n=s.size(), m=p.size();
vector<int> lps = table(p);
int j = 0;
for (int i = 0; i < n; i++) {
while (j and s[i] != p[j]) j = lps[j];
if (s[i] == p[j]) j++;
if (j == m) return i - m + 1;
}
return -1;
}
public:
int strStr(string haystack, string needle) {
if (needle.size() == 0) return 0;
return match(haystack, needle);
}
};
class Solution {
public:
bool isBalanced(TreeNode* root) {
unordered_map<TreeNode*, int> heights;
heights[nullptr] = 0;
stack<pair<TreeNode*, int>> tour;
tour.push({root, 0});
while (not tour.empty()) {
auto element = tour.top(); tour.pop();
auto node = element.first;
int backtrack = element.second;
if (node == nullptr) continue;
if (backtrack) {
int l = heights[node->left], r = heights[node->right];
if (r > l + 1 or l > r + 1) return false;
heights[node] = max(l, r) + 1;
} else {
tour.push({node, 1});
tour.push({node->left, 0});
tour.push({node->right, 0});
}
}
return true;
}
};
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
vector<int> table = {0, 0};
int j = 0;
for (int i = 1; i < n; i++) {
while (j > 0 and s[i] != s[j]) j = table[j];
if (s[i] == s[j]) j++;
table.push_back(j);
}
return (table[n] and table[n] % (n - table[n]) == 0);
}
};
class Solution {
private:
int eval(int num1, int num2, string op) {
if (op == "+") return num1 + num2;
if (op == "-") return num1 - num2;
if (op == "*") return num1 * num2;
if (op == "/") return num1 / num2;
return 0;
}
public:
int evalRPN(vector<string>& tokens) {
unordered_set<string> operators = {"+", "-", "*", "/"};
stack<int> partials;
for (auto token: tokens) {
if (operators.count(token)) {
int num2 = partials.top(); partials.pop();
int num1 = partials.top(); partials.pop();
partials.push(eval(num1, num2, token));
} else {
partials.push(stoi(token));
}
}
return partials.top();
}
};
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int carry = 1;
for (int i = digits.size() - 1; i >= 0; --i) {
auto result = div(digits[i] + carry, 10);
digits[i] = result.rem;
carry = result.quot;
}
if (carry) digits.insert(digits.begin(), carry);
return digits;
}
};
class Solution {
private:
bool is_sub_path_dfs(ListNode* lnode, TreeNode* tnode) {
if (lnode->val != tnode->val) return false;
if (lnode->next == nullptr) return true;
bool l_ok = false, r_ok = false;
if (tnode->left) l_ok = is_sub_path_dfs(lnode->next, tnode->left);
if (tnode->right) r_ok = is_sub_path_dfs(lnode->next, tnode->right);
return l_ok or r_ok;
}
public:
bool isSubPath(ListNode* head, TreeNode* root) {
stack<TreeNode*> s;
s.push(root);
while (not s.empty()) {
auto tnode = s.top(); s.pop();
if (is_sub_path_dfs(head, tnode)) return true;
if (tnode->left) s.push(tnode->left);
if (tnode->right) s.push(tnode->right);
}
return false;
}
};
class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" or num2 == "0") return "0";
int l1 = num1.size(), l2 = num2.size();
vector<int> result(l1+l2, 0);
for (int i = l1-1; i >= 0; i--) {
int d1 = num1[i] - '0';
for (int j = l2-1; j >= 0; j--) {
int d2 = num2[j] - '0';
result[i + j + 1] += d1 * d2;
result[i + j] += result[i + j + 1] / 10;
result[i + j + 1] %= 10;
}
}
int i = 0;
string ans = "";
while (result[i] == 0) i++;
while (i < result.size()) ans += to_string(result[i++]);
return ans;
}
};
class Solution {
public:
string addBinary(string a, string b) {
string result;
int carry = 0, i = a.size()-1, j = b.size()-1;
while (i >= 0 or j >= 0 or carry != 0) {
if (i >= 0) carry += a[i--] - '0';
if (j >= 0) carry += b[j--] - '0';
result.push_back((char)(carry % 2 + '0'));
carry /= 2;
}
reverse(result.begin(), result.end());
return result;
}
};
class Solution {
public:
vector<int> addToArrayForm(vector<int>& num, int k) {
vector<int> result;
int i = num.size() - 1, carry = 0;
while (i >= 0 or k > 0 or carry > 0) {
if (i >= 0) carry += num[i--];
if (k){
carry += k % 10;
k /= 10;
}
result.push_back(carry % 10);
carry /= 10;
}
reverse(result.begin(), result.end());
return result;
}
};
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> result (temperatures.size(), 0);
stack<int> s;
int n = temperatures.size();
for (int day = 0; day < n; day++) {
int temp = temperatures[day];
while (!s.empty() and temp > temperatures[s.top()]) {
int prev_day = s.top(); s.pop();
result[prev_day] = day - prev_day;
}
s.push(day);
}
return result;
}
};
class Solution {
public:
int lengthOfLastWord(string s) {
int last = 0, curr = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ' and curr) last = curr;
if (s[i] == ' ') curr = 0;
else curr++;
}
return curr > 0 ? curr : last;
}
};
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i=0; i < (n - n / 2); i++) {
for (int j=0; j < n / 2; j++) {
vector<int> tmp = {
matrix[n - j - 1][i],
matrix[n - i - 1][n - j - 1],
matrix[j][n - i - 1],
matrix[i][j]
};
matrix[i][j] = tmp[0];
matrix[n - j - 1][i] = tmp[1];
matrix[n - i - 1][n - j - 1] = tmp[2];
matrix[j][n - i - 1] = tmp[3];
}
}
}
};
class Solution {
public:
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
vector<bool> c(4, true);
int n = mat.size();
for (int i=0; i < n; i++) {
for (int j=0; j < n; j++) {
if (mat[i][j] != target[i][j]) c[0] = false;
if (mat[i][j] != target[n-j-1][i]) c[1] = false;
if (mat[i][j] != target[j][n-i-1]) c[2] = false;
if (mat[i][j] != target[n-i-1][n-j-1]) c[3] = false;
}
}
return c[0] or c[1] or c[2] or c[3];
}
};
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> result;
int row_start = 0, col_start = 0, row_end = matrix.size() - 1, col_end = matrix[0].size() - 1;
while (row_start <= row_end and col_start <= col_end) {
for (int c=col_start; c<=col_end; c++) result.push_back(matrix[row_start][c]);
row_start++;
for (int r=row_start; r<=row_end; r++) result.push_back(matrix[r][col_end]);
col_end--;
if (row_start <= row_end) {
for (int c=col_end; c>=col_start; c--) result.push_back(matrix[row_end][c]);
row_end--;
}
if (col_start <= col_end) {
for (int r=row_end; r>=row_start; r--) result.push_back(matrix[r][col_start]);
col_start++;
}
}
return result;
}
};
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
priority_queue<vector<int>> pq;
auto dist = [](auto x) { return x[0] * x[0] + x[1] * x[1]; };
for (auto p: points) {
int d = dist(p);
pq.push({d, p[0], p[1]});
if (pq.size() > k) pq.pop();
}
vector<vector<int>> result;
while (!pq.empty()) {
auto r = pq.top(); pq.pop();
result.push_back({r[1], r[2]});
}
return result;
}
};
class Solution {
public:
vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
vector<bool> result;
for (int i = 0; i < l.size(); i ++){
unordered_set<int> window;
for (int j = l[i]; j <= r[i]; j++) window.insert(nums[j]);
int window_size = (r[i] - l[i] + 1);
int min_val = *min_element(window.begin(), window.end());
int max_val = *max_element(window.begin(), window.end());
auto divmod = div(max_val - min_val, window_size - 1);
if (divmod.rem != 0) {
result.push_back(false);
} else {
bool is_arithmetic_subarr = true;
for (int k = 0; k < window_size; k++) {
if (not window.count(min_val + k * divmod.quot)) {
is_arithmetic_subarr = false;
}
}
result.push_back(is_arithmetic_subarr);
}
}
return result;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> result;
queue<Node*> q;
if (root == nullptr) return result;
q.push(root);
while (!q.empty()) {
vector<int> level_vals;
int size = q.size();
for (int i = 0; i < size; i++) {
auto node = q.front(); q.pop();
level_vals.push_back(node->val);
for (auto child: node->children) q.push(child);
}
result.push_back(level_vals);
}
return result;
}
};
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> next_greater(nums.size(), -1);
stack<int> s;
for (int i=0; i<nums.size() * 2; i++) {
int j = i % nums.size();
int num = nums[j];
while (!s.empty() and nums[s.top()] < num) {
next_greater[s.top()] = num;
s.pop();
}
s.push(j);
}
return next_greater;
}
};
class Solution {
public:
int nextGreaterElement(int n) {
string digits = to_string(n);
int i = digits.size() - 1;
while (i > 0 and digits[i-1] >= digits[i]) i--;
if (i == 0) return -1;
int j = digits.size() - 1;
while (j > 0 and digits[j] <= digits[i-1]) j--;
swap(digits[j], digits[i-1]);
reverse(digits.begin()+i, digits.end());
size_t ans = stoll(digits);
return ans > INT_MAX ? -1 : ans;
}
};
class Solution {
public:
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
unordered_map<int, vector<int>> reports;
for (int e=0; e<manager.size(); e++) reports[manager[e]].push_back(e);
stack<pair<int, int>> s;
s.push({headID, 0});
int max_time = INT_MIN;
while (!s.empty()) {
auto node = s.top(); s.pop();
int e_id = node.first, t = node.second;
max_time = max(max_time, t);
for (auto report: reports[e_id]) s.push({report, t + informTime[e_id]});
}
return max_time;
}
};
class Solution {
public:
string hash(string str) {
stringstream freq_str;
vector<int> freq_table(26);
for (auto chr: str) freq_table[chr - 'a'] += 1;
copy(freq_table.begin(), freq_table.end(), ostream_iterator<int>(freq_str, ","));
return freq_str.str().c_str();
}
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> group_by;
vector<vector<string>> anagrams;
for (auto str: strs) group_by[hash(str)].push_back(str);
for (auto group: group_by) anagrams.push_back(group.second);
return anagrams;
}
};
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
if (s.size() < p.size()) return {};
unordered_map<char, int> req_freq, window;
for (char c:p) req_freq[c]++;
for (int i=0;i<p.size();i++) if (req_freq.count(s[i])) window[s[i]]++;
int to_match = req_freq.size();
for (auto kv:window) to_match -= kv.second == req_freq[kv.first];
if (not to_match) result.push_back(0);
for (int r=p.size(),l=0;r<s.size();r++,l++){
char in_char=s[r], out_char=s[l];
if (req_freq.count(in_char)) {
if (window[in_char] == req_freq[in_char]) to_match++;
if (window[in_char]+1==req_freq[in_char]) to_match--;
window[in_char]++;
}
if (req_freq.count(out_char)){
if (window[out_char] == req_freq[out_char]) to_match++;
if (window[out_char]-1==req_freq[out_char]) to_match--;
window[out_char]--;
}
if (not to_match) result.push_back(l+1);
}
return result;
}
};
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int accum=1, count=0, l=0;
for (int r=0; r<nums.size(); r++) {
int num = nums[r];
accum *= num;
while (l <= r and accum >= k) {
accum /= nums[l];
l++;
}
if (accum < k) count += r - l + 1;
}
return count;
}
};
class NumMatrix {
private:
vector<vector<int>> dp;
public:
NumMatrix(vector<vector<int>>& matrix) {
int nrow = matrix.size(), ncol = matrix[0].size();
dp.resize(nrow + 1, vector<int>(ncol+1));
for (int r = 1; r < nrow + 1; r++) {
for (int c = 1; c < ncol + 1; c++) {
dp[r][c] = dp[r][c-1] + dp[r-1][c] - dp[r-1][c-1] + matrix[r-1][c-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1];
}
};
class Solution {
public:
int smallestRangeII(vector<int>& nums, int k) {
int n = nums.size();
sort(nums.begin(), nums.end());
int min_range = nums[n-1] - nums[0];
for (int i = 0; i < n-1; i ++) {
int large = max(nums[n-1], nums[i] + 2 * k);
int small = min(nums[i+1], nums[0] + 2 * k);
min_range = min(min_range, large - small);
}
return min_range;
}
};
class Solution {
private:
ListNode* get_middle(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast != nullptr and fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverse(ListNode* head) {
ListNode *prev = nullptr, *curr = head, *temp = nullptr;
while (curr != nullptr) {
temp = curr->next, curr->next = prev, prev = curr, curr = temp;
}
return prev;
}
void merge(ListNode* l1, ListNode* l2) {
ListNode *curr = new ListNode();
while (l1 != nullptr and l2 != nullptr) {
curr->next = l1, curr = l1, l1 = l1->next;
curr->next = l2, curr = l2, l2 = l2->next;
}
if (l1 != nullptr) curr->next = l1;
}
public:
void reorderList(ListNode* head) {
ListNode *l1_tail = get_middle(head);
ListNode *l2_head = l1_tail->next;
l1_tail->next = nullptr;
l2_head = reverse(l2_head);
merge(head, l2_head);
}
};
class Solution {
public:
Node* copyRandomList(Node* head) {
if (not head) return head;
Node *curr=head, *copy, *new_head;
while (curr) {
copy = new Node(curr->val);
copy->next = curr->next;
curr->next = copy;
curr = copy->next;
}
curr = head;
while (curr) {
if (curr->random) curr->next->random = curr->random->next;
curr = curr->next->next;
}
curr = head;
copy = head->next;
new_head = head->next;
while (curr) {
curr->next = curr->next->next;
copy->next = copy->next ? copy->next->next : nullptr;
curr = curr->next;
copy = copy->next;
}
return new_head;
}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* ret = new ListNode();
ListNode* curr = ret;
int carry = 0;
while (l1 or l2 or carry) {
if (l1) {
carry += l1->val;
l1 = l1->next;
}
if (l2) {
carry += l2->val;
l2 = l2->next;
}
curr->next = new ListNode(carry%10);
curr = curr-> next;
carry = carry / 10;
}
return ret->next;
}
};
class Solution {
private:
ListNode* reverse(ListNode* head) {
ListNode *prev = nullptr, *curr = head, *temp = nullptr;
while (curr != nullptr) {
temp = curr->next, curr->next = prev, prev = curr, curr = temp;
}
return prev;
}
ListNode* add(ListNode* l1, ListNode* l2) {
int carry = 0, val = 0;
ListNode *sentinel = new ListNode();
ListNode *curr = new ListNode();
sentinel->next = curr;
while (l1 != nullptr or l2 != nullptr or carry != 0) {
if (l1 != nullptr) {
carry += l1->val;
l1 = l1->next;
}
if (l2 != nullptr) {
carry += l2->val;
l2 = l2->next;
}
val = carry % 10;
carry /= 10;
curr->next = new ListNode(val);
curr = curr->next;
}
return sentinel->next->next;
}
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
l1 = reverse(l1);
l2 = reverse(l2);
ListNode *l3 = add(l1, l2);
l3 = reverse(l3);
return l3;
}
};
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (not head or not head->next) return head;
ListNode *curr = head, *tail, *prev;
int n = 1;
while (curr->next) {
curr = curr->next;
n++;
}
tail = curr;
tail->next = head;
// find split point
curr = head;
k %= n;
while (k < n) {
prev = curr;
curr = curr->next;
k++;
}
// split
prev->next = nullptr;
return curr;
}
};
class BSTIterator {
private:
TreeNode* root_node;
stack<pair<TreeNode*, int>> s;
public:
BSTIterator(TreeNode* root) {
root_node = root;
s = {};
s.push({root_node, 0});
}
int next() {
while (!s.empty()) {
auto e = s.top(); s.pop();
TreeNode* node = e.first;
int is_backtrack = e.second;
if (is_backtrack) return node->val;
if (node->right != nullptr) s.push({node->right, 0});
if (node != nullptr) s.push({node, 1});
if (node->left != nullptr) s.push({node->left, 0});
}
return 0;
}
bool hasNext() {
return (!s.empty());
}
};
class SeatManager {
private:
set<int> set;
public:
SeatManager(int n) {
for (int i = 1; i <= n; ++i) set.insert(set.end(), i);
}
int reserve() {
int val = *set.begin();
set.erase(set.begin());
return val;
}
void unreserve(int seatNumber) {
set.insert(seatNumber);
}
};
class Bank {
private:
vector<int> vals = {20, 10, 5};
unordered_map<int, int> changes;
public:
Bank() { for (int val: vals) changes[val] = 0; }
bool change(int bill) {
changes[bill]++;
bill -= 5;
for (int val: vals) {
while (bill >= val and changes[val] > 0) {
bill -= val;
changes[val]--;
}
}
return bill == 0;
}
};
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
Bank* bank = new Bank();
for (int bill: bills) {
if (not bank->change(bill)) return false;
}
return true;
}
};
class MinStack {
private:
stack<int> vals;
stack<tuple<int, int>> mins;
public:
MinStack() {
vals = {};
mins = {};
}
void push(int x) {
vals.push(x);
if (mins.empty() or x < getMin()) mins.push({x, 1});
else if (x == getMin()) get<1>(mins.top())++;
}
void pop() {
if (vals.top() == getMin()) {
if (get<1>(mins.top()) == 1) mins.pop();
else get<1>(mins.top())--;
}
vals.pop();
}
int top() { return vals.top(); }
int getMin() { return get<0>(mins.top()); }
};
class NestedIterator {
private:
stack<NestedInteger*> stack;
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (int i = nestedList.size() - 1; i >= 0; i--)
stack.push(&nestedList[i]);
}
int next() {
int nxt = stack.top()->getInteger();
stack.pop();
return nxt;
}
bool hasNext() {
while (!stack.empty()) {
NestedInteger *p = stack.top();
if (p->isInteger()) return true;
vector<NestedInteger> &vec = p->getList();
stack.pop();
for (int i = vec.size() - 1; i >= 0; i--)
stack.push(&vec[i]);
}
return false;
}
};
class AuthenticationManager {
int ttl;
unordered_map<string, int> tokens;
public:
AuthenticationManager(int timeToLive) { ttl = timeToLive; }
void generate(string tokenId, int currentTime) {
tokens[tokenId] = currentTime + ttl;
}
void renew(string tokenId, int currentTime) {
auto tokenIt = tokens.find(tokenId);
if (tokenIt != end(tokens) && tokenIt->second > currentTime) {
tokenIt->second = currentTime + ttl;
}
}
int countUnexpiredTokens(int currentTime) {
int res = 0;
for (auto token: tokens) {
if (token.second > currentTime) res++;
}
return res;
}
};
struct MyListNode {
int val;
MyListNode *next;
MyListNode(int x) : val(x), next(NULL) {}
};
class MyLinkedList {
private:
MyListNode* head;
public:
MyLinkedList() { head=nullptr;}
MyListNode* getNode(int index) {
MyListNode* trav = head;
for (int i=0;i<index and trav;i++) trav=trav->next;
return index >= 0 ? trav : nullptr;
}
MyListNode* getTail() {
MyListNode* trav = head;
MyListNode* tail = nullptr;
while (trav) {
if (not trav->next) tail=trav;
trav = trav->next;
}
return tail;
}
int get(int index) {
auto node = getNode(index);
return node ? node->val : -1;
}
void addAtHead(int val) {
MyListNode *node = new MyListNode(val);
node->next = head;
head = node;
}
void addAtTail(int val) {
if (not head) { addAtHead(val); return; }
MyListNode *tail = getTail();
MyListNode *node = new MyListNode(val);
tail->next = node;
}
void addAtIndex(int index, int val) {
if (index == 0) { addAtHead(val); return; }
MyListNode *prev = getNode(index - 1);
if (not prev) { return; }
MyListNode *node = new MyListNode(val);
MyListNode *next = prev->next;
node->next = next;
prev->next = node;
}
void deleteAtIndex(int index) {
MyListNode *node = getNode(index);
if (not node) { return; }
MyListNode *prev = getNode(index-1);
if (prev) prev->next = node->next;
else head = node->next;
}
};
class RandomizedSet {
private:
unordered_map<int, int> lookup;
vector<int> values;
public:
/** Initialize your data structure here. */
RandomizedSet() {
lookup = {};
values = {};
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val) {
if (lookup.count(val)) return false;
lookup[val] = values.size();
values.push_back(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
if (not lookup.count(val)) return false;
int last_elem = values.back();
lookup[values.back()] = lookup[val];
swap(values[lookup[val]], values[values.size()-1]);
values.pop_back();
lookup.erase(val);
return true;
}
/** Get a random element from the set. */
int getRandom() {
return values[rand() % values.size()];
}
};
class MyCircularQueue {
private:
int capacity, first, n;
vector<int> queue;
public:
MyCircularQueue(int k) {
capacity = k;
queue.resize(k, 0);
first = 0;
n = 0;
}
bool enQueue(int value) {
if (n == capacity) return false;
queue[(first + n) % capacity] = value;
n++;
return true;
}
bool deQueue() {
if (n == 0) return false;
first = (first + 1) % capacity;
n--;
return true;
}
int Front() {
if (n == 0) return -1;
return queue[first];
}
int Rear() {
if (n == 0) return -1;
return queue[(first + n - 1) % capacity];
}
bool isEmpty() {
return n == 0;
}
bool isFull() {
return n == capacity;
}
};
class MyCalendar {
public:
MyCalendar() {}
bool book(int start, int end) {
auto it = booked_.lower_bound(start);
if (it != booked_.cend() && it->first < end)
return false;
if (it != booked_.cbegin() && (--it)->second > start)
return false;
booked_[start] = end;
return true;
}
private:
map<int, int> booked_;
};
Leetcode Programming Skills study plan list III
- Day 1
- Day 2
- Day 3
- Day 4
- Day 5
- Day 6
- Day 7
- Day 8
- Day 9
- Day 10
- Day 11
- Day 12
- Day 13
- Day 14
- Day 20
- Day 21
- Day 22
class Solution {
public:
PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
PolyNode *sentinel = new PolyNode();
PolyNode *curr = sentinel;
while (poly1 != nullptr and poly2 != nullptr) {
if (poly1->power > poly2->power) {
curr->next = new PolyNode(poly1->coefficient, poly1->power);
curr = curr->next;
poly1 = poly1->next;
} else if (poly2->power > poly1->power) {
curr->next = new PolyNode(poly2->coefficient, poly2->power);
curr = curr->next;
poly2 = poly2->next;
} else {
int coef = poly1->coefficient + poly2->coefficient;
if (coef != 0) {
curr->next = new PolyNode(coef, poly1->power);
curr = curr->next;
}
poly1 = poly1->next;
poly2 = poly2->next;
}
// curr->next = nullptr;
}
if (poly1 != nullptr) curr->next = poly1;
if (poly2 != nullptr) curr->next = poly2;
return sentinel->next;
}
};
class Solution {
ListNode* reverseList(ListNode* head) {
ListNode *prev=nullptr, *trav=head, *next;
while (trav) {
next = trav->next;
trav->next = prev;
prev = trav;
trav = next;
}
return prev;
}
public:
ListNode* plusOne(ListNode* head) {
head = reverseList(head);
ListNode *trav=head;
int carry = 0;
trav->val++; // change to other values if problem changes
while (trav) {
carry += trav->val;
trav->val = carry % 10;
carry /= 10;
if (not trav->next and carry) trav->next = new ListNode(0);
trav = trav->next;
}
return reverseList(head);
}
};
class Solution {
public:
ListNode* deleteDuplicatesUnsorted(ListNode* head) {
ListNode *sentinel = new ListNode(), *curr = head;
sentinel->next = head;
unordered_map<int, int> freq_count;
while (curr) {
if (!freq_count.count(curr->val)) freq_count[curr->val] = 0;
freq_count[curr->val]++;
curr = curr->next;
}
ListNode *prev = sentinel;
curr = head;
while (curr) {
while (curr and freq_count[curr->val] > 1) curr = curr->next;
prev->next = curr;
prev = curr;
if (curr) curr = curr->next;
}
return sentinel->next;
}
};
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if (!root) return nullptr;
Node *curr = root, *head = nullptr, *prev = nullptr;
stack<Node*> stack;
while (curr or stack.size()) {
while (curr) {
stack.push(curr);
curr = curr->left;
}
curr = stack.top(); stack.pop();
if (!prev) head = curr;
else prev->right = curr, curr->left = prev;
prev = curr, curr = curr->right;
}
prev->right = head, head->left = prev;
return head;
}
};
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int max_len = 0, accum = 0;
unordered_map<int, int> prefix_sum = 0;
for (int r=0; r < nums.size(); ++r) {
accum += nums[r];
if (prefix_sum.count(accum - k))
max_len = max(max_len, r - prefix_sum[accum - k]);
if (!prefix_sum.count(accum))
prefix_sum[accum] = r;
}
return max_len;
}
};
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l = 0, window_sum = 0, min_size = INT_MAX;
for (int r=0; r < nums.size(); ++r) {
window_sum += nums[r];
while (l <= r and window_sum >= target) {
min_size = min(min_size, r - l + 1);
window_sum -= nums[l++];
}
}
return min_size != INT_MAX ? min_size : 0;
}
};
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> m = 0;
int r=0, max_length=0;
for (int i=0; i<nums.size(); i++){
r += (nums[i]) ? 1 : -1;
if (m.count(r)) max_length = max(max_length, i-m[r]);
else m[r] = i;
}
return max_length;
}
};
class Solution {
public:
int getMaximumConsecutive(vector<int>& coins) {
sort(coins.begin(), coins.end());
int accum = 1;
for (int coin: coins) {
if (coin > accum) break;
accum += coin;
}
return accum;
}
};
class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
stack<int> stack;
int lower = INT_MIN;
for (auto x: preorder) {
if (x < lower) return false;
while (!stack.empty() and stack.top() < x) {
lower = stack.top(); stack.pop();
}
stack.push(x);
}
return true;
}
};
class Solution {
private:
int operation(char op, int first, int second) {
if (op == '+') return first + second;
if (op == '-') return first - second;
return 0;
}
public:
int calculate(string s) {
stack<pair<char, int>> stack;
char op = '+';
int partial = 0, operand = 0;
for (char c: s) {
if (isdigit(c)) {
operand = operand * 10 + (c - '0');
} else if (c == '+' or c == '-') {
partial = operation(op, partial, operand);
op = c;
operand = 0;
} else if (c == ')') {
operand = operation(op, partial, operand);
auto item = stack.top(); stack.pop();
op = item.first;
partial = item.second;
partial = operation(op, partial, operand);
operand = 0;
} else if (c == '(') {
stack.push({op, partial});
op = '+';
partial = 0;
}
}
return operation(op, partial, operand);
}
};
class StockSpanner {
private:
vector<pair<int, int>> spanner;
public:
StockSpanner() {
spanner = {};
}
int next(int price) {
int span = 1;
while (not spanner.empty() and spanner.back().first <= price) {
span += spanner.back().second;
spanner.pop_back();
}
spanner.push_back({price, span});
return span;
}
};
class Solution {
private:
unordered_map<string, vector<int>> memo;
public:
vector<int> diffWaysToCompute(string expression) {
vector<int> result, nums;
vector<char> ops;
auto to_key = [](char a, char b) {
string s;
return s + a + '-' + b;
};
auto eval = [](int a, int b, char op) {
if (op == '+') return a + b;
if (op == '*') return a * b;
if (op == '-') return a - b;
return 0;
};
int num = 0;
for (char c: expression) {
if (isdigit(c)) {
num = 10 * num + (c - '0');
} else {
ops.push_back(c);
nums.push_back(num);
num = 0;
}
}
nums.push_back(num);
function<vector<int>(int, int)> dfs = [&](int l, int r) {
string key = to_key(l, r);
if (memo.count(key)) return memo[key];
if (l == r) {
memo[key] = vector<int> {nums[l]};
} else {
vector<int> res = {};
for (int k = l; k < r; ++k) {
vector<int> ls = dfs(l, k), rs = dfs(k+1, r);
for (auto l_val: ls) {
for (auto r_val: rs) {
res.push_back(eval(l_val, r_val, ops[k]));
}
}
}
memo[key] = res;
}
return memo[key];
};
return dfs(0, nums.size() - 1);
}
};
class Codec {
private:
int encode_flag(TreeNode* node) {
int flag = 0;
if (node) {
flag |= 1;
if (node->left) flag |= 2;
if (node->right) flag |= 4;
}
return flag;
}
void serialize(TreeNode* node, string& s) {
char flag = encode_flag(node);
s.push_back(flag);
if (!node) return;
s.append(reinterpret_cast<char*>(&node->val), sizeof(node->val));
if (node->left) serialize(node->left, s);
if (node->right) serialize(node->right, s);
}
TreeNode* deserialize(const string& s, int& pos) {
char flag = s[pos++];
if (!flag) return nullptr;
TreeNode* root = new TreeNode(0);
memcpy(&root->val, s.data() + pos, sizeof(root->val));
pos += sizeof(root->val);
root->left = (flag & 2) ? deserialize(s, pos) : nullptr;
root->right = (flag & 4) ? deserialize(s, pos) : nullptr;
return root;
}
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string s;
serialize(root, s);
return s;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int pos = 0;
return deserialize(data, pos);
}
};
class Solution {
public:
int myAtoi(string s) {
long res = 0;
int sign = 1, i = 0, n = s.size();
while (i < n && s[i] == ' ') ++i;
if (i < n && ( s[i] == '-' || s[i] == '+')) {
if (s[i] == '-') sign = -1;
++i;
}
while (i < n && isdigit(s[i])) {
if (res > INT_MAX / 10 ||
(res == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10)
)
return (sign == 1) ? INT_MAX : INT_MIN;
res = res * 10 + s[i] - '0';
++i;
}
res *= sign;
return res;
}
};
class Solution {
private:
int count_nodes(ListNode* head) {
int total = 0;
while (head) {
head = head->next;
total++;
}
return total;
}
ListNode* split(ListNode* node, int length) {
while (length > 1 and node) {
length--;
node = node->next;
}
if (!node) return nullptr;
ListNode* temp = node->next;
node->next = nullptr;
return temp;
}
ListNode* merge(ListNode* l, ListNode* r, ListNode* node) {
while (l and r) {
if (l->val < r->val) {
node->next = l;
l = l->next;
} else {
node->next = r;
r = r->next;
}
node = node->next;
}
node->next = l != nullptr ? l : r;
while (node->next) node = node->next;
return node;
}
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr) return nullptr;
int size = count_nodes(head);
ListNode* sentinel = new ListNode(0, head);
ListNode *l, *r, *node, *tail;
int length = 1;
while (length < size) {
node = sentinel->next;
tail = sentinel;
while (node) {
l = node;
r = split(node, length);
node = split(r, length);
tail = merge(l, r, tail);
}
length <<=1;
}
return sentinel->next;
}
};
class Solution {
private:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode ret(0);
ListNode* trav = &ret;
while (l1 and l2){
if (l1->val < l2->val) {
trav->next = l1;
l1 = l1->next;
} else {
trav->next = l2;
l2 = l2->next;
}
trav = trav->next;
}
trav->next = l1 ? l1 : l2;
return ret.next;
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
queue<ListNode*> q;
for (auto node:lists) q.push(node);
while (q.size() > 1) {
ListNode* l1 = q.front(); q.pop();
ListNode* l2 = q.front(); q.pop();
ListNode* l3 = mergeTwoLists(l1, l2);
q.push(l3);
}
return q.empty() ? nullptr: q.front();
}
};
class Solution {
public:
Node* insert(Node* head, int insertVal) {
if (not head) {
Node *node = new Node(insertVal);
node->next = node;
return node;
}
Node *prev=head, *trav=head->next;
while (trav != head) {
if (prev->val <= insertVal and insertVal <= trav->val) break;
if (prev->val > trav->val and insertVal >= prev->val) break;
if (prev->val > trav->val and insertVal <= trav->val) break;
prev = trav;
trav = trav->next;
}
prev->next = new Node(insertVal, trav);
return head;
}
};
class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string> result;
function<void(string, int, long, long)> dfs = [&](string candidate, int i, long total, long prev) {
if (i == num.size() and total == target) {
result.push_back(candidate);
return;
}
for (int l = 1; i + l <= num.size(); l++) {
string s = num.substr(i, l);
long d = stoll(s);
int j = i + l;
if (num[i] == '0' and s != "0") continue;
if (candidate.size() == 0) {
dfs(s, j, d, d);
} else {
dfs(candidate + '+' + s, j, total + d, d);
dfs(candidate + '-' + s, j, total - d, -d);
dfs(candidate + '*' + s, j, total - prev + prev * d, prev * d);
}
}
};
dfs("", 0, 0, 0);
return result;
}
};
class Solution {
public:
int calculate(string s) {
unordered_set<char> ops = {'+', '-', '*', '/'};
char opr = '+';
int opd = 0;
stack<int> stack;
auto operation = [&]() {
if (opr == '+') stack.push(opd);
if (opr == '-') stack.push(-opd);
if (opr == '*') {
int prev = stack.top(); stack.pop();
stack.push(prev * opd);
}
if (opr == '/') {
int prev = stack.top(); stack.pop();
stack.push(prev / opd);
}
};
for (char c: s) {
if (isdigit(c)) opd = opd * 10 + (c - '0');
if (ops.count(c)) {
operation();
opd = 0;
opr = c;
}
}
operation();
int total = 0;
while (!stack.empty()) {
total += stack.top();
stack.pop();
}
return total;
}
};
class Solution {
public:
int calculate(string s) {
if (s.size() == 0) return 0;
stack<int> stack;
char sign = '+'; // sign only indicaite next element attribute
long number = 0;
for (int i = 0; i< s.size(); i++) {
// Step 1. calculate the current number you meet. have a recursive call the func encounter a parenthese
if (isdigit(s[i])) {
number = number*10 + long(s[i]-'0');
} else if (s[i] == '(') {
int j = i + 1;
int braces = 1;
while (braces > 0) {
if (s[j] == '(')
braces++;
else if (s[j] ==')')
braces--;
j++;
}
int length = (j-1) -i ;
number = calculate(s.substr(i + 1, length));
i = j-1; // adjust cursor to the last calculated character
}
// Step 2. push the current number inside your stack based on the **last sign** you meet
if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == s.size() - 1) {
switch (sign) {
case '+':
stack.push(number);
break;
case '-':
stack.push(-number);
break;
case '*': {
int top = stack.top();
stack.pop();
stack.push(top*number);
break;
}
case '/': {
int top = stack.top();
stack.pop();
stack.push(top/number);
break;
}
}
sign = s[i]; // assign new operator
number = 0; // reset the current number
}
}
// Step 3. sum up all the numbers you have meet by poping elements from the stack
int sum = 0;
while(!stack.empty()) {
sum += stack.top();
stack.pop();
}
return sum;
}
};
class MyCircularDeque {
private:
int K, n, first, last;
int* deque;
public:
MyCircularDeque(int k) {
K=k, n=0, first=0, last=K-1;
deque = new int[K]{0};
}
bool insertFront(int value) {
if (isFull()) return false;
first = (first + K - 1) % K;
deque[first] = value;
n++;
return true;
}
bool insertLast(int value) {
if (isFull()) return false;
last = (last + 1) % K;
deque[last] = value;
n++;
return true;
}
bool deleteFront() {
if (isEmpty()) return false;
deque[first] = 0;
first = (first + 1) % K;
n--;
return true;
}
bool deleteLast() {
if (isEmpty()) return false;
deque[last] = 0;
last = (last + K - 1) % K;
n--;
return true;
}
int getFront() { return isEmpty() ? -1 : deque[first]; }
int getRear() { return isEmpty() ? -1 : deque[last]; }
bool isEmpty() { return n == 0; }
bool isFull() { return n == K; }
};
class ProductOfNumbers {
private:
vector<int> prefix_prods;
public:
ProductOfNumbers() { prefix_prods = {1}; }
void add(int num) {
if (num == 0) prefix_prods = {1};
else prefix_prods.push_back(prefix_prods.back() * num);
}
int getProduct(int k) {
if (k >= prefix_prods.size()) return 0;
return prefix_prods.back() / prefix_prods[prefix_prods.size() - k - 1];
}
};
class Solution {
private:
vector<int> kmp_table(string s) {
int m = s.size();
vector<int> table = {0, 0};
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 and s[i] != s[j]) j = table[j];
if (s[i] == s[j]) j++;
table.push_back(j);
}
return table;
}
public:
string shortestPalindrome(string s) {
string ss = s + "+" + string(s.rbegin(), s.rend());
vector<int> table = kmp_table(ss);
string first, second, third;
first = s.substr(table.back());
reverse(first.begin(), first.end());
second = s.substr(0, table.back());
third = s.substr(table.back());
return first + second + third;
}
};
class Solution {
public:
Node* expTree(string s) {
//M2: define a BNF
//exp := s
//s := term | term {[+, -] term}
//term := factor | factor {[*, /] factor}
//factor := digit | '(' exp ')'
int pos = 0;
return parseExp(s, pos);
}
private:
Node* parseExp(string &s, int &pos) {
Node *lhs = parseTerm(s, pos);
while (pos < s.size() && (s[pos] == '+' || s[pos] == '-')) {
char op = s[pos];
++pos;
Node* rhs = parseTerm(s, pos);
lhs = new Node(op, lhs, rhs);
}
return lhs;
}
Node* parseTerm(string &s, int &pos) {
Node* lhs = parseFactor(s, pos);
while (pos < s.size() && (s[pos] == '*' || s[pos] == '/')) {
char op = s[pos];
++pos;
Node* rhs = parseFactor(s, pos);
lhs = new Node(op, lhs, rhs);
}
return lhs;
}
Node* parseFactor(string &s, int &pos) {
if (s[pos] == '(') {
++pos; //consume '('
Node* exp = parseExp(s, pos);
++pos; //consume ')'
return exp;
}
//is a digit
Node* digit = new Node(s[pos]);
++pos;
return digit;
}
};
class Solution {
private:
int delta[10][6] = {
{0,1,2,3,9,9},
{9,9,2,3,9,9},
{8,9,2,4,5,9},
{9,9,4,9,9,9},
{8,9,4,9,5,9},
{9,6,7,9,9,9},
{9,9,7,9,9,9},
{8,9,7,9,9,9},
{8,9,9,9,9,9},
{9,9,9,9,9,9}
};
int char_to_input(char c) {
if (c == ' ') return 0;
if (c == '+' or c == '-') return 1;
if (isdigit(c)) return 2;
if (c == '.') return 3;
if (c == 'e' or c == 'E') return 4;
return 5;
}
public:
bool isNumber(string s) {
int state = 0;
for (char c: s) {
int input = char_to_input(c);
state = delta[state][input];
if (state == 9) return false;
}
state = delta[state][0];
return state == 8;
}
};
class TrieNode {
public:
bool flag;
unordered_map<char, TrieNode*> children;
TrieNode() {
flag=false;
children={};
}
};
class Trie {
private:
TrieNode* root;
TrieNode* find(string term){
TrieNode* node = root;
for (char c:term){
if (!node->children.count(c)) return nullptr;
node = node->children[c];
}
return node;
}
public:
Trie() {root = new TrieNode();}
void insert(string word) {
TrieNode* node = root;
for (char c:word){
if (!node->children.count(c)) node->children[c] = new TrieNode();
node = node->children[c];
}
node->flag = true;
}
bool search(string word) {
TrieNode* node = find(word);
return node ? node->flag : false;
}
bool startsWith(string prefix) {
TrieNode* node = find(prefix);
return node ? true : false;
}
};
class TrieNode {
public:
int count;
unordered_map<char, TrieNode*> children;
TrieNode() {
count = 0;
children = {};
}
};
class Trie {
private:
TrieNode* root;
TrieNode* find(string term){
TrieNode* node = root;
for (char c:term){
if (!node->children.count(c)) return nullptr;
node = node->children[c];
}
return node;
}
public:
Trie() {root = new TrieNode();}
void insert(string word) {
TrieNode* node = root;
for (char c:word){
if (!node->children.count(c)) node->children[c] = new TrieNode();
node = node->children[c];
}
node->count++;
}
int countWordsEqualTo(string word) {
TrieNode* node = find(word);
if (node and node->count > 0) return node->count;
return 0;
}
int countWordsStartingWith(string prefix) {
int total = 0;
TrieNode* node = find(prefix);
stack<TrieNode*> stack;
stack.push(node);
while (!stack.empty()) {
node = stack.top(); stack.pop();
if (node == nullptr) continue;
if (node->count > 0) total += node->count;
for (auto child: node->children) {
stack.push(child.second);
}
}
return total;
}
void erase(string word) {
TrieNode* node = find(word);
if (node) node->count--;
}
};
class TrieNode {
public:
unordered_set<int> indices;
unordered_map<char, TrieNode*> children;
TrieNode() {
indices.clear();
children.clear();
};
};
class AutocompleteSystem {
private:
TrieNode *root, *curr, *node;
string query;
unordered_map<string, pair<int, int>> statistics;
unordered_map<int, string> idx_to_sentence;
public:
AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
root = new TrieNode();
init_query();
statistics.clear();
for (int i = 0; i < sentences.size(); i++) insert(sentences[i], times[i]);
}
void init_query() {
query.clear();
curr = root;
}
void insert(string sentence, int time) {
if (statistics.count(sentence)) statistics[sentence].first += time;
else statistics[sentence] = {time, statistics.size()};
int i = statistics[sentence].second;
idx_to_sentence[i] = sentence;
node = root;
for (char c: sentence) {
if (!node->children.count(c)) node->children[c] = new TrieNode();
node = node->children[c];
node->indices.insert(i);
}
}
vector<string> auto_complete(char c, int k=3) {
node = curr;
vector<string> result = {};
vector<pair<string, int>> matched = {};
if (!node || !node->children.count(c)) {
curr = nullptr;
return result;
}
node = node->children[c];
curr = node;
for (auto i: node->indices) {
string sentence = idx_to_sentence[i];
int freq = statistics[sentence].first;
matched.push_back({sentence, freq});
}
auto compare = [](pair<string, int> lhs, pair<string, int> rhs) -> bool {
if (lhs.second > rhs.second) return true;
if (lhs.second == rhs.second) return lhs.first < rhs.first;
return false;
};
sort(matched.begin(), matched.end(), compare);
for (int i = 0; i < k and i < matched.size(); i++) {
if (matched[i].first != "") result.push_back(matched[i].first);
}
return result;
}
vector<string> input(char c) {
if (c == '#') {
insert(query, 1);
init_query();
return {};
}
query += c;
return auto_complete(c);
}
};
class MedianFinder {
public:
priority_queue<int> max_q;
priority_queue<int, vector<int>, greater<int>> min_q;
MedianFinder() {}
void addNum(int num) {
if(min_q.empty() || num >= min_q.top()){
min_q.push(num);
if (min_q.size() > max_q.size() + 1) {
max_q.push(min_q.top());
min_q.pop();
}
} else {
max_q.push(num);
if (max_q.size() > min_q.size()) {
min_q.push(max_q.top());
max_q.pop();
}
}
}
double findMedian() {
if ((max_q.size() + min_q.size()) % 2 == 0) return (min_q.top() + max_q.top()) / 2.;
return min_q.top();
}
};
class FreqStack {
public:
unordered_map<int, int> freq;
unordered_map<int, vector<int>> buckets;
int max_freq = 0;
FreqStack() {}
void push(int val) {
freq[val]++;
max_freq = max(max_freq, freq[val]);
buckets[freq[val]].push_back(val);
}
int pop() {
int val = buckets[max_freq].back();
buckets[max_freq].pop_back();
if (buckets[max_freq].size() == 0) max_freq--;
freq[val]--;
return val;
}
};
class LRUCache {
private:
int _capacity;
list<pair<int, int>> l;
unordered_map<int, list<pair<int, int>>::iterator> m;
public:
LRUCache(int capacity) { _capacity = capacity; }
int get(int key) {
if (not m.count(key)) return -1;
l.splice(l.begin(), l, m[key]);
return m[key]->second;
}
void put(int key, int value) {
if (l.size() == _capacity and not m.count(key)) {
m.erase(l.back().first);
l.pop_back();
}
if (m.count(key)) l.erase(m[key]);
l.push_front({key, value});
m[key] = l.begin();
}
};
class Vector2D {
private:
int li, el, n;
public:
vector<vector<int>> v;
Vector2D(vector<vector<int>>& vec) {
for (auto vv: vec) {
if (!vv.empty()) v.push_back(vv);
}
n = v.size();
li = 0;
el = 0;
}
int next() {
int val;
val = v[li][el];
if (li < n - 1) {
if (el < v[li].size() - 1) el++;
else li++, el = 0;
} else {
if (el <= v[li].size() - 1) el++;
}
return val;
}
bool hasNext() {
if (n == 0) return false;
if (li < n - 1) return true;
else if (el <= v[li].size() - 1) return true;
return false;
}
};
struct pair_hash {
inline std::size_t operator()(const std::pair<int,int> & v) const {
return v.first*31+v.second;
}
};
class SnakeGame {
private:
int _w, _h, _i;
vector<vector<int>> _f;
queue<pair<int, int>> body;
unordered_set<pair<int, int>, pair_hash> lkp;
bool gameover = false;
public:
SnakeGame(int width, int height, vector<vector<int>>& food) {
_w = width, _h = height, _i = 0;
_f = food;
body.push({0, 0});
lkp.insert({0, 0});
}
pair<int, int> next_loc(pair<int, int> loc, string d) {
auto [r, c] = loc;
if (d == "U") return {r-1, c};
if (d == "D") return {r+1, c};
if (d == "L") return {r, c-1};
if (d == "R") return {r, c+1};
return {0, 0};
}
int move(string direction) {
auto [nr, nc] = next_loc(body.back(), direction);
if (nr < 0 or nr == _h or nc < 0 or nc == _w) {
gameover = true;
return -1;
}
if (_i < _f.size() and nr == _f[_i][0] and nc == _f[_i][1]) {
_i++;
} else {
auto old_tail = body.front(); body.pop();
lkp.erase(old_tail);
}
if (lkp.count({nr, nc})) {
gameover = true;
return -1;
}
lkp.insert({nr, nc});
body.push({nr, nc});
return body.size() - 1;
}
};
class Fancy {
private:
vector<array<int, 3>> num;
public:
Fancy() {}
int r_mul = 1, r_inc = 0, mod = 1000000007;
int modPow(int n, int p) {
if (p == 1)
return n;
long p2 = modPow(n, p / 2);
return (p2 * p2 % mod * (p % 2 ? n : 1)) % mod;
}
void append(int val) { num.push_back({val, r_mul, r_inc}); }
void addAll(int inc) { r_inc += inc; }
void multAll(int m) {
r_mul = (long)r_mul * m % mod;
r_inc = (long)r_inc * m % mod;
}
int getIndex(int idx) {
if (idx >= num.size())
return -1;
auto &[val, mul, inc] = num[idx];
auto ratio = (long)r_mul * modPow(mul, mod - 2) % mod;
return (ratio * (mod + val - inc) + r_inc) % mod;
}
};
class ExamRoom {
private:
int _n;
vector<int> seats;
public:
ExamRoom(int n) {
_n = n;
seats.clear();
}
int seat() {
int s = 0, dist, new_dist;
if (!seats.empty()) {
dist = seats[0];
for (int l = 0, r = 1; r < seats.size(); ++l, ++r) {
new_dist = (seats[r] - seats[l]) / 2;
if (new_dist > dist) {
dist = new_dist;
s = seats[l] + new_dist;
}
}
if (_n - 1 - seats.back() > dist) { s = _n - 1;}
}
seats.insert(upper_bound(seats.begin(), seats.end(), s), s);
return s;
}
void leave(int p) {
int i = 0;
for (; i < seats.size(); ++i) {
if (seats[i] == p) break;
}
seats.erase(seats.begin() + i);
}
};
class Excel {
private:
int n, m;
vector <unordered_map<int, int>> edges;
vector<int> grid;
public:
Excel(int _height, char _width) { // O(N*M) time/cur_space init
auto [height, width] = getCell(_height, _width);
n = height + 1;
m = width + 1;
edges.resize(n * m);
grid.resize(n * m, 0);
}
pair<int, int> getCell(int r, char c) { return {r - 1, c - 'A'};}
void set(int row, char column, int val) { // O(N*M) clear
auto [xx, yy] = getCell(row, column);
int x = xx * m + yy; //id
edges[x].clear();
grid[x] = val;
}
int dfs(int x) { // O(N*M)
int ret = grid[x];
for (auto &[y, z] : edges[x]) // O(N*M)
ret += dfs(y) * z;
return ret;
}
int get(int row, char column) { // O(N^2*M^2)
auto [x, y] = getCell(row, column);
return dfs(x * m + y);
}
void add(int row, char column, string &s) { // O(N*M)
auto [xx, yy] = getCell(row, column);
int x = xx * m + yy; // id of the cell
if (s.size() < 5) // streamline
s = s + ":" + s;
stringstream ss(s);
int r1, r2;
char c1, c2, q;
ss >> c1 >> r1 >> q >> c2 >> r2;
auto [i1, j1] = getCell(r1, c1);
auto [i2, j2] = getCell(r2, c2);
for (int i = i1; i <= i2; i++) {
for (int j = j1; j <= j2; j++) {
int y = i * m + j; // y is prereq to x
edges[x][y]++; //
}
}
}
int sum(int row, char column, vector<string> numbers) { // O(N^2*M^2)
set(row, column, 0); // O(N*M) reset the cell
for (auto &s : numbers) // 5
add(row, column, s); // O(N*M)
return get(row, column); // O(N^2*M^2)
}
};