leetcode問題解(スタックとキューの問題)
16385 ワード
スタックとキューは単純なデータ構造であるが,これらの単純なデータ構造を用いて解決されるアルゴリズム問題は必ずしも単純ではなく,主にスタックとキューに関連するleetcodeアルゴリズム問題を紹介する.
スタックの基礎応用
leetcode 20. 有効なかっこ
問題を解く構想.スタックというデータ構造を用いて「左シンボル」 を格納するスタックトップ要素は、ネストされた階層関係において、最近一致する必要がある要素 を反映する.
コード実装
そうじもんだい
leetcode 150. 逆ポーランド式の評価
leetcode 71. パスの簡略化
スタックと再帰の緊密な関係
まず二叉木の先順を見てみましょう
ぶんせき
具体的な遍歴を見てみましょう.親ノードが1で、左ノードが2で、右ノードが3であると仮定します.まず、ルートノードを使用して関数preorderを呼び出し、ノード2を使用して関数preorderを呼び出し、ノード3を使用して関数preorderを呼び出します.この3つのpreorderの入力パラメータは異なりますが、この3つの関数の呼び出し順序はどうですか.ルートノード呼び出しの場合、ノード2呼び出しが実行されるまで停止し、ノード2呼び出しが終了するまでサブ関数であるノード2の呼び出しを実行し、ノード3サブ関数の呼び出しを行うことを抽象化することができる.オペレーティングシステムはスタックによってこのような動作を実現する.ルートノードが呼び出す関数がスタックに押し込まれて実行が開始されると、関数スタックノード2に遭遇する.ノード2の関数がスタックに押し込まれた直後に実行され、実行が完了するまで値が返され(または返されない)、ノード2の関数がポップアップされる.ノード2の関数がポップアップされると、ノード1の関数が実行され続け、ノード3の関数が押し込まれて直ちに実行される.
leetcode144. ツリーの前順遍歴
そうじもんだい
leetcode 94. ツリーの中順遍歴
leetcode 145. 二叉木の後順遍歴
スタックシミュレーションを用いて再帰する
スタックシミュレーションシステムスタックを使用して、非再帰プログラムを書きます.私たちはまず右の子供を押し込み、左の子供を押し込み、最後に印刷を押し込みます.そうすれば、スタックの後進先出で先順遍歴が完了します.
そうじもんだい
leetcode 341
キューの一般的な応用
leetcode 102. ツリーの階層遍歴
実はキューQueueにとって、主に処理するアルゴリズムの問題は広さ優先遍歴(木:層序遍歴、図:無権図の最短経路)です.これは実は二叉木の層序遍歴ですが、多くの会社の面接問題で、普段は典型的な基礎データ構造の応用を重視しなければなりません.
コード実装
そうじもんだい
leetcode 107
leetcode 103
leetcode 199
図の広さ優先遍歴(BFS)と図の最短経路
図を優先的に巡回すると,最短経路の問題を解決できる.しかし、実際には多くのアルゴリズムの問題は、図の最短経路という考え方を使って解決されていますが、この問題の最初の目は図論の問題のように見えません.問題の説明では、図を使って問題を解決する必要があることを明確に教えてくれません.この場合、問題を深く分析し、モデリングする必要があります.
leetcode279. かんぜんへいきんすう
解決策
直感解法?欲張る?
欲張りアルゴリズムについては後述するが、欲張りアルゴリズムの実現は簡単だが、私たちは誤解に陥りやすい.一つの問題は欲張りアルゴリズムで解決できないが、欲張りアルゴリズムを使って解決できると思っている.
ワイドパスモデリング
この問題に対してモデリングする:全体の問題は1つの図論の問題に転化して、nから0まで、各数字は1つのノードを表して、もし2つの数字xからyが1つの完全な平方数差があるならば、1本の辺を接続して、私達は1つの無権図を得て、原の問題は変換して、この無権図の中でnから0までの最短の経路を求めます
ぶんせき
このように実装されるプログラムは、標準的な広さ優先実装ではなく、パフォーマンスの問題があります.問題は、num-i*iをキューに押し込むたびに、各数字が複数のパスから到達できるため、多くの重複が含まれています.冗長性を処理するために、0からnまでのn+1の数字がアクセスされたかどうかを示す新しい配列visitedを設立しました.
そうじもんだい
leetcode 127
leetcode 126
優先キュー(c++)
優先キューは特殊なキューであり、通常、優先キューの最下位実装はスタックである.スタックの最下位実装には、ホワイトボードを使用してプログラミングする必要があります.
c++ライブラリpriority_queue
優先キューに関するアルゴリズムの問題
leetcode 347. 前K個の高周波要素
最も簡単な考え方:統計周波数をスキャンする:ソートして前のk個の出現周波数が最も高い要素を見つけて、O(nlogn).
考えてみると、実はk個の要素を含む優先キューを維持することができます.巡回する要素がキュー内の最小周波数要素よりも頻度が高い場合は、キュー内の最小周波数の要素を取り出し、新しい要素をキューに入れます.最終的に、キューに残っているのは、最初のk個の出現頻度が最も高い要素である.
コード実装
ぶんせき上のコードの時間的複雑度はO(N*longK) である.しかしkがNに近づくと時間的複雑度はO(N*N) に脱皮する.は、kがNに近づくと、時間的複雑度がO(nlog(n-k)) である上記コードを修正することができる.
そうじもんだい
leetcode 23
-------------------------------華やかな分割線-----------------
见终わった友达は好き/関心を持つことができて、あなたの支持は私に対する最大の励ましです.
個人ブログトマトテクノロジースタック
もっと知りたいなら、私の微信の公衆番号に注目してください:トマト技術の小さなスタック
スタックの基礎応用
leetcode 20. 有効なかっこ
問題を解く構想.
コード実装
class Solution {
public:
bool isValid(string s) {
stack st;
for (int i = 0; i < s.size(); i++){
//
if (s[i] == '(' || s[i] == '{'|| s[i] == '['){
st.push(s[i]);
}else{
if (st.size() == 0){
return false;
}
char top = st.top();
st.pop();
char match;
if (s[i] == ')'){
match = '(';
}else if(s[i] == '}'){
match = '{';
}else{
assert(s[i] == ']');
match = '[';
}
if (top != match){
return false;
}
}
}
if (st.size() != 0){
return false;
}
return true;
}
};
そうじもんだい
leetcode 150. 逆ポーランド式の評価
leetcode 71. パスの簡略化
スタックと再帰の緊密な関係
まず二叉木の先順を見てみましょう
function preorder(node){
if(node){
cout << node -> val;
preorder(node.left);
preorder(node.right);
}
}
ぶんせき
具体的な遍歴を見てみましょう.親ノードが1で、左ノードが2で、右ノードが3であると仮定します.まず、ルートノードを使用して関数preorderを呼び出し、ノード2を使用して関数preorderを呼び出し、ノード3を使用して関数preorderを呼び出します.この3つのpreorderの入力パラメータは異なりますが、この3つの関数の呼び出し順序はどうですか.ルートノード呼び出しの場合、ノード2呼び出しが実行されるまで停止し、ノード2呼び出しが終了するまでサブ関数であるノード2の呼び出しを実行し、ノード3サブ関数の呼び出しを行うことを抽象化することができる.オペレーティングシステムはスタックによってこのような動作を実現する.ルートノードが呼び出す関数がスタックに押し込まれて実行が開始されると、関数スタックノード2に遭遇する.ノード2の関数がスタックに押し込まれた直後に実行され、実行が完了するまで値が返され(または返されない)、ノード2の関数がポップアップされる.ノード2の関数がポップアップされると、ノード1の関数が実行され続け、ノード3の関数が押し込まれて直ちに実行される.
leetcode144. ツリーの前順遍歴
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
vector vec;
preHelp(root, vec);
return vec;
}
private:
void preHelp(TreeNode* root, vector &vec){
if(root){
vec.push_back(root->val);
preHelp(root->left, vec);
preHelp(root->right, vec);
}
}
};
そうじもんだい
leetcode 94. ツリーの中順遍歴
leetcode 145. 二叉木の後順遍歴
スタックシミュレーションを用いて再帰する
スタックシミュレーションシステムスタックを使用して、非再帰プログラムを書きます.私たちはまず右の子供を押し込み、左の子供を押し込み、最後に印刷を押し込みます.そうすれば、スタックの後進先出で先順遍歴が完了します.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
private:
struct Command{
string s; // go, print
TreeNode* node;
Command(string s, TreeNode* node): s(s), node(node){}
};
public:
vector preorderTraversal(TreeNode* root) {
vector res;
if(root == NULL)
return res;
stack stack;
stack.push(Command("go", root));
while(!stack.empty()){
Command command = stack.top();
stack.pop();
if(command.s == "print")
res.push_back(command.node->val);
else{
assert(command.s == "go");
//stack.push(Command("print", command.node));//
if(command.node->right)
stack.push(Command("go",command.node->right));
//stack.push(Command("print", command.node));//
if(command.node->left)
stack.push(Command("go",command.node->left));
stack.push(Command("print", command.node));//
}
}
return res;
}
};
int main() {
return 0;
}
そうじもんだい
leetcode 341
キューの一般的な応用
leetcode 102. ツリーの階層遍歴
実はキューQueueにとって、主に処理するアルゴリズムの問題は広さ優先遍歴(木:層序遍歴、図:無権図の最短経路)です.これは実は二叉木の層序遍歴ですが、多くの会社の面接問題で、普段は典型的な基礎データ構造の応用を重視しなければなりません.
コード実装
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector> levelOrder(TreeNode* root) {
vector> res;
if (root == NULL){
return res;
}
queue> q;//
q.push(make_pair(root, 0));
while(!q.empty()){
TreeNode* node = q.front().first;
int level = q.front().second;
q.pop();
if (res.size() == level){
res.push_back(vector());
}
res[level].push_back(node->val);
if (node->left){
q.push(make_pair(node->left, level+1));
}
if (node -> right){
q.push(make_pair(node->right, level+1));
}
}
return res;
}
};
そうじもんだい
leetcode 107
leetcode 103
leetcode 199
図の広さ優先遍歴(BFS)と図の最短経路
図を優先的に巡回すると,最短経路の問題を解決できる.しかし、実際には多くのアルゴリズムの問題は、図の最短経路という考え方を使って解決されていますが、この問題の最初の目は図論の問題のように見えません.問題の説明では、図を使って問題を解決する必要があることを明確に教えてくれません.この場合、問題を深く分析し、モデリングする必要があります.
leetcode279. かんぜんへいきんすう
解決策
直感解法?欲張る?
12 = 9 + 1 + 1 + 1
12 = 4 + 4 + 4
欲張りアルゴリズムについては後述するが、欲張りアルゴリズムの実現は簡単だが、私たちは誤解に陥りやすい.一つの問題は欲張りアルゴリズムで解決できないが、欲張りアルゴリズムを使って解決できると思っている.
ワイドパスモデリング
この問題に対してモデリングする:全体の問題は1つの図論の問題に転化して、nから0まで、各数字は1つのノードを表して、もし2つの数字xからyが1つの完全な平方数差があるならば、1本の辺を接続して、私達は1つの無権図を得て、原の問題は変換して、この無権図の中でnから0までの最短の経路を求めます
class Solution {
public:
int numSquares(int n) {
queue> q;
q.push(make_pair(n, 0));// n ， n 0
while(!q.empty()){
int num = q.front().first;
int step = q.front().second;
q.pop();
if (num == 0){
return step;
}else{
for(int i = 1; num - i *i >= 0; i++){
q.push(make_pair(num - i *i, step + 1));
}
}
}
throw invalid_argument("no answer!");
}
};
ぶんせき
このように実装されるプログラムは、標準的な広さ優先実装ではなく、パフォーマンスの問題があります.問題は、num-i*iをキューに押し込むたびに、各数字が複数のパスから到達できるため、多くの重複が含まれています.
class Solution {
public:
int numSquares(int n) {
queue> q;
q.push(make_pair(n, 0));// n ， n 0
vector visited(n + 1, false);
visited[n] = true;
while(!q.empty()){
int num = q.front().first;
int step = q.front().second;
q.pop();
if (num == 0){
return step;
}else{
for(int i = 1; ; i++){
int tmp = num - i *i;
if (tmp < 0){
break;
}
if (!visited[tmp]){
q.push(make_pair(tmp, step + 1));
visited[tmp] = true;
}
}
}
}
throw invalid_argument("no answer!");
}
};
そうじもんだい
leetcode 127
leetcode 126
優先キュー(c++)
優先キューは特殊なキューであり、通常、優先キューの最下位実装はスタックである.スタックの最下位実装には、ホワイトボードを使用してプログラミングする必要があります.
c++ライブラリpriority_queue
#include pq;
for(int i = 0 ; i < 10 ; i ++){
int num = rand() % 100;
pq.push(num);
cout << "insert " << num << " in priority queue." << endl;
}
while(!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
cout << endl << endl;
// greater priority queue,
priority_queue, greater> pq2;
for(int i = 0; i < 10; i ++){
int num = rand() % 100;
pq2.push(num);
cout << "insert " << num << " in priority queue." << endl;
}
while(!pq2.empty()){
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl << endl;
// Comparator priority queue
priority_queue, function> pq3(myCmp);
for(int i = 0; i < 10; i ++){
int num = rand() % 100;
pq3.push(num);
cout << "insert " << num << " in priority queue." << endl;
}
while(!pq3.empty()){
cout << pq3.top() << " ";
pq3.pop();
}
return 0;
}
優先キューに関するアルゴリズムの問題
leetcode 347. 前K個の高周波要素
最も簡単な考え方:統計周波数をスキャンする:ソートして前のk個の出現周波数が最も高い要素を見つけて、O(nlogn).
考えてみると、実はk個の要素を含む優先キューを維持することができます.巡回する要素がキュー内の最小周波数要素よりも頻度が高い場合は、キュー内の最小周波数の要素を取り出し、新しい要素をキューに入れます.最終的に、キューに残っているのは、最初のk個の出現頻度が最も高い要素である.
コード実装
#include topKFrequent(vector& nums, int k) {
assert( k > 0 );
//
unordered_map freq;
for(int i = 0 ; i < nums.size() ; i ++ )
freq[nums[i]] ++;
assert( k <= freq.size() );
// freq, k
// , , ( , )
priority_queue< pair , vector> , greater> > pq;
for( unordered_map::iterator iter = freq.begin() ;
iter != freq.end() ; iter ++ ){
if( pq.size() == k ){
if( iter->second > pq.top().first ){
pq.pop();
pq.push( make_pair( iter->second , iter->first) );
}
}
else
pq.push( make_pair( iter->second , iter->first ) );
}
vector res;
while( !pq.empty() ){
res.push_back( pq.top().second );
pq.pop();
}
return res;
}
};
ぶんせき
そうじもんだい
leetcode 23
-------------------------------華やかな分割線-----------------
见终わった友达は好き/関心を持つことができて、あなたの支持は私に対する最大の励ましです.
個人ブログトマトテクノロジースタック
もっと知りたいなら、私の微信の公衆番号に注目してください:トマト技術の小さなスタック