Skip to content

Instantly share code, notes, and snippets.

@huynhthaihoa

huynhthaihoa/132-pattern

Created March 2, 2024 06:46
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save huynhthaihoa/e69a7cea261519ad390b65455a3c16fd to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save huynhthaihoa/e69a7cea261519ad390b65455a3c16fd to your computer and use it in GitHub Desktop.
Download ZIP
Stack
Raw
132-pattern
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
int i, j, k;
for(i = 0; i < n - 2; ++i)
{
for(j = n - 1; j > 1; --j)
{
if(nums[i] < nums[j])
{
for(k = i + 1; k < j; ++k)
{
if(nums[j] < nums[k])
return true;
}
}
}
// if(nums[i] < nums[i + 2] && nums[i + 2] < nums[i + 1])
// return true;
}
return false;
}
};
Raw
add-two-numbers-ii
/**
* Definition for singly-linked list.
* 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1;
stack<int> s2;
while(l1 != nullptr)
{
s1.push(l1->val);
l1 = l1->next;
}
while(l2 != nullptr)
{
s2.push(l2->val);
l2 = l2->next;
}
ListNode *res = nullptr;
ListNode *tmp = nullptr;
bool isLeap = false;
int sum = 0;
while(!s1.empty() || !s2.empty())
{
if(s1.empty())
sum = s2.top() + isLeap;
else if(s2.empty())
sum = s1.top() + isLeap;
else
sum = s1.top() + s2.top() + isLeap;
//cout << sum << endl;
if(sum >= 10)
{
sum -= 10;
isLeap = true;
}
else
isLeap = false;
tmp = new ListNode(sum);
if(res)
{
tmp->next = res;
res = tmp;
}
else
res = tmp;
//cout << res->val << endl;
if(!s1.empty())
s1.pop();
if(!s2.empty())
s2.pop();
}
if(isLeap)
{
tmp = new ListNode(1);
if(res)
{
tmp->next = res;
res = tmp;
}
}
//cout << "Pending!";
return res;
}
};
Raw
asteroid-collision
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
int n = asteroids.size();
vector<int> res;
for(int i = 0; i < n; ++i)
{
if(asteroids[i] < 0) //move to the left, possibly collide to the left asteroid
{
while(!res.empty() && res.back() > 0 && res.back() + asteroids[i] < 0)
res.pop_back();
if(res.empty() || res.back() < 0)
res.push_back(asteroids[i]);
else if(res.back() + asteroids[i] == 0)
res.pop_back();
}
else
res.push_back(asteroids[i]);
}
return res;
}
};
Raw
backspace-string-compare
class Solution {
public:
bool backspaceCompare(string s, string t) {
string sReal;
string tReal;
for(auto const &c: s)
{
if(c == '#')
{
if(sReal.size() > 0)
sReal.pop_back();
}
else
sReal.push_back(c);
}
for(auto const &c: t)
{
if(c == '#')
{
if(tReal.size() > 0)
tReal.pop_back();
}
else
tReal.push_back(c);
}
return sReal == tReal;
}
};
Raw
baseball-game
class Solution {
public:
int calPoints(vector<string>& ops) {
vector<int> record;
int idx = 0;
int pts = 0;
int n = ops.size();
for(int i = 0; i < n; ++i)
{
if(ops[i] == "C")
{
record.pop_back();
--idx;
}
else
{
if(ops[i] == "+")
record.push_back(record[idx - 1] + record[idx - 2]);
else if(ops[i] == "D")
record.push_back((record[idx - 1] * 2));
else
{
int tmp = 0;
bool isPositive = true;
for(auto const &c: ops[i])
{
if(c == '-')
isPositive = false;
else
tmp = (tmp * 10) + (c - '0');
}
record.push_back((isPositive)? tmp : - tmp);
}
++idx;
}
}
for(int i = 0; i < idx; ++i)
{
pts += record[i];
cout << record[i] << " ";
}
return pts;
}
};
Raw
crawler-log-folder
class Solution {
public:
int minOperations(vector<string>& logs) {
int count = 0;
for(auto const &log: logs)
{
if(log == "../")
{
if(count > 0)
--count;
}
else if(log != "./")
++count;
}
return count;
}
};
Raw
daily-temperatures
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> answer(n);
stack<pair<int, int>> mystack;
for(int i = n - 1; i > -1; --i)
{
while(mystack.size() && mystack.top().first <= temperatures[i])
mystack.pop();
if(mystack.size())
answer[i] = mystack.top().second - i;
mystack.push(make_pair(temperatures[i], i));
}
return answer;
}
};
Raw
decoded-string-at-index
class Solution {
public:
string decodeAtIndex(string s, int k) {
if(k == 1)
{
string r(1, s[0]);
return r;
}
string res = "";
for(auto const &c: s)
{
if(c < '0' || c > '9')
res.push_back(c);
else
{
string node = res;
for(char i = '1'; i < c; ++i)
res.append(node);
}
}
string r(1, res[k - 1]);
return r;
}
};
Raw
design-a-stack-with-increment-operation
class CustomStack {
private:
int* mVal;
int mMaxSize;
int mCurSize;
public:
CustomStack(int maxSize) {
mMaxSize = maxSize;
mVal = new int[mMaxSize];
mCurSize = -1;
}
void push(int x) {
if(mCurSize < mMaxSize - 1)
mVal[++mCurSize] = x;
}
int pop() {
if(mCurSize == -1)
return -1;
return mVal[mCurSize--];
}
void increment(int k, int val) {
int n = min(k - 1, mCurSize);
for(int i = 0; i <= n; ++i)
mVal[i] += val;
}
};
/**
* Your CustomStack object will be instantiated and called as such:
* CustomStack* obj = new CustomStack(maxSize);
* obj->push(x);
* int param_2 = obj->pop();
* obj->increment(k,val);
*/
Raw
design-browser-history
class BrowserHistory {
private:
vector<string> urlVector;
int curIndex;
public:
BrowserHistory(string homepage) {
urlVector.push_back(homepage);
curIndex = 0;
}
void visit(string url) {
int nErase = urlVector.size() - 1 - curIndex;
for(int i = 0; i < nErase; ++i)
urlVector.pop_back();
urlVector.push_back(url);
curIndex += 1;
}
string back(int steps) {
curIndex -= steps;
if(curIndex < 0)
curIndex = 0;
return urlVector[curIndex];
}
string forward(int steps) {
curIndex += steps;
if(curIndex >= urlVector.size())
curIndex = urlVector.size() - 1;
return urlVector[curIndex];
}
};
/**
* Your BrowserHistory object will be instantiated and called as such:
* BrowserHistory* obj = new BrowserHistory(homepage);
* obj->visit(url);
* string param_2 = obj->back(steps);
* string param_3 = obj->forward(steps);
*/
Raw
final-prices-with-a-special-discount-in-a-shop
class Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
int n = prices.size();
vector<int> res(n);
int i, j;
for(i = 0; i < n; ++i)
{
for(j = i + 1; j < n && prices[j] > prices[i]; ++j);
res[i] = (j == n)? prices[i] : prices[i] - prices[j];
}
return res;
}
};
Raw
largest-rectangle-in-histogram
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
map<pair<int, int>, int> minVal;
int n = heights.size();
int res = 0;
int i, j;
for(i = 0; i < n; ++i)
{
for(j = 1; j <= n - i; ++j)
{
if(j == 1)
minVal[{i, j}] = heights[i];
else
minVal[{i, j}] = min(minVal[{i, j - 1}], heights[i + j - 1]);
}
}
int tmp;
for(auto const &it: minVal)
{
tmp = it.first.second * it.second;
if(res < tmp)
res = tmp;
}
return res;
}
};
Raw
min-stack
class MinStack {
private:
vector<int> arr;
int size;
public:
/** initialize your data structure here. */
MinStack() {
size = 0;
}
void push(int x) {
arr.push_back(x);
++size;
}
void pop() {
arr.erase(arr.begin() + size - 1);
--size;
}
int top() {
return arr[size - 1];
}
int getMin() {
int idx = 0;
for(int i = 1; i < size; ++i)
{
if(arr[i] < arr[idx])
idx = i;
}
return arr[idx];
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
Raw
minimum-add-to-make-parentheses-valid
class Solution {
public:
int minAddToMakeValid(string s) {
int open = 0;
int close = 0;
for(auto const &c: s)
{
if(c == '(')
++open;
else if(c == ')')
{
if(open > 0)
--open;
else
++close;
}
}
return close + open;
}
};
Raw
remove-all-adjacent-duplicates-in-string-ii
class Solution {
public:
string removeDuplicates(string s, int k) {
//int n = s.size();
set<int> indexSet;
for(int i = 0; i < s.size(); ++i)
indexSet.insert(i);
while(indexSet.size() >= k)
{
bool hasDelete = false;
set<int>::iterator it = indexSet.begin();
int dist = 0;
while(it != indexSet.end())
{
int i;
for(i = 1; i < k; ++i)
{
set<int>::iterator check = it;
advance(check, i);
if(s[*check] != s[*it])
break;
}
if(i == k)
{
//int dist = distance(indexSet.begin(), it);
//remove from (it) to (it + k - 1)
set<int>::iterator last = indexSet.begin();
advance(last, dist + k);
indexSet.erase(it, last);
// for(int j = 0; j < k; ++j)
// {
// set<int>::iterator tmp = indexSet.begin();
// advance(tmp, dist);
// indexSet.erase(tmp);
// }
it = indexSet.begin();
advance(it, dist);
hasDelete = true;
}
else
{
advance(it, i);
dist += i;
}
}
if(!hasDelete)
break;
}
string res;
for(auto const &idx: indexSet)
res.push_back(s[idx]);
return res;
}
};
Raw
steps-to-make-array-non-decreasing
class Solution {
public:
int totalSteps(vector<int>& nums) {
int n = nums.size();
vector<bool> erases(n);
for(int i = 0; i < n; ++i)
erases[i] = false;
int cnt = 0;
while(true)
{
vector<int> eraseIndices;
int pivot = 0;
for(int i = 1; i < n; ++i)
{
if(!erases[i])
{
if(nums[i] < nums[pivot])
eraseIndices.push_back(i);
pivot = i;
}
}
if(!eraseIndices.size())
break;
for(int i = 0; i < eraseIndices.size(); ++i)
erases[eraseIndices[i]] = true;
++cnt;
}
return cnt;
}
};
Raw
valid-parentheses
class Solution {
public:
bool isValid(string s) {
stack<char> opens;
for(auto const &c: s)
{
if(c == '(' || c == '{' || c == '[')
opens.push(c);
else
{
if(!opens.empty() && ((c == ')' && opens.top() == '(') || (c == ']' && opens.top() == '[') || (c == '}' && opens.top() == '{')))
opens.pop();
else
return false;
}
}
return opens.empty();
}
};
Raw
valid-parenthesis-string
class Solution {
public:
bool checkValidString(string s) {
stack<int> left;
stack<int> asterisk;
int idx = 0;
for(auto const &c: s)
{
if(c == '(')
left.push(idx);
else if(c == '*')
asterisk.push(idx);
else
{
if(!left.empty())
left.pop();
else
{
if(!asterisk.empty())//'*'' plays a role of '('
asterisk.pop();
else
return false;
}
}
++idx;
}
while(!left.empty())//'*' plays a role of ')'
{
if(asterisk.empty() || (asterisk.top() < left.top()))
return false;
asterisk.pop();
left.pop();
}
return true;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment