2020-01-19

LeetCode / Isomorphic Strings

LeetCode

https://leetcode.com/problems/isomorphic-strings/

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:
Input: s = "egg", t = "add"
Output: true

Example 2:
Input: s = "foo", t = "bar"
Output: false

Example 3:
Input: s = "paper", t = "title"
Output: true

Note:
You may assume both s and t have the same length.

2つの同じ長さの文字列があって、文字iを文字jに置き換えると文字列sが文字列tに変わる、という対応関係が崩れていないことをisomorphicと言うそうです。

数学では同型写像を意味するそうです（聞いたこともない用語でしたが）。

解法がたくさんあって面白いですが、計算量オーダー的にはそこまで大きな差はありません。

解答・解説

解法1

sの各文字をkey, tの各文字をvalueに持つdictと、tの各文字をkey, sの各文字をvalueに持つdictの2つを用意し、対応関係をチェックします。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_d = {}; t_d = {}
        for i,j in zip(s,t):
            if i in s_d and s_d[i] != j:
                return False
            elif j in t_d and t_d[j] != i:
                return False
            else:
                s_d[i] = j
                t_d[j] = i
        return True

2つdictを用意するので、空間計算量は $O(2n)$ とあまり効率的ではありませんが、分かりやすい解法かと思います。

解法2

同じ2つのdictを使う手法としては以下もあります。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        d1, d2 = {}, {}
        for i, val in enumerate(s):
            d1[val] = d1.get(val, []) + [i]
        for i, val in enumerate(t):
            d2[val] = d2.get(val, []) + [i]
        return sorted(d1.values()) == sorted(d2.values())

ただ、最後のsortに時間がかかるので時間計算量の面で劣ります。

解法3

文字列に対するfindメソッドで、文字列中の各文字が初めて出てくるインデックスを返させ、2つの文字列について同じ値が返ってくるかチェックします。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        return [s.find(i) for i in s] == [t.find(j) for j in t]

ただ $O(n)$ のfindメソッドをn回繰り返すことになるので、時間計算量の面で劣ります。

解法4

文字列sと文字列t中の文字を集合としたときの要素数と、文字列sとt中の文字のペアを集合としたときの要素数が同じかどうかをチェックするという解法もあります。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        return len(set(zip(s, t))) == len(set(s)) == len(set(t))

これが時間計算量/空間計算量的にも、コードの短さ的にも最も優れているかと思います。

解法5

最後に、アスキーコードを利用する解法。

アスキーコードの要素数である256個の要素からなるリストを用意します。
文字列sの各文字xをアスキーコードiに変換し、リストのi番目に、xのsにおけるインデックス+1を値として格納します。
文字列sが"abc"なら、ord("a")が97なので、リストの97番目の要素に0+1=1を格納します。
インデックス+1とするのは、リストの各要素の初期値を0としているためです。
このインデックスが文字列sとtでずれていないかをチェックします。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        l1, l2 = [0 for _ in range(256)], [0 for _ in range(256)]
        for i in range(len(s)):
            if l1[ord(s[i])] != l2[ord(t[i])]:
                return False
            l1[ord(s[i])] = i+1
            l2[ord(t[i])] = i+1
        return True

2020-01-18

LeetCode / Count Primes

LeetCode

https://leetcode.com/problems/count-primes/

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

与えられた値より小さい素数の数を返す問題。

解答・解説

誤答(TLE)

TLEですが、重要な考え方その1が含まれます。それは、

nが何らかの数pで割り切れる場合、n=pqであり、qがpより小さい場合には既にqもしくはqの約数で確かめた際に素因数が検出されているはずである。したがって、素因数候補として確かめるべきは ${\sqrt {n}}$ までで十分

です。

以上の考え方を取り入れたのが下記コードで、偶数の判定を飛ばす（2以外素数でない）改善も加えています。

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, math.floor(math.sqrt(n))+1, 2):
        if n % i == 0:
            return False
    return True

class Solution:
    def countPrimes(self, n: int) -> int:
        return sum([is_prime(i) for i in range(n)])

が、これだとまだTLEになります。もう一段の高速化を考えないといけません。

解法1

さらに高速化するにあたり、エラトステネスの篩というアルゴリズムがあります。これは、

$x^{1/2}$ 以下の素数が既知のとき、 $x^{1/2}$ 以上 $x$ 以下の素数を決定するには、 $x$ 以下の整数で $x^{1/2}$ 以下の素数の倍数を全て取り除けば（= 篩えば）よい

というものです。

class Solution:
    def countPrimes(self, n):
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
        return sum(primes)

2020-01-13

LeetCode / Remove Linked List Elements

LeetCode

https://leetcode.com/problems/remove-linked-list-elements/

Remove all elements from a linked list of integers that have value val.

Example:

Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

これがlistだったりsetだったら問題にもならないのですが、linked listならではのコードを書く必要があります。

