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

投稿

ゼロから始めるLeetCode Day57 「35. Search Insert Position」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day56 「1480. Running Sum of 1d Array」 次回 ゼロから始めるLeetCode Day58 「20. Valid Parentheses」 Twitter やってます。 問題 35. Search Insert Position 難易度はEasy。 とあるアルゴリズムを学ぶのに良い問題だと思ったので記事を書きました。 問題としては、ソートされた配列とターゲットの値が与えられたます。 ターゲットが見つかった場合はそのインデックスを返します。見つからなかった場合は、それが順番に挿入された場合のインデックスを返すような、アルゴリズムを設計してください、というものです。 なお、配列内に重複がないと仮定しても構いません。 Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0 解法 class Solution : def searchI

ゼロから始めるLeetCode Day56 「1480. Running Sum of 1d Array」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day55「22. Generate Parentheses」 次回 ゼロから始めるLeetCode Day57 「35. Search Insert Position」 Twitter やってます。 問題 1480. Running Sum of 1d Array 難易度はEasy。 問題としては配列 nums が与えられます。全ての数を足した数をリストで返してください、という問題です。 Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4]. Example 2: Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]. Example 3: Input: nums = [3,1,2,10,1] Output: [3,4,6,16,17] Constraints: 1 &l

ゼロから始めるLeetCode Day55「22. Generate Parentheses」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day54 「1290. Convert Binary Number in a Linked List to Integer」 次回 ゼロから始めるLeetCode Day56 「1480. Running Sum of 1d Array」 Twitter やってます。 #問題 22. Generate Parentheses 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 問題としては、正の整数である n が与えられます。その数の括弧の組み合わせを全て書き出すようなアルゴリズムを設計しましょう、というものです。 最近知ったんですけど自然数って大学数学とかだと0も含むんですね・・・ For example, given n = 3, a solution set is: [ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ] 例を見た方が分かりやすいですね。 # 解法 組み合わせについての問題です、今回初見で解けなかったのでdiscussをチラチラ見て考え方を勉強して書きました。 カッコを右、`right`と左、`left`に分けて考えると分かりやすいです。 それぞれの引

ゼロから始めるLeetCode Day54 「1290. Convert Binary Number in a Linked List to Integer」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day53 「1365. How Many Numbers Are Smaller Than the Current Number」 次回 ゼロから始めるLeetCode Day55「22. Generate Parentheses」 Twitter やってます。 問題 1290. Convert Binary Number in a Linked List to Integer 難易度はEasy。 問題としては、単方向の連結リスト head が与えられます。 各ノードは 0 か 1 を値として持っており、それらを2進法の値として扱います。ここではそれらの二進法表記の値を10進法に直し、数字を返すアルゴリズムを設計してください、というものです。 Input: head = [1,0,1] Output: 5 Explanation: (101) in base 2 = (5) in base 10 Input: head = [0] Output: 0 Input: head = [1] Output: 1 Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] Output: 18880 Input: head =

ゼロから始めるLeetCode Day53 「1365. How Many Numbers Are Smaller Than the Current Number」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day52 「1351. Count Negative Numbers in a Sorted Matrix」 次回 ゼロから始めるLeetCode Day54 「1290. Convert Binary Number in a Linked List to Integer」 Twitter やってます。 問題 1365. How Many Numbers Are Smaller Than the Current Number 難易度はEasy。 良い問題だったので書きます。 問題としては、配列 nums が与えられます。 それらの配列の中の各要素が他の要素より大きい回数を導くようなアルゴリズムを設計してください、という問題です。 日本語的に難しいので例を見てみましょう。 Input: nums = [8,1,2,2,3] Output: [4,0,1,1,3] Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). For nums[1]=1 does not exist any smaller number than it. For nums[2]=2 the

ゼロから始めるLeetCode Day52 「1351. Count Negative Numbers in a Sorted Matrix」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 [ゼロから始めるLeetCode Day51 「647. Palindromic Substrings」] 次回 ゼロから始めるLeetCode Day53 「1365. How Many Numbers Are Smaller Than the Current Number」 Twitter やってます。 問題 1351. Count Negative Numbers in a Sorted Matrix 難易度はEasy。 m*n の行列 grid が与えられます。その行と列両方とも増加が起こらないような形式でソートされています。 (つまり、要素の値が現状維持、ないしは減少する順である、ということです。) その grid のなかに存在する負の数を返すようなアルゴリズムを設計してください、という問題です。 Example 1: Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix. Example 2: Input: grid = [[3,2],[1,0]] Output: 0 Examp

ゼロから始めるLeetCode Day51 「647. Palindromic Substrings」

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day50「739. Daily Temperatures」 次回 ゼロから始めるLeetCode Day52 「1351. Count Negative Numbers in a Sorted Matrix」 Twitter やってます。 問題 647. Palindromic Substrings 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 問題としては、文字列 s が与えられます。 この文字列内の回文の数を数え、その数を返すアルゴリズムを実装してください、というものです。 なお、開始インデックスまたは終了インデックスが異なる部分文字列は、同じ文字で構成されていても、異なる部分文字列としてカウントされます。 Input: “abc” Output: 3 Explanation: Three palindromic strings: “a”, “b”, “c”. Input: “aaa” Output: 6 Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”. 解法 よくある回文のチェック方法としては最初から文字列を舐めたものと反対