LeetCode 初级算法 Swift 练习

发表于 更新于 分类于 阅读次数：

五个月的实习告一段落了，学习还是要继续的。接触不到业务，刷一下 LeetCode 初级算法吧。顺便好像欠了几篇博文……

Array

Remove Duplicates from Sorted Array

26-e1.swiftview raw
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
//
//  26-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/17.
//  Updated by nuomi1 on 2021/5/7.
//  Updated by nuomi1 on 2021/5/11.
//

// Remove Duplicates from Sorted Array
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/727/
// https://leetcode.com/explore/learn/card/fun-with-arrays/526/deleting-items-from-an-array/3248/
// https://leetcode.com/explore/learn/card/fun-with-arrays/511/in-place-operations/3258/
// https://leetcode.com/problems/remove-duplicates-from-sorted-array/

// 删除排序数组中的重复项
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

// MARK: Two Pointers

func removeDuplicates(_ nums: inout [Int]) -> Int {
    // 数组元素个数小于 2 时不需要处理
    guard nums.count > 1 else {
        return nums.count
    }

    // 对比下标
    var leftIndex = nums.startIndex

    // 扫描下标，跳过初始的对比下标
    for rightIndex in nums.indices.dropFirst() {
        // 对比下标与扫描下标的元素不相等，对比下标前进
        if nums[leftIndex] != nums[rightIndex] {
            nums.formIndex(after: &leftIndex)
            nums[leftIndex] = nums[rightIndex]
        }
    }

    // 返回个数为扫描下标加一
    let distance = nums.distance(from: nums.startIndex, to: leftIndex)
    return distance + 1
}

Best Time to Buy and Sell Stock II

122-e3.swiftview raw
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
//
//  122-e3.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/18.
//

// Best Time to Buy and Sell Stock II
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/564/
// https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

// 买卖股票的最佳时机 II
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/
// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

// MARK: Simple One Pass

func maxProfit(_ prices: [Int]) -> Int {
    var profit = 0

    // 扫描下标，跳过初始下标
    for currentIndex in prices.indices.dropFirst() {
        // 当天与前一天的价格差
        // 价格差大于 0，盈利
        // 价格差小于 0，忽略
        let previousIndex = prices.index(before: currentIndex)
        profit += max(prices[currentIndex] - prices[previousIndex], 0)
    }

    return profit
}

Rotate Array

189-e4.swiftview raw
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
//
//  189-e4.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/19.
//

// Rotate Array
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/646/
// https://leetcode.com/problems/rotate-array/

// 旋转数组
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
// https://leetcode-cn.com/problems/rotate-array/

// MARK: Using Reverse

func rotate(_ nums: inout [Int], _ k: Int) {
    // 右移长度不应超过数组元素个数
    let realK = k % nums.count

    // 实际右移长度大于 0 时才继续
    guard realK > 0 else {
        return
    }

    // 先翻转整个数组，再以 k 为分割线翻转两个子数组
    // nums = [1, 2, 3, 4, 5], k = 2
    // [5, 4, 3, 2, 1]
    // [4, 5, 3, 2, 1]
    // [4, 5, 1, 2, 3]
    nums.reverse()
    nums[..<realK].reverse()
    nums[realK...].reverse()
}
189-s1.swiftview raw
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
//
//  189-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/19.
//

// Rotate Array
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/646/
// https://leetcode.com/problems/rotate-array/

// 旋转数组
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
// https://leetcode-cn.com/problems/rotate-array/

// MARK: BAD (not in-place)

func rotate(_ nums: inout [Int], _ k: Int) {
    let realK = k % nums.count

    guard realK > 0 else {
        return
    }

    let prefixNums = nums.prefix(nums.count - realK)
    let suffixNums = nums.suffix(realK)

    nums = Array(suffixNums + prefixNums)
}

Contains Duplicate

217-e3.swiftview raw
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
//
//  217-e3.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/20.
//

// Contains Duplicate
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/578/
// https://leetcode.com/problems/contains-duplicate/

// 存在重复元素
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x248f5/
// https://leetcode-cn.com/problems/contains-duplicate/

// MARK: Hash Table

func containsDuplicate(_ nums: [Int]) -> Bool {
    var counts: Set<Int> = []

    for num in nums {
        if !counts.insert(num).inserted {
            return true
        }
    }

    return false
}
217-s1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//
//  217-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/20.
//

// Contains Duplicate
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/578/
// https://leetcode.com/problems/contains-duplicate/

// 存在重复元素
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x248f5/
// https://leetcode-cn.com/problems/contains-duplicate/

func containsDuplicate(_ nums: [Int]) -> Bool {
    // 比较原始数组和构造集合（元素互不相同 / hashValue）的个数
    return nums.count != Set(nums).count
}

Single Number

136-e4.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//
//  136-e4.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/21.
//

// Single Number
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/549/
// https://leetcode.com/problems/single-number/

// 只出现一次的数字
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x21ib6/
// https://leetcode-cn.com/problems/single-number/

// MARK: Bit Manipulation

func singleNumber(_ nums: [Int]) -> Int {
    // 异或运算
    // a ^ 0 = a
    // a ^ a = 0
    // a ^ b ^ a = a ^ a ^ b = 0 ^ b = b
    return nums.reduce(0) { $0 ^ $1 }
}
136-s1.swiftview raw
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
//
//  136-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/21.
//

// Single Number
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/549/
// https://leetcode.com/problems/single-number/

// 只出现一次的数字
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x21ib6/
// https://leetcode-cn.com/problems/single-number/

// MARK: BAD (not in-place)

func singleNumber(_ nums: [Int]) -> Int {
    let nums = nums.sorted()

    for currentIndex in nums.indices.dropLast() where currentIndex.isMultiple(of: 2) {
        let nextIndex = nums.index(after: currentIndex)
        if nums[currentIndex] != nums[nextIndex] {
            return nums[currentIndex]
        }
    }

    return nums.last!
}

Intersection of Two Arrays II

350-c1.swiftview raw
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
//
//  350-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/22.
//

// Intersection of Two Arrays II
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/674/
// https://leetcode.com/problems/intersection-of-two-arrays-ii/

// 两个数组的交集 II
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/
// https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

// MARK: 哈希表

func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
    var counts = [Int: Int]()
    var result = [Int]()

    // 记录 nums1 数组元素出现的次数
    for num in nums1 {
        counts[num, default: 0] += 1
    }

    // 当元素同时存在于两个数组时记录，并减去一次计数
    for num in nums2 {
        if counts[num, default: 0] > 0 {
            result.append(num)
            counts[num, default: 0] -= 1
        }
    }

    return result
}
350-c2.swiftview raw
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
//
//  350-c2.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/22.
//

