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)$が必要ですが，連想配列…

tags: leetcode 問題 Explore Problems アイデア 重複した文字を持たない最長の文字列の長さを返せという問題です． 今まで現れた文字列を保持するデータ構造を使えば良さそうです． 解法 文字列のある部分を開始地点と終了地点までを見て，今までに現れた文…

tags: leetcode 問題 Explore Problems アイデア Jというジュエリーである宝石の種類を表現する文字列とSという持っている宝石を表現する文字列が与えられます．持っている宝石のうち，ジュエリーであるものの個数を返せという問題です． 解法 setでJの宝石…

tags: leetcode 問題 Explore Problems アイデア 二分木が与えられたとき，全ての同じ構造の部分木を返せという問題です． 解法 連想配列を使います． trees[あるノードの部分木] = あるノード helperという関数内関数を使って左部分木，右部分木に対して再…

tags: leetcode 問題 Explore Problems アイデア 縦，横，斜めそれぞれに1-9が重複していないかを確かめます． おそらくやるだけです… 解法 書きます． 計算量 ボードの1辺の長さを$N$とします．($N=9$ですが) 時間計算量 is_validメソッドは$O(N)$必要です…

tags: leetcode 問題 Explore Problems アイデア 文字列の配列が与えられた時，アナグラム(文字の位置を入れ替えて全く同じ文字列になる文字列群)をまとめて二次元配列で返せという問題です． …これと同じ問題を某社の面接で解かされました(なお前回は解けな…

tags: leetcode 問題 Explore Problems アイデア 昇順にソート済みの配列が与えられた時，高さのバランスが取れたBSTに変換しろという問題です． ソートした配列の中心の値よりも，右側は大きく，左側は小さいということを利用してやります． 解法 配列の中…

tags: その他 現在 題名のままです．少なくとも春学期の間に2つインターンの予定がありました． 片方は今年中の募集を取りやめ，もう片方はインターン受け入れをpendingという状況です． (留年しちゃったので)仕事をたくさんするつもりだったのですがしょう…

tags: leetcode 問題 Explore Problems アイデア 二分木が与えられるので，その木が高さがバランス木かどうかを判定しろという問題です． 高さがバランスとは 左右部分木の全てのノードの高さの差が1しかない ことを言うらしいです． 高さを求めることと，bo…

tags: leetcode 問題 Explore Problems アイデア 整数の配列numsが与えられたとき，abs(nums[i] - nums[j]) <= tかつabs(i - j) <= kであるようなiとjがあるかを探せという問題です． 解法 まずtは非負なのでその時点でFalseを返します 連想配列cache[numをt…

tags: leetcode 問題 Explore Problems アイデア BSTを与えられた時に，LCAを探せという問題です． LCA(lower common ancestor)とはあるノードpとqが与えられたときに，pとqを子として持つ，もしくはそのノード自身として持つノードのことです． 解法 LCAは…

tags: leetcode 問題 Explore Problems アイデア 配列のk番目に大きい要素を常に返すようなクラスを作れという問題です． 必要なのはk番目に大きい値なのでそれより小さい値は使わなくても良いです． また，配列を常に整列していれば時間計算量を効率化出来…

tags: leetcode 問題 Explore Problems アイデア 二分木を文字列に変換し，その文字列を二分木に戻すメソッドを書けという問題です． どのような変換の仕方でも良いようですが，メソッド間で使える変数を使ってその状態を保持しないようにしろとのことです．…

tags: leetcode スクリプト言語ってろくな言語がないような気がするのは私だけでしょうか… JS，Python，Shell script…Rubyがもっと海外で使われていればこうなっていなかったのか… 問題 Explore Problems アイデア 二分木を与えられた時，この木の2つのノー…

tags: leetcode 問題 Explore Problems アイデア 二分木が与えられた時に，あるノードと同じ深さにある右のノードをポインタnextで指せという問題です． 使用するメモリは定数倍でないといけないらしいですが，再帰ならセーフらしいです．今回は再帰の分がセ…

tags: leetcode 問題 Explore Problems アイデア 完全二分木が与えられた時に，あるノードと同じ深さにある右のノードをポインタnextで指せという問題です． 使用するメモリは定数倍でないといけないらしいですが，再帰ならセーフらしいです．今回は再帰の分…

tags: leetcode 最近の疑問としてPythonの関数内関数は出来るだけ使わない方がいいのかということがあります…(便利そうだし今後はもう少し使うことにしようかな…？) 問題 Explore Problems アイデア preorderのBSTとinorderのBSTが与えられた時に，BSTを構築…

tags: leetcode 問題 Explore Problems アイデア BSTのノードを削除せよという問題です．典型的な問題なのでやるだけ？ 解法(recursive) rootが空ならrootを返します． root.val == keyのとき 右の部分木がなければ，左部分木を返せば良いです． 右の部分木…