LeetCode Hash Table

发表于 更新于 Disqus： 本文字数： 7k 阅读时长 ≈ 6 分钟

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
    }
}