// Intersection of Two Arrays II
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/674/
// https://leetcode.com/problems/intersection-of-two-arrays-ii/

// 两个数组的交集 II
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/
// https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

// MARK: 排序 + 双指针

func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
    // 排序
    let nums1 = nums1.sorted()
    let nums2 = nums2.sorted()

    // 扫描下标
    var iIndex = nums1.startIndex
    var jIndex = nums2.startIndex

    var result = [Int]()

    // 比较 nums1[iIndex] 与 nums2[jIndex] 的大小
    // 不相等时较小者的扫描下标前进
    // 相等时即为重复元素且扫描下标同时前进
    while iIndex < nums1.endIndex, jIndex < nums2.endIndex {
        switch nums1[iIndex] - nums2[jIndex] {
        case ...(-1):
            nums1.formIndex(after: &iIndex)
        case 0:
            result.append(nums1[iIndex])
            nums1.formIndex(after: &iIndex)
            nums2.formIndex(after: &jIndex)
        case 1...:
            nums2.formIndex(after: &jIndex)
        default:
            fatalError()
        }
    }

    return result
}

Plus One

66-s1.swiftview raw
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
//
//  66-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/23.
//

// Plus One
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/559/
// https://leetcode.com/problems/plus-one/

// 加一
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2cv1c/
// https://leetcode-cn.com/problems/plus-one/

func plusOne(_ digits: [Int]) -> [Int] {
    var digits = digits

    // 扫描下标逆序
    for index in digits.indices.reversed() {
        // 当前位不到 9 时，直接加一然后退出
        if digits[index] < 9 {
            digits[index] += 1
            return digits
        }

        // 当前位是 9 时，置零
        // 往左继续执行
        digits[index] = 0
    }

    // 顺序第 2 位是 9，进位
    digits.insert(1, at: 0)

    return digits
}
66-s2.swiftview raw
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
//
//  66-s2.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/23.
//

// Plus One
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/559/
// https://leetcode.com/problems/plus-one/

// 加一
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2cv1c/
// https://leetcode-cn.com/problems/plus-one/

func plusOne(_ digits: [Int]) -> [Int] {
    var digits = digits

    // 进位
    var carry = 1

    // 扫描下标逆序
    for index in digits.indices.reversed() {
        // 把进位与当前位相加，除以 10 取得商和余数
        (carry, digits[index]) = (digits[index] + carry).quotientAndRemainder(dividingBy: 10)

        // 不需要进位时直接退出
        if carry == 0 {
            return digits
        }
    }

    // 顺序第 2 位是 9，进位
    digits.insert(carry, at: 0)

    return digits
}
66-s3.swiftview raw
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
//
//  66-s3.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/23.
//

// Plus One
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/559/
// https://leetcode.com/problems/plus-one/

// 加一
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2cv1c/
// https://leetcode-cn.com/problems/plus-one/

func plusOne(_ digits: [Int]) -> [Int] {
    // 最高位补零
    var digits = [0] + digits

    // 个位进一
    digits[digits.indices.last!] += 1

    // 除最高位外，从低位到高位，逢十进一
    for currentIndex in digits.indices.dropFirst().reversed() {
        if digits[currentIndex] >= 10 {
            let previousIndex = digits.index(before: currentIndex)
            digits[currentIndex] -= 10
            digits[previousIndex] += 1
        }
    }

    // 最高位为零时，移除并返回剩余元素
    if digits.first! == 0 {
        return Array(digits.dropFirst())
    }

    return digits
}

Move Zeroes

283-e1.swiftview raw
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
//
//  283-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/24.
//  Updated by nuomi1 on 2021/5/12.
//

// Move Zeroes
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/567/
// https://leetcode.com/explore/learn/card/fun-with-arrays/511/in-place-operations/3157/
// https://leetcode.com/problems/move-zeroes/

// 移动零
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2ba4i/
// https://leetcode-cn.com/problems/move-zeroes/

// MARK: Space Sub-Optimal

func moveZeroes(_ nums: inout [Int]) {
    // 统计 0 的个数
    let count = nums.filter { $0 == 0 }.count
    // 删除所有 0
    nums.removeAll { $0 == 0 }
    // 末尾补 0
    nums.append(contentsOf: Array(repeating: 0, count: count))
}
283-e3.swiftview raw
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
//
//  283-e3.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/24.
//  Updated by nuomi1 on 2021/5/12.
//

// Move Zeroes
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/567/
// https://leetcode.com/explore/learn/card/fun-with-arrays/511/in-place-operations/3157/
// https://leetcode.com/problems/move-zeroes/

// 移动零
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2ba4i/
// https://leetcode-cn.com/problems/move-zeroes/

// MARK: Optimal

func moveZeroes(_ nums: inout [Int]) {
    var leftIndex = nums.startIndex

    // 把非零项移动到前方，后方即为零项
    for rightIndex in nums.indices {
        if nums[rightIndex] != 0 {
            nums.swapAt(rightIndex, leftIndex)
            nums.formIndex(after: &leftIndex)
        }
    }
}

Two Sum

1-e1.swiftview raw
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
//
//  1-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/25.
//

// Two Sum
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/546/
// https://leetcode.com/problems/two-sum/

// 两数之和
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2jrse/
// https://leetcode-cn.com/problems/two-sum/

// MARK: Brute Force

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    for leftIndex in nums.indices.dropLast() {
        let distance = nums.distance(from: nums.startIndex, to: nums.index(after: leftIndex))
        for rightIndex in nums.indices.dropFirst(distance) {
            // 依次判断剩余数组元素是否符合
            if nums[leftIndex] + nums[rightIndex] == target {
                return [leftIndex, rightIndex]
            }
        }
    }

    fatalError()
}
1-e2.swiftview raw
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
//
//  1-e2.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/25.
//

// Two Sum
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/546/
// https://leetcode.com/problems/two-sum/

// 两数之和
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2jrse/
// https://leetcode-cn.com/problems/two-sum/

// MARK: Two-pass Hash Table

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    typealias Element = Int
    typealias Index = Array<Element>.Index

    // 转换数组到 [下标: 元素] 的字典
    let positions = nums.indices.reduce(into: [Index: Element]()) {
        $0[nums[$1]] = $1
    }

    // 在字典中找到另一个加数，两者下标不相同则输出
    for currentIndex in nums.indices {
        let another = target - nums[currentIndex]
        if let anotherIndex = positions[another], currentIndex != anotherIndex {
            return [currentIndex, anotherIndex]
        }
    }

    fatalError()
}

Valid Sudoku

36-e1.swiftview raw
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
//
//  36-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/26.
//