解答・解説

誤答

各ノードを走査するための変数current_nodeを定義し、current_nodeを動かしながらvalを取り除いていくと考えます。

と、ここまでは良いのですが以下のようにやってしまうと誤答です。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        
        current_node = head
        while current_node.next != None:
            if current_node.next.val == val:
                current_node.next = current_node.next.next
            else:
                current_node = current_node.next
                
        return head

これだと、1つ目の要素をチェックできないので
Inputが[1,2,6,3,4,5,6], val=6のときは良いですが
Inputが[1,2,6,3,4,5,6], val=1のときは正しい戻り値を返せません。

解法1

シンプルに1つ目の要素をチェックする処理を追加する、のが案1です。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        
        while head is not None and head.val == val:
            head = head.next
        
        current = head
        while current is not None:
            if current.next is not None and current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        
        return head

解法2

誤答のコードは1つ目の要素をチェックできないことが問題だったので、1つ目の要素の前にダミーのnodeを追加したlinked listを作ってやれば問題なくなる、と考えます。

そこで、dummy_headという変数を、ListNode(-1)とheadを結合させる形で作り、dummy_headの各nodeを走査します。

最後に返す値はdummy_head.nextである点に注意します（でないと、ダミーで追加したnodeも含めて返してしまう）。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        
        dummy_head = ListNode(-1)
        dummy_head.next = head
        
        current_node = dummy_head
        while current_node.next != None:
            if current_node.next.val == val:
                current_node.next = current_node.next.next
            else:
                current_node = current_node.next
                
        return dummy_head.next

2020-01-12

LeetCode / Happy Number

LeetCode

https://leetcode.com/problems/happy-number/

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example:

Input: 19 Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

ある値について、各桁の値の二乗和をとり、新しくできた数についても各桁の値の二乗和をとり、、、と繰り返したとき、最終的に1となる数をハッピー数と呼ぶそうです。

与えられた値がハッピー数であるかどうかを判定する問題。易しいです。

解答・解説

解法1

各桁の値の二乗和をとる過程で、1となる前に同じ値が2度出現したらループに入っているため、ハッピー数となりません。

class Solution:
    def isHappy(self, n: int) -> bool:
        seens = set()
        while n != 1:
            n = sum([int(i)**2 for i in str(n)])
            if n in seens:
                return False
            else:
                seens.add(n)
        return True

2020-01-11

LeetCode / House Robber

LeetCode

プログラミングの技術ではなく、高校（中学？）数学の知識を頭の片隅から引っ張り出す必要がある問題。

https://leetcode.com/problems/house-robber/

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

道路に家が立ち並んでいて、リストの各値が各家が貯めているお金だとして、泥棒が各家からお金を盗むケースを想定します。

ただし、隣り合う家から盗ってしまうと警察に連絡されてしまうという前提で、最大限盗めるお金の額を返す問題です。

解答・解説

誤答1

一応示しておくと、以下のようにやってしまうと間違いです。

class Solution:
    def rob(self, nums: List[int]) -> int:
        return max(sum(nums[::2]), sum(nums[1::2]))

初めの要素から1つ飛ばしで和をとる場合と、2つ目の要素から1つ飛ばしで和をとる場合を比べてmaxをとっていますが、

これだと例えば[2,1,1,2]の場合に正しい答えを返せません。

解法1

リストの各要素についてループを回していき、「2つ前の要素までの和の最大値に今の要素を足した値」と「1つ前の要素までの和の最大値」を比べてmaxをとっていく、という方法をとります。
数学的には漸化式と呼ばれる関係になりますが、コードで書くと以下のようになることを意味します。

nums[0] = nums[0]
nums[1] = max(nums[0], nums[1])
nums[k] = max(k + nums[k-2], nums[k-1])

以上の考え方を用いると、以下のように書けます。
numsと同じ長さのリストdpを用意し、漸化式に基づいて計算したnumsの各要素までの最大値を格納します。最終的に返すべき値はdpの最後の要素になります。

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        if not nums: return 0
        if len(nums) == 1: return nums[0]
        
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            dp[i] = max(nums[i] + dp[i-2], dp[i-1])
            
        return dp[-1]

numsと同じ長さのリストを用意したので、時間計算量、空間計算量ともに $O(n)$ となります。

解法2

以下の書き方で、空間計算量を $O(1)$ に抑えることができます。

class Solution:
    def rob(self, nums: List[int]) -> int:
        nlast, nmax = 0, 0
        for i in nums: 
            nlast, nmax = nmax, max(nlast + i, nmax)
        return nmax

2020-01-08

LeetCode / Find the Difference

LeetCode

シンプルな問題ですが、dictionary使ったり、Counter使ったり、アスキーコード使ったり、ビット演算使ったりと、解法が多岐にわたる良問かも。

https://leetcode.com/problems/find-the-difference/

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

