Kuehar's Blog

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策として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 ...

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策として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 ...