// Valid Sudoku
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/769/
// https://leetcode.com/problems/valid-sudoku/

// 有效的数独
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
// https://leetcode-cn.com/problems/valid-sudoku/

// MARK: One iteration

func isValidSudoku(_ board: [[Character]]) -> Bool {
    var rows = [Set<Character>](repeating: [], count: board.count)
    var columns = [Set<Character>](repeating: [], count: board.count)
    var cubes = [Set<Character>](repeating: [], count: board.count)

    // 第 i 行第 j 列元素属于第 i 行 / 列 / 块
    for iIndex in board.indices {
        for jIndex in board.indices {
            let num = board[iIndex][jIndex]

            guard num != "." else {
                continue
            }

            let rowIndex = iIndex
            let columnIndex = jIndex
            let cubeIndex = 3 * (iIndex / 3) + (jIndex / 3)

            // 存在重复时退出
            guard !rows[rowIndex].contains(num), !columns[columnIndex].contains(num), !cubes[cubeIndex].contains(num) else {
                return false
            }

            rows[rowIndex].insert(num)
            columns[columnIndex].insert(num)
            cubes[cubeIndex].insert(num)
        }
    }

    return true
}
36-s1.swiftview raw
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
50
51
52
53
54
55
//
//  36-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/26.
//

// Valid Sudoku
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/769/
// https://leetcode.com/problems/valid-sudoku/

// 有效的数独
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
// https://leetcode-cn.com/problems/valid-sudoku/

func isValidSudoku(_ board: [[Character]]) -> Bool {
    // 第 i 行 / 列 / 块的第 j 个元素
    for iIndex in board.indices {
        var row = Set<Character>()
        var column = Set<Character>()
        var cube = Set<Character>()

        // 依次遍历行 / 列 / 块，存在重复时退出
        for jIndex in board.indices {
            let rowElement = board[iIndex][jIndex]
            if rowElement != "." {
                guard !row.contains(rowElement) else {
                    return false
                }

                row.insert(rowElement)
            }

            let columnElement = board[jIndex][iIndex]
            if columnElement != "." {
                guard !column.contains(columnElement) else {
                    return false
                }

                column.insert(columnElement)
            }

            let cubeElement = board[3 * (iIndex / 3) + jIndex / 3][3 * (iIndex % 3) + jIndex % 3]
            if cubeElement != "." {
                guard !cube.contains(cubeElement) else {
                    return false
                }

                cube.insert(cubeElement)
            }
        }
    }

    return true
}
36-s2.swiftview raw
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
//
//  36-s2.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/26.
//

// Valid Sudoku
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/769/
// https://leetcode.com/problems/valid-sudoku/

// 有效的数独
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
// https://leetcode-cn.com/problems/valid-sudoku/

func isValidSudoku(_ board: [[Character]]) -> Bool {
    // 第 index 行 / 列 / 块的所有元素
    for index in board.indices {
        let row = board[index].filter { $0 != "." }
        guard row.count == Set(row).count else {
            return false
        }

        let column = board.map { $0[index] }.filter { $0 != "." }
        guard column.count == Set(column).count else {
            return false
        }

        let cubeIndex = (i: 3 * (index / 3), j: 3 * (index % 3))
        let cube = board[cubeIndex.i ..< cubeIndex.i + 3].flatMap { $0[cubeIndex.j ..< cubeIndex.j + 3] }.filter { $0 != "." }
        guard cube.count == Set(cube).count else {
            return false
        }
    }

    return true
}

Rotate Image

48-e1.swiftview raw
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
//
//  48-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/27.
//

// Rotate Image
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/770/
// https://leetcode.com/problems/rotate-image/

// 旋转图像
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhhkv/
// https://leetcode-cn.com/problems/rotate-image/

// MARK: Rotate Groups of Four Cells

func rotate(_ matrix: inout [[Int]]) {
    let n = matrix.indices.last!

    // 第 i 圈第 j 次交换
    for i in matrix.indices.prefix(matrix.endIndex / 2) {
        for j in matrix.indices.dropLast(i + 1).dropFirst(i) {
            // 左上
            let topLeft = (i: i, j: j)
            // 右上
            let topRight = (i: j, j: n - i)
            // 右下
            let bottomRight = (i: n - i, j: n - j)
            // 左下
            let bottomLeft = (i: n - j, j: i)

            (
                matrix[topLeft.i][topLeft.j],
                matrix[topRight.i][topRight.j],
                matrix[bottomRight.i][bottomRight.j],
                matrix[bottomLeft.i][bottomLeft.j]
            )
                =
                (
                    matrix[bottomLeft.i][bottomLeft.j],
                    matrix[topLeft.i][topLeft.j],
                    matrix[topRight.i][topRight.j],
                    matrix[bottomRight.i][bottomRight.j]
                )
        }
    }
}

Strings

Reverse String

344-e2.swiftview raw
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
//
//  344-e2.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/28.
//

// Reverse String
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/879/
// https://leetcode.com/problems/reverse-string/

// 反转字符串
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhbqj/
// https://leetcode-cn.com/problems/reverse-string/

// MARK: Two Pointers, Iteration

func reverseString(_ s: inout [Character]) {
    // 扫描下标
    var leftIndex = s.startIndex
    var rightIndex = s.index(before: s.endIndex)

    // 最左最右交换，然后向内前进
    while leftIndex < rightIndex {
        s.swapAt(leftIndex, rightIndex)
        s.formIndex(after: &leftIndex)
        s.formIndex(before: &rightIndex)
    }
}

Reverse Integer

7-e1.swiftview raw
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
//
//  7-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/29.
//

// Reverse Integer
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/880/
// https://leetcode.com/problems/reverse-integer/

// 整数反转
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnx13t/
// https://leetcode-cn.com/problems/reverse-integer/

// MARK: Pop and Push Digits & Check before Overflow

func reverse(_ x: Int) -> Int {
    var x = Int32(x)
    var overflow = (false, false)
    var result: Int32 = 0

    while x != 0 {
        // 除以 10 取商和余数
        let (quotient, remainder) = x.quotientAndRemainder(dividingBy: 10)

        // 乘以 10
        (result, overflow.0) = result.multipliedReportingOverflow(by: 10)
        // 加上余数
        (result, overflow.1) = result.addingReportingOverflow(remainder)

        // 溢出返回 0
        guard !overflow.0, !overflow.1 else {
            return 0
        }

        // 用商继续循环
        x = quotient
    }

    return Int(result)
}

First Unique Character in a String

387-e1.swiftview raw
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
//
//  387-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/30.
//

// First Unique Character in a String
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/881/
// https://leetcode.com/problems/first-unique-character-in-a-string/