文字列sに対して、ランダムに組み換えた上で新たな文字を追加した文字列tがあり、追加された文字を特定する問題。

解答・解説

解法1

私の解法です。collections.Counterを使う方法。

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        count_s = collections.Counter(s)
        count_t = collections.Counter(t)
        for k in count_t:
            if count_t[k] != count_s[k]:
                return k

公式ドキュメントに記載の通り、カウンタオブジェクトは辞書のインタフェースを持ちますが、存在しない要素に対して KeyError を送出する代わりに 0 を返すという違いがあるので、if count_t[k] != count_s[k] とすれば、kがsに存在しない場合もcount_s[k] = 0が返り、if条件にひっかけることができます。

解法2

以下、Discussionから。 Counterを使わずdictionaryで解く方法。dic.get()でkeyがなくても処理できることをなかなか覚えられない。。

class Solution(object):
    def findTheDifference(self, s, t):
        dic = {}
        for ch in s:
            dic[ch] = dic.get(ch, 0) + 1
        for ch in t:
            if dic.get(ch, 0) == 0:
                return ch
            else:
                dic[ch] -= 1

解法3

アスキーコードを使って文字列を整数の和としてしまい、2つの文字列の差分をとって、最後に文字に戻す方法。

class Solution:
    def findTheDifference(self, s, t):
        diff = 0
        for i in range(len(s)):
            diff -= ord(s[i])
            diff += ord(t[i])
        diff += ord(t[-1])
        return chr(diff)

解法4

XOR(排他的論理和)を使う方法。

class Solution:
    def findTheDifference(self, s, t):
        code = 0
        for ch in s + t:
            code ^= ord(ch)
        return chr(code)

XORは和をとった2つの要素が同じであれば0になることを利用します。例えば、"aabbc"という文字列についてアスキーコードに変換してXORをとっていくと、以下のようになります。

for ch in "aabbc":
    code ^= ord(ch)
    print(ch, code)
# a 97
# a 0
# b 98
# b 0
# c 99

つまり、s, tの2つの文字列を結合してXORをとっていくと、文字列の差の分だけが残ることになります。

2020-01-05

LeetCode / First Unique Character in a String

LeetCode

今日は、いくら計算量を頑張って削減してもPythonの超えられない壁があるよ、ということを身を以て伝えてくれる問題です。

https://leetcode.com/problems/first-unique-character-in-a-string/

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

文字列中で出現する回数が1度のみの文字について、初めて登場するインデックスを返す問題です。

解答・解説

解法1

素朴に書いて解くこともできます。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        d = {}
        for c in s:
            if c not in d:
                d[c] = 1
            else:
                d[c] += 1
        uniques = []
        for k,v in d.items():
            if v == 1:
                uniques.append(k)
        if uniques:
            for i,c in enumerate(s):
                if c in uniques:
                    return i
        else:
            return -1

時間計算量、空間計算量ともに $O(n)$ となりますが、空間計算量についてはdとuniquesの2つ変数を作ってしまっているので少し無駄が多い。

解法2

Pythonであれば、collections.Counterを使うとよりスッキリ書ける。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = collections.Counter(s)    
        for i, c in enumerate(s):
            if count[c] == 1:
                return i
        return -1

解法3

Discussionを見ていて面白かったのが以下の解法。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        letters = 'abcdefghijklmnopqrstuvwxyz'
        indexes = [s.index(l) for l in letters if s.count(l) == 1]
        return min(indexes) if len(indexes) > 0 else -1

解法2などの時間計算量は、countとfindの2回ループを回す必要があるので、いわば $O(2n)$ になっていますが、この解法はアルファベットの文字数26個分のループも加わっているので $O(52n)$ になっている。
しかし、こちらの解法の方が爆速で速いのです。私のsubmitしたときは、解法2が84msかかったのに対し、解法3では44msでした。

その理由ですが、string.indexはCで実装された関数だから、ということのようです。

Its only faster because s.index is a C function that python is calling. So you are changing the python loop to be the 26 characters, and the C loop is doing the heavy lifting searching the string. From an algo perspective this is slower than the others. But good to know for python users for runtime speedup

ここでもC系言語の威力を感じます。今年中にC++の学習に取り組めるだろうか。。。

オットセイの経営日誌

データサイエンス系ベンチャーを経営してます。経営のこと、趣味のことつぶやきます。

LeetCode / Isomorphic Strings

解答・解説

解法1

解法2

解法3

解法4

解法5

LeetCode / Count Primes

解答・解説

誤答(TLE)

解法1

LeetCode / Remove Linked List Elements

解答・解説

誤答

解法1

解法2

LeetCode / Happy Number

解答・解説

解法1

LeetCode / House Robber

解答・解説

誤答1

解法1

解法2

LeetCode / Find the Difference

解答・解説

解法1

解法2

解法3

解法4

LeetCode / First Unique Character in a String

解答・解説

解法1

解法2

解法3