Kuehar's Blog

速い速い速い こんな印象。 昔Pythonで解いたEasyの問題とかを遊びがてらJavaで解いてみました。 普段PythonでLeetCodeを解いている身からすると異常なほど速い。 いや、もちろん速さ自体はそりゃPythonはスクリプト言語だし、軽量だし、どっちかというと書きやすさや手軽に記述できる点が良いっていうのは分かってはいましたが、大体こんな感じだろうな〜ってJavaで適当に書いてもPythonが話にならないくらい。 そりゃそうだろお前何いってんだ。ってなる人がほとんどだとは思いますけど、いざ目の当たりにすると衝撃的だったので。 しかし書きやすさは圧倒的にPythonだし、これからもおそらくLeetCodeを解く時はPython、なんだろうけど・・・ うーん、通った時のコードが速いとすんごい脳汁がドバドバ出るんですよね。 昔Matzさんの講演会にいった時におっしゃってた「俺ってばすげー感」が味わえる感じがすごく心地いいというか。 あー、俺今この瞬間は間違いなく天才だわ。って感覚がたまらない。 でも解いてるのEasyだけどね。大体の人が解ける問題だけどね。 でも人と比べるよりも楽しく自分が気持ち良くなれるような楽しさがあった方が絶対いいし、爽快感もある。しかも一人で楽しんでいるので誰にも迷惑をかけなくて済む！ こんなに楽しくて役に立つ趣味があるだろうか、いや、ない（反語） これはハマるかもしれない・・・ あ、一応 リポジトリ を作って管理しているので気になる方はどうぞ。 僕が飽きなければ徐々に増えていくと思います。 なおC++はやりません。

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day64「287. Find the Duplicate Number」 次回 ゼロから始めるLeetCode Day66「438. Find All Anagrams in a String」 Twitter やってます。 問題 560. Subarray Sum Equals K 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 整数の配列と整数 k が与えられたとき，和が k に等しい連続部分配列の総数を求めよ、という問題です。 Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Constraints: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7]. 解法 import collections class Solution : def subarraySum ( self , nums : List [ int ] , k : int )

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day63 「195. Tenth Line」 次回 まだ Twitter やってます。 問題 287. Find the Duplicate Number 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 問題としては、各整数が1からnまでの間にあるn + 1の整数を含む配列 nums が与えられたとき，少なくとも1つの重複した数が存在しなければならないことを証明してください。 重複する数が1つしかないと仮定して，重複する数を求めるアルゴリズムを設計してください。 Example 1: Input: [1,3,4,2,2] Output: 2 Example 2: Input: [3,1,3,4,2] Output: 3 Note: 配列を変更してはいけません（配列は読み取り専用と仮定してください）。 定数，O(1) の余分な空間のみを使用しなければなりません。 実行時の複雑さは，O(n2)以下でなければなりません。 配列の中に重複する数は1つだけですが，それが複数回繰り返される可能性があります。 解法 読み取り専用であり、ソートできないという制約があるのを見落とさずに確認しておきましょう。 class Solution : def

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day62「83. Remove Duplicates from Sorted List」 次回 まだ Twitter やってます。 問題 195. Tenth Line 嗜好を少し変えて今回はshellについての問題です。 問題としては、テキストファイルである file.text が与えられます。10行目を出力してください。 Line 1 Line 2 Line 3 Line 4 Line 5 Line 6 Line 7 Line 8 Line 9 Line 10 Your script should output the tenth line, which is: Line 10 解法 awkコマンドを使って以下のように叩けば問題の条件を満たすことができます。 # Read from the file file.txt and output the tenth line to stdout. awk 'NR == 10' file.txt 実はLeetCodeの問題はアルゴリズムだけではなく、データベースなどについての問題もあります。（数は少ないですが・・・） 今後はアルゴリズムだけではなく、こういった問題もたまには乗せていけると良いかなぁと思います。 では今回はここ

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day61「7. Reverse Integer」 次回 まだ 今はTop 100 Liked QuestionsのMediumを優先的に解いています。 Easyは全て解いたので気になる方は目次の方へどうぞ。 Twitter やってます。 問題 83. Remove Duplicates from Sorted List 解いた問題と記事を書いた問題の管理が上手くできていなくて、てっきり書いたものだと思っていました。 ゼロから始めるLeetCode Day48 「26. Remove Duplicates from Sorted Array」 こっちの方しか書いてませんでした。 名前が紛らわしくて思わず笑っちゃいました。 さて、今回の問題ですが、連結リストが与えられるので、全ての要素が一度しか登場しないようにDuplicates(複製)を取り除いてください、という問題です。 Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1->2->3 解法 僕は以下のように書きました。 他言語特有のん？となるような要素も少ないですし、他

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 #問題 7. Reverse Integer 難易度はEasy。 32ビット符号付き整数 x が与えられたとき、整数の逆数を計算するアルゴリズムを設計してください、という問題です。 Input: 123 Output: 321 Input: -123 Output: -321 Input: 120 Output: 21 解法 Pythonの場合はスライスと abs を使えば要素の指定と絶対値の管理ができるので比較的解きやすいのではないかと思います。 他の言語については知りませんが、スタックを使って解くのが一般的なのかもしれませんね。 今回は32bit整数という前提があるため、処理に入る前に別の桁を追加してもオーバーフローしないかを事前に確認しておく方が良いでしょう。 Pythonではint型に最大値がないのでメモリの有る限りいくらでも計算できます。 なので以下のように自分で設定しておく必要があります。 max_32 = 2 ** 31 - 1 最初にこの値より x が大きかった場合は無条件で0を返すときちんと場合分けできていると思います。 そして、この後の分岐ですが、正の値ならば後ろから要素を取ってあげて、負の値ならば絶対値の逆から要素を取ってあげて代入する前に - を付けてあげます。 Pythonでは負の値ならば代入する要素の先

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day59 「1221. Split a String in Balanced Strings」 次回 ゼロから始めるLeetCode Day61「7. Reverse Integer Twitter やってます。 問題 1481. Least Number of Unique Integers after K Removals 難易度はMedium。 最近追加されたかなり新しめの問題ですね。 問題としては、配列の arr と整数の k が与えられます。 k 個分の要素を配列から削除した後、ユニークな整数の数の最小値を求めるアルゴリズムを設計してください、という問題です。 少し分かりづらいので例を見てみましょう。 Input: arr = [5,5,4], k = 1 Output: 1 Explanation: Remove the single 4, only 5 is left. この例だと1個の要素は配列内に 4 しかありません。なので4を削除します。 残った要素は 5 のみになるためそのまま 5 を返します。 Input: arr = [4,3,1,1,3,3,2], k = 3 Output: 2 Explanation: Remove 4, 2 and e

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day58 「20. Valid Parentheses」 次回 ゼロから始めるLeetCode Day60「1481. Least Number of Unique Integers after K Removals」 Twitter やってます。 問題 1221. Split a String in Balanced Strings 難易度はEasy。 問題としては、文字列 s が与えられます、この文字列の中には 'L' か 'R' しか入っていません。 これらの文字数が等しい文字列を最大量のバランスが取れた文字列で分割し、その分割の最大量を返してください。 自分で翻訳しててもわかりづらいのでとりあえず例を見てみましょう。 Input: s = “RLRRLLRLRL” Output: 4 Explanation: s can be split into “RL”, “RRLL”, “RL”, “RL”, each substring contains same number of ‘L’ and ‘R’. Input: s = “RLLLLRRRLR” Output: 3 Explanation: s can be split int

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day57 「35. Search Insert Position」 次回 ゼロから始めるLeetCode Day59 「1221. Split a String in Balanced Strings」 Twitter やってます。 問題 20. Valid Parentheses 難易度はEasy。 問題としては文字 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ および ‘]’ だけを含む文字列 s が与えられた場合、入力された文字列が有効かどうかを判断します。 入力文字列は、以下のような場合に有効です。 開いているカッコは、同じ種類のカッコで閉じなければなりません。 カッコは正しい順序で閉じなければなりません。 空の文字列も有効とみなされることに注意してください。 Input: “()” Output: true Input: “()[]{}” Output: true Input: “(]” Output: false Input: “([)]” Output: false Input: “{[]}” Output: true 解法 例を見ればわかりますが、括弧の中で別に括弧が完結すれば True になり得ますが、そうでない場合ならば

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day56 「1480. Running Sum of 1d Array」 次回 ゼロから始めるLeetCode Day58 「20. Valid Parentheses」 Twitter やってます。 問題 35. Search Insert Position 難易度はEasy。 とあるアルゴリズムを学ぶのに良い問題だと思ったので記事を書きました。 問題としては、ソートされた配列とターゲットの値が与えられたます。 ターゲットが見つかった場合はそのインデックスを返します。見つからなかった場合は、それが順番に挿入された場合のインデックスを返すような、アルゴリズムを設計してください、というものです。 なお、配列内に重複がないと仮定しても構いません。 Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0 解法 class Solution : def searchI

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day55「22. Generate Parentheses」 次回 ゼロから始めるLeetCode Day57 「35. Search Insert Position」 Twitter やってます。 問題 1480. Running Sum of 1d Array 難易度はEasy。 問題としては配列 nums が与えられます。全ての数を足した数をリストで返してください、という問題です。 Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4]. Example 2: Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]. Example 3: Input: nums = [3,1,2,10,1] Output: [3,4,6,16,17] Constraints: 1 &l

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day54 「1290. Convert Binary Number in a Linked List to Integer」 次回 ゼロから始めるLeetCode Day56 「1480. Running Sum of 1d Array」 Twitter やってます。 #問題 22. Generate Parentheses 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 問題としては、正の整数である n が与えられます。その数の括弧の組み合わせを全て書き出すようなアルゴリズムを設計しましょう、というものです。 最近知ったんですけど自然数って大学数学とかだと0も含むんですね・・・ For example, given n = 3, a solution set is: [ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ] 例を見た方が分かりやすいですね。 # 解法 組み合わせについての問題です、今回初見で解けなかったのでdiscussをチラチラ見て考え方を勉強して書きました。 カッコを右、`right`と左、`left`に分けて考えると分かりやすいです。 それぞれの引

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day53 「1365. How Many Numbers Are Smaller Than the Current Number」 次回 ゼロから始めるLeetCode Day55「22. Generate Parentheses」 Twitter やってます。 問題 1290. Convert Binary Number in a Linked List to Integer 難易度はEasy。 問題としては、単方向の連結リスト head が与えられます。 各ノードは 0 か 1 を値として持っており、それらを2進法の値として扱います。ここではそれらの二進法表記の値を10進法に直し、数字を返すアルゴリズムを設計してください、というものです。 Input: head = [1,0,1] Output: 5 Explanation: (101) in base 2 = (5) in base 10 Input: head = [0] Output: 0 Input: head = [1] Output: 1 Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] Output: 18880 Input: head =

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day52 「1351. Count Negative Numbers in a Sorted Matrix」 次回 ゼロから始めるLeetCode Day54 「1290. Convert Binary Number in a Linked List to Integer」 Twitter やってます。 問題 1365. How Many Numbers Are Smaller Than the Current Number 難易度はEasy。 良い問題だったので書きます。 問題としては、配列 nums が与えられます。 それらの配列の中の各要素が他の要素より大きい回数を導くようなアルゴリズムを設計してください、という問題です。 日本語的に難しいので例を見てみましょう。 Input: nums = [8,1,2,2,3] Output: [4,0,1,1,3] Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). For nums[1]=1 does not exist any smaller number than it. For nums[2]=2 the

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 [ゼロから始めるLeetCode Day51 「647. Palindromic Substrings」] 次回 ゼロから始めるLeetCode Day53 「1365. How Many Numbers Are Smaller Than the Current Number」 Twitter やってます。 問題 1351. Count Negative Numbers in a Sorted Matrix 難易度はEasy。 m*n の行列 grid が与えられます。その行と列両方とも増加が起こらないような形式でソートされています。 （つまり、要素の値が現状維持、ないしは減少する順である、ということです。） その grid のなかに存在する負の数を返すようなアルゴリズムを設計してください、という問題です。 Example 1: Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix. Example 2: Input: grid = [[3,2],[1,0]] Output: 0 Examp

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day50「739. Daily Temperatures」 次回 ゼロから始めるLeetCode Day52 「1351. Count Negative Numbers in a Sorted Matrix」 Twitter やってます。 問題 647. Palindromic Substrings 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 問題としては、文字列 s が与えられます。 この文字列内の回文の数を数え、その数を返すアルゴリズムを実装してください、というものです。 なお、開始インデックスまたは終了インデックスが異なる部分文字列は、同じ文字で構成されていても、異なる部分文字列としてカウントされます。 Input: “abc” Output: 3 Explanation: Three palindromic strings: “a”, “b”, “c”. Input: “aaa” Output: 6 Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”. 解法 よくある回文のチェック方法としては最初から文字列を舐めたものと反対

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day49 「1323. Maximum 69 Number」 次回 ゼロから始めるLeetCode Day51 「647. Palindromic Substrings」 Twitter やってます。 問題 739. Daily Temperatures 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 問題としては、それぞれの日の気温を格納したリストである T が与えられます。 それらの要素が入力の各日より暖かい気温になるまで何日かかるかを示すリストを返すアルゴリズムを設計してください。 例えば、 T = [73、74、75、71、69、72、76、73] である場合、返すリストは [1、1、4、2、1、1、0、0] となります。 なお、気温の長さは [1,30000] 、各気温は [30,100] の間で与えられるものとします。 問題を見た時、最初はえ？？なんで出力がこうなるの？と思いましたが、よくよく見てみたら自分の理解力が低いだけでした。 次の日との差とかではなく、単純に何日後にその日の気温を超えるかを導けば良いだけなんですね。 解法 最初に0が要素の長さ分入ったリストを用意してあげて、素直にリストを舐めていくのが分かりやすいかと思

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day48 「26. Remove Duplicates from Sorted Array」 次回 ゼロから始めるLeetCode Day50「739. Daily Temperatures」 Twitter やってます。 問題 1323. Maximum 69 Number 難易度はEasy。 Goodの数の方が多く、面白そうな問題だと思ったので紹介します。 6と9のみで構成された正の整数である num が与えられます。 一桁だけ数字を6から9,もしくは9から6に変えても良いので、 num を変えることのできる最大値にして返すようなアルゴリズムを設計してください、という問題です。 Input: num = 9669 Output: 9969 Explanation: Changing the first digit results in 6669. Changing the second digit results in 9969. Changing the third digit results in 9699. Changing the fourth digit results in 9666. The maximum number is 9969. Inpu

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day47 「14. Longest Common Prefix」 次回 ゼロから始めるLeetCode Day49 「1323. Maximum 69 Number」 Twitter やってます。 問題 26. Remove Duplicates from Sorted Array 難易度はEasy。 問題としては、ソートされた配列が与えられます。 その配列から重複した要素を削除し、書く要素を1回だけ表示し、新しい長さを返す、という問題です。 Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the returned length. Given nums = [0,0,1,1,1,2,2,3,3,4], Your function should return length = 5, with the first five elements of nums being modified t

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 [ ゼロから始めるLeetCode Day46「406. Queue Reconstruction by Height」 次回 ゼロから始めるLeetCode Day48 「26. Remove Duplicates from Sorted Array」 Twitter やってます。 問題 14. Longest Common Prefix 難易度はEasy。 箸休め的に解いた問題なのでそこまで難しくはないかもしれません。 問題としては、与えられた文字列の配列において、それぞれの文字列の中で最も長い共通部分を返すような関数を設計する、というものです。 仮に何も共通部分がない場合は "" を返します。 Input: [“flower”,“flow”,“flight”] Output: “fl” Example 2: Input: [“dog”,“racecar”,“car”] Output: “” Explanation: There is no common prefix among the input strings. 解法 class Solution : def longestCommonPrefix ( self , strs : List [ str