// 字符串中的第一个唯一字符
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn5z8r/
// https://leetcode-cn.com/problems/first-unique-character-in-a-string/

// MARK: Linear time solution

func firstUniqChar(_ s: String) -> Int {
    // 转换字符串到 [元素: 个数] 的字典
    let counts = s.reduce(into: [Character: Int]()) {
        $0[$1, default: 0] += 1
    }

    // 遍历字符串，当个数为 1 时退出
    for (index, character) in s.enumerated() {
        if counts[character, default: 0] == 1 {
            return index
        }
    }

    return -1
}

Valid Anagram

242-e1.swiftview raw
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
//
//  242-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/31.
//

// Valid Anagram
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/882/
// https://leetcode.com/problems/valid-anagram/

// 有效的字母异位词
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn96us/
// https://leetcode-cn.com/problems/valid-anagram/

// MARK: Sorting

func isAnagram(_ s: String, _ t: String) -> Bool {
    guard s.count == t.count else {
        return false
    }

    let s = s.sorted()
    let t = t.sorted()

    return s == t
}
242-s1.swiftview raw
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
//
//  242-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2018/12/31.
//

// Valid Anagram
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/882/
// https://leetcode.com/problems/valid-anagram/

// 有效的字母异位词
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn96us/
// https://leetcode-cn.com/problems/valid-anagram/

func isAnagram(_ s: String, _ t: String) -> Bool {
    guard s.count == t.count else {
        return false
    }

    let sCounts = s.reduce(into: [Character: Int]()) {
        $0[$1, default: 0] += 1
    }

    let tCounts = t.reduce(into: [Character: Int]()) {
        $0[$1, default: 0] += 1
    }

    return sCounts == tCounts
}

Valid Palindrome

125-c1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//
//  125-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/1.
//

// Valid Palindrome
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/883/
// https://leetcode.com/problems/valid-palindrome/

// 验证回文串
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xne8id/
// https://leetcode-cn.com/problems/valid-palindrome/

// MARK: 筛选 + 判断

func isPalindrome(_ s: String) -> Bool {
    let s = s.filter { $0.isNumber || $0.isLetter }.lowercased()
    return s == String(s.reversed())
}
125-c2.swiftview raw
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
//
//  125-c2.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/1.
//

// Valid Palindrome
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/883/
// https://leetcode.com/problems/valid-palindrome/

// 验证回文串
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xne8id/
// https://leetcode-cn.com/problems/valid-palindrome/

// MARK: 在原字符串上直接判断

func isPalindrome(_ s: String) -> Bool {
    guard !s.isEmpty else {
        return true
    }

    var leftIndex = s.startIndex
    var rightIndex = s.index(before: s.endIndex)

    // leftIndex 下标从开到尾，rightIndex 下标从尾到头，直到 leftIndex 与 rightIndex 相遇
    while leftIndex < rightIndex {
        guard s[leftIndex].isNumber || s[leftIndex].isLetter else {
            s.formIndex(after: &leftIndex)
            continue
        }

        guard s[rightIndex].isNumber || s[rightIndex].isLetter else {
            s.formIndex(before: &rightIndex)
            continue
        }

        guard s[leftIndex].lowercased() == s[rightIndex].lowercased() else {
            return false
        }

        s.formIndex(after: &leftIndex)
        s.formIndex(before: &rightIndex)
    }

    return true
}

String to Integer (atoi)

8-e1.swiftview raw
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
50
//
//  8-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/2.
//

// String to Integer (atoi)
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/884/
// https://leetcode.com/problems/string-to-integer-atoi/

// 字符串转换整数 (atoi)
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnoilh/
// https://leetcode-cn.com/problems/string-to-integer-atoi/

// MARK: Scan from left to right

func myAtoi(_ str: String) -> Int {
    var sign: Int32 = 1
    var overflow = (false, false)
    var result: Int32 = 0

    var index = str.startIndex

    // 跳过前导空格
    while index != str.endIndex, str[index].isWhitespace {
        str.formIndex(after: &index)
    }

    // 识别正负号
    if index != str.endIndex, ["+", "-"].contains(str[index]) {
        sign = str[index] == "+" ? 1 : -1

        str.formIndex(after: &index)
    }

    // 识别数字并累进
    while index != str.endIndex, str[index].isNumber {
        (result, overflow.0) = result.multipliedReportingOverflow(by: 10)
        (result, overflow.1) = result.addingReportingOverflow(sign * Int32(str[index].asciiValue! - ("0" as Character).asciiValue!))

        guard !overflow.0, !overflow.1 else {
            return sign == 1 ? Int(Int32.max) : Int(Int32.min)
        }

        str.formIndex(after: &index)
    }

    return Int(result)
}

Implement strStr()

28-c1.swiftview raw
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
//
//  28-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/3.
//

// Implement strStr()
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/885/
// https://leetcode.com/problems/implement-strstr/

// 实现 strStr()
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnr003/
// https://leetcode-cn.com/problems/implement-strstr/

// MARK: 子串逐一比较

func strStr(_ haystack: String, _ needle: String) -> Int {
    guard !needle.isEmpty else {
        return 0
    }

    // 只处理 haystack 前面，完整遍历会越界
    for index in haystack.indices.dropLast(needle.count - 1) {
        // subscript[...] 转换为包含所有元素的 Substring
        if haystack[index ..< haystack.index(index, offsetBy: needle.count)] == needle[...] {
            return index.utf16Offset(in: haystack)
        }
    }

    return -1
}

Count and Say

38-s1.swiftview raw
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
//
//  38-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/4.
//

// Count and Say
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/886/
// https://leetcode.com/problems/count-and-say/

// 外观数列
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnpvdm/
// https://leetcode-cn.com/problems/count-and-say/

func countAndSay(_ n: Int) -> String {
    var result = "1"

    // result 存在默认值，遍历 n - 1 次
    for _ in 1 ..< n {
        var count = 0
        var current = result.first!
        var tempResult = ""

        for number in result {
            if number == current {
                count += 1
            } else {
                tempResult.append(contentsOf: "\(count)\(current)")
                count = 1
                current = number
            }
        }

        // 处理 result 最后一个元素
        tempResult.append(contentsOf: "\(count)\(current)")

        result = tempResult
    }

    return result
}

Longest Common Prefix

14-e2.swiftview raw
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
//
//  14-e2.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/5.
//

// Longest Common Prefix
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/887/
// https://leetcode.com/problems/longest-common-prefix/

// 最长公共前缀
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnmav1/
// https://leetcode-cn.com/problems/longest-common-prefix/

// MARK: Vertical scanning

