コーディング面接対策のために解きたい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. 全探索
|
|
計算量 : \(O(n^2) \)
全探索なので効率が悪い
解答その2. HashMap
|
|
計算量 : \( 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
アナグラムとは文字の並びを入れ替えることで別の意味を作る言葉遊びのこと.
解答
|
|
単語をアルファベット順に並び替え,タプルにした.
その後タプルを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
解答
|
|
自分が書いたコードと模範解答を見比べて,模範解答の方がコードがきれいだったので公式の解答を載せている.
Unique Email Addresses
Every email consists of local name and a domain name, separated by the @ sign.
For example, inalice@leetcode.com
,alice
is the local name, andleetcode.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 tomy@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 ofemails
, 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.
解答
|
|
実行結果はこんな感じ.
そこそこ早いコードがかけた気がする.
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
|
|
はじめに思い浮かんだ方法.
解答その2の方が早かった.
解答その2
|
|
模範解答.
このコードの方が実行時間が短かった.
今回のような辞書を作成する場合はcollection.Counter
を使うと1行で作成してくれる.
forを回すときはenumerate
を使うと,インデックス番号も一緒に取得してくれるので便利.
解答その3
|
|
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:
- The length of the array is iin range[1, 20000]
- The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7]
連続した数字の合計がkになる組み合わせは何個ありますかという問題.
解答その1 全探索
|
|
TLE
計算量 : \(O(n^2) \)
メモリ : \(O(n) \)
解答その2 累積和
|
|
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の改良版
|
|
TLE(JavaではAcceptedされるらしい)
計算量 : \(O(n^2)\)
メモリ : \(O(n)\)
解答その4 HashMap
|
|
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便利だなぁ.
うまく使いこなせるようになりたいです.