「アウトプットと言う名の備忘録@Texas」

日本じゃない何処かの脳筋パイソニスタによる何かしらの走り書き

【海外エンジニア転職 Coding Interview鍛錬】LeetCode 217. Contains Duplicate

こんにちは脳筋ニシキです!

今回もこちらで紹介したLeetCode75選(Blind75)から1問easy選んで解いていきたいと思います!
atsashimipy.hatenablog.com

今回解いていくのはこちらの問題

f:id:At_sashimi_py:20220319161847p:plain
217. Contains Duplicate
f:id:At_sashimi_py:20220319161726p:plain:w300
被ってる?

やること

整数の配列 nums が与えられたとき、いずれかの値が配列中に少なくとも2個ある時Trueを返し、 すべての要素が異なる場合はFalseを返す。

条件

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Input: nums = [1,2,3,1]
Output: True

Input: nums = [1,2,3,4]
Output: False

カテゴリ

Arrays

考え方

配列を一巡する過程で、要素を記録かつその記録された要素を参照。Memoizationの考え方
atsashimipy.hatenablog.com

もし、その要素が記録にあれば、True。

早速解いていく!

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:

出現した要素を記録するmemoを設定

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        memo = set()

ここでset()を使ったのは、参照にかかる負担を減らすため。

for loop で要素を一つ一つチェックしていく

今まで見たことない要素であれば、memoに記録し、
memo内に存在するのであれば その時点でTrue を返す。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        memo = set()
        
        for i in nums:
            if i not in memo:
                memo.add(i)
            else:
                return True

最後までダブり要素がなかった場合 False を返す。

解答例

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        memo = set()
        
        for i in nums:
            if i not in memo:
                memo.add(i)
            else:
                return True
            
        return False

Complexity Analysis

Time complexity : O(n)

N回づつ参照し、記録。

Space complexity : O(n)

setのサイズは線形に増加

f:id:At_sashimi_py:20220319170955p:plain

おまけ

おそらく問題の意図から反してしまうが、

set()を使ってこうも解ける。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        
        if len(nums) != len(set(nums)):
            return True
        else:
            return False

set()はユニークな要素しか含まないので、ダブりがあった場合もとのnumsより短くなる。

f:id:At_sashimi_py:20220320020803p:plain:w300
みんなユニークでみんな良い


誰かの参考になって来れば幸いです!
それではまた次のLeetCodeで!
ありがとうございましたー!

【海外エンジニア転職 Coding Interview鍛錬】LeetCode121. Best Time to Buy and Sell Stock

こんにちは脳筋ニシキです!

今回はこちらで紹介したLeetCode75選(Blind75)から1問easy選んで解いていきたいと思います!
atsashimipy.hatenablog.com

f:id:At_sashimi_py:20220319091722p:plain:w300
最高益を求めよ!

今日解いていくのはこちらの問題

LeetCode121. Best Time to Buy and Sell Stock

leetcode.com

f:id:At_sashimi_py:20220319091613p:plain
121. Best Time to Buy and Sell Stock

やること

"prices"として渡されたとある銘柄の株の値動き表した配列から、一度づつの売買で最高益を返す。
prices[i] は、この銘柄のi日目の価格

条件

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4

Input: prices = [7,1,5,3,6,4]
Output: 5

この条件下で最高益
価格がの時に買い、の時に売って得られる

カテゴリ

Arrays

考え方

とりあえず現実世界と同じで一番安い時に買って一番高い時に売る
ここで大事なのは買った時の値段売った時の値段、そしてその差のから生まれる利益

利益 = 売値 - 買値

0日目からN日目までの利益の動きをチェックしつつ、できるだけO(N)で解いていきたい。

上の例を見て考えてみる。

その日時点での一番の買い時(最安値)最高益に注意しながら
0日目から見ていく。

prices = [7,1,5,3,6,4]

0日目:価格7 初日で比べる対象がないので、最安値=7 最高益=0
1日目:価格1 前日の7より安いので、この時点での最安値=1に更新 最高益=0 のまま
2日目:価格5 利益は5−1で4で現時点での最高益 最安値=1のままで 最高益=4に更新
3日目:価格3 利益は3−1で2出ているが最高益でないので 最安値=1 最高益=4のまま
4日目:価格6 利益は6−1で5最高益を更新 最安値=1のままで、最高益=5に更新
5日目:価格4 利益は4−1で3 最安値=1 最高益=5のまま

