Kuehar's Blog

概要 問題 解法 概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day104「103. Binary Tree Zigzag Level Order Traversal」 次回 ゼロから始めるLeetCode Day106「209. Minimum Size Subarray Sum」 Twitter やってます。 問題 111. Minimum Depth of Binary Tree 難易度はEasy。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、二分木が与えられた場合、その最小深度を求めよ、というものです。 なお、最小深度とは、ルートノードから最も近い葉までの最短経路に沿ったノードの数である。 注意：葉とは，子を持たないノードのことである。 解法 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def

概要 問題 解法 概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day103「122. Best Time to Buy and Sell Stock II」 次回 ゼロから始めるLeetCode Day105「111. Minimum Depth of Binary Tree」 Twitter やってます。 問題 103. Binary Tree Zigzag Level Order Traversal 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、二分木が与えられた場合、そのノードの値のジグザグレベル順のトラバーサルを返すという問題です。 （左から右へ、次のレベルでは右から左へ、その間では交互に）。(つまり、左から右へ、そして次のレベルは右から左へ、そしてその間を交互に) For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] 解法 # Definition for a binary tree

目的 環境 CpawCTF Level1 Q1.[Misc] Test Problem Q6.[Crypto] Classical Cipher Q7.[Reversing] Can you execute ? Q8.[Misc] Can you open this file ? Q9.[Web] HTML Page Q10.[Forensics] River Q11.[Network]pcap Q12.[Crypto]HashHashHash! Q14.[PPC]並べ替えろ! まとめ 目的 ネットワークやセキュリティなどの勉強はしたいが実際に何から手をつけたら良いのか分からない・・・ 無料でコンテスト形式の何かに取り組みたい といった人におすすめなのがCTF！ 基本的にはチーム形式でセキュリティやネットワークの問題を解く、というコンテストで頻繁に開催されているため、楽しく学べます。 僕も最近始めたばかりで、ひとまず基本的なことを学ぶために一人で簡単なものから解いています。 環境 MacOS Catalina 10.15.4 Ubuntu 64-bit(VM) CpawCTF Level1 現在解いているのはこちらの CpawCTF で、初学者でも楽しくクイズ形式で学ぶことができます。 今回はLevel1を全て埋めたので内容について触れていきたいと思います。 なお、解答については触れません。 どういう風に解いたかに焦点を当てていきたいと思います。 Q1.[Misc] Test Problem この問題の答え（FLAG）は、 cpaw{this_is_Cpaw_CTF} です。 下の入力欄にFLAGを入力してSubmitボタンを押して、答えを送信しましょう！ 記念すべき第一問。どういった形式で解答すればよいかを教えてくれます。 このコンテストでは基本的に cpaw{flag} といった形式で、 cpaw の部分は固定で、それ以降の {} の中にそれぞれの問題を解いた時に得られる flag を入れることで正解かどうかを判定します。 これがCTFがCatch the flagと呼ばれる所以ですね。 とにもかくにも解答の方法は基本的にこういった形なので理解するにはうってつけ

概要 問題 解法 概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day102「322. Coin Change」 次回 ゼロから始めるLeetCode Day104「103. Binary Tree Zigzag Level Order Traversal」 Twitter やってます。 問題 122. Best Time to Buy and Sell Stock II 難易度はEasy。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、 ith の要素が i 日目に指定された株式の価格である配列の価格を与えられます。 最大の利益を見つけるためにアルゴリズムを設計します。あなたは好きなだけ多くのトランザクションを完了することができます。 なお、再び購入する前に株式を売却する必要があります。 Example 1: Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3

概要 問題 解法 概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day101「387. First Unique Character in a String 次回 ゼロから始めるLeetCode Day102「322. Coin Change」 Twitter やってます。 問題 322. Coin Change 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、異なる額面のコインと合計金額が与えられます。その金額を作るのに必要なコインの数が最も少ないコインを計算する関数を実装してください、という問題です。なお、コインのどの組み合わせでもその金額を作ることができない場合は、-1を返す。 Example 1: Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], amount = 3 Output: -1 解法 典型的なナップザック問題ですね。 ちなみにナップザック問題というのは このような もので、与えられた条件の中から最適な場合を求めるための例として挙げられる問題群のことです。 そして、それら

