tags: leetcode 問題 Explore Problems アイデア ｢無向グラフの deepcopy を作成し､返せ｣という問題です｡ BFS､DFSで実装出来ると思いますが､今回はBFSで実装します｡ 解法 Queueを使います｡つまりBFSです｡ 与えられた node を queue に格納します｡ 今まで通っ…

tags: leetcode 問題 Explore Problems アイデア ｢ポーランド記法で記述された数式を評価しろ｣という問題です｡ 数式はいつも正しく解くことが出来るそうで､特にエラー処理についか考える必要はなさそうです｡ 解法 そのままやるだけですが､プログラミング言語…

tags: leetcode 問題 Explore Problems アイデア ｢文字列が与えられ､正しいカッコであるかどうかを判定せよ｣という問題です｡ 正しいカッコかどうかはスタックを使えば簡単に判定することが可能です｡ 解法 文字列を走査して､文字の種類に応じて処理をします｡ …

tags: leetcode 問題 Explore Problems アイデア ｢毎日の気温の配列 T が与えられたとき､次にその日よりも温かい日が後何日で来るかを伝える配列を返せ｣という問題です｡こないならば 0 を代わりに返すようです｡ これは要素を1つずつ見て､それ以降の要素を見…

tags: leetcode 問題 Explore Problems アイデア ｢push，pop，top，getMinというメソッドをサポートするスタックを実装せよ｣という問題です．ただし，getMinの時間計算量は定数時間です． 実装するだけです． 解法 stackに(x，

tags: leetcode 問題 Explore Problems アイデア ｢正整数 $n$ が与えられた時， $n$ を平方数の和だけで表した時に，使うのに必要な最小の平方数の数を返せ｣という問題です． よくわからない… 解法 動的計画法でした(完) 配列を dp[i番目までの数] = iを平方…

tags: leetcode 問題 Explore Problems アイデア ｢ランダムな位置のノードを指すポインタを持つ単方向連結リストをdeep copyせよ，つまり完全にコピーせよ｣という問題です． やるだけですね(出来なかった並感)． 解法 連想配列を使ってコピーします． 最初に…

tags: leetcode 問題 Explore Problems アイデア ｢単方向連結リストを右向きにkだけ回転させろ｣という問題です． 解法 先頭のノードへのポインタを2つ作ります．(1つはノードの数を数え，最後のノードを先頭に繋げるp，1つは位置をずらす際に使うp) ノードを…

tags: leetcode 問題 Explore Problems アイデア ｢前後ポインタだけでなく，子リストへのポインタも持つ連結リストが与えられる．この複数層連結リストを単層化しろ｣という問題です． 与えられる連結リストのheadは最も上の層のもので，DFSをしろということ…

tags: leetcode 問題 Explore Problems アイデア ｢空でない2つの非負整数を表現する連結リストが与えられる．それらの桁は反対順に入れられており，それぞれ単一の桁を持つ．2つの数を足した値を連結リストで返せ｣という問題です． 問題なのは桁上がりくらい…

tags: leetcode 問題 Explore Problems アイデア ｢単方向連結リストが与えられた時，それが左右対称か判定しろ｣という問題です． 実装するだけの問題ですね…これも(自力で出来なかった顔) 解法 連結リストリストを前半と後半に分けます． ポインタを1つずつ…

tags: leetcode 問題 Explore Problems アイデア ｢後ろからn番目のノードを連結リストから取り除け｣という問題です． 2つのポインタを使います． 解法 片方のポインタをnつ先に進め，このポインタが末尾にたどり着いたときのもう片方のポインタが答えです． …

tags: leetcode 問題 Explore Problems アイデア ｢与えられた単方向連結リストの奇数番目のノード群から繋げて，偶数番目のノード群を繋げろ｣という問題です．つまり1->2->3->4->5->NULLを1->3->5->2->4にしろということです(1-indexed)． 更にin-place，つ…

tags: leetcode 問題 Explore Problems アイデア ｢valという値を連結リストから取り除け｣という問題です． やるだけです． 解法 先頭からvalと同じ値を持つノードを取り除きます． 問題の連結リストは単方向連結リストなので，node1->node2->node3->...と繋…

tags: leetcode 問題 Explore Problems アイデア ｢ソートされた配列から同じ要素を取り除いたサイトの配列の大きさを返せ｣という問題です． ただし，in-placeなアルゴリズムにせよとのこと．つまり$O(1)$で解く必要があります． 整列されているという特徴を…

tags: leetcode 問題 Explore Problems アイデア ｢文字列中にある単語を反転させた文字列を返せ｣という問題です． やるだけです． 解法 空白区切りで分解して，分解後の文字列を反転させます． 計算量 文字列の個数を$N$とし，それぞれの単語の最大の長さを$…

tags: leetcode 問題 Explore Problems アイデア ｢文字列が与えられるので，空白で区切られた単語を反転させて返せ｣という問題です． 最初は完全に問題を勘違いして " ".join([word[::-1] for word in s.split()]) と書いていました…単語の順番を反転させま…