leetcode
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()]) と書いていました…単語の順番を反転させま…
tags: leetcode 問題 Explore Problems アイデア ｢1次元配列が与えられた時，kだけ右に要素をずらせ｣という問題です．右端から右にずらした場合，左端に行きます． 解法 kを，kを配列の大きさで割った余りとします． これは配列の大きさと同じ分だけ右にずら…
tags: leetcode 問題 Explore Problems アイデア ｢n個の正の整数の配列を与えられた時，s以上の和を持つ連続した部分列の最小の大きさを探せ｣という問題です．ただし，部分列の大きさは最低でも2で，大きさが1のときは0を返します． 全探索をしようとすると…
tags: leetcode 問題 Explore Problems アイデア ｢2つの文字列を与えられた時，片方の文字列haystackに別の文字列needleが含まれているなら，needleがhaystackのどの位置から始まるか添字を返せ｣という問題です． needleが空文字のときは0を返します． 愚直…
tags: leetcode 問題 Explore Problems アイデア ｢バイナリの配列が与えられたとき，最長の1の列を探して長さを返せ｣という問題です． 解法 最大の長さと現在連続している長さの2つを保持して解きます． 計算量 配列の長さを$N$とします． 時間計算量 $O(N)$…
tags: leetcode 問題 Explore Problems アイデア ｢配列と値が与えられた時，新たにメモリを使わずに値と一致する全ての要素を取り除いてできる新たな配列の大きさを返せ｣という問題です． 実装するだけ(？)です． 解法 どうやら内部だと(意味がわからないが)…
tags: leetcode 問題 Explore Problems アイデア ｢2n個($n \in \mathbb{N}$)の整数の配列が与えられた時に，n個のペアを作り，それぞれのペアの小さい方の和を最大にせよ｣という問題です． 最小なものは絶対にこの和に加わるということに気付くと解くことが…
tags: leetcode 問題 Explore Problems アイデア ｢複数の文字列から，共通する最長の接頭辞を探せ｣という問題です．ない場合は空の文字列を返せば良いようです． 2文字列を比較して設備時を探す，これを全ての文字列に対して行うという2つの問題に分割出来る…
tags: leetcode 問題 Explore Problems アイデア ｢2つの二進数の文字列を与えられたとき，それらの和を二進数で返せ｣という問題です． 普段する計算と同じように文字列の小さい桁から見ていきます． 解法 a，bの文字列で現在見ている箇所を指すための変数a_p…
tags: leetcode 問題 Explore Problems アイデア ｢m x n行列が与えられたとき，右回りに螺旋状に動いた際に通る要素の配列にして返せ｣という問題です． 螺旋状に動くとは左上→右上→右下→左下→...のように動くことです(直感的には)． これを如何に実直に実装…
tags: leetcode 問題 Explore Problems アイデア ｢M x Nの行列が与えられたとき，対角線方向にジグザグに動いた時に通る要素を返せ｣という問題です． このような問題で重要なのは問題を小分けすることで，ここでは最初に右上から左下への対角線方向に進んだ…
tags: leetcode 問題 Explore Problems アイデア ハッシュ関数を用いたSetを実装する問題です． 解法 辞書を使うことで，実装します． 計算量 以下は時間計算量，空間計算量の順です． __init__ $O(1)$ $O(1)$ insert $O(1)$ $O(1)$ remove $O(1)$ $O(1)$ `g…
tags: leetcode 問題 Explore Problems アイデア 空でない整数列が与えられた時，$k$個の最も頻繁に現れる整数を返せという問題です． 整数と登場回数を結びつけるようなデータ構造を使えばいいですね． 解法 連想配列を使ってkey=整数，value=登場回数とし…
tags: leetcode 問題 Explore Problems アイデア 整数列A，B，C，Dが与えられるとき，それぞれの要素を1つずつ取り出してその総和が0となるようなものは何通り考えられるかを答えろという問題です． ナイーブに解こうとすると$O(N4)$が必要ですが，連想配列…
