柳婼の blog – 第81页 – 我不管，反正我最萌～

[swift] LeetCode 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

func sortColors(_ nums: inout [Int]) {
    var i0 = 0, i1 = 0, i2 = nums.count-1
    while i1 <= i2 {
        if nums[i1] == 2 {
            nums.swapAt(i1, i2)
            i2 -= 1
        } else if nums[i1] == 0 {
            nums.swapAt(i0, i1)
            i0 += 1; i1 += 1
        } else {
            i1 += 1
        }
    }
}

func sortColors(_ nums: inout [Int]) {

var i0 = 0, i1 = 0, i2 = nums.count-1

while i1 <= i2 {

if nums[i1] == 2 {

nums.swapAt(i1, i2)

i2 -= 1

} else if nums[i1] == 0 {

nums.swapAt(i0, i1)

i0 += 1; i1 += 1

} else {

i1 += 1

}

[swift] LeetCode 70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

func climbStairs(_ n: Int) -> Int {
    if n < 4 { return n }
    var arr = Array(repeating: 1, count: n+1)

    arr[2] = 2; arr[3] = 3
    for i in (4...n) {
        arr[i] = arr[i-1] + arr[i-2]
    }

    return arr[n]
}

func climbStairs(_ n: Int) -> Int {

if n < 4 { return n }

var arr = Array(repeating: 1, count: n+1)

arr[2] = 2; arr[3] = 3

for i in (4...n) {

arr[i] = arr[i-1] + arr[i-2]

}

return arr[n]

}

[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