func longestCommonPrefix(_ strs: [String]) -> String {
    // 第 1 个当做前缀
    guard let prefixString = strs.first else {
        return ""
    }

    // 遍历前缀
    for prefixStringIndex in prefixString.indices {
        let prefixCount = prefixStringIndex.utf16Offset(in: prefixString)
        let character = prefixString[prefixStringIndex]

        // 遍历剩余字符串
        for strsIndex in strs.indices.dropFirst() {
            if prefixCount == strs[strsIndex].count || strs[strsIndex][prefixStringIndex] != character {
                return String(prefixString[..<prefixStringIndex])
            }
        }
    }

    return prefixString
}
14-s1.swiftview raw
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
//
//  14-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/5.
//

// Longest Common Prefix
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/887/
// https://leetcode.com/problems/longest-common-prefix/

// 最长公共前缀
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnmav1/
// https://leetcode-cn.com/problems/longest-common-prefix/

func longestCommonPrefix(_ strs: [String]) -> String {
    var prefix = ""

    guard let prefixString = strs.first else {
        return prefix
    }

    // 第一个字符串与剩下所有字符串逐一对比前缀，前缀逐渐加一
    for index in prefixString.indices {
        let tempPrefix = prefixString[...index]

        for string in strs.dropFirst() {
            if !string.hasPrefix(tempPrefix) {
                return prefix
            }
        }

        prefix = String(tempPrefix)
    }

    return prefix
}

Linked List

Delete Node in a Linked List

237-e1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//
//  237-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/6.
//

// Delete Node in a Linked List
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/553/
// https://leetcode.com/problems/delete-node-in-a-linked-list/

// 删除链表中的节点
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnarn7/
// https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

// MARK: Swap with Next Node

func deleteNode(_ node: ListNode?) {
    guard let next = node?.next else { return }

    node?.val = next.val
    node?.next = next.next
}

Remove Nth Node From End of List

19-e2.swiftview raw
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
//
//  19-e2.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/7.
//  Updated by nuomi1 on 2021/5/23.
//

// Remove Nth Node From End of List
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/603/
// https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1296/
// https://leetcode.com/problems/remove-nth-node-from-end-of-list/

// 删除链表的倒数第N个节点
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn2925/
// https://leetcode-cn.com/leetbook/read/linked-list/jf1cc/
// https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

// MARK: One pass algorithm

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    var fastNode = head
    var slowNode = head

    for _ in 0 ..< n {
        fastNode = fastNode?.next
    }

    guard fastNode != nil else {
        return head?.next
    }

    while fastNode?.next != nil {
        fastNode = fastNode?.next
        slowNode = slowNode?.next
    }

    slowNode?.next = slowNode?.next?.next
    return head
}
19-s1.swiftview raw
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
//
//  19-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/7.
//  Updated by nuomi1 on 2021/5/23.
//

// Remove Nth Node From End of List
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/603/
// https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1296/
// https://leetcode.com/problems/remove-nth-node-from-end-of-list/

// 删除链表的倒数第N个节点
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn2925/
// https://leetcode-cn.com/leetbook/read/linked-list/jf1cc/
// https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    var fastNode = head
    var slowNode: ListNode?

    var count = n

    while fastNode != nil {
        if count <= 0 {
            slowNode = slowNode == nil ? head : slowNode?.next
        }

        fastNode = fastNode?.next

        count -= 1
    }

    guard slowNode != nil else {
        return head?.next
    }

    slowNode?.next = slowNode?.next?.next
    return head
}

Reverse Linked List

206-e1.swiftview raw
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
//
//  206-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/8.
//  Updated by nuomi1 on 2021/5/24.
//

// Reverse Linked List
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/560/
// https://leetcode.com/explore/learn/card/linked-list/219/classic-problems/1205/
// https://leetcode.com/problems/reverse-linked-list/

// 反转链表
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnhm6/
// https://leetcode-cn.com/leetbook/read/linked-list/f58sg/
// https://leetcode-cn.com/problems/reverse-linked-list/

// MARK: Iterative

func reverseList(_ head: ListNode?) -> ListNode? {
    var newHead: ListNode?
    var currentNode = head

    while currentNode != nil {
        let tempNode = currentNode?.next
        currentNode?.next = newHead
        newHead = currentNode
        currentNode = tempNode
    }

    return newHead
}

Merge Two Sorted Lists

21-c1.swiftview raw
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
//
//  21-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/9.
//  Updated by nuomi1 on 2021/5/29.
//

// Merge Two Sorted Lists
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/771/
// https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1227/
// https://leetcode.com/problems/merge-two-sorted-lists/

// 合并两个有序链表
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnbp2/
// https://leetcode-cn.com/leetbook/read/linked-list/fnzd1/
// https://leetcode-cn.com/problems/merge-two-sorted-lists/

// MARK: 递归

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    guard let list1 = l1, let list2 = l2 else {
        return l1 ?? l2
    }

    let list3: ListNode?

    if list1.val > list2.val {
        list3 = list2
        list3?.next = mergeTwoLists(list1, list2.next)
    } else {
        list3 = list1
        list3?.next = mergeTwoLists(list1.next, list2)
    }

    return list3
}
21-s1.swiftview raw
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
50
51
52
53
54
55
56
//
//  21-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/9.
//  Updated by nuomi1 on 2021/5/29.
//

// Merge Two Sorted Lists
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/771/
// https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1227/
// https://leetcode.com/problems/merge-two-sorted-lists/

// 合并两个有序链表
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnbp2/
// https://leetcode-cn.com/leetbook/read/linked-list/fnzd1/
// https://leetcode-cn.com/problems/merge-two-sorted-lists/

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    guard let list1 = l1, let list2 = l2 else {
        return l1 ?? l2
    }

    var list3: ListNode?

    var node1: ListNode? = list1
    var node2: ListNode? = list2
    var node3: ListNode? = ListNode(0)

    while node1 != nil, node2 != nil {
        if node1!.val > node2!.val {
            node3?.next = node2
            node2 = node2?.next
        } else {
            node3?.next = node1
            node1 = node1?.next
        }

        // 跳过第一个无用结点
        if list3 == nil {
            list3 = node3?.next
        }

        node3 = node3?.next
    }

    if node1 != nil {
        node3?.next = node1
    }

    if node2 != nil {
        node3?.next = node2
    }

    return list3
}

Palindrome Linked List

234-c1.swiftview raw
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
//
//  234-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/10.
//  Updated by nuomi1 on 2021/5/27.
//

// Palindrome Linked List
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/772/
// https://leetcode.com/explore/learn/card/linked-list/219/classic-problems/1209/
// https://leetcode.com/problems/palindrome-linked-list/

// 回文链表
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/
// https://leetcode-cn.com/leetbook/read/linked-list/fov6t/
// https://leetcode-cn.com/problems/palindrome-linked-list/

