Kuehar's Blog

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

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 [ ゼロから始めるLeetCode Day45 「1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree」 次回 ゼロから始めるLeetCode Day47 「14. Longest Common Prefix」 Twitter やってます。 問題 406. Queue Reconstruction by Height 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 待ち行列に立っている人のランダムなリストがあるとします。 それぞれの人は整数のペア、 (h,k) で構成されており、 h は人の高さ、 k はその人の前にいて h 以上の高さを持つ人の人数を指します。 この問題では与えられた待ち行列を再構成するようなアルゴリズムを設計します。 Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] 解法 二つの整数についてしっかりと整理し、的確にアルゴリズムを組むことが求められる良い問題です。 こういった問題の場合はやはり問題を細か

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day44「543. Diameter of Binary Tree」 次回 ゼロから始めるLeetCode Day46「406. Queue Reconstruction by Height」 Twitter やってます。 問題 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree 難易度はMedium。 original と cloned の2つのバイナリツリーが与えられ、 original の target への参照が与えられます。 複製されたツリーは、元のツリーのコピーで、複製されたツリー内の同じノードへの参照を返します。 2つのツリーまたは target を変更することは許可されておらず、回答は cloned されたツリー内のノードへの参照でなければなりません。 フォローアップ：ツリーで繰り返し値が許可されている場合は、問題を解決してください。 解法 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x #

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day43「5. Longest Palindromic Substring」 次回 ゼロから始めるLeetCode Day45 「1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree」 Twitter やってます。 問題 543. Diameter of Binary Tree 難易度はeasy。 Top 100 Liked Questionsからの抜粋です。 解いていたのに記事を書くのを忘れていたのを見つけたので書きます！ 問題としては、二分木が与えられます。 その木の直径を調べ、二点間のノードの最も長い経路の長さを返すようなアルゴリズムを設計する、というものです。 1 / \ 2 3 / \ 4 5 Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3]. この場合は3が返されるとなっていますね。 解説 # Definition for a binary tree node. # class TreeN

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day42「2. Add Two Numbers」 次回 ゼロから始めるLeetCode Day44「543. Diameter of Binary Tree」 Twitter やってます。 問題 5. Longest Palindromic Substring 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 文字列である s が与えられるのでその文字列の中で最も長い回文（どちらから読んでも同じになる）を探し出すようなアルゴリズムを設計してください。 Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Input: “cbbd” Output: “bb” 以前解いた、 ゼロから始めるLeetCode Day30「234. Palindrome Linked List」 こちらに似ていますが、前回はあくまで与えられた連結リストが回文であるかをチェックするだけであったのに対し、今回は文字列でその中から最長のものを抽出するというものに変わっており、少し複雑になっています。 解法 とはいえ、回文の問題のオーソドックスな考え方は前回のような要素をひっくり返した

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day40「114. Flatten Binary Tree to Linked List」 次回 ゼロから始めるLeetCode Day42「2. Add Two Numbers」 Twitter やってます。 問題 394. Decode String 問題としては、エンコードされた文字列を指定すると、そのデコードされた文字列を返すようなアルゴリズムを設計しましょう、というものです。 エンコーディングルールは、k[encoded_string]です。角かっこ内のencoding_stringは、正確にk回繰り返されます。 kは正の整数であることが保証されていることに注意してください。 入力文字列は常に有効であると想定できます。余分な空白はなく、角括弧は整形式などです。 さらに、元のデータに数字が含まれておらず、数字はこれらの繰り返し番号kのみに対応していると想定することもできます。たとえば、3aや2[4]のような入力はありません。 例としては以下の通りです。 s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s =

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day39「494. Target Sum」 次回 ゼロから始めるLeetCode Day41「394. Decode String」 Twitter やってます。 問題 114. Flatten Binary Tree to Linked List 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 二分木が与えられるので、フラットなリストに変換するようなアルゴリズムを設計してください。 これだけでは分かりづらいので例を見てみましょう。 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6 やはり例を見ると分かりやすいですね。 解法 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day38「208. Implement Trie (Prefix Tree)」 次回 ゼロから始めるLeetCode Day40「114. Flatten Binary Tree to Linked List」 Twitter やってます。 問題 494. Target Sum 自然数の配列 nums と自然数 S が与えられます。 +と-が与えられるので、配列を全て足すか引いてSの値と一致させるような組み合わせの数を返してください。 Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. こんな感じです。 言いたいことは例から分かると思います。 解法 class Solution : def calc ( self , nums , index , sums , S ) :

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day37「105. Construct Binary Tree from Preorder and Inorder Traversal」 次回 ゼロから始めるLeetCode Day39「494. Target Sum」 今はTop 100 Liked QuestionsのMediumを解いています。 Easyは全て解いたので気になる方は目次の方へどうぞ。 Twitter やってます。 問題 208. Implement Trie (Prefix Tree) 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 問題としては、insert関数、search関数、startsWith関数をTrieというクラスにまとめて実装してください、というものです。 なお、それぞれの挙動としては、 Trie trie = new Trie(); trie.insert(“apple”); trie.search(“apple”); // returns true trie.search(“app”); // returns false trie.startsWith(“app”); // returns true trie.insert(

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day36「155. Min Stack」 次回 ゼロから始めるLeetCode Day38「208. Implement Trie (Prefix Tree)」 問題 105. Construct Binary Tree from Preorder and Inorder Traversal 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 前回でEasyが全て解き終わったので今回からはMediumを解いていきます。 問題としては、木の構造として、 inorder と preorder が引数として与えられるので、それらを元に二分木を構築するようなアルゴリズムを書いてください、というものです。 preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree: 3 / \ 9 20 / \ 15 7 解法 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None,

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day35「160. Intersection of Two Linked Lists」 次回 ゼロから始めるLeetCode Day37「105. Construct Binary Tree from Preorder and Inorder Traversal」 問題 難易度はeasy。 Top 100 Liked Questionsのeasyはこれが最後の問題になります。 問題としては、push,pop,top,getMinという関数を持つMinStackクラスを実装してくださいというものです。 なお、それぞれの関数の仕様は以下の通り。 push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack. Input [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”] [[],[-2],[0],[-3],[],[],[],[]]

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day34「118. Pascal’s Triangle」 次回 ゼロから始めるLeetCode Day36「155. Min Stack」 問題 160. Intersection of Two Linked Lists Top 100 Liked QuestionsのEasy問題の最後から二つ目の問題です。 問題としては、2つの単方向連結リストの共通部分が始まるノードを見つけてくださいというものです。 例が図で解説されており、諸事情でこちらに直接載せることはできないので各々が確認して頂けると幸いです。 解法 最初こう書いたら、 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution : def getIntersectionNode ( self , headA : ListNode , headB : ListNode ) - > ListNode : if headA == No

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day33「1. Two Sum」 次回 ゼロから始めるLeetCode Day35「160. Intersection of Two Linked Lists」 問題 118. Pascal’s Triangle 偶然YouTubeでこの問題をJavaで解いてるのを見たので私も解いてみようと思いました。 難易度はEasyです！ 問題としては、自然数である numRows が与えられるので、例のようなパスカルの三角形を作ってください、という問題です。 Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 解説 最初と最後に1を入れることは確定しているので、予め1を挿入した状態を用意してあげて、処理の最後に再び1をappendしてあげれば良さそうです。 問題はどういう風に上位の数字の和を計算し、挿入するかについてですが、forループを二重に回せば二つ分の要素を取得し、足すことが出来そうですね。 なお、今回は numRows が0と1の場合は例外として除外するような書き方をしました。 こうすることで、3段目からの処理のみを書けば良いのでより読みやすいと思います。 class So