LeetCodeの問題を解き始めた当初、それぞれが新しい世界のように感じました。しばらくして、多くの問題が構造によってグループ化されていることに気づきました。パターンを認識すれば、問題は自ずと解けるのです。今日はスタックの問題です.
前回の記事ではスタックの動作について見ました。今日はその基礎を活かして、三つの古典的な問題を解決します。
ここで見つけるもの:
- ステップバイステップで解決する三つの問題: 平衡した括弧、文字列の逆転、パスの簡略化
- スタックがインタビューの外でどのように現れるか
急いで思い出そう
LIFO: 最後に追加されたものが最初に取り出される。push頂部に追加するpop トップから取り出す。JavaScriptでは配列はすでにスタックとして機能している。完全な詳細が必要な場合は、前の記事にある。
さて、問題に進む。
問題1: 平衡した括弧
問題: 文字列sが与えられ、それにはただ()[]{} が有効かどうか確認します。各開始タグには対応する閉じタグがあり、正しい順序で配置されている必要があります。
例
Input: "()[]{}" → true
Input: "([)]" → false
Input: "{[]}" → true
どう考えますか？
「最後に開いたものが最初に閉じられる」これがスタックが正しく行うことです。
文字列をたどります。各開き括弧はスタックに格納されます。各閉じ括弧はスタックの一番上と一致する必要があります。最後にスタックが空なら、すべて閉じたことを意味します.
解決策
function validParentheses(s) {
const stack = [];
const pairs = { ")": "(", "}": "{", "]": "[" };
for (const char of s) {
if (char === "(" || char === "{" || char === "[") {
stack.push(char);
} else if (stack.pop() !== pairs[char]) {
return false;
}
}
return stack.length === 0;
}
重要な点：
-
pairs閉じ括弧をそれぞれの開き括弧に対応させます. - 開き括弧はスタックに格納されます。閉じ括弧は
popし、検証します。 - スタックが空である場合に
popを実行すると、undefinedを返し、比較が失敗します。楽です、これで追加のチェックは必要ありません. - 最終的に、スタックは空である必要があります.
複雑性：O(n)時間とO(n)空間.
問題2：文字列の反転（簡単）
LeetCodeの"Reverse String"のアダプテーションスタックを使って単語を逆転させます
問題: 文字列sを与えられたら、その逆順の文字列を返します
例
Input: "stack" → "kcats"
Input: "hello" → "olleh"
どう考えたか？
「逆転させる」がヒントです。順番に要素を入れて、逆順に取り出す。それがスタックがするのと同じです。
実際にはs.split("").reverse().join("")を使えばいいし、それだけ。ここではスタックを使ってパターンが実際にどう動作するかを見る。
解決策
var reverseString = function (s) {
const stack = [...s]; // crea un stack con los caracteres
let reversed = "";
while (stack.length > 0) {
reversed += stack.pop();
}
return reversed;
};
全ての文字をスタックに入れ、一つずつ取り出す。popが最後に入ったものを返すので、文字は逆順で出てくる。
複雑性：O(n)時間とO(n)空間.
問題3：パスを簡略化する（中級）
問題：Unixの絶対パスをその標準形に変換する.
ルール：
-
.は現在のディレクトリを意味する. -
..は一つ上の階層に移動する. -
//は/と扱われる. - の結果は
/で終わらない、根を除く.
例
Input: "/home//foo/" → "/home/foo"
Input: "/../" → "/"
Input: "/a/./b/../../c/" → "/c"
どう考えたか？
..は何をする？ 直前のディレクトリに戻る.
そこに信号がある、私たちは通った道を覚えて戻れる必要がある.__JHSNS_SEG_9c3f6c85_74__ルートを分割する/ それぞれのコンポーネントをたどります：
-
""または"."は無視します。 -
".."でスタックのトップを取り出します。 - その他はディレクトリでスタックに追加されます。
最終的に、スタックには簡略化されたパスのディレクトリが含まれます。
解決策
var simplifyPath = function (path) {
const stack = [];
for (const part of path.split("/")) {
if (part === "" || part === ".") continue;
if (part === "..") stack.pop();
else stack.push(part);
}
return "/" + stack.join("/");
};
ヒント: JavaScriptにおいて、popがスタックが空である場合に何も壊さず、undefinedを返すだけです。そのため、ルートが根元を超えてアップロードしようとする場合、追加の検証は不要です。
複雑性: O(n)時間とO(n)空間です。
三つのパターン背後にあるもの
順番に読んでみると同じことに気づくでしょう。三者は根本的な同じ問題を解決します。以前の状態に戻る能力です.
- バランスの取れた括弧：閉じ括弧を検証するために最後の開き括弧を覚える.
- 文字列の反転：逆の順序に戻る.
- パスの簡略化：
..は一つ階層を戻します.
それはスタックのスーパーポワーだ。問題が最後に覚えておくこと、何かを取り消すこと、後ろから処理することを求める時、ほとんどの場合、答えはスタックだ.
インタビューを超えたスタック
スタックはインタビューの trivia ではない。『戻る』というパターンは至る所に現れる:
- ブラウザの戻るボタンはスタックだ.
- あなたのエディタの undo/redo もそうだ.
- 言語のスタックトレース（そのためスタックオーバーフローエラーが存在する）.
- データパイプラインは最後に見たもののコンテキストを保持する必要がある.
実践を続けるために
LeetCodeの難易度順に並べられた問題：
- Min Stack、簡単.
- Baseball Game、簡単.
- 逆ポーランド記法の評価、中級
- 日々の気温、中級。これは単調スタックのパターンの導入です
。どれが最も難しかった？コメントで教えてください。私にとってはSimplify Pathが解決するのに少し時間がかかりました。