こうして最高益 = 5が確定される。

ではこの考え方をもとに

早速codeしていく!

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

まず特殊ケースを対処。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if len(prices) == 1:
            return 0

思いつくのは与えられた配列の長さが1の時。
つまり0日目で終わってる時、これは価格がどうあろうと最高益は0。というか取引できない。
問題文にも利益が出ないときは0を返せと書いてある。

If you cannot achieve any profit, return 0

次に買う日&売る日の初期値(2ポインター)と現時点での利益を設定する。
買う日と売る日は別々でないといけないので、
買う日を0日目
売る日を1日目
最高益を0

とする。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if len(prices) == 1:
            return 0
        
        buy = 0
        sell = 1
        profit = 0

そして、この2つのポインターを上で考えたように

while loop で1日ずつ価格の変動と現在の利益(売値–買値)をチェックしていく。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if len(prices) == 1:
            return 0
        
        buy = 0
        sell = 1
        profit = 0
        
        while sell < len(prices):
            curr_profit = (prices[sell] - prices[buy])

もし現在の時点で利益がマイナスだった場合。

それはつまり最安値が更新されたということ。
なのでこの価格で買うのが現状ベスト。
ということで”buy”ポインターをこの日に移動。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if len(prices) == 1:
            return 0
        
        buy = 0
        sell = 1
        profit = 0
        
        while sell < len(prices):
            curr_profit = (prices[sell] - prices[buy])
            if curr_profit <= 0:
                buy = sell

そして次は

もし現在の時点で利益がプラスだった場合。

それはつまり最高益が更新された可能性があるということ。
なので今までの最高益の値と今回の利益を比べて、大きい方を新たな最高益と再設定。

lass Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if len(prices) == 1:
            return 0
        
        buy = 0
        sell = 1
        profit = 0
        
        while sell < len(prices):
            curr_profit = (prices[sell] - prices[buy])
            if curr_profit <= 0:
                buy = sell
            else:
                profit = max(profit, curr_profit)


そして1日の価格をチェックし終えたら次の日を調べるため”sell”ポインターを一つ次に進めます。

lass Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if len(prices) == 1:
            return 0
        
        buy = 0
        sell = 1
        profit = 0
        
        while sell < len(prices):
            curr_profit = (prices[sell] - prices[buy])
            if curr_profit <= 0:
                buy = sell
            else:
                profit = max(profit, curr_profit)
            sell += 1

とこんな感じで書いていくと、あとは勝手にpythonさんがやってくれるので、
while loop が終わったらあとはprofitを返すだけ。


そうするとこんな感じになります。

解答例

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if len(prices) == 1:
            return 0
        
        buy = 0
        sell = 1
        profit = 0
        
        while sell < len(prices):
            curr_profit = (prices[sell] - prices[buy])
            if curr_profit <= 0:
                buy = sell
            else:
                profit = max(profit, curr_profit)
            sell += 1
            
        return profit

Complexity Analysis

Time complexity: O(n)

与えられた長さnの配列を一巡するだけ

Space complexity: O(1)

3つの変数(buy, sell, profit)


f:id:At_sashimi_py:20220319140850p:plain

f:id:At_sashimi_py:20220319100818p:plain:w300
億り人ー!


自分の考えを文字に起こすと理解が深まっていいな!

ただ、伝わりづらい部分も多々あると思うので、ご意見、感想、アドバイスお待ちしています!

それではまた次のLeetCodeの問題でお会いしましょう!

【海外エンジニア転職 Coding Interview鍛錬】LeetCode はこれをやっとけ75選!出典:blind

Coding Interview 鍛錬 ~LeetCode 75本ノック~


絶賛転職活動中脳筋にしきはCoding Interview対策にLeetCodeを活用しています。

おそらく海外エンジニア転職を目指している多くの方々もそうなのではないでしょうか?

LeetCodeのいいところは多くの分野をカバーした余りある問題数の量!
そして、似た問題が出題された会社も教えてくれるので面接対策にはもってこいのサイトでおすすめです。