概要 問題 解法 概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day100「108. Convert Sorted Array to Binary Search Tree」 次回 ゼロから始めるLeetCode Day102「322. Coin Change」 Twitter やってます。 問題 387. First Unique Character in a String 難易度はEasy。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、文字列が与えられるので、その中から最初の反復されない文字（文字列の中に一度しか表示されない文字）を見つけ、そのインデックスを返す、というものです。なお、存在しない場合は -1 を返します。 Examples: s = “leetcode” return 0. s = “loveleetcode” return 2. 解法 軽くサクサクっと解けるような考え方としては Counter を使うと手っ取り早いですね。 collections.Cpunter を使うと文字列の中にどの文字が何回表示されるかを出してくれます。 例えば、今回のテストケースである leetcode の場合は以下のようになります。 count = collections

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day98「39. Combination Sum」 次回 ゼロから始めるLeetCode Day100「108. Convert Sorted Array to Binary Search Tree」 Twitter やってます。 問題 112. Path Sum 難易度はEasy。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、二分木と和が与えられたとき、その木がルートから葉へのパスを持ち、パスに沿ってすべての値を加算すると、与えられた和に等しくなるかどうかを判断してください、というものです。 Example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22. 解法 スタックを使って解きました。 # Definition for a binary tree node. # class TreeNode:

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day99 「112. Path Sum」 次回 ゼロから始めるLeetCode Day101「387. First Unique Character in a String Twitter やってます。 問題 108. Convert Sorted Array to Binary Search Tree 難易度はEasy。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、要素が昇順にソートされた配列が与えられた場合，それを高さバランスのとれた二分探索木に変換してください、というものです。 この問題では、二分探索木とは，各ノードの2つの部分木の深さが1以上異なることがない二分木と定義されます。 Example: Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 解法 # Definition for a binary tree node. # class

CTFを始めたよ！ CTFとは 現段階の進捗 これからの予定 CTFを始めたよ！ ということで。 LeetCodeを100回解いたので今度は新しくセキュリティ領域に手を出そうかと思います。全体的にセキュリティ、ネットワークは知ってて当然ですよね。って感じがしたのでゲーム形式で参加できそうなこちらで勉強していこうかなと。 CTFとは Capture the flagの略。 いわゆる竸プロのセキュリティ領域版みたいなもので、特定の問題をこなすとflagというものが与えられ、それを入力するとポイントが加算され、より多くのポイントを集めた人が勝ち！という至極簡単なルール。 現段階の進捗 とりあえずCpawCTFをやってみたけど楽しい。 与えられたファイルを解析してflagを取るために立てたVM上でUbuntuを動かそうとして少し詰まったのは秘密 とある方がシステム設計とかの勉強にはpicoCTFとかいいんじゃね？って記事で書いてたけど、あのレベルですら調べないと詰まったので本当に基礎の基礎から学び直します。 あ！もちろんハリネズミ本は買いましたよ！というかハリネズミ本を買った後コンテストの存在を知りました。 セキュリティ本を含め、近所のブックオフで技術書を衝動買いしてしまったのでじっくり消化できるようにしないと。 今の段階でCpawCTFを数問解いただけだけど、こんな世界もあるのかっていうLeetCodeを解き始めた時と同じような気持ちで取り組めているので非常に良い。 何事も楽しいのは大事。 これからの予定 割とアルゴリズムとデータ構造を勉強するためにLeetCodeをガリガリ解いてきたんですけど、途中まで解いていた60問の内、残りを解いてしっかり復習をしようかなと。毎日解いてはいたけど、いざ思い返すと厳しい問題もあると思うし、確実に解ける問題を増やしていくのが目的なので。 僕は数学的に飛び抜けた資質がなければ、そこを今から突出できるまで伸ばす気もないので、競技プログラミングみたいなとんでもない才能と努力家揃いの領域に手を出そうとは思いませんし、むしろ確実に解ける領域をコツコツ作ることの方が大事だと思うので、解いて満足みたいなことはしないようにしたいです。 てなわけでしばらくは今まで解いてきたLeetCodeの復習と新

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