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

ゼロから始めるLeetCode Day60「1481. Least Number of Unique Integers after K Removals」

概要

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

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day59 「1221. Split a String in Balanced Strings」
次回
ゼロから始めるLeetCode Day61「7. Reverse Integer

Twitterやってます。

問題

1481. Least Number of Unique Integers after K Removals

難易度はMedium。
最近追加されたかなり新しめの問題ですね。

問題としては、配列のarrと整数のkが与えられます。k個分の要素を配列から削除した後、ユニークな整数の数の最小値を求めるアルゴリズムを設計してください、という問題です。

少し分かりづらいので例を見てみましょう。

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

この例だと1個の要素は配列内に4しかありません。なので4を削除します。
残った要素は5のみになるためそのまま5を返します。

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

42を削除することは決まりますが、残りの1つは13のいずれかを削除します。13が残りますが、それらの内ユニークな数の長さ自体は2となるのでそれを返します。

解法

今回返すのは整数であり、配列についてはどう扱っても解答に影響がないので早いうちにソートしておくと分かりやすいと思いました。
例のarr = [4,3,1,1,3,3,2]であればarr = [1,1,2,3,3,4]といった風にソートを行うと何を削除すれば良いかが一目瞭然になりますね。

さて、手っ取り早く書いてしまうと、今回の問題は、与えられたkと要素の個数を比較して仮にkが要素の個数以上であればkからk+要素の個数を引き、そして引いた回数をカウントします。
そして、最終的に元のソートした配列の長さから引いた回数を引いてあげれば良いです。

ただ、これだけ書かれても正直分からないと思うので実際のコードを見てみましょう。

import collections

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        sorted_counts,removed_counts = sorted(Counter(arr).items(),key=lambda x: x[1]),0
        for keys,values in sorted_counts:
            if k >= values:
                k -= values
                removed_counts += 1
        return len(sorted_counts) - removed_counts
                
# Runtime: 496 ms, faster than 92.08% of Python3 online submissions for Least Number of Unique Integers after K Removals.
# Memory Usage: 32.9 MB, less than 33.33% of Python3 online submissions for Least Number of Unique Integers after K Removals.

PythonではcollectionsのCounterという便利なライブラリがあるのでひとまず各個数をカウントしてあげるとよいですね。

なお、例1の場合は以下のようになります。

Counter({5: 2, 4: 1})

そして、これをkeyの値でソートしてあげると以下のようになる。

[(4, 1), (5, 2)]

ちなみに、Pythonをあまり書かない方はぱっと見ソートの部分を

sorted_counts = sorted(Counter(arr))
# [4,5]

と書きたくなるかもしれないですが、この場合、出力が[4,5]となるため個数がなくなってしまうためNGです。

なお、Pythonのlambda式が出てきていますが、

名前 = lambda 引数, 引数, ...:

といった形で書くことができます。
しかし、PEP8でPythonにおいてはlambda式は無名関数として書くことを推奨しているので、今回はそれに倣っています。

なお、今回の使い方はsorted()の引数として使っていますが、これはsorted()においてlambda式を使うと任意の関数を各要素に適用してその結果を元にソートできる、という性質を生かすためです。

もちろんdefで関数を定義し、それをkeyに指定しても良いのですが、今回のように一度しか使わないような状況であれば、今回のような書き方の方が簡潔に書けます。

今回は問題が新しく、あまり回答者がいないせいか速さ的にも悪くないものができたのではないでしょうか。

今回はここまで。お疲れ様でした。

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