ただ逆に、問題数が多すぎてどこまで対策すればいいのかわからないというのが当初の感想でした。

そんな折、LeetCode界隈でよく耳にするようになったのがBlind 75 というワード。

通称Blind 75 とは
Blind というサイトに投稿された75問の厳選されたLeetCode の問題集(プレミア専用問題も含む)。

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time - Blind


つまり、優しい先輩が、後輩の私たちの時間をセーブするため厳選してくれたLeetCode75選通称Blind 75

あらゆる問題のタイプ、アルゴリズムを網羅したこの75問の問題を練習すればコアとなる解き方のテクニックや問題のコンセプトをマスターすることができるらしい!

そしてこれが結構いい評判!


こいつは活用しない選択肢はねぇ!!


ということで以下に、ソースを基にカテゴリー別&難易度別にリンク付きでまとめました!


海外転職仲間の皆さんの参考にもなれば幸いです。

どこから始めたら良いかわからないという私のような方はこのリストをガンガンに解いていきましょう!(...とりあえず、Easy問題から)


f:id:At_sashimi_py:20220222145024p:plain:w300

【海外エンジニア転職活動】Coding Interview鍛錬: 02.Memoization - フィボナッチ数(Fibonacci numbers)

今回はフィボナッチの問題を違うアプローチで解いていく!

前回の問題点
Time Complexity = O(2N)

再帰の各レベルでの必要な演算量が、nに近づくにつれて指数関数的に増加してしまう!

atsashimipy.hatenablog.com

というのも一度計算したフィボナッチ数も再帰のなかで何度も計算しているから。

なので今回はメモ化(memoization)を使っていこうと思います。
(注意:Memorization(暗記)ではなくMemoization)
ja.wikipedia.org

キャッシュ(Cache)という呼び方の方が馴染みがある方もいるかもしれません。
つまるところ、一度計算したフィボナッチ数を何処かに保存して、何度も計算する手間を省く手法。

では解いていきます!

1. cache と名付けた辞書に一度計算したフィボナッチ数を補完。この時, key=n
2. nがcacheの中に存在する場合は計算せずに、そちらを参照。

class Solution:
    def fib(self, n: int) -> int:
        cache = {}
        
        def recur_fib(n):
            if n == 0:
                cache[n] = 0
                return 0
            elif n == 1:
                cache[n] = 1
                return 1
            
            if n in cache:
                return cache[n]
            else:
                
                cache[n] = recur_fib(n-2) + recur_fib(n-1)
                return cache[n]
            
        return recur_fib(n)

こうするとnまでの各フィボナッチ数の計算は一度のみで、
Time complexityは O(N)

f:id:At_sashimi_py:20190610134533p:plain
速いぞ!

余談
ちなみにさっき知ったのですが...
pythonの場合、
Built-inデコレータの一つに、@cacheというものがあり、前回使った関数の上にこのようにくっつけると

class Solution:
    @cache
    def fib(self, n: int) -> int:
        
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        return self.fib(n - 1) + self.fib(n - 2)

自動的にメモ化して余分な計算を省いてくれるそうです!なんと便利!
詳しくはこちら(バージョン 3.9 で追加)
docs.python.org

まとめ

最後にデコレータの便利さにインパクト持ってかれたが、このメモ化の解き方はいろんなところに応用できそう!


ご意見感想、こんな風にも解けるよ!というアドバイスお待ちしてます!
ありがとうございましたー!
f:id:At_sashimi_py:20210809115236p:plain:w200

【海外エンジニア転職活動】Coding Interview鍛錬: 01.Recursion - フィボナッチ数(Fibonacci numbers)

問:フィボナッチ数(一般にF(n)と表記)

ja.wikipedia.org
のn番目の数を求めよ。

このような数式で表される。

