コーディング面接対策のために解きたいLeetCode 60問のうち，HashMapに関する問題を解いた．

Two Sum

Given an array of integers, return indices of two number such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example :

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解答その１. 全探索

1
2
3
4
5
6
7

class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums)):
                j = i + 1
                for j in range(j, len(nums)):
                        if nums[i] + nums[j] == target:
                                return [i, j]

計算量 : \(O(n^2) \)

全探索なので効率が悪い

解答その2. HashMap

1
2
3
4
5
6
7
8
9

class Solution:
    def twoSum(self, nums, target):
        dic = {}
        for i in range(len(nums)):
                num = target - nums[i]
                if j not in dic:
                    dic[num] = i
                else:
                    return [dic[num], i]

計算量 : \( O(n) \)

ハッシュテーブルを使ったので計算量が少ない．
速い．

Group Anagrams

Given an array of strings, group anagrams together.

Example :

Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
Output;
[
[“ate”, “eat”, “tea”],
[“nat”, “tan”],
[“bat”]
]

Note

• All input will be in lowercase
• The order of your output does not matter

アナグラムとは文字の並びを入れ替えることで別の意味を作る言葉遊びのこと．

解答

1
2
3
4
5
6
7

class Solution:
    def groupAnagrams(self, strs):
        if tuple(sorted(s)) not in ans:
            ans[tuple(sorted(s))] = [s]
        else:
            ans[tuple(sorted(s))].append(s)
    return ans.values()

単語をアルファベット順に並び替え，タプルにした．
その後タプルをkeyとした辞書に単語がなければkeyとvalueを追加し，そうでなければvalueだけを追加するとvalueが求める答えになる．

Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2]

Example 2:

Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [9, 4]

Note

• Each element in the result must be unique
• The result can be in any order

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def set_intersection(self, set1, set2):
        return [x for x in set1 if x in set2]

    def intersection(self, nums1, nums2):
        set1 = set(nums1)
        set2 = set(nums2)

        if len(set1) < len(set2):
            return self.set_intersection(set1, set2)
        else:
            return self.set_intersection(set2, set1)

自分が書いたコードと模範解答を見比べて，模範解答の方がコードがきれいだったので公式の解答を載せている．

Unique Email Addresses

Every email consists of local name and a domain name, separated by the @ sign.
For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.
Besides lowercase letters, these emails may contain '.' or '+'s.
If you add periods ('.') between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name.
For example, \"alice.z@leetcode.com\" and \"alicez@leetcode.com\" forward to the same email address. (Note that this rule does not apply for domain names)
If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example, m.y+name@email.com will be forwarded to my@email.com. (Again, this rule does not apply for domain names.)
It is possible to use both of these rules at the same time.
Given a list of emails, we send one email to each address in the list. How many different addresses actually receive mails?

Example 1:

Input: [“test.email+alex@leetcode.com”,“test.e.mail+bob.cathy@leetcode.com”,“testemail+david@lee.tcode.com”]
Output: 2
Explanation: “testemail@leetcode.com” and “testemail@lee.tcode.com” actually receive mails

Note

• 1 <= emails[i].length <= 100
• 1 <= emails.length <= 100
• Each emails[i] contains exactly one '@' character.
• All local and domain names are non-empty.
• Local names do not start with a '+' character.

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def numUniqueEmail(self, emails):
        count = 0
        dic = []
        for email in emails:
            local, domain = email.split('@')
            local = local.replace('.', '')
            if '+' in local:
                local = local[: local.find('+')]
            email = local + '@' + domain
            if email not in dic:
                dic.append(email)
                count += 1
        return count

実行結果はこんな感じ．
そこそこ早いコードがかけた気がする．

Runtime:40 ms, faster than 99.05 % of Python3 online submissitions for Unique Email Addresses.
Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Unique Email Addresses.

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.

Example:

s = “leetcode”
return 0.

s = “loveleetcode”
return 2.

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

解答その1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def firstUniqueChar(self, s):
        dic = {}
        for i in s:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1
        for k, v in dic.items():
            if v == 1:
                return s.find(k)
        return -1

はじめに思い浮かんだ方法．
解答その２の方が早かった．

解答その2

1
2
3
4
5
6
7
8

class Solution:
    def firstUniqChar(self, s):
        dic = collections.Counter(s)

        for idx, ch in enumurate(s):
            if dic[ch] == 1:
                return idx
        return -1

