LeetCode Hash Table

Design HashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyHashSet {
private var bucket = Array(repeating: false, count: 1000001)

func add(_ key: Int) {
bucket[key] = true
}

func remove(_ key: Int) {
bucket[key] = false
}

func contains(_ key: Int) -> Bool {
return bucket[key]
}
}

Design HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyHashMap {
private var bucket = Array(repeating: -1, count: 1000001)

func put(_ key: Int, _ value: Int) {
bucket[key] = value
}

func get(_ key: Int) -> Int {
return bucket[key]
}

func remove(_ key: Int) {
bucket[key] = -1
}
}

Contains Duplicate

1
2
3
4
5
6
7
8
9
10
class Solution {
func containsDuplicate(_ nums: [Int]) -> Bool {
var set = Set<Int>()
for i in nums {
if set.contains(i) { return true }
set.insert(i)
}
return false
}
}

Single Number

1
2
3
4
5
class Solution {
func singleNumber(_ nums: [Int]) -> Int {
return nums.reduce(0) { $0 ^ $1 }
}
}

Intersection of Two Arrays

1
2
3
4
5
6
class Solution {
func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
let set1 = Set(nums1), set2 = Set(nums2)
return Array(set1.intersection(set2))
}
}

Happy Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private var setI = Set<Int>()
func isHappy(_ n: Int) -> Bool {
if n == 1 { return true }
var i = n, r = 0
while i > 0 {
let t = i%10
r += t*t
i /= 10
}

if setI.contains(r) { return false }

setI.insert(r)
return isHappy(r)
}
}

1

1

Minimum Index Sum of Two Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
// 452 ms
func findRestaurant(_ list1: [String], _ list2: [String]) -> [String] {
var dict2 = [String: Int](), least = Int.max, arr = [String]()
for i in 0..<list2.count {
dict2[ list2[i] ] = i
}
for i in 0..<list1.count {
if let j = dict2[ list1[i] ] {
let n = i+j
if n < least {
arr = [list1[i]]
least = n
} else if n == least {
arr.append(list1[i])
}
}
}
return arr
}

// 2104 ms
func findRestaurant(_ list1: [String], _ list2: [String]) -> [String] {
let dict1 = list1.enumerated().reduce(into: [String: Int]()) { $0[$1.1] = $1.0 }
let dict2 = list2.enumerated().reduce(into: [String: Int]()) { $0[$1.1] = $1.0 }
let dict = Set(dict1.keys).intersection(dict2.keys).reduce(into: [String: Int]()) { $0[$1] = dict1[$1]! + dict2[$1]! }

return dict.filter { $0.value == dict.map({ $0.value }).min() }.map { $0.key }
}
}

Intersection of Two Arrays II

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

class Solution {
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var dict = [Int: Int](), ans = [Int]()
for n in nums1 {
dict[n, default: 0] += 1
}
for n in nums2 {
if let v = dict[n], v > 0 {
ans.append(n)
dict[n] = v - 1
}
}
return ans
}
}

Contains Duplicate II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
var dict = [Int: [Int]]()
for i in 0..<nums.count {
let n = nums[i]
if let arr = dict[n] {
for j in arr {
if i-j <= k { return true }
}
dict[n] = arr + [i]
} else {
dict[n] = [i]
}
}

return false
}
}

Logger Rate Limiter

1
2
3
4
5
6
7
8
9
10
class Logger {
private var logs = [String: Int]()
func shouldPrintMessage(_ timestamp: Int, _ message: String) -> Bool {
if let lastTimestamp = logs[message], timestamp - lastTimestamp < 10 {
return false
}
logs[message] = timestamp
return true
}
}

Group Shifted Strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
func groupStrings(_ strings: [String]) -> [[String]] {
var dict = [[Int]: [String]]()
for s in strings {
let arrS = Array(s)
var arr = [Int]()
for i in (1..<arrS.count) {
arr.append((Int(arrS[i].asciiValue!)-Int(arrS[i-1].asciiValue!)+26)%26)
}
dict[arr, default: []] += [s]
}
return dict.map { $0.value }
}
}