f(0) = 0, f(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

例えばn=8の時、
答えは13

0, 1, 1, 2, 3, 5, 8, 13, 21

早速解いていく

f:id:At_sashimi_py:20220222143502p:plain
早速解いていくよ

再帰の問題で定番のフィボナッチ。
今回も前回に引き続きRecursion(再帰で攻めていく!
atsashimipy.hatenablog.com

1. 最初の0, 1 はそのまま。
2. それ以降はfib自身を繰り返す関数をコードしていく。

class Solution:
    def fib(self, n: int) -> int:
        
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        return self.fib(n - 1) + self.fib(n - 2)

秒!!

いやいや、これは流石に定番すぎー!

...と思いきや、

Time Complexity は O(2N)

秒で解けても、実際にこのコードでは

再帰の各レベルでの必要な演算量が、nに近づくにつれて指数関数的に増加してしまう!

f:id:At_sashimi_py:20220222143333p:plain
圧倒的に遅い...


企業にもよると思うけど、これでクリアってところもあれば
O(N)で解いてねっていうところもあるかもしれないので、

次回

Memoization

乞うご期待!

ありがとうございましたー!

【海外エンジニア転職活動】Coding Interview鍛錬: 00.Recursion - Reverse String

問:配列:s を反転させる関数を作成せよ。

  • O(1)
  • 配列をin-placeで変更すること

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

解いてく

ちなみにpythonなら

s.reverse()


でクリアできてしまうが練習のため
とりあえずRecursion(再帰で攻めていく。

1. 配列の右端:r と左端:l から順番に位置を交換していく。
2. l < r が満たされる限り続ける。

解答

class Solution:
    def reverseString(self, s: List[str]) -> None:
        
        def helper(l, r, ls):
            if l < r:
                ls[l], ls[r] = ls[r], ls[l] 
                l+=1
                r-=1
                helper(l, r, ls)
        l, r = 0, len(s)-1
        
        helper(l, r, s)


と、こんな感じでコーディング鍛錬始めました!
ご意見、アドバイス等あればよろしくお願いいたします!

【Git】Fetch と Pull 結局何が違うのか

Git ユーザーであれば、日々の呼吸をするように開発過程で行うのが pull と fetch。

響き的にどちらもリモートレポジトリから最新の情報をローカルに持ってくるイメージ。。

f:id:At_sashimi_py:20220118021836p:plain:w200
fetchは英語で取ってくるの意味。ワンちゃんのボール取ってこーい!の時もFetch!

詰まるところその違いはなんなのか?

結論

git fetch を使用すると、前回の git pull 以降にリモートリポジトリ/ブランチで行われたメタデータの変更を取得する。

git pullfetch の機能に加え、オリジナルに加えられたコード変更をローカルのコードに加えることができる。


以下のシナリオからその違いをちゃんと確認しよう。

シナリオ

git clone <url>

によって、ローカルにコピーしたチームの共同プロジェクトに取り組んでいるとき、

  • ローカルとリモートブランチの差分を確認したい。
  • チームメイトが加えたオリジナルへの変更を自分のローカルコードに反映させたい。

こんな時に fetchpullが便利です。
一つずつ見ていきましょう。

ローカルとリモートブランチの差分を確認したい。

この場合は、

git fetch
git diff <local branch> <remote>/<remote branch>

git fetch は、ローカルの git にオリジナルのメタデータを取得するように指示するコマンド。ただし、ファイルの転送はしない。
つまり、利用可能な変更があるかどうかをチェックするだけでローカルのコードに直接的な変化なし。
なのでまず、git fetchでリモートブランチのメタデータを取得することで、git diff のコマンドをリモートブランチに対して使えるようになる。


以前のポスト
atsashimipy.hatenablog.com
ここで言う「git fetchをお忘れなく」と言うのは新しく作られた他人のブランチのメタデータがない状態で

git checkout taros_branch

しても「そんなブランチ知りません!」とgitさんに怒られてしまうから。
なので先に git fetch をしてメタデータを取得しておく必要があると言うこと。


一方

チームメイトが加えたオリジナルへ変更を自分のローカルコードに反映させたい。

git pull origin master

git pull は、リモートリポジトリから最新のメタデータを取得し、さらにその変更をローカルに取り込む(コピーする)コマンド。
つまり、 git fetch した上にその新しい変更をローカルのコードに加える。

まとめ

今回は簡単にgit pull と fetchの違いを紹介しました。
初心者の方や記憶が曖昧だった方の参考になってもらえれば幸いです!

ありがとうございました!

f:id:At_sashimi_py:20191117112122p:plain:w300
gitはまだまだ奥が深い