Matsushita's Blog

LeetCode

Binary Search Tree Iterator in LeetCode

問題 Binary Search Treeにおけるイテレータを実装する問題。next()メソッドで取得できる値は現時点での最小値となる。 Binary Search Tree Iterator - LeetCode ソースコード

House robber ⅲ in LeetCode

問題 2分木が与えられる。ノードは数値を持っていて以下の条件で数値の和が最大の値を見つける問題。 条件 直接つながれている隣同士のノードは取る事ができない。 House Robber III - LeetCode 解き方 それぞれのノードについて、そのノードの値を和に含め…

Serialize and Deserialize BST in LeetCode

問題 2分木に対するSerializeとDeserializeを実装するクラスを作る問題 leetcode.com ソースコード My simple and clear Java solution | LeetCode Discuss

Insert Delete GetRandom O(1) - Duplicates allowed

問題 通常のHashTableの機能に加え、テーブル内の要素をランダムで返すメソッドを実装されているデータ構造を作る。データ構造内の要素は重複が許されており、重複した要素の数はランダムな要素を返す関数に影響する。 leetcode.com ソースコード

Insert Delete GetRandom O(1)

問題 通常のハッシュテーブルの機能に加えて、テーブル内の要素をランダムで取得するメソッドが実装されたデータ構造をデザインする問題。 全ての操作はO(1)で行う必要がある。 leetcode.com 解法 HashMapとArrayListを用いることで解くことができる。問題は…

Add One Row to Tree

問題 2分木が与えられ、与えられた深さに1行分ノードを追加するという問題 leetcode.com ソースコード

Design TinyURL in LeetCode

Problem TinyUrl is a URL that a original URL is compressed. This problem is how should we design TinyURL services. https://leetcode.com/problems/design-tinyurl/#/solutionsDesign TinyURL - LeetCode How to code First, I prepare two HashMap t…

2分探索木からノードを削除する Delete Node in a BST in LeetCode

問題 2分探索木とint型のkeyが与えられる。BSTからkeyの要素を削除する問題。 leetcode.com 解法 以下のステップで解く 2分探索でkeyを見つける 削除するノードの右側のサブツリーの最小値を持つノードを削除するノードに置き換える。 右側のサブツリーから…

Perfect SquareかをO(logN)で判定する LeetCode

問題 leetcode.com 解法 単純にfor文を用いた解法だとO(√N)となり間に合わない。 2文探索を用いることでO(logN)で解くことができる。 ソースコード

Least Recently Used (LRU) cache を実装する

問題 LRUキャッシュとはキーとバリューをマッピングするデータ構造で、キャパティを超えたら最後に使われたキャッシュが削除されるという挙動をする。 leetcode.com 解法 HashMapと双方向連結リストを利用することで実装することができる。 リストを用いるこ…

平面上のN個の点を最も多く通る線を見つける

問題 xy平面上にN個の点が与えられる。最も多くの点を通るように直線を引いた時の点の最大値を求める問題 leetcode.com 解法 HashMapを用いることでO(N2)で解くことができる。forループを2回使い2つの点を全列挙する。2つの点のを結ぶ傾きをキーとして、H…

二分木のルートから葉までのルートを全列挙 Binary Tree Paths in LeetCode

問題 leetcode.com 解法 Pre-Oderで頑張る。 Tree traversal - Wikipedia

LinkedListが回文になっているか否かを判定 Palindrome Linked List in LeetCode

問題 leetcode.com 解法 通常の速さと、その2倍の速さでLinkedListを探索していくと、早いほうが末尾に到着する時に遅い方はちょうど中間地点にいる。 中間地点まできたら、そこから末尾まで進むと同時にリストを逆順にしていく。 ここまでの操作で、リスト…

2分木を左右対象にひっくり返す Invert Binary Tree in LeetCode

問題 leetcode.com それぞれのノードのleft, rightプロパティを交換すればOK。 ソースコード

Longest Substring Without Repeating Characters

問題 文字列sが与えられ、以下の条件での最大の部分文字列の長さを出力する。 条件は、部分文字列内には同じ文字は被ってはいけない。 leetcode.com 解法 ハッシュマップを用いて、キーに文字をバリューにその文字が出現した場所(index)を保存することでO(N…

N以下の素数の個数を求める Count Primes in LeetCode

問題 leetcode.com 解法 N√Nの解法だと間に合わない。 素数の倍数は全て素数ではないという性質を使って解く。 素数を見つけたら、その倍数を予め素数ではない印を付けておく。 ソースコード 参考 この解法の計算量はO(NloglogN)らしい。 www.youtube.com

隣接する要素は盗めない泥棒 House Robber in LeetCode 動的計画法

問題 N個の整数を持つ配列が与えられる。隣接する要素は取れないという条件で、各要素の和の最大を求める問題。 例 [1, 2, 3, 4, 5] という配列の場合は以下のようなとり方がある 1 , 3, 5 → 9 1, 4 → 5 1, 5 → 6 2, 4 → 6 2, 5 → 7 max = 9 leetcode.com 解…

2つのLinkedListが交わる点を見つける Intersection of Two Linked Lists in LeetCode

問題 2つのLinkedListが与えられ、2つが交差する点を見つける問題 leetcode.com 解法 HashMapを用いた解法は空間計算量がO(N)となるが、O(1)で解ける方法がある。 以下の2つの処理を同時に行う リストAを順番に先頭から見ていき、末尾までいったらリストB…

Excel Sheet Column Number

問題 アルファベットの文字列が与えられ、それをエクセルシートに対応した数字を出力する問題 leetcode.com ソースコード アルファベットから数字へ 数字からアルファベットへ

配列の中のマジョリティーを探す Majority Element in LeetCode

問題 Int型の配列が与えられて、出現回数が配列の要素数の過半数以上の物を出力する問題。 必ずマジョリティな要素は存在すると保証されている。 leetcode.com 解き方 HashMapを用いれば時間計算量O(N)で解けるが、空間計算量はO(N)になってしまう。この問題…

Best Time to Buy and Sell Stock in LeetCode

問題 Best Time to Buy and Sell Stock | LeetCode OJ ソースコード

3Sum Closest : LeetCode

Problem leetcode.com 与えられたInt型の配列numsの要素の内、3つ選んだ要素の和がtargetに最も近い値を見つける問題。 Solution 全列挙によるO(N3)の解法 配列の全ての3つの要素の和を算出し、その中から一番targetに近い値を見つける事で問題を解くこと…

Maximum Size Subarray Sum Equals k

Problem discuss.leetcode.com Solution This problem can be solved by using HashMap effectively. First, we store each sum of range from 0 to i (0 <= i < N). While we traverse the array, we check if the (sum - k) is stored in HashMap. If the …

Alien Dictionary : LeetCode

Problem https://leetcode.com/problems/alien-dictionary/?tab=Description Solution This problem can be solved by using Topological Sort.