遙かなるマチョジニア

マッチョXエンジニアを目指すブログ

LeetCode

【LeetCode】Longest Substring Without Repeating Characters 解法【Python】

Longest Substring Without Repeating Characters leetcode.com 与えられた文字列内で、文字が重複しない範囲の最大の文字数を返却する。 解法 1文字見ていって、重複した時点の1文字前までの文字数を最大候補として、 重複した文字の最初に出てきた場所か…

【LeetCode】Maximum Product Subarray 解法【Python】

leetcode.com Maximum Subarrayの総乗バージョン。 しかし、解法が全然違う(自分が思いついた解法は)。 総和の場合と同じように、スプレッドシートで計算する。 ここから見えてきたものをルール化する。 inputの配列の内、最大になる候補を「特定範囲」と…

【LeetCode】Maximum Subarray 解法【Python】

Maximum Subarray leetcode.com inputの配列の内、隣接する数字の合計が最も高くなる値を求めよ。 制限:O(n) 二重loop使えば簡単に解けるがもちろんそれはダメ。 サンプルのINPUTを可視化すると↓ 4, -1, 2, 1 の範囲が最大で6になる。 それぞれ開始位置をず…

【LeetCode】Product of Array Except Self 解法【python】

leetcode.com これはかなり考えたけどO(N)かつ除算なしという制限をクリアする解放が思い付かずにいた。 solutionをちらっと見たら図が載っていてそれでなるほど、となった(ソースと解説は読んでいない)。 ある1次配列について、自分以外の要素を乗算した…

【LeetCode】Contains Duplicate 解法 【python】

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 - Best Time to Buy and Sell Stock leetcode.com 自分的な解法はfinalである。 v1は5800ms、finalは120ms。 v1はスライス多様しすぎなへっぽこコード。 finalはsolutionに書かれていたものを理解したもの。 ループを時系列に例えて、その際の最小…

【LeetCode】Two Sumの解法

LeetCode - Two Sum leetcode.com 解法。自分の場合は最初はv1(ブルートフォース)。 その次にv2(ハッシュ)、これで速度が100倍になった。 で、コメントをみてv3,finalです。 finalの場合、target - nums[i]をifの中で 計算しているようにしているが、if…