Code – 第81页

[swift] LeetCode 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

func uniquePaths(_ m: Int, _ n: Int) -> Int {
    pathMatrix = Array(repeating: Array(repeating: 0, count: n+1), count: m+1)
    return pathMatrix(m, n)
}

private var pathMatrix: [[Int]]!
private func pathMatrix(_ m: Int, _ n: Int) -> Int {
    if m <= 0 || n <= 0 { return 0 }
    if m < 2 || n < 2 { pathMatrix[m][n] = 1; return 1 }

    if pathMatrix[m-1][n] == 0 {
        pathMatrix[m-1][n] = pathMatrix(m-1, n)
    }
    if pathMatrix[m][n-1] == 0 {
        pathMatrix[m][n-1] = pathMatrix(m, n-1)
    }
    return pathMatrix[m-1][n] + pathMatrix[m][n-1]
}

func uniquePaths(_ m: Int, _ n: Int) -> Int {

pathMatrix = Array(repeating: Array(repeating: 0, count: n+1), count: m+1)

return pathMatrix(m, n)

}

private var pathMatrix: [[Int]]!

private func pathMatrix(_ m: Int, _ n: Int) -> Int {

if m <= 0 || n <= 0 { return 0 }

if m < 2 || n < 2 { pathMatrix[m][n] = 1; return 1 }

if pathMatrix[m-1][n] == 0 {

pathMatrix[m-1][n] = pathMatrix(m-1, n)

}

if pathMatrix[m][n-1] == 0 {

pathMatrix[m][n-1] = pathMatrix(m, n-1)

}

return pathMatrix[m-1][n] + pathMatrix[m][n-1]

}

[swift] LeetCode 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
click to show more practice.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

func maxSubArray(_ nums: [Int]) -> Int {
    if nums.isEmpty { return 0 }

    var gMax = nums[0], lMax = nums[0]
    for i in 1..<nums.count {
        lMax = nums[i] + max(lMax, 0)
        gMax = max(gMax, lMax)
    }

    return gMax
}

func maxSubArray(_ nums: [Int]) -> Int {

if nums.isEmpty { return 0 }

var gMax = nums[0], lMax = nums[0]

for i in 1..<nums.count {

lMax = nums[i] + max(lMax, 0)

gMax = max(gMax, lMax)

}

return gMax

}

[swift] LeetCode 49. 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 inputs will be in lowercase.
The order of your output does not matter.

func groupAnagrams(_ strs: [String]) -> [[String]] {
    var dict = [String: [String]]()
    strs.forEach {
        let s = String($0.sorted())
        dict[s] = (dict[s] == nil) ? [$0] : dict[s]! + [$0]
    }
    return dict.map({$0.value})
}

func groupAnagrams(_ strs: [String]) -> [[String]] {

var dict = [String: [String]]()

strs.forEach {

let s = String($0.sorted())

dict[s] = (dict[s] == nil) ? [$0] : dict[s]! + [$0]

}

return dict.map({$0.value})

}

[swift] LeetCode 35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

return nums.map({$0 - target}).filter({$0 < 0}).count

1	return nums.map({$0 - target}).filter({$0 < 0}).count

[swift] LeetCode 23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [ 1->4->5, 1->3->4, 2->6 ]
Output: 1->1->2->3->4->4->5->6

func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
    var i = 0, j = 0, fl = lists.compactMap({$0}), n = fl.count, p: ListNode?
    if n < 1 { return nil }

    var arr = Array(repeating: 0, count: 256*256)
    while i < n {
        p = fl[i]; i += 1
        while let p1 = p {
            arr[j] = p1.val
            p = p1.next; j += 1
            if p == nil, i < n {
                p1.next = fl[i]
            }
        }
    }

    arr = Array(arr[..<j]).sorted()

    i = 0; p = fl[0]
    while let q = p, i < j {
        q.val = arr[i]
        p = q.next; i += 1
    }

    return fl[0]
}

func mergeKLists(_ lists: [ListNode?]) -> ListNode? {

var i = 0, j = 0, fl = lists.compactMap({$0}), n = fl.count, p: ListNode?

if n < 1 { return nil }

var arr = Array(repeating: 0, count: 256*256)

while i < n {

p = fl[i]; i += 1

while let p1 = p {

arr[j] = p1.val

p = p1.next; j += 1

if p == nil, i < n {

p1.next = fl[i]

}

arr = Array(arr[..<j]).sorted()

i = 0; p = fl[0]

while let q = p, i < j {

q.val = arr[i]

p = q.next; i += 1

}

return fl[0]

}

[swift] LeetCode 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    var arr = [Int](), p1 = l1, p2 = l2, r = l1

    while let q1 = p1, let q2 = p2 {
        if q1.val < q2.val {
            arr.append(q1.val)
            p1 = q1.next
        } else {
            arr.append(q2.val)
            p2 = q2.next
        }
    }
    while let q1 = p1 {
        arr.append(q1.val)
        p1 = q1.next
        if p1 == nil {
            q1.next = l2
            r = l1
        }
    }
    while let q2 = p2 {
        arr.append(q2.val)
        p2 = q2.next
        if p2 == nil {
            q2.next = l1
            r = l2
        }
    }

    p1 = r
    arr.forEach {
        p1?.val = $0
        p1 = p1?.next
    }

    return r
}

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {

var arr = [Int](), p1 = l1, p2 = l2, r = l1

while let q1 = p1, let q2 = p2 {

if q1.val < q2.val {

arr.append(q1.val)

p1 = q1.next

} else {

arr.append(q2.val)

p2 = q2.next

}

while let q1 = p1 {

arr.append(q1.val)

p1 = q1.next

if p1 == nil {

q1.next = l2

r = l1

}

while let q2 = p2 {

arr.append(q2.val)

p2 = q2.next

if p2 == nil {

q2.next = l1

r = l2

}

p1 = r

arr.forEach {

p1?.val = $0

p1 = p1?.next

}

return r

}