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: 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のとき 右の部分木がなければ，左部分木を返せば良いです． 右の部分木…

tags: leetcode 問題 Explore Problems アイデア 配列内の0を全て末尾の方に移せという問題です． 末尾の要素と交換をすれば良いですね． 大事なのは与えられた配列を操作することは許されていますが，新たにメモリ内に配列を作ってコピーしてはいけないとい…

tags: leetcode 30-Day LeetCoding Challengeが始まったので問題を解いていきます 問題 Problems アイデア 整数列が与えられるので，その部分数列の和が最大と成る配列を探せという問題です． 解法 Kadane's Algorithm 配列の全ての要素を走査します． 今ま…

tags: leetcode 問題 Explore Problems アイデア inorderのBSTとpostorderのBSTが与えられた時に，BSTを構築しろという問題です． 木の探索順序 木を探索する際の順序として以下の図ように Inorder(左→根→右) Preorder(根→左→右) Postorder(左→右→根) があり…

tags: leetcode 問題 Explore Problems 実際のコーディングテストでPython3を使うことが多いことから，Python3で書くことに… 発言に一貫性がないという点で自分は一貫性がある？ アイデア BSTに新たな値を挿入しろという問題です． その値はBST内に存在しな…

tags: leetcode 問題 Explore Problems アイデア ｢ダイアル式の鍵で，4桁の暗証番号が0000から始まったときに，targetの番号になるのに最短で何回ダイアルを回せばよいのか｣という問題です． ただし，deadendsにある数字を経由しては行けないです． 全探索す…

tags: leetcode 問題 Explore Problems アイデア ｢2つの単一方向リストの共通部分がどこノードから始まるのかを探せ｣という問題です． 普通に1つ1つノードを辿っていけば良いでしょう． 解法 2つのリストをそれぞれA，Bとします． この際，それぞれのリスト…

tags: leetcode 問題 Explore Problems アイデア ｢kという整数と整数の配列を与えられたとき，i-j=kかつnums[i]==nums[j]となるようなiとjとなるものがあるかどうかを探す｣問題です． 解法 連想配列を用意します．(map[num[index]] = index) 0 <= i < nums.l…

tags: leetcode この問題はRustが使えなかったのでC++です． 問題 Explore Problems アイデア 以前やった問題と同じです． propyon.hateblo.jp 循環するような点を探す問題ではFloyd's cycleが使えます． 解法 2つのポインタを使います．一方(fast)はもう一…

tags: leetcode C++よりもRustの方が書いていて楽しいのでRustで書けそうな問題はRustで書いていくことにします． (コーディングインタビューで使われる程度のC++の文法ならば，普段から使っていなくてもなんとかなると楽観視しています) 問題 Explore Probl…

tags: leetcode 問題 Explore Problems アイデア 2つのレストラン名の格納された配列が与えられます． このときに，最も小さいindexの合計を持つ共通したレストランを探し，それらを配列に入れて返せという問題です． 連想配列が使えそうです． 解法 最初に…

tags: leetcode 問題 Explore Problems アイデア 文字列sとtが与えられた時に，isomorphicかどうか調べろという問題です． isomorphicとはsの文字がtの文字へ一対一に写像出来るということです． ただし，2種類の文字が同じ文字に写像されることはなく，ある…

tags: leetcode 問題 Explore Problems アイデア 与えられた2桁数がhappy numberかどうか返せという問題です． happy numberとは 各桁の2乗の和から出来た数をnext_numとします next_numが1になるときhappy numberです． next_numの各桁の2乗の和が1になるま…

tags: leetcode 問題 Explore Problems アイデア 連結リストが与えられたとき，循環がないかを返せという問題です． 追加の課題として これを$O(1)$のメモリで解くことがあります． この問題は末尾の次のノードに今まで訪れたことがあるかを調べればよく， …

tags: leetcode 問題 Explore Problems アイデア 島を1が縦横に繋がったものと考えて，0を海と考えます．このときに，島の数を返せという問題です． 蟻本の冒頭に類題がありました．DFS，BFSを使って解くことが可能です． 解法1(DFS･再帰) 現在の位置が島な…