leetcode-スタック-キュー-スタック
69078 ワード
LeetCode-スタック-キュー-スタック
文書ディレクトリ LeetCode-スタック-キュー-スタック LeetCode 225-Implement Stack using Queues-キューでスタックを実装-easy LeetCode 232-Implement Queue using Stack-スタックでキューを実現-easy LeetCode 155-Min Stack-最小スタック-easy Leetcode 946-Validate Stack Sequences-検証スタックシーケンス-Medium LeetCode 224 - Basic Calculator - Hard LeetCode 215-Kth Largest Element in an Array-配列のk番目に大きい数-easy 二叉山 解 LeetCode 295-Find Median from Data Stream-中位数を探す-Hard 構想 に3種類の要素が追加された場合. コード LeetCode 225-Implement Stack using Queues-キューでスタック-easyを実現
キューを使用してスタックを実装するには、次の手順に従います.
注意:
キューの基本的な操作、すなわちpush to back、peek/pop from front、size、is emptyの操作しか使用できません.
あなたが使っている言語はキューをサポートしていないかもしれません.listまたはdeque(両端キュー)を使用して、標準的なキュー操作であれば、キューをシミュレートできます.
すべての操作が有効であると仮定できます(たとえば、空のスタックに対してpopまたはtop操作は呼び出されません).
問題の幹の要求は,キューのback関数,すなわち純粋な一方向キューを使用することはできない.
では、一時的なキューを借りる必要があります.
なぜかnTmpを使わず、直接
LeetCode 232-Implement Queue using Stack-スタックによるキュー-easyの実装
LeetCode 155-Min Stack-最小スタック-easy
push,pop,top動作をサポートし,定数時間(時間複雑度O(1))内で最小要素を取得できるスタックを設計した.
例:
最初の2つの問題の時間的複雑さはいずれもO(n)である.考えは空間で時間を変えることですが、4つだけプライベート変数nMinを追加するとpopの後、
1つの変数がだめなら、複数の変数を追加します:最小値スタック、topは現在の状態の最小値を記録します.
コンテナにアクセスするには、空であるかどうかを判断する必要があります.
Leetcode 946-Validate Stack Sequences-検証スタックシーケンス-Medium
同様にpojプラットフォーム1363 Railsもある.
pushedとpoppedの2つのシーケンスが与えられ、各シーケンスの値は重複せず、最初の空きスタックで行われたプッシュpushとポップアップpop操作シーケンスの結果である可能性がある場合にのみtrueを返す.そうでなければfalseを返します.
例1:
例2:
考え方は、pushedシーケンスをスタックに格納することによって、
この複雑さはO(n)であり,n方ではない.
LeetCode 224 - Basic Calculator - Hard
単純な文字列式の値を計算するために、基本的な計算機を実装します.
文字列式には、左かっこ(,右かっこ)、プラス記号+,マイナス記号-,非負の整数およびスペースを含めることができます.
例:
説明:
与えられた式が有効だと仮定することができます.内蔵のライブラリ関数evalは使用しないでください.
デジタルスタックとシンボルスタックに基づいて、逆ポーランド式を実現する必要があります.接尾辞式とも呼ばれます.
設計ステータスマシン:
'0'-'9'
parentheses
'0'-'9'
'+''-'
'0'-'9'
begin
number state
operaition state
フレーム:
完全版:
LeetCode 215-Kth Largest Element in an Array-配列でk番目に大きい数-easy
ソートされていない配列にk番目の最大要素が見つかります.配列ソート後のk番目の最大要素であり、k番目の異なる要素ではないことに注意してください.
例1:
例2:
説明:
kは常に有効であり、1≦k≦配列の長さであると仮定することができます.
ふたまた山
最大/小二叉スタック:最大/小値が先に出る完全二叉木.
最大ヒープ:
1
4
6
7
10
33
99
最小ヒープ:
1
4
6
7
99
スタックは優先キューとも呼ばれ、
解
topをk番目に大きい数にするには、二叉木の残りの要素は、スタックトップのk−1より大きい数、すなわち、1つの要素個数kの最小スタックを借りる必要がある.
LeetCode 295-Find Median from Data Stream-中位数を探す-Hard
中位数は、シーケンステーブルの中央にある数です.リスト長が偶数の場合、中央値は中間の2つの数の平均です.
たとえば、
次の2つの操作をサポートするデータ構造を設計します.
例:
ステップ:データストリームのすべての整数が0から100の範囲内にある場合、アルゴリズムをどのように最適化しますか? データストリームの99%の整数が0から100の範囲内にある場合、アルゴリズムをどのように最適化しますか?
構想
最も愚かな方法は、追加するたびに配列をソートし、addNumはO(n)、findMedianはO(1)である.中位数を検索してソートするとaddNumはO(1)、findMedianはO(nlogn)となります.
両方の操作がランダムであるため,n回の操作の最も理想的な複雑さはn方である.
考え方は,最上位と最小のスタックでそれぞれ半分のデータを格納し,最上位topを最小のスタックtopより小さく保つことである.
最小スタックには大きなデータの半分が格納されていることが明らかになった.
要素を3種類追加した場合.
2つのスタックsizeが同時に存在する場合:の新しい要素が2つのtopより小さい場合、小さなデータに追加されます(最大スタック). の新しい要素が2つのtopより大きい場合、大きなデータの半分(最小スタック)に追加されます.
最大ヒープは最小ヒープより1つ多い要素:の新しい要素は最も大きなtopより大きく、直接pushは少ない最小のスタックに入る. の新しい要素が最上位のtopより小さい場合は、pushが最大のスタックに入るに違いありませんが、まずtopを最小のスタックに追加します.
最大スタックは最小スタックより1つの要素が少なく、クラスは前の場合よりもよい.
コード#コード#
文書ディレクトリ
キューを使用してスタックを実装するには、次の手順に従います.
push(x) -- x
pop() --
top() --
empty() --
注意:
キューの基本的な操作、すなわちpush to back、peek/pop from front、size、is emptyの操作しか使用できません.
あなたが使っている言語はキューをサポートしていないかもしれません.listまたはdeque(両端キュー)を使用して、標準的なキュー操作であれば、キューをシミュレートできます.
すべての操作が有効であると仮定できます(たとえば、空のスタックに対してpopまたはtop操作は呼び出されません).
問題の幹の要求は,キューのback関数,すなわち純粋な一方向キューを使用することはできない.
では、一時的なキューを借りる必要があります.
class MyStack {
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
//
std::queue<int> queTmp;
queTmp.push(x);
int nTmp = 0;
while(!queData.empty())
{
nTmp = queData.front();
queTmp.push(nTmp);
queData.pop();
}
while(!queTmp.empty())
{
nTmp = queTmp.front();
queData.push(nTmp);
queTmp.pop();
}
//queData.swap(queTmp);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int nTmp = queData.front();
queData.pop();
return nTmp;
}
/** Get the top element. */
int top() {
return queData.front();
}
/** Returns whether the stack is empty. */
bool empty() {
return queData.empty();
}
private:
std::queue<int> queData;
};
なぜかnTmpを使わず、直接
push(front())であればメモリ消費がもっと大きい.LeetCode 232-Implement Queue using Stack-スタックによるキュー-easyの実装
：
push(x) -- 。
pop() -- 。
peek() -- 。
empty() -- 。
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
std::stack<int> sTmp;
while(!sData.empty())
{
sTmp.push(sData.top());
sData.pop();
}
sData.push(x);
while(!sTmp.empty())
{
sData.push(sTmp.top());
sTmp.pop();
}
// swap
//sTmp.swap(sData);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int n = sData.top();
sData.pop();
return n;
}
/** Get the front element. */
int peek() {
return sData.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return sData.empty();
}
private:
std::stack<int> sData;
};
LeetCode 155-Min Stack-最小スタック-easy
push,pop,top動作をサポートし,定数時間(時間複雑度O(1))内で最小要素を取得できるスタックを設計した.
push(x) —— x 。
pop() —— 。
top() —— 。
getMin() —— 。
例:
：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
：
[null,null,null,null,-3,null,0,-2]
：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> -3.
minStack.pop();
minStack.top(); --> 0.
minStack.getMin(); --> -2.
最初の2つの問題の時間的複雑さはいずれもO(n)である.考えは空間で時間を変えることですが、4つだけプライベート変数nMinを追加するとpopの後、
1つの変数がだめなら、複数の変数を追加します:最小値スタック、topは現在の状態の最小値を記録します.
コンテナにアクセスするには、空であるかどうかを判断する必要があります.
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
sData.push(x);
if(sMin.empty())
{
sMin.push(x);
}
else
{
sMin.push( x < sMin.top() ? x : sMin.top());
}
}
void pop() {
sData.pop();
sMin.pop();
}
int top() {
return sData.top();
}
int getMin() {
return sMin.top();
}
private:
std::stack<int> sData;
// ，top 。
std::stack<int> sMin;
};
Leetcode 946-Validate Stack Sequences-検証スタックシーケンス-Medium
同様にpojプラットフォーム1363 Railsもある.
pushedとpoppedの2つのシーケンスが与えられ、各シーケンスの値は重複せず、最初の空きスタックで行われたプッシュpushとポップアップpop操作シーケンスの結果である可能性がある場合にのみtrueを返す.そうでなければfalseを返します.
例1:
：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
：true
： ：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
例2:
：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
：false
：1 2 。
考え方は、pushedシーケンスをスタックに格納することによって、
pushed.top() == poped.front()の判定があり、マッチングはいずれもpopである.最後のスタックが空の場合はtrueを返します.この複雑さはO(n)であり,n方ではない.
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> s;
int nSize = pushed.size();
int j = 0;
for (int i = 0; i < nSize; ++i)
{
s.push(pushed[i]);
while(!s.empty() && s.top() == popped[j])
{
s.pop();
++j;
}
}
return s.empty() ? true : false;
}
};
LeetCode 224 - Basic Calculator - Hard
単純な文字列式の値を計算するために、基本的な計算機を実装します.
文字列式には、左かっこ(,右かっこ)、プラス記号+,マイナス記号-,非負の整数およびスペースを含めることができます.
例:
: "(1+(4+5+2)-3)+(6+8)"
: 23
説明:
与えられた式が有効だと仮定することができます.内蔵のライブラリ関数evalは使用しないでください.
デジタルスタックとシンボルスタックに基づいて、逆ポーランド式を実現する必要があります.接尾辞式とも呼ばれます.
設計ステータスマシン:
'0'-'9'
parentheses
'0'-'9'
'+''-'
'0'-'9'
begin
number state
operaition state
フレーム:
for (int i = 0; i < nLen; ++i)
{
if ( s[i] == ' ' ) continue;
switch(state)
{
case STATE_BEGIN:
// judge STATE
--i
break;
case STATE_NUM:
// if num, number = ...
// else, compute, then STATE_OP
break;
case STATE_OP:
// if +-, push, then set bCalc
// if (, STATE_NUM, unset bCalc
// if ), compute
// if num, STATE_NUM
break;
}
}
if (nRes != 0)
{
stackNum.push(nRes);
compute(stackNum, stackOp);
}
else if( nRes == 0 && stackNum.empty())
{
return 0;
}
完全版:
class Solution {
public:
int calculate(string s) {
// (2**31-1 ， long
std::stack<long> stackNum;
std::stack<char> stackOp;
long nNum = 0;
enum State state = STATE_BEGIN;
bool bCalc = false;
int nLen = s.length();
for (int i = 0; i < nLen; ++i)
{
if (s[i] == ' ') continue;
switch (state)
{
case STATE_BEGIN:
// judge STATE
state = (s[i] >= '0' && s[i] <= '9')
? STATE_NUM
: STATE_OP;
--i;
break;
case STATE_NUM:
// if num, number = ...
// else, compute, then STATE_OP
if (s[i] >= '0' && s[i] <= '9')
{
nNum = nNum * 10 + s[i] - '0';
}
else
{
stackNum.push(nNum);
if (bCalc)
{
compute(stackNum, stackOp);
}
nNum = 0;
--i;
state = STATE_OP;
}
break;
case STATE_OP:
// if +-, push, then set bCalc
// if (, STATE_NUM, unset bCalc
// if ), compute
// if num, STATE_NUM
if (s[i] == '+' || s[i] == '-')
{
stackOp.push(s[i]);
bCalc = true;
}
else if (s[i] == '(')
{
state = STATE_NUM;
bCalc = false;
}
else if (s[i] == ')')
{
compute(stackNum, stackOp);
}
else if (s[i] >= '0' && s[i] <= '9')
{
state = STATE_NUM;
--i;
}
break;
}
}
if (nNum != 0)
{
stackNum.push(nNum);
compute(stackNum, stackOp);
}
else if (nNum == 0 && stackNum.empty())
{
return 0;
}
return stackNum.top();
}
private:
void compute(std::stack<long> &stackNum, std::stack<char> &stackOp)
{
if (stackNum.size() < 2) return;
long nNum1 = stackNum.top();
stackNum.pop();
long nNum2 = stackNum.top();
stackNum.pop();
char cOp = stackOp.top();
if (cOp == '+')
{
stackNum.push(nNum2 + nNum1);
}
else if (cOp == '-')
{
stackNum.push(nNum2 - nNum1);
}
stackOp.pop();
}
private:
enum State {
STATE_BEGIN = 0,
STATE_NUM = 1,
STATE_OP = 2
};
};
LeetCode 215-Kth Largest Element in an Array-配列でk番目に大きい数-easy
ソートされていない配列にk番目の最大要素が見つかります.配列ソート後のk番目の最大要素であり、k番目の異なる要素ではないことに注意してください.
例1:
: [3,2,1,5,6,4] k = 2
: 5
例2:
: [3,2,3,1,2,4,5,5,6] k = 4
: 4
説明:
kは常に有効であり、1≦k≦配列の長さであると仮定することができます.
ふたまた山
最大/小二叉スタック:最大/小値が先に出る完全二叉木.
最大ヒープ:
1
4
6
7
10
33
99
最小ヒープ:
1
4
6
7
99
スタックは優先キューとも呼ばれ、
std::priority_queueコンテナに対応しています.int main()
{
std::vector<int> v({ 6, 10, 1, 7, 99, 4, 33 });
//
std::priority_queue<int> big_heap(v.begin(), v.end());
//
std::priority_queue<int, std::vector<int>, std::greater<int>> small_heap(v.begin(), v.end());
//
std::priority_queue<int, std::vector<int>, std::greater<int>> big_heap_1;
// 99
std::cout << big_heap.top() << std::endl;
// 1
std::cout << small_heap.top() << std::endl;
big_heap.push(1000);
// 1000
std::cout << big_heap.top() << std::endl;
big_heap.pop();
big_heap.pop();
big_heap.pop();
// 10
std::cout << big_heap.top() << std::endl;
return 0;
}
解
topをk番目に大きい数にするには、二叉木の残りの要素は、スタックトップのk−1より大きい数、すなわち、1つの要素個数kの最小スタックを借りる必要がある.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
std::priority_queue<int, std::vector<int>, std::greater<int>>
small_heap;
int nSize = nums.size();
for(int i = 0; i < nSize; ++i)
{
if (small_heap.size() < k)
{
small_heap.push(nums[i]);
}
else if ( nums[i] > small_heap.top())
{
small_heap.pop();
small_heap.push(nums[i]);
}
}
return small_heap.top();
}
};
LeetCode 295-Find Median from Data Stream-中位数を探す-Hard
中位数は、シーケンステーブルの中央にある数です.リスト長が偶数の場合、中央値は中間の2つの数の平均です.
たとえば、
[2,3,4] 3
[2,3] (2 + 3) / 2 = 2.5
次の2つの操作をサポートするデータ構造を設計します.
void addNum(int num) - 。
double findMedian() - 。
例:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
ステップ:
構想
最も愚かな方法は、追加するたびに配列をソートし、addNumはO(n)、findMedianはO(1)である.中位数を検索してソートするとaddNumはO(1)、findMedianはO(nlogn)となります.
両方の操作がランダムであるため,n回の操作の最も理想的な複雑さはn方である.
考え方は,最上位と最小のスタックでそれぞれ半分のデータを格納し,最上位topを最小のスタックtopより小さく保つことである.
最小スタックには大きなデータの半分が格納されていることが明らかになった.
要素を3種類追加した場合.
2つのスタックsizeが同時に存在する場合:
最大ヒープは最小ヒープより1つ多い要素:
最大スタックは最小スタックより1つの要素が少なく、クラスは前の場合よりもよい.
コード#コード#
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
if (big_heap.empty())
{
big_heap.push(num);
return;
}
int nBigHeap = big_heap.size();
int nSmallHeap = small_heap.size();
if (nBigHeap == nSmallHeap)
{
if (num < big_heap.top())
{
big_heap.push(num);
}
else
{
small_heap.push(num);
}
}
else if (nBigHeap > nSmallHeap)
{
if (num > big_heap.top())
{
small_heap.push(num);
}
else
{
small_heap.push(big_heap.top());
big_heap.pop();
big_heap.push(num);
}
}
else if (nBigHeap < nSmallHeap)
{
if (num < small_heap.top())
{
big_heap.push(num);
}
else
{
big_heap.push(small_heap.top());
small_heap.pop();
small_heap.push(num);
}
}
}
double findMedian() {
if (big_heap.size() == small_heap.size())
{
return (big_heap.top() + small_heap.top()) / 2.0;
}
return (big_heap.size() > small_heap.size())
? big_heap.top()
: small_heap.top();
}
private:
//
// top top
std::priority_queue<int> big_heap;
std::priority_queue<int, std::vector<int>, std::greater<int>> small_heap;
};