Exercises: 232. Implement Queue using Stacks
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Solution: take advantage of the features of both stacks
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
sta0.push( x );
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
while( !sta0.empty() ){
sta1.push( sta0.top() );
sta0.pop();
}
int ans = sta1.top();
sta1.pop();
while( !sta1.empty() ){
sta0.push( sta1.top() );
sta1.pop();
}
return ans;
}
/** Get the front element. */
int peek() {
while( !sta0.empty() ){
sta1.push( sta0.top() );
sta0.pop();
}
int ans = sta1.top();
while( !sta1.empty() ){
sta0.push( sta1.top() );
sta1.pop();
}
return ans;
}
/** Returns whether the queue is empty. */
bool empty() {
return sta0.empty();
}
protected:
stack<int> sta0;
stack<int> sta1;
};
int main()
{
MyQueue *obj = new MyQueue();
obj->push(1);
obj->push(2);
cout << obj->peek() << endl;
cout << obj->empty() << endl;
delete obj;
return 0;
}
Exercises: 155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Solution: store min value in an another stack when push a new number. Pop the top value if the last value is min value. Get the minimum element from the min stack.
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int val) {
nums.push( val );
if( mins.size() == 0 ){
mins.push( val );
}
else{
if( val <= mins.top() ){
mins.push( val );
}
}
}
void pop() {
if( nums.size() == 0 ) return ;
if( nums.top() == mins.top() ){
mins.pop();
}
nums.pop();
}
int top() {
return nums.top();
}
int getMin() {
return mins.top();
}
protected:
stack<int> nums;
stack<int> mins;
};
int main()
{
MinStack *obj = new MinStack();
obj->push(-2);
obj->push(0);
obj->push(-3);
cout << obj->getMin() << endl;
obj->pop();
cout << obj->top() << endl;
cout << obj->getMin() << endl;
delete obj;
return 0;
}
Exercises: 20. Valid Parentheses
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
Solution: use stack to compare the lastest char and the new char.
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
class Solution {
public:
bool IsValidPair( char ch0, char ch1 ){
if( ch0 == '(' && ch1 == ')' ){
return true;
}
if( ch0 == '{' && ch1 == '}' ){
return true;
}
if( ch0 == '[' && ch1 == ']' ){
return true;
}
return false;
}
bool isValid(string s) {
for( auto ch: s ){
if( charStack.size() && IsValidPair( charStack.top(), ch ) ){
charStack.pop();
}
else {
charStack.push( ch );
}
}
return charStack.size() == 0;
}
protected:
stack<char> charStack;
};
int main()
{
Solution *obj = new Solution();
cout << obj->isValid( "()[]{}" ) << endl;
delete obj;
return 0;
}
Exercises: 739. Daily Temperatures
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] 0 instead.
Solution: check the old values and set the number of the days when a new temperature comes.
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> ans;
for( auto value: temperatures )
{
ans.push_back( 0 );
for( int j = ans.size() - 2; j >= 0; --j ){
if( temperatures[j] >= value ){
break;
}
if( ans[j] == 0 && value > temperatures[j] ){
ans[j] = ans.size() - 1 - j;
}
}
}
return ans;
}
};
int main()
{
Solution *obj = new Solution();
vector<int> vec{ 73, 74, 75, 71, 69, 72, 76, 73 };
auto ans = obj->dailyTemperatures( vec );
for( auto element: ans ){
cout << element << "\t";
}
delete obj;
return 0;
}
Exercises: 23. Merge k Sorted Lists
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.Merge all the linked-lists into one sorted linked-list and return it.
Solution: use priority_queue to sort all elements and generate a list.
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
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) {
priority_queue <int,vector<int>,greater<int> > q;
for( auto myList: lists ){
while( myList ){
q.push( myList->val );
myList = myList->next;
}
}
if( q.empty() ){
return nullptr;
}
ListNode *head = new ListNode( q.top() );
ListNode *pointer = head;
q.pop();
while( !q.empty() ){
pointer->next = new ListNode( q.top() );
q.pop();
pointer = pointer->next;
}
return head;
}
};
int main()
{
Solution *obj = new Solution();
ListNode *list1 = new ListNode( 1 );
ListNode *tmp = new ListNode( 4 );
list1->next = tmp;
tmp = new ListNode( 5 );
list1->next->next = tmp;
vector<ListNode*> lists;
lists.push_back( list1 );
ListNode *nums = obj->mergeKLists( lists );
while( nums ){
cout << nums->val << "\t";
nums = nums->next;
}
delete obj;
return 0;
}
