Kuehar's Blog

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day76「3. Longest Substring Without Repeating Characters」 次回 ゼロから始めるLeetCode Day78 「206. Reverse Linked List」 Twitter やってます。 #問題 1502. Can Make Arithmetic Progression From Sequence 難易度はEasy。 最近追加された新しめの問題です。 Easyっぽくない問題なので是非解いてみてください。 問題としては、数の配列 arr が与えられた時、連続する2つの要素間の差が同じであれば，数列は算術進行と呼ばれます。 配列を再編成して算術進行を形成できる場合は true を返し,そうでない場合は false を返してください。 Example 1: Input: arr = [3,5,1] Output: true Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements. Example 2: Input: arr =

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day75 「15. 3Sum」 次回 ゼロから始めるLeetCode Day77「1502. Can Make Arithmetic Progression From Sequence」 Twitter やってます。 問題 3. Longest Substring Without Repeating Characters 難易度はMedium。 問題としては、文字列が与えられたとき、文字を繰り返さずに最長の部分文字列の長さを求めなさいというものです。 Example 1: Input: “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3. Example 2: Input: “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1. Example 3: Input: “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Note that the answer must be a substring, “pw

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day74 「12. Integer to Roman」 次回 ゼロから始めるLeetCode Day76「3. Longest Substring Without Repeating Characters」 Twitter やってます。 問題 15. 3Sum 難易度はMedium。 問題としては、n個の整数の配列 nums があるとすると、 nums に a + b + c = 0 となる要素 a, b, c があるかどうかを確認するアルゴリズムを設計し、0の和を与える配列の中のすべてのユニークな三重項を求めよ。 Example: Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] 解法 3つ選び、0になる組み合わせを選べ、というものです。 組み合わせの鉄則とも言えるかもしれませんが、先に何を固定するかを決めたほうが良いと思います。 今回は以下のように書きました。 class Solution : def threeSum ( self , nums : List [ int ] ) - > List [ List [ int ] ]

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day72 「1498. Number of Subsequences That Satisfy the Given Sum Condition」 次回 ゼロから始めるLeetCode Day74 「12. Integer to Roman」 Twitter やってます。 問題 1491. Average Salary Excluding the Minimum and Maximum Salary 難易度はEasy。 今日はかなり軽めの問題です。 問題としては、 salary[i] が従業員iの給与である一意の整数 salary の配列が与えられます。 最小給料と最大給料を除いた従業員の平均給料を返します。 Example 1: Input: salary = [4000,3000,1000,2000] Output: 2500.00000 Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively. Average salary excluding minimum and maximum salary is (2000+3000)/2= 2500 Example 2: Input: salary

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day73 「1491. Average Salary Excluding the Minimum and Maximum Salary」 次回 ゼロから始めるLeetCode Day75 「15. 3Sum」 Twitter やってます。 問題 12. Integer to Roman 難易度はMedium。 なんかBadの方が多いので嫌な予感がしてました・・・ ローマ数字は7つの異なる記号で表されます。I、V、X、L、C、D、Mの7つの異なる記号で表されます。 この問題では、以下のように変換されています。 Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例えば、2はローマ数字でIIと書かれていますが、これは単に2つの1を足しただけです。12はXIIと書かれていますが、これは単にX + IIです。二十七という数字は、XXVIIと書かれていますが、これはXX + V + IIです。 ローマ数字は通常、左から右に大きい方から小さい方へと書かれています。しかし、4という数字はIIIIではありませ

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day71 「1496. Path Crossing」 次回 ゼロから始めるLeetCode Day73 「1491. Average Salary Excluding the Minimum and Maximum Salary」 Twitter やってます。 問題 1498. Number of Subsequences That Satisfy the Given Sum Condition 難易度はMedium。 問題としては、整数の配列 nums と整数 target が与えられます。 numsの最小値と最大値の和が目標値以下になるような、空ではない部分列の数を返します。 答えが大きすぎるかもしれないので、10^9 + 7の剰余演算を返します。 Example 1: Input: nums = [3,5,6,7], target = 9 Output: 4 Explanation: There are 4 subsequences that satisfy the condition. [3] -> Min value + max value <= target (3 + 3 <= 9) [3,5] -> (3 + 5 <= 9) [3,5,6] -> (

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day72 「1498. Number of Subsequences That Satisfy the Given Sum Condition」 次回 まだ Twitter やってます。 問題 1491. Average Salary Excluding the Minimum and Maximum Salary 難易度はEasy。 今日はかなり軽めの問題です。 問題としては、 salary[i] が従業員iの給与である一意の整数 salary の配列が与えられます。 最小給料と最大給料を除いた従業員の平均給料を返します。 Example 1: Input: salary = [4000,3000,1000,2000] Output: 2500.00000 Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively. Average salary excluding minimum and maximum salary is (2000+3000)/2= 2500 Example 2: Input: salary = [1000,2000,3000] Output: 2000.00000 Ex

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day70 「295. Find Median from Data Stream」 次回 ゼロから始めるLeetCode Day72 「1498. Number of Subsequences That Satisfy the Given Sum Condition」 Twitter やってます。 問題 1496. Path Crossing 難易度はEasy。 一番新しく追加されたEasyの問題です。 問題としては、path[i] = ‘N’, ‘S’, ‘E’, ‘W’ のような文字列のパスが与えられたとき，それぞれ1単位の移動を表す．2 次元平面上の原点 (0, 0) を起点とし、path で指定されたパス上を歩きます。 パスが任意の点で交差している場合、つまり以前に訪れたことのある場所にいる場合はTrueを返します。それ以外の場合は False を返します。 画像の関係で例を貼れないので各自確認をよろしくお願いいたします。 解法 x,yで座標を管理して最初の座標をdictで管理する、という方法を取りました。 うーん。 あまりスマートではないと思うのですが、pathをfor文で回して各文字列と一致するならば座標を変更するというものです。 しかしこれでも回答数が少ないせいかスピード自体は上位なんですよね・・

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day69 「279. Perfect Squares」 次回 ゼロから始めるLeetCode Day71 「1496. Path Crossing」 Twitter やってます。 問題 295. Find Median from Data Stream 難易度はHard。 Top 100 Liked Questionsからの抜粋です。 問題としては、クラスの実装になります。 中央値は、順序付き整数リストの中間値です。リストのサイズが偶数の場合、中間値はありません。したがって、中央値は2つの中間値の平均値となります。 例えば、 [2,3,4] 中央値は3 [2,3] 中央値は(2 + 3) / 2 = 2.5 以下の2つの操作をサポートするデータ構造体を設計します。 void addNum(int num) - データストリームからデータ構造体に整数値を追加します。 double findMedian() - これまでのすべての要素の中央値を返します。 Example: addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 解法 平均値ではなく中央値であることを念頭において、その部分を

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day68 「709. To Lower Case」 次回 ゼロから始めるLeetCode Day70 「295. Find Median from Data Stream」 Twitter やってます。 問題 279. Perfect Squares 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 正の整数nが与えられたとき、足してnになる完全な平方数の最小数（例えば、1, 4, 9, 16, …）を求めよ、という問題です。 Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. #解法 class Solution : def numSquares ( self , n : int ) - > int : dp = [ i for i in range ( n + 1 ) ] for i in range ( 2 , n + 1 ) : for j in

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day67 「1486. XOR Operation in an Array」 次回 ゼロから始めるLeetCode Day69 「279. Perfect Squares」 Twitter やってます。 問題 709. To Lower Case 問題としては文字列パラメータ str を持ち、同じ文字列を小文字で返す関数 ToLowerCase() を実装する、という問題です。 Example 1: Input: “Hello” Output: “hello” Example 2: Input: “here” Output: “here” Example 3: Input: “LOVELY” Output: “lovely” 解法 class Solution : def toLowerCase ( self , str : str ) - > str : return str . lower ( ) # Runtime: 24 ms, faster than 91.12% of Python3 online submissions for To Lower Case. # Memory Usage: 14 MB, less th

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 [ゼロから始めるLeetCode Day66「438. Find All Anagrams in a String」](( https://kueharx.blogspot.com/2020/06/leetcode-day66438-find-all-anagrams-in.html ) 次回 ゼロから始めるLeetCode Day68 「709. To Lower Case」 Twitter やってます。 問題 1486. XOR Operation in an Array 問題としては、整数 n と整数 start が与えられます。 nums[i] = start + 2*i (0-indexed) で n == nums.length の配列 nums を定義します。 nums の全要素のビット単位の XOR を返します。 Example 1: Input: n = 5, start = 0 Output: 8 Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8. Where “^” corresponds to bitwise XOR operator. Example 2: Input: n =

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day65「560. Subarray Sum Equals K」 次回 [ゼロから始めるLeetCode Day67 「1486. XOR Operation in an Array」](( https://kueharx.blogspot.com/2020/06/leetcode-day67-1486-xor-operation-in.html ) Twitter やってます。 問題 438. Find All Anagrams in a String 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 文字列 s と空でない文字列 p が与えられたとき、 s の中の p のアナグラムの開始インデックスをすべて求めなさい、という問題です。 Stringsは英小文字のみで構成され、 s と p の長さはともに20,100を超えてはいけません。 なお、出力の順番は関係ありません。 Example 1: Input: s: “cbaebabacd” p: “abc” Output: [0, 6] Explanation: The substring with start index = 0 is “cba”, which is an anagram of “a