読者です 読者をやめる 読者になる 読者になる

LeetCode

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.