Braveブラウザを使い始めて結構経った 設定 1 .同期ページを開く 2.QRコードの表示 3.iPhoneで読み取る Braveブラウザを使い始めて結構経った Google Domainsで独自ドメインを持っているBloggerをBrave Creatorsに登録した話。 この記事を書いた頃から僕はBraveしか使わなくなっちゃいましたね〜。 広告がないとネットサーフィンが捗りますし、Braveの直接クリエイターに貢献できるような仕組みが特に気に入っています。Blogger,ひいてはGoogle的にどうなんだって話もありそうですけど、ただのユーザなのでそんなのは気にせず便利なものは使います。 それで本題です。 タイトルのように今回同期機能を設定しました。 余計なことをしていたせいで少しハマったので設定ついでに誰かが困ったときに役に立つように設定方法を残しておこうかと思います。 ちなみにこちらの記事はPCの同期にiPhoneを追加するという設定方法についての解説です。iPhone→PCの同期方法などはまた別の話のようです。 設定 1 .同期ページを開く ブラウザのタブの右上にある上矢印のマークをクリックすると以下のような項目が表示されます。 こちらの同期という欄をクリックします。 すると以下のページが表示されます。 自動的に設定ページの中の同期欄が表示されるわけですね。 2.QRコードの表示 同期欄に同期済みのデバイスを管理という欄があるのでそちらをクリックします。 すると以下のようなページが表示されるのでそちらの中の新たなデバイスを追加、スマホ/タブレットという順にクリックしていくとQRコードが表示されます。 これでこのステップは完了です。 3.iPhoneで読み取る このQRコードをiPhoneで読み取っていく訳ですが、このQRコードはプリインストールされているQRコードで読み取っても正しく処理してくれません。 書いてある通り、iPhoneのBraveブラウザで読み取って上げる必要があります。 なのでひとまずiPhoneでBraveブラウザを開き、画面右下の**•••**という所をタップしてください。 すると上から二番目に歯車アイコンの設定が表示されますのでそちらをタップします。 初期表示で画面中部に表示さ

JavaのindexOf関数はナイーブ法で実装されているらしい

indexOf関数とは 実際のソースを見よう ナイーブ法ってなんぞや indexOf関数とは ドキュメント はここ。 indexOf の細かい使い方は説明はしないが、簡単にいうと二つの文字列を比較して重複する箇所がある場合にその開始部分のインデックスを返すというもの。 実際のソースを見よう どのように実装されているのかが気になったので jdkの中に存在するsrc.zipを解凍して確認してみることに。 public int indexOf ( String str ) { return indexOf ( str , 0 ) ; } public int indexOf ( String str , int fromIndex ) { return indexOf ( value , 0 , value . length , str . value , 0 , str . value . length , fromIndex ) ; } static int indexOf ( char [ ] source , int sourceOffset , int sourceCount , char [ ] target , int targetOffset , int targetCount , int fromIndex ) { if ( fromIndex >= sourceCount ) { return ( targetCount == 0 ? sourceCount : - 1 ) ; } if ( fromIndex < 0 ) { fromIndex = 0 ; } if ( targetCount == 0 ) { return fromIndex ; } char

djoserを使ったDjango REST Frameworkでのカスタムユーザーモデル認証機能の実装

djoserとは 使い方 djoserとは djoser とはDjango REST Framework上での基本的なユーザー認証や登録などの認証周りをサポートしてくれるライブラリです。 カスタムモデルに対しても使え、Djangoのコードを再利用するような形をとるのではなく、Single Page Application(以下SPA)によりフィットするようなアーキテクチャを目指して作られています。 今回はdjoserの最もシンプルな認証機能の実装について書きます。 なお、この認証はセキュリティの面などから実際に使用するべきではなく、以下のJWT認証のようなより強固なセキュリティの設定があります。 あくまでお手軽な認証として紹介します。 ソースコードは こちら なお、以下の全てが導入後にエンドポイントとして使えます。 /users/ /users/me/ /users/confirm/ /users/resend_activation/ /users/set_password/ /users/reset_password/ /users/reset_password_confirm/ /users/set_username/ /users/reset_username/ /users/reset_username_confirm/ /token/login/ (Token Based Authentication) /token/logout/ (Token Based Authentication) /jwt/create/ (JSON Web Token Authentication) /jwt/refresh/ (JSON Web Token Authentication) /jwt/verify/ (JSON Web Token Authentication) Getting started djoser関連の記事を他にも書いています。 djoserを使ったDjango REST Frameworkでの認証機能の実装 djoserを使ったDjango REST FrameworkでのJWT認証機能の実装 なお、今回はJWT認証を用いたユーザー認証を実装することとします。 使い方 途中