スキップしてメイン コンテンツに移動

投稿

ラベル(Algorithm)が付いた投稿を表示しています

ゼロから始めるLeetCode Day98「39. Combination Sum」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day97 「349. Intersection of Two Arrays」 次回 ゼロから始めるLeetCode Day99 「112. Path Sum」 Twitter やってます。 問題 39. Combination Sum 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、候補番号(候補)(重複なし)と目標番号(目標)の集合が与えられたとき、候補番号の和が目標になるような、候補の中のすべてのユニークな組み合わせを求めなさい、というものです。 なお、同じ繰り返し数は何度でもいいとします。 Example 1: Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ] Example 2: Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ] 解法 class Solution : def combinationSum ( self , candidates

ゼロから始めるLeetCode Day96 「78. Subsets」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day95「82. Remove Duplicates from Sorted List II」 次回 ゼロから始めるLeetCode Day97 「349. Intersection of Two Arrays」 Twitter やってます。 問題 78. Subsets 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、異なる整数の集合 nums が与えられます。 その中の可能なすべての部分集合を返します。 なお、解の集合には重複した部分集合を含んではいけません。 Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 解法 class Solution : def subsets ( self , nums : List [ int ] ) - > List [ List [ int ] ] : ans = [ ] def dfs ( temp , end ) : ans . append (

ゼロから始めるLeetCode Day97 「349. Intersection of Two Arrays」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day96 「78. Subsets」 次回 ゼロから始めるLeetCode Day98「39. Combination Sum」 Twitter やってます。 問題 349. Intersection of Two Arrays 難易度はEasy。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、2つの配列が与えられたとき,その交点を計算する関数を書いてくださいというものです。 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2] Example 2: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] 解法 class Solution : def intersection ( self , nums1 : List [ int ] , nums2 : List [ int ] ) - > List [ int ] : set1 , set2 = set ( nums1 ) , set ( nums2 ) return list ( set1 &a

ゼロから始めるLeetCode Day95「82. Remove Duplicates from Sorted List II」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day94 「929. Unique Email Addresses」 次回 ゼロから始めるLeetCode Day96 「78. Subsets」 Twitter やってます。 問題 82. Remove Duplicates from Sorted List II 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、ソートされた連結リストが与えられた場合、重複した番号を持つすべてのノードを削除し、元のリストとは異なる番号のみを残します。 同様にソートされた連結リストを返します。 Example 1: Input: 1->2->3->3->4->4->5 Output: 1->2->5 Example 2: Input: 1->1->1->2->3 Output: 2->3 解法 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val #

ゼロから始めるLeetCode Day94 「929. Unique Email Addresses」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day93 「49. Group Anagrams」 次回 まだ Twitter やってます。 問題 929. Unique Email Addresses 難易度はEasy。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、すべての電子メールは、@記号で区切られたローカル名とドメイン名で構成されています。 例えば、alice@leetcode.com では、alice がローカル名で、 leetcode.com がドメイン名です。 小文字の他に、これらの電子メールには ‘.‘や’+‘が含まれている場合があります。 メールアドレスのローカル名の一部の文字の間にピリオド(’.’)を追加すると、ローカル名のドットがない同じアドレスに送信されたメールが転送されます。 例えば、「alice.z@leetcode.com」と「alicez@leetcode.com」は同じメールアドレスに転送されます。 (この規則はドメイン名には適用されませんのでご注意ください)。 ローカル名にプラス(’+’)を追加した場合、最初のプラス記号以降はすべて無視されます。これにより、特定のメールをフィルタリングすることができます。例えば、m.y+name@email.com は my@email.co

ゼロから始めるLeetCode Day93 「49. Group Anagrams」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day92 「4. Median of Two Sorted Arrays」 次回 まだ Twitter やってます。 問題 49. Group Anagrams 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としてはアナグラムである文字列の入った配列が与えられます。 Example: Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], Output: [ [“ate”,“eat”,“tea”], [“nat”,“tan”], [“bat”] ] 解法 class Solution : def groupAnagrams ( self , strs : List [ str ] ) - > List [ List [ str ] ] : ans = collections . defaultdict ( list ) for s in strs : sorted_word = '' . join ( sorted ( s ) ) ans [ sort

ゼロから始めるLeetCode Day92 「4. Median of Two Sorted Arrays」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day91「153. Find Minimum in Rotated Sorted Array」 次回 まだ Twitter やってます。 問題 4. Median of Two Sorted Arrays 難易度はHard。 問題としては、サイズ m と n の2つのソートされた配列 nums1 と nums2 がある。2つの並べ替え配列の中央値を求めよ。 なお、全体の実行時間の複雑さは, O(log (m+n)) でなければならず、 nums1 と nums2 はどちらも空ではないと仮定してもよい。 Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 解法 O(log(m+n)) である、ということは二分探索が使えますね。 ただ、難易度がHardということで、扱うリストが二つになっています。 これで書くコードの量が増えますし、書く量が増えるということは凡ミスも増える可能性が高くなります。 そして、二つとも同じ大きさのリストとは限らないのでその点もきちんと頭に入れておきましょう。

ゼロから始めるLeetCode Day90「1011. Capacity To Ship Packages Within D Days」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day89 「62. Unique Paths」 次回 ゼロから始めるLeetCode Day91「153. Find Minimum in Rotated Sorted Array」 Twitter やってます。 問題 1011. Capacity To Ship Packages Within D Days 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 コンベアベルトには,ある港から別の港へD日以内に出荷しなければならない荷物がある. コンベヤベルト上のi番目の荷物には重み[i]がある. 毎日,コンベヤベルト上の荷物を船に積み込む(重さで与えられた順序で).船の最大重量容量を超える重量を積むことはできない. コンベヤベルト上のすべての荷物がD日以内に出荷されるようになる船の最小重量容量を返します。 Example 1: Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5 Output: 15 Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1

ゼロから始めるLeetCode Day91「153. Find Minimum in Rotated Sorted Array」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day90「1011. Capacity To Ship Packages Within D Days」 次回 まだ Twitter やってます。 問題 153. Find Minimum in Rotated Sorted Array 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、昇順にソートされた配列を,あらかじめ知らないピボットで回転させたとします。([0,1,2,4,5,6,7]が[4,5,6,7,0,1,2]になるといったような例を思い浮かべていただけると分かりやすいかもしれません。) そのリストの中から最小の要素を探します。 なお、配列の中に重複した要素はないと考えてよい。 Example 1: Input: [3,4,5,1,2] Output: 1 Example 2: Input: [4,5,6,7,0,1,2] Output: 0 解法 class Solution : def findMin ( self , nums : List [ int ] ) - > int : low , high = 0 , len ( nums ) - 1

ゼロから始めるLeetCode Day89 「62. Unique Paths」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day88「139. Word Break」 次回 ゼロから始めるLeetCode Day90「1011. Capacity To Ship Packages Within D Days」 Twitter やってます。 問題 62. Unique Paths 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としてはユニークな経路の数を求める、というものです。 ロボットが m x n のグリッドの左上隅に位置しています(下図では「スタート」と表示されています)。 なお、ロボットはどの時点でも下か右にしか移動できません.ロボットはグリッドの右下隅に到達しようとしています(下図では「Finish」と表示されています)。 今回は図を載せないので、噛み砕いて考えたい方は直接問題のリンクで確認してください。 Example 1: Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: Right -> Right -> Down Ri

ゼロから始めるLeetCode Day88「139. Word Break」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day87 「 1512. Number of Good Pairs」 次回 ゼロから始めるLeetCode Day89 「62. Unique Paths」 Twitter やってます。 問題 139. Word Break 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、空ではない文字列 s と、空ではない単語のリストを含む辞書 wordDict が与えられた場合、 s が1つ以上の辞書単語のスペースで区切られたシーケンスに分割できるかどうかを判断する、というものです。 Example 1: Input: s = “leetcode”, wordDict = [“leet”, “code”] Output: true Explanation: Return true because “leetcode” can be segmented as “leet code”. Example 2: Input: s = “applepenapple”, wordDict = [“apple”, “pen”] Output: true Explanation: Return true because “applepenapple”

ゼロから始めるLeetCode Day87 「 1512. Number of Good Pairs」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day86 「33. Search in Rotated Sorted Array」 次回 ゼロから始めるLeetCode Day88「139. Word Break」 Twitter やってます。 問題 1512. Number of Good Pairs 難易度はEasy。 問題としては、整数の配列 nums が与えられます。 nums[i] == nums[j] で i < j の場合,ペア (i,j) を有効とし、有効であるペアの数を返すアルゴリズムを設計してください。 Example 1: Input: nums = [1,2,3,1,1,3] Output: 4 Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed. Example 2: Input: nums = [1,1,1,1] Output: 6 Explanation: Each pair in the array are good. Example 3: Input: nums = [1,2,3] Output: 0 解法 class Solution : def numIdentic

ゼロから始めるLeetCode Day86 「33. Search in Rotated Sorted Array」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day85 「6. ZigZag Conversion」 次回 ゼロから始めるLeetCode Day87 「 1512. Number of Good Pairs」 Twitter やってます。 問題 33. Search in Rotated Sorted Array 難易度はMedium。 問題としては、昇順にソートされた配列を,あらかじめ知らないピボットで回転させたとします( [0,1,2,4,5,6,7] が [4,5,6,7,0,1,2] になるかもしれません。) (例えば, [0,1,2,4,5,6,7] は [4,5,6,7,0,1,2] になるかもしれません。) 検索対象の値が与えられます。配列の中に見つかった場合はそのインデックスを返し、そうでない場合は -1 を返します。 配列の中に重複したものが存在しないと仮定しても構いません。 なお、アルゴリズムの実行時の複雑さは, O(log n) のオーダーでなければなりません。 Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2: Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

ゼロから始めるLeetCode Day85 「6. ZigZag Conversion」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day84「142. Linked List Cycle Ⅱ」 次回 ゼロから始めるLeetCode Day86 「33. Search in Rotated Sorted Array」 Twitter やってます。 問題 6. ZigZag Conversion 難易度はMedium。 前回に引き続き、 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、まず、文字列、例えば PAYPALISHIRING という文字列が与えられます。それらの文字列は以下のように所定の行数にジグザグパターンで書かれています。(読みやすくするために、このパターンを固定フォントで表示するとよいでしょう) P A H N A P L S I I G Y I R これらを一行ずつ読んでいくと "PAHNAPLSIIGYIR" となります。 これらの文字列を受け取り、行数を指定して変換するコードを書きます。 string convert(string s, int numRows). Example 1: Input: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR” Exam

ゼロから始めるLeetCode Day84「142. Linked List Cycle Ⅱ」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day83 「102. Binary Tree Level Order Traversal」 次回 ゼロから始めるLeetCode Day85 「6. ZigZag Conversion」 Twitter やってます。 問題 142. Linked List Cycle Ⅱ 難易度はMedium。 前回もそうでしたが、問題集からの抜粋です。 問題としては、以前解いた Linked List Cycle と似たような形式です。 連結リストが与えられます。その連結リストのサイクルが始まるノードを返します。仮にサイクルがない場合はnullを返します。 与えられた連結リスト内のサイクルを表現するには、連結リスト内の末尾が接続する位置(インデックス0)を表す整数posを使用します。posが-1の場合、リンク先リストにはサイクルはありません。 注意:リンク先のリストを変更しないでください。 Example 1: Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second

ゼロから始めるLeetCode Day82「392. Is Subsequence」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day81 「347. Top K Frequent Elements」 次回 ゼロから始めるLeetCode Day83 「102. Binary Tree Level Order Traversal」 Twitter やってます。 問題 392. Is Subsequence 難易度はEasy。 前回と同様問題集からの抜粋です。 問題としては、文字列sと文字列tが与えられたとき,sがtの部分連続であるかどうかを調べよ、というものです。 なお、ここでの文字列の部分連続とは、元の文字列から、残りの文字の相対的な位置を崩さずに、文字の一部を削除することによって形成される新しい文字列のことです(何もなくてもよい)。(例えば、"ace "は "abcde "の部分文字列ですが、"aec "はそうではありません)。 Example 1: Input: s = “abc”, t = “ahbgdc” Output: true Example 2: Input: s = “axc”, t = “ahbgdc” Output: false 解法 class Solution : def isSubsequence ( self ,

ゼロから始めるLeetCode Day83 「102. Binary Tree Level Order Traversal」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day82「392. Is Subsequence」 次回 まだ Twitter やってます。 問題 102. Binary Tree Level Order Traversal 難易度はMedium。 前回と同じく問題集からの抜粋です。 問題としては、バイナリツリーが与えられた場合、そのノードの値の階層順の横の同値をまとめたリストを返すアルゴリズムを設計してください。(すなわち、左から右へ、レベルごとに)というものです。 For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] 例はこんな感じ。 言いたいことは理解してもらえたと思います。 解法 DFSで解きました。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val #

ゼロから始めるLeetCode Day81 「347. Top K Frequent Elements」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day80「703. Kth Largest Element in a Stream」 次回 ゼロから始めるLeetCode Day82「392. Is Subsequence」 Twitter やってます。 問題 347. Top K Frequent Elements 難易度はMedium。 前回の問題同様Heapを使った問題です。 問題としては、数字が格納された空ではない配列が与えられます。その配列の中から K 番目まで頻出の要素を返すようなアルゴリズムを設計してください、というものです。 Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] 解法 Counter を使ってリストの要素を調べ、keyを取得、そしてheapの nlargest を使って書きました。 import heapq import collections class Solution : def topKFrequent ( self , nums : List [ int ] , k : int ) - > List

ゼロから始めるLeetCode Day80「703. Kth Largest Element in a Stream」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day79「1282. Group the People Given the Group Size They Belong To」 次回 ゼロから始めるLeetCode Day81 「347. Top K Frequent Elements」 Twitter やってます。 #問題 703. Kth Largest Element in a Stream 難易度はEasy。 問題としては、ストリーム内の k 番目に大きい要素を見つけるクラスを設計してください.これは、ソートされた順番の中で k 番目に大きい要素であって、 k 番目の異なる要素ではないことに注意してください。 KthLargest は、整数 k とストリームの初期要素を含む整数配列 nums を受け入れるコンストラクタを持ちます KthLargest.add メソッドを呼び出すたびに、ストリーム内の k 番目に大きい要素を表す要素を返します。 Example: int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // retu