投稿

ゼロから始めるLeetCode Day50「739. Daily Temperatures」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day49 「1323. Maximum 69 Number」 次回 ゼロから始めるLeetCode Day51 「647. Palindromic Substrings」 Twitter やってます。 問題 739. Daily Temperatures 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 問題としては、それぞれの日の気温を格納したリストである T が与えられます。 それらの要素が入力の各日より暖かい気温になるまで何日かかるかを示すリストを返すアルゴリズムを設計してください。 例えば、 T = [73、74、75、71、69、72、76、73] である場合、返すリストは [1、1、4、2、1、1、0、0] となります。 なお、気温の長さは [1,30000] 、各気温は [30,100] の間で与えられるものとします。 問題を見た時、最初はえ??なんで出力がこうなるの?と思いましたが、よくよく見てみたら自分の理解力が低いだけでした。 次の日との差とかではなく、単純に何日後にその日の気温を超えるかを導けば良いだけなんですね。 解法 最初に0が要素の長さ分入ったリストを用意してあげて、素直にリストを舐めていくのが分かりやすいかと思

ゼロから始めるLeetCode Day49 「1323. Maximum 69 Number」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day48 「26. Remove Duplicates from Sorted Array」 次回 ゼロから始めるLeetCode Day50「739. Daily Temperatures」 Twitter やってます。 問題 1323. Maximum 69 Number 難易度はEasy。 Goodの数の方が多く、面白そうな問題だと思ったので紹介します。 6と9のみで構成された正の整数である num が与えられます。 一桁だけ数字を6から9,もしくは9から6に変えても良いので、 num を変えることのできる最大値にして返すようなアルゴリズムを設計してください、という問題です。 Input: num = 9669 Output: 9969 Explanation: Changing the first digit results in 6669. Changing the second digit results in 9969. Changing the third digit results in 9699. Changing the fourth digit results in 9666. The maximum number is 9969. Inpu

ゼロから始めるLeetCode Day48 「26. Remove Duplicates from Sorted Array」

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

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

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

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

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