Kuehar's Blog

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策として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なるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、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なるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、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なるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、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なるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、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なるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、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なるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、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 #