Valid Sudoku

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
func isValidSudoku(_ board: [[Character]]) -> Bool {
var sets = Array(repeating: Set<Character>(), count: 9)
for i in 0..<9 {
for j in 0..<9 {
let c = board[i][j]
if c == "." { continue }
if sets[i].contains(c) {
return false
} else {
sets[i].insert(c)
}
}
}

sets = Array(repeating: Set<Character>(), count: 9)
for j in 0..<9 {
for i in 0..<9 {
let c = board[i][j]
if c == "." { continue }
if sets[j].contains(c) {
return false
} else {
sets[j].insert(c)
}
}
}

for i in 0..<3 {
for j in 0..<3 {
var setC = Set<Character>()
for k in 0..<3 {
for l in 0..<3 {
let c = board[i*3+k][j*3+l]
if c == "." { continue }
if setC.contains(c) {
return false
} else {
setC.insert(c)
}
}
}

}
}

return true
}
}

Find Duplicate Subtrees

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
dfs(root)
return nodeDict.filter { $0.value.1 > 1 }.map { $0.value.0 }
}

private var nodeDict = [[Int?]: (TreeNode, Int)]()
private func dfs(_ node: TreeNode?) -> [Int?] {
guard let node = node else { return [nil] }
let key: [Int?] = [node.val] + dfs(node.left) + dfs(node.right)
nodeDict[key, default: (node, 0)].1 += 1
return key
}
}

Jewels and Stones

1
2
3
4
5
6
class Solution {
func numJewelsInStones(_ J: String, _ S: String) -> Int {
let j = Set(J)
return S.reduce(0) { $0 + (j.contains($1) ? 1 : 0) }
}
}

Longest Substring Without Repeating Characters

1
2


Two Sum III - Data structure design

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class TwoSum {
private var numbers = [Int: Int]()

func add(_ number: Int) {
numbers[number, default: 0] += 1
}

func find(_ value: Int) -> Bool {
for (k, v) in numbers {
let rest = value-k
if let num = numbers[rest], (num > ((rest == k) ? 1 : 0)) {
return true
}
}
return false
}
}

4Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
func fourSumCount(_ A: [Int], _ B: [Int], _ C: [Int], _ D: [Int]) -> Int {
var num = 0, ab = [Int: Int]()
for i in A {
for j in B {
ab[i+j, default: 0] += 1
}
}
for i in C {
for j in D {
if let v = ab[-i-j] { num += v }
}
}
return num
}
}

Top K Frequent Elements

1
2
3
4
5
class Solution {
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
return nums.reduce(into: [Int: Int]()) { $0[$1, default: 0] += 1 }.sorted(by: {$0.value > $1.value})[..<k].map{$0.key}
}
}

Unique Word Abbreviation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ValidWordAbbr {
private var abbrDict = [String: Set<String>]()
init(_ dictionary: [String]) {
dictionary.forEach { abbrDict[abbreviate($0), default: Set<String>()].insert($0) }
}

func isUnique(_ word: String) -> Bool {
if let abbrSet = abbrDict[abbreviate(word)] {
return abbrSet.contains(word) && abbrSet.count == 1
}
return true
}

private func abbreviate(_ word: String) -> String {
return word.count < 3 ? word : (String(word.first!) + String(word.count-2) + String(word.last!))
}
}

Insert Delete GetRandom O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 220 ms, 30.27%
class RandomizedSet {
private var vals = Set<Int>()

func insert(_ val: Int) -> Bool {
if vals.contains(val) { return false }
vals.insert(val)
return true
}

func remove(_ val: Int) -> Bool {
if !vals.contains(val) { return false }
vals.remove(val)
return true
}

func getRandom() -> Int {
return vals.randomElement() ?? 0
}
}