// MARK: 将值复制到数组中后用双指针法

func isPalindrome(_ head: ListNode?) -> Bool {
    var currentNode = head
    var nodes = [ListNode]()

    while currentNode != nil {
        nodes.append(currentNode!)
        currentNode = currentNode?.next
    }

    var leftIndex = nodes.startIndex
    var rightIndex = nodes.index(before: nodes.endIndex)

    while leftIndex < rightIndex {
        guard nodes[leftIndex].val == nodes[rightIndex].val else {
            return false
        }

        nodes.formIndex(after: &leftIndex)
        nodes.formIndex(before: &rightIndex)
    }

    return true
}

Linked List Cycle

141-e2.swiftview raw
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
//
//  141-e2.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/11.
//  Updated by nuomi1 on 2021/5/20.
//

// Linked List Cycle
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/773/
// https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1212/
// https://leetcode.com/problems/linked-list-cycle/

// 环形链表
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnwzei/
// https://leetcode-cn.com/leetbook/read/linked-list/jbex5/
// https://leetcode-cn.com/problems/linked-list-cycle/

// MARK: Floyd's Cycle Finding Algorithm

func hasCycle(_ head: ListNode?) -> Bool {
    var fastNode = head
    var slowNode = head

    while slowNode != nil, fastNode != nil, fastNode?.next != nil {
        fastNode = fastNode?.next?.next
        slowNode = slowNode?.next

        if fastNode === slowNode {
            return true
        }
    }

    return false
}

Trees

Maximum Depth of Binary Tree

104-c1.swiftview raw
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
//
//  104-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/12.
//

// Maximum Depth of Binary Tree
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/555/
// https://leetcode.com/problems/maximum-depth-of-binary-tree/

// 二叉树的最大深度
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnd69e/
// https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

// MARK: 深度优先搜索

func maxDepth(_ root: TreeNode?) -> Int {
    guard let root = root else {
        return 0
    }

    // 递归获取左右子树的最大深度
    return max(maxDepth(root.left), maxDepth(root.right)) + 1
}

Validate Binary Search Tree

98-e1.swiftview raw
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
//
//  98-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/13.
//

// Validate Binary Search Tree
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/625/
// https://leetcode.com/problems/validate-binary-search-tree/

// 验证二叉搜索树
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn08xg/
// https://leetcode-cn.com/problems/validate-binary-search-tree/

// MARK: Recursive Traversal with Valid Range

func isValidBST(_ root: TreeNode?) -> Bool {
    return isValidBSTHelper(root, nil, nil)
}

private func isValidBSTHelper(_ root: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
    guard let root = root else {
        return true
    }

    if let min = min, root.val <= min {
        return false
    }

    if let max = max, root.val >= max {
        return false
    }

    // 验证左子树时，当前结点值为最大值
    // 验证右子树时，当前结点值为最小值
    return isValidBSTHelper(root.left, min, root.val) && isValidBSTHelper(root.right, root.val, max)
}

Symmetric Tree

101-e1.swiftview raw
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
//
//  101-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/14.
//

// Symmetric Tree
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/627/
// https://leetcode.com/problems/symmetric-tree/

// 对称二叉树
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn7ihv/
// https://leetcode-cn.com/problems/symmetric-tree/

// MARK: Recursive

func isSymmetric(_ root: TreeNode?) -> Bool {
    return isSymmetricHelper(root?.left, root?.right)
}

private func isSymmetricHelper(_ left: TreeNode?, _ right: TreeNode?) -> Bool {
    switch (left, right) {
    case let (.some(lhs), .some(rhs)) where lhs.val == rhs.val: // 左右结点同时存在且值相等
        return isSymmetricHelper(lhs.left, rhs.right) && isSymmetricHelper(rhs.left, lhs.right)
    case (nil, nil): // 左右结点同时不存在
        return true
    default: // 左右结点只存在一个 或 同时存在但值不相等
        return false
    }
}

Binary Tree Level Order Traversal

102-c1.swiftview raw
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
//
//  102-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/15.
//  Updated by nuomi1 on 2021/6/6.
//

// Binary Tree Level Order Traversal
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/628/
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/931/
// https://leetcode.com/problems/binary-tree-level-order-traversal/

// 二叉树的层序遍历
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnldjj/
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefh1i/
// https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

// MARK: 广度优先搜索

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else {
        return []
    }

    var queue = [root]
    var result = [[Int]]()

    while !queue.isEmpty {
        var level = [Int]()
        let count = queue.count

        // 不能使用 queue.indices 因为 queue 被修改
        for _ in 0 ..< count {
            let node = queue.removeFirst()
            level.append(node.val)
            if let left = node.left {
                queue.append(left)
            }
            if let right = node.right {
                queue.append(right)
            }
        }

        result.append(level)
    }

    return result
}
102-s1.swiftview raw
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
//
//  102-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/15.
//  Updated by nuomi1 on 2021/6/6.
//

// Binary Tree Level Order Traversal
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/628/
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/931/
// https://leetcode.com/problems/binary-tree-level-order-traversal/

// 二叉树的层序遍历
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnldjj/
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefh1i/
// https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    var result = [[Int]]()

    levelOrderHelper(root, 0, &result)

    return result
}

private func levelOrderHelper(_ root: TreeNode?, _ depth: Int, _ result: inout [[Int]]) {
    guard let root = root else {
        return
    }

    // 里层数组不存在时插入空数组
    if !result.indices.contains(depth) {
        result.insert([], at: depth)
    }

    result[depth].append(root.val)
    levelOrderHelper(root.left, depth + 1, &result)
    levelOrderHelper(root.right, depth + 1, &result)
}

Convert Sorted Array to Binary Search Tree

108-c1.swiftview raw
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
//
//  108-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/16.
//

// Convert Sorted Array to Binary Search Tree
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/631/
// https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

// 将有序数组转换为二叉搜索树
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xninbt/
// https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

// MARK: 中序遍历

func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
    return sortedArrayToBSTHelper(nums, nums.indices)
}

private func sortedArrayToBSTHelper(_ nums: [Int], _ range: Range<Int>) -> TreeNode? {
    guard range.lowerBound < range.upperBound else {
        return nil
    }

    // 防止溢出
    let middleIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2

    let node = TreeNode(nums[middleIndex])

    // 跳过 middleIndex
    node.left = sortedArrayToBSTHelper(nums, range.lowerBound ..< middleIndex)
    node.right = sortedArrayToBSTHelper(nums, middleIndex + 1 ..< range.upperBound)

    return node
}

Sorting and Searching

Merge Sorted Array