模範解答．
このコードの方が実行時間が短かった．
今回のような辞書を作成する場合はcollection.Counterを使うと1行で作成してくれる．
forを回すときはenumerateを使うと，インデックス番号も一緒に取得してくれるので便利．

解答その3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def firstUniqueChar(self, s):
        alphabet = 'abcdefghijklmnopqrstrvwxyz'
        n = len(s)
        for ch in alphabet:
            left = s.find(ch)
            if left != -1 and left == s.rfind(ch):
                if left < n:
                    n = left
        return n if n != len(s) else -1

Discussで見つけた解答．
はじめに全てのアルファベットが入った文字列を作成するのでHashMapを作る必要がない．
計算時間は3つの中で一番早い．
入力が日本語や中国語だったらはじめの文字列が大変なことになりそう(適当)

Subarray Sum Equals K

Given an array integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

input: nums = [1, 1, 1], k = 2
Output: 2

Note:

1. The length of the array is iin range[1, 20000]
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7]

連続した数字の合計がkになる組み合わせは何個ありますかという問題．

解答その1 全探索

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def subarraySum(self, nums, k):
        count = 0
        for start in range(len(nums)):
            for end in range(start+1, len(nums)+1):
                sum = 0
                for i in range(start, end):
                    sum += nums[i]
                if sum ==k:
                    count += 1
        return count

TLE
計算量 : \(O(n^2) \)
メモリ : \(O(n) \)

解答その2 累積和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def subarraySum(self, nums, k):
        count = 0
        ruiseki = [0] * (len(nums)+1)
        for i in range(1, len(nums)+1):
            ruiseki[i] = ruiseki[i-1] + nums[i-1]
        for start in range(0, len(nums)):
            for end in range(start+1, len(nums)+1)
                if ruiseki[end] - ruiseki[start] == k:
                    count += 1
        return count

TLE(JavaではAcceptedされるらしい)
計算量 : \(O(n^2)\)
メモリ : \(O(n)\)

累積和とは

累積和とは配列 \(a_0, a_1, a_2, \cdots, a_{N-1} \)に対して，配列\(s_0, s_1, s_2, \cdots, s_N\)を以下のように定めた\(s_N \)のこと．
\(s_0 = 0\)
\(s_1 = a_0\)
\(s_2 = a_0 + a_1 = s_0 + a_1\)
\(s_3 = a_0 + a_1 + a_2 = s_2 + a_2\)
\(\vdots\)
\(s_N = a_0 + a_1 + a_2 + \cdots + a_{N-1} = s_{N-1} + a_{N-1} \)
累積和を使うと\(a_2 + a_3 + a_4 + a_5\)は\(s_6 - s_2\)と求めることが出来る．

解答その3 その2の改良版

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def subarraySum(self, nums, k):
    count = 0
    for start in range(len(nums)):
        goukei = 0
        for end in range(start, len(nums)):
            goukei += nums[end]
            if goukei == k:
                count += 1
    return count

TLE(JavaではAcceptedされるらしい)
計算量 : \(O(n^2)\)
メモリ : \(O(n)\)

解答その4 HashMap

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def subarraySum(self, nums, k):
    count = 0
    goukei = 0
    dic = {0: 1}
    for num in nums:
        goukei += num
        count += dic.get(goukei-k, 0)
        dic[goukei] = dic.get(goukei, 0) + 1
    return count

HashMapを使うと通った．
計算量 : \(O(n)\)
メモリ : \(O(n)\)

Runtime: 112 ms, faster than 89.41 % of Python3 online submissions for Subarray Sum Equals K.
Memory Usage: 15.1 MB, less than 96.00 % of Python3 online submissions for Subarray Sum Equals K.

累積和を辞書に保存して\(a_i\)までの合計から欲しい和\(k\)を引いた値(=累積和)が辞書にあれば，その累積和から\(a_i\)までの合計が\(k\)になることが分かるので，カウンターを回す．
辞書を作りながら調べるので計算量が少ない．

具体例:
\(a_2 + a_3 + a_4 + a_5 = k\)は\((a_0 + a_1 + \cdots + a_5) - s_2 = k\)となるので，\((a_0 + a_1 + \cdots + a_5) - k = s_2\)となる．
だから\(s_2\)が辞書にあれば，存在する累積和からの連続した数字の合計は\(k\)になる．

感想

HashMap便利だなぁ．
うまく使いこなせるようになりたいです．