Kuehar's Blog

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

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day32「437. Path Sum III」 次回 ゼロから始めるLeetCode Day34「118. Pascal’s Triangle」 問題 1. Two Sum LeetCodeに登録した際に一番最初に解くであろう問題について書いてなかったので、今更ながら書きます。 難易度はEasy。 Top 100 Liked Questionsからの抜粋です。 問題としては、整数の入った配列と特定の値が格納された変数 target が与えられます。配列の中から二つの整数を選び、 target と一致する組み合わせを見つけ、配列のインデックスを返すような関数を実装してください。 なお、その組み合わせは一つしか存在せず、かつ同じ値を二度使うことは許されません。 Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. 解法 例えば全探索で書いてみるとこうなります。 全探索とはいわゆるしらみつぶしに調べるようにする書き方で、全てのパターンを調べようとする代わりに致命的なパフォーマンスとなってしまうことがほとんどです。 class Soluti

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day31「581. Shortest Unsorted Continuous Subarray」 次回 ゼロから始めるLeetCode Day33「1. Two Sum」 問題 437. Path Sum III 難易度はeasy。 Top 100 Liked Questionsのeasyがこれを入れて残り三問となりました。 各ノードに整数値が含まれている二分木が与えられます。 ノードの値を合計して特定の値 sum になるパスの数を求めます。 経路は親または葉で開始または終了する必要はありませんが、下方向に移動する必要があります（親ノードから子ノードへの移動のみ）。 なお、ツリーのノード数は1,000以下で、値の範囲は-1,000,000〜1,000,000です。 root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 Return 3. The paths that sum to 8 are: 5 -> 3 5 -> 2 -> 1 -3 ->

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day30「234. Palindrome Linked List」 次回 ゼロから始めるLeetCode Day32「437. Path Sum III」 問題 581. Shortest Unsorted Continuous Subarray 難易度はeasy。 Top 100 Liked Questionsからの抜粋です。 問題としては、整数の配列が与えられます。 この配列を昇順で並べ替えると、配列全体を昇順で並べ替えられる連続したサブ配列を見つけてください。 それらの中で最短のサブの配列を見つけ、その長さを返してください、という問題です。 例をみながら考えてみましょう。 Example 1: Input: [2, 6, 4, 8, 10, 9, 15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order. この中で並べ替えれば配列全体が昇順に整頓されるサブ配列の中最短のものは 6 から 9 までですので、その要素数を取得して5を返しています。 解法 ソートした変数と

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day29「46. Permutations」 次回 ゼロから始めるLeetCode Day31「581. Shortest Unsorted Continuous Subarray」 問題 234. Palindrome Linked List 単方向の連結リストが与えられるので、回文であるかをチェックしてください。 Example 1: Input: 1->2 Output: false Example 2: Input: 1->2->2->1 Output: true 解法 最も簡単な方法としては、与えられた連結リストをひっくり返したものと一致すれば True を、一致しなければ False を返すというものです。 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def isPalindrome ( self , head :

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day28「198. House Robber」 次回 ゼロから始めるLeetCode Day30「234. Palindrome Linked List」 問題 46. Permutations 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 異なる数字を集めたリストが与えられるので、全ての順列を返しなさい、という問題です。 タイトルのPermutationは順列という意味らしいですよ。 Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] これが全ての順列を返している例ですね。 解法 class Solution : def permute ( self , nums : List [ int ] ) - > List [ List [ int ] ] : return list ( itertools . permutations ( nums ) ) # Runtime: 36 ms, faster than 87.99% of Pytho