88-c3.swiftview raw
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
//
//  88-c3.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/17.
//  Updated by nuomi1 on 2021/5/5.
//

// Merge Sorted Array
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/96/sorting-and-searching/587/
// https://leetcode.com/explore/learn/card/fun-with-arrays/525/inserting-items-into-an-array/3253/
// https://leetcode.com/problems/merge-sorted-array/

// 合并两个有序数组
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnumcr/
// https://leetcode-cn.com/problems/merge-sorted-array/

// MARK: 逆向双指针

func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
    // nums1 扫描下标
    var indexI = m - 1
    // nums2 扫描下标
    var indexJ = n - 1
    // nums1 赋值下标
    var indexTail = m + n - 1

    while indexI >= nums1.startIndex || indexJ >= nums2.startIndex {
        if indexI < nums1.startIndex {
            nums1[indexTail] = nums2[indexJ]
            nums2.formIndex(before: &indexJ)
        } else if indexJ < nums2.startIndex {
            nums1[indexTail] = nums1[indexI]
            nums1.formIndex(before: &indexI)
        } else if nums1[indexI] > nums2[indexJ] {
            nums1[indexTail] = nums1[indexI]
            nums1.formIndex(before: &indexI)
        } else {
            nums1[indexTail] = nums2[indexJ]
            nums2.formIndex(before: &indexJ)
        }
        nums1.formIndex(before: &indexTail)
    }
}

First Bad Version

278-e2.swiftview raw
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
//
//  278-e2.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/18.
//

// First Bad Version
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/96/sorting-and-searching/774/
// https://leetcode.com/problems/first-bad-version/

// 第一个错误的版本
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnto1s/
// https://leetcode-cn.com/problems/first-bad-version/

// MARK: Binary Search

func firstBadVersion(_ n: Int) -> Int {
    var left = 1
    var right = n

    while left != right {
        let middle = left + (right - left) / 2

        if isBadVersion(middle) {
            right = middle
        } else {
            left = middle + 1
        }
    }

    return left
}

Dynamic Programming

Climbing Stairs

70-e4.swiftview raw
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
//
//  70-e4.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/19.
//

// Climbing Stairs
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/569/
// https://leetcode.com/problems/climbing-stairs/

// 爬楼梯
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn854d/
// https://leetcode-cn.com/problems/climbing-stairs/

// MARK: Fibonacci Number

func climbStairs(_ n: Int) -> Int {
    // 滑动数组
    var first = 0
    var second = 0

    var result = 1

    for _ in 1 ... n {
        first = second
        second = result
        result = first + second
    }

    return result
}

Best Time to Buy and Sell Stock

121-e2.swiftview raw
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
//
//  121-e2.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/20.
//

// Best Time to Buy and Sell Stock
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/572/
// https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

// 买卖股票的最佳时机
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn8fsh/
// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

// MARK: One Pass

func maxProfit(_ prices: [Int]) -> Int {
    var profit = 0

    guard var minBuy = prices.first else {
        return profit
    }

    for price in prices {
        profit = max(profit, price - minBuy)
        minBuy = min(minBuy, price)
    }

    return profit
}

Maximum Subarray

53-c1.swiftview raw
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
//
//  53-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/21.
//

// Maximum Subarray
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/566/
// https://leetcode.com/problems/maximum-subarray/

// 最大子序和
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn3cg3/
// https://leetcode-cn.com/problems/maximum-subarray/

// MARK: 动态规划

func maxSubArray(_ nums: [Int]) -> Int {
    var sum = nums.first!
    var maxSum = nums.first!

    for num in nums.dropFirst() {
        sum = max(sum + num, num)
        maxSum = max(maxSum, sum)
    }

    return maxSum
}

House Robber

198-c1.swiftview raw
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
//
//  198-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/22.
//

// House Robber
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/576/
// https://leetcode.com/problems/house-robber/

// 打家劫舍
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnq4km/
// https://leetcode-cn.com/problems/house-robber/

// MARK: 动态规划

func rob(_ nums: [Int]) -> Int {
    var last = 0
    var now = 0

    for num in nums {
        (last, now) = (now, max(now, last + num))
    }

    return now
}

Design

Shuffle an Array

384-s1.swiftview raw
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
//
//  384-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/23.
//

// Shuffle an Array
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/98/design/670/
// https://leetcode.com/problems/shuffle-an-array/

// 打乱数组
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn6gq1/
// https://leetcode-cn.com/problems/shuffle-an-array/

class Solution {
    let nums: [Int]

    init(_ nums: [Int]) {
        self.nums = nums
    }

    func reset() -> [Int] {
        return nums
    }

    func shuffle() -> [Int] {
        return nums.shuffled()
    }
}
384-s2.swiftview raw
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
//
//  384-s2.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/23.
//

// Shuffle an Array
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/98/design/670/
// https://leetcode.com/problems/shuffle-an-array/

// 打乱数组
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn6gq1/
// https://leetcode-cn.com/problems/shuffle-an-array/

class Solution {
    let nums: [Int]

    init(_ nums: [Int]) {
        self.nums = nums
    }

    func reset() -> [Int] {
        return nums
    }

    // https://yjk94.wordpress.com/2017/03/17/%E6%B4%97%E7%89%8C%E7%9A%84%E6%AD%A3%E7%A1%AE%E5%A7%BF%E5%8A%BF-knuth-shuffle%E7%AE%97%E6%B3%95/
    func shuffle() -> [Int] {
        var copy = nums

        for currentIndex in copy.indices {
            let anotherIndex = Int.random(in: copy.startIndex ... currentIndex)
            copy.swapAt(currentIndex, anotherIndex)
        }

        return copy
    }
}

Min Stack

155-c1.swiftview raw
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
//
//  155-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/24.
//

// Min Stack
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/98/design/562/
// https://leetcode.com/problems/min-stack/

// 最小栈
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnkq37/
// https://leetcode-cn.com/problems/min-stack/

// MARK: 辅助栈

class MinStack {
    var normalStack: [Int]
    var minStack: [Int]

    init() {
        normalStack = []
        minStack = []
    }

    func push(_ x: Int) {
        normalStack.append(x)

        if minStack.last == nil || minStack.last! >= x {
            minStack.append(x)
        }
    }

    func pop() {
        let top = normalStack.removeLast()
        if top == getMin() {
            minStack.removeLast()
        }
    }

    func top() -> Int {
        return normalStack.last!
    }

    func getMin() -> Int {
        return minStack.last!
    }
}

Math

Fizz Buzz

412-e1.swiftview raw
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
//
//  412-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/25.
//

// Fizz Buzz
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/102/math/743/
// https://leetcode.com/problems/fizz-buzz/

