LeetCode
Climbing Stairs leetcode.com 動的計画法のジャンルとして紹介されていたので解いてみたが、 なんとなく動的計画法ぽいなあと思いつつ具体的な解放が思いつかず。 ツリー構造で表現してみる。 これはn=3のとき。ノードの部分の残りの数が同じ場合は、その子…
Reverse a Linked List leetcode.com 独自のリンクリストクラスを逆順にする問題。こういうのは現実問題として結構多いと思う。 解放としては、愚直にやるしかないって感じ。再帰使ったやりかたもあるが、可読性が下がるのであまり好きじゃない。 leetcodeの…
Sum of Two Integers leetcode.com 加算と減算を計算する関数を作る、ただし+と-を使わずに。という問題。 これは流石にわからなかった。バイナリ演算というのは想像できるが、 実際のアルゴリズムを考える余力もなく、答えをみた。 コード class Solution: …
Longest Substring Without Repeating Characters leetcode.com 与えられた文字列内で、文字が重複しない範囲の最大の文字数を返却する。 解法 １文字見ていって、重複した時点の１文字前までの文字数を最大候補として、 重複した文字の最初に出てきた場所か…
leetcode.com Maximum Subarrayの総乗バージョン。 しかし、解法が全然違う（自分が思いついた解法は）。 総和の場合と同じように、スプレッドシートで計算する。 ここから見えてきたものをルール化する。 inputの配列の内、最大になる候補を「特定範囲」と…
Maximum Subarray leetcode.com inputの配列の内、隣接する数字の合計が最も高くなる値を求めよ。 制限：O(n) 二重loop使えば簡単に解けるがもちろんそれはダメ。 サンプルのINPUTを可視化すると↓ 4, -1, 2, 1 の範囲が最大で6になる。 それぞれ開始位置をず…
leetcode.com これはかなり考えたけどO(N)かつ除算なしという制限をクリアする解放が思い付かずにいた。 solutionをちらっと見たら図が載っていてそれでなるほど、となった（ソースと解説は読んでいない）。 ある１次配列について、自分以外の要素を乗算した…
leetcode.com これはpythonだから簡単だった。set（集合）で重複が削除できるので、 listとsetでサイズが同じかどうかを判定すればOK。 class Solution: def containsDuplicate(self, nums: List[int]) -> bool: return len(nums) != len(set(nums))
LeetCode - Best Time to Buy and Sell Stock leetcode.com 自分的な解法はfinalである。 v1は5800ms、finalは120ms。 v1はスライス多様しすぎなへっぽこコード。 finalはsolutionに書かれていたものを理解したもの。 ループを時系列に例えて、その際の最小…
LeetCode - Two Sum leetcode.com 解法。自分の場合は最初はv1（ブルートフォース）。 その次にv2（ハッシュ）、これで速度が100倍になった。 で、コメントをみてv3,finalです。 finalの場合、target - nums[i]をifの中で 計算しているようにしているが、if…