// Fizz Buzz
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xngt85/
// https://leetcode-cn.com/problems/fizz-buzz/

// MARK: Naive Approach

func fizzBuzz(_ n: Int) -> [String] {
    var result = [String]()
    result.reserveCapacity(n)

    for index in 1 ... n {
        switch index {
        case _ where index.isMultiple(of: 3) && index.isMultiple(of: 5):
            result.append("FizzBuzz")
        case _ where index.isMultiple(of: 3):
            result.append("Fizz")
        case _ where index.isMultiple(of: 5):
            result.append("Buzz")
        default:
            result.append("\(index)")
        }
    }

    return result
}

Count Primes

204-e1.swiftview raw
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
//
//  204-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/26.
//

// Count Primes
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/102/math/744/
// https://leetcode.com/problems/count-primes/

// 计数质数
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnzlu6/
// https://leetcode-cn.com/problems/count-primes/

// MARK: Sieve of Eratosthenes

func countPrimes(_ n: Int) -> Int {
    var primes = [Bool?](repeating: nil, count: n + 1)
    var count = 0

    for prime in stride(from: 2, to: n, by: 1) where primes[prime] == nil {
        primes[prime] = true
        count += 1
        for composite in stride(from: 2 * prime, through: n, by: prime) {
            primes[composite] = false
        }
    }

    return count
}

Power of Three

326-e3.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//
//  326-e3.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/27.
//

// Power of Three
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/102/math/745/
// https://leetcode.com/problems/power-of-three/

// 3的幂
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnsdi2/
// https://leetcode-cn.com/problems/power-of-three/

// MARK: Mathematics

func isPowerOfThree(_ n: Int) -> Bool {
    let logAns = log10(Double(n)) / log10(3.0)
    return n > 0 && logAns == Double(Int(logAns))
}

Roman to Integer

13-s1.swiftview raw
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
50
//
//  13-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/28.
//

// Roman to Integer
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/102/math/878/
// https://leetcode.com/problems/roman-to-integer/

// 罗马数字转整数
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn4n7c/
// https://leetcode-cn.com/problems/roman-to-integer/

func romanToInt(_ s: String) -> Int {
    let table1: [Substring: Int] = [
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    ]

    let table2: [Substring: Int] = [
        "IV": 4,
        "IX": 9,
        "XL": 40,
        "XC": 90,
        "CD": 400,
        "CM": 900,
    ]

    var string = s
    var result = 0

    while !string.isEmpty {
        if let number = table2[string.prefix(2)] {
            result += number
            string.removeFirst(2)
        } else if let number = table1[string.prefix(1)] {
            result += number
            string.removeFirst(1)
        }
    }

    return result
}

Others

Number of 1 Bits

191-e1.swiftview raw
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
//
//  191-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/29.
//

// Number of 1 Bits
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/565/
// https://leetcode.com/problems/number-of-1-bits/

// 位1的个数
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn1m0i/
// https://leetcode-cn.com/problems/number-of-1-bits/

// MARK: Loop and Flip

func hammingWeight(_ n: Int) -> Int {
    var bits = 0
    var mask = 1

    for _ in 0 ..< Int32.bitWidth {
        if (n & mask) != 0 {
            bits += 1
        }

        mask <<= 1
    }

    return bits
}

Hamming Distance

461-s1.swiftview raw
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
//
//  461-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/30.
//

// Hamming Distance
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/762/
// https://leetcode.com/problems/hamming-distance/

// 汉明距离
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnyode/
// https://leetcode-cn.com/problems/hamming-distance/

func hammingDistance(_ x: Int, _ y: Int) -> Int {
    let z = x ^ y

    var bits = 0
    var mask = 1

    for _ in 0 ..< Int32.bitWidth {
        if (z & mask) != 0 {
            bits += 1
        }

        mask <<= 1
    }

    return bits
}

Reverse Bits

190-e1.swiftview raw
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
//
//  190-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/31.
//

// Reverse Bits
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/648/
// https://leetcode.com/problems/reverse-bits/

// 颠倒二进制位
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnc5vg/
// https://leetcode-cn.com/problems/reverse-bits/

// MARK: Bit by Bit

func reverseBits(_ n: Int) -> Int {
    var n = n
    var result = 0

    for bit in 0 ..< Int32.bitWidth {
        result += (n & 1) << (Int32.bitWidth - 1 - bit)
        n >>= 1
    }

    return result
}

Pascal’s Triangle

118-e1.swiftview raw
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
//
//  118-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/2/1.
//

// Pascal's Triangle
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/601/
// https://leetcode.com/problems/pascals-triangle/

// 杨辉三角
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xncfnv/
// https://leetcode-cn.com/problems/pascals-triangle/

// MARK: Dynamic Programming

func generate(_ numRows: Int) -> [[Int]] {
    var result: [[Int]] = Array(repeating: [], count: numRows)

    for rowIndex in 0 ..< numRows {
        for columnIndex in 0 ..< numRows {
            if columnIndex - rowIndex > 0 {
                continue
            }

            let lhs = result[safe: rowIndex - 1]?[safe: columnIndex - 1] ?? 0
            let rhs = result[safe: rowIndex - 1]?[safe: columnIndex] ?? 0

            result[rowIndex].append(max(lhs + rhs, 1))
        }
    }

    return result
}

extension Array {
    subscript(safe index: Index) -> Element? {
        indices.contains(index) ? self[index] : nil
    }
}

Valid Parentheses

20-e1.swiftview raw
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
//
//  20-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/2/2.
//

// Valid Parentheses
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/721/
// https://leetcode.com/problems/valid-parentheses/

// 有效的括号
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnbcaj/
// https://leetcode-cn.com/problems/valid-parentheses/

// MARK: Stacks

func isValid(_ s: String) -> Bool {
    var stack: [Character] = []

    let lhs: [Character] = ["(", "[", "{"]
    let rhs: [Character] = [")", "]", "}"]

    for character in s {
        if lhs.contains(character) {
            stack.append(character)
            continue
        }

        if rhs.contains(character) {
            switch (stack.last, character) {
            case ("(", ")"), ("[", "]"), ("{", "}"):
                stack.removeLast()
            default:
                return false
            }
        }
    }

    return stack.isEmpty
}

Missing Number

268-e4.swiftview raw
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
//
//  268-e4.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/2/3.
//

// Missing Number
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/722/
// https://leetcode.com/problems/missing-number/

// 缺失数字
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnj4mt/
// https://leetcode-cn.com/problems/missing-number/

// MARK: Gauss' Formula

func missingNumber(_ nums: [Int]) -> Int {
    var count = 0
    var total = 0

    for num in nums {
        count += 1
        total += num
    }

    return (count + 1) * count / 2 - total
}