Swift – 第3页

[swift] LeetCode 438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:

Input:
s: “abab” p: “ab”

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

func findAnagrams(_ s: String, _ p: String) -> [Int] {
    let n = p.count
    var arr = Array(repeating: 0, count: s.count) , i = 0, c: Character, j = 0

    var pArr = Array(repeating: 0, count: 26)
    p.utf8.forEach({ pArr[Int($0-97)] += 1 })
    let pSet = pArr.enumerated().filter({$0.element > 0}).map({ Character(UnicodeScalar($0.offset + 97)!)  })

    while i + n <= s.count {
        let start = s.index(s.startIndex, offsetBy: i)
        let end = s.index(s.startIndex, offsetBy: i + n)
        c = s[start]
        let t = s[start..<end]

        var tArr = Array(repeating: 0, count: 26)
        t.utf8.forEach({ tArr[Int($0-97)] += 1 })

        if tArr == pArr {
            arr[j] = i; j += 1
            while i + n < s.count {
                let c1 = s[s.index(s.startIndex, offsetBy: i + n)]
                if c == c1 {
                    i += 1
                    c = s[s.index(s.startIndex, offsetBy: i)]
                    arr[j] = i; j += 1
                } else if !pSet.contains(c1) {
                    i += n; break
                } else {
                    break
                }
            }
        }
        i += 1
    }

    return Array(arr[0..<j])
}

func findAnagrams(_ s: String, _ p: String) -> [Int] {

let n = p.count

var arr = Array(repeating: 0, count: s.count) , i = 0, c: Character, j = 0

var pArr = Array(repeating: 0, count: 26)

p.utf8.forEach({ pArr[Int($0-97)] += 1 })

let pSet = pArr.enumerated().filter({$0.element > 0}).map({ Character(UnicodeScalar($0.offset + 97)!) })

while i + n <= s.count {

let start = s.index(s.startIndex, offsetBy: i)

let end = s.index(s.startIndex, offsetBy: i + n)

c = s[start]

let t = s[start..<end]

var tArr = Array(repeating: 0, count: 26)

t.utf8.forEach({ tArr[Int($0-97)] += 1 })

if tArr == pArr {

arr[j] = i; j += 1

while i + n < s.count {

let c1 = s[s.index(s.startIndex, offsetBy: i + n)]

if c == c1 {

i += 1

c = s[s.index(s.startIndex, offsetBy: i)]

arr[j] = i; j += 1

} else if !pSet.contains(c1) {

i += n; break

} else {

break

}

i += 1

}

return Array(arr[0..<j])

}

[swift] LeetCode 437. Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1

Return 3. The paths that sum to 8 are:

1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
    return pathSumNote(root, sum).0
}

private func pathSumNote(_ root: TreeNode?, _ sum: Int) -> (Int, [Int]) {
    guard let p = root else { return (0, []) }

    let ls = pathSumNote(p.left, sum)
    let rs = pathSumNote(p.right, sum)
    let arr = (ls.1 + rs.1).map({$0 + p.val}) + [p.val]

    let sum = ls.0 + rs.0 + arr.filter({$0 == sum}).count
    return (sum, arr)
}

func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {

return pathSumNote(root, sum).0

}

private func pathSumNote(_ root: TreeNode?, _ sum: Int) -> (Int, [Int]) {

guard let p = root else { return (0, []) }

let ls = pathSumNote(p.left, sum)

let rs = pathSumNote(p.right, sum)

let arr = (ls.1 + rs.1).map({$0 + p.val}) + [p.val]

let sum = ls.0 + rs.0 + arr.filter({$0 == sum}).count

return (sum, arr)

}

[swift] LeetCode 394. Decode String

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

s = "3[a]2[bc]", return "aaabcbc".

s = "3[a2[c]]", return "accaccacc".

s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

func decodeString(_ s: String) -> String {
    var stack = [String]()
    s.forEach {
        switch $0 {
        case "]":
            var s = "", i = ""
            while let c = stack.popLast(), c != "[" {
                s = "\(c)\(s)"
            }
            while let sl = stack.last, nil != Int("\(sl)"), let c = stack.popLast() {
                i = "\(c)\(i)"
            }
            stack.append(String(repeating: s, count: Int(i)!))
        default:
            stack.append(String($0))
        }
    }

    return stack.joined()
}

func decodeString(_ s: String) -> String {

var stack = [String]()

s.forEach {

switch $0 {

case "]":

var s = "", i = ""

while let c = stack.popLast(), c != "[" {

s = "\(c)\(s)"

}

while let sl = stack.last, nil != Int("\(sl)"), let c = stack.popLast() {

i = "\(c)\(i)"

}

stack.append(String(repeating: s, count: Int(i)!))

default:

stack.append(String($0))

}

return stack.joined()

}

[swift] LeetCode 347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
    var dict = [Int:Int]()
    nums.forEach {
        dict[$0] = (dict[$0] == nil ? 0 : dict[$0]! ) + 1
    }

    return dict.sorted(by:  { $0.value > $1.value } )[0..<k].map({$0.key})
}

func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {

var dict = [Int:Int]()

nums.forEach {

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

}

return dict.sorted(by: { $0.value > $1.value } )[0..<k].map({$0.key})

}

[swift] LeetCode 338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

func countBits(_ num: Int) -> [Int] {
    var arr = Array(repeating: 0, count: num+1), i = 0
    while i <= num {
        arr[i] = i.nonzeroBitCount
        i += 1
    }

    return arr
}

func countBits(_ num: Int) -> [Int] {

var arr = Array(repeating: 0, count: num+1), i = 0

while i <= num {

arr[i] = i.nonzeroBitCount

i += 1

}

return arr

}

[swift] 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2] Output: 2

1	Input: [1,3,4,2,2] Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

1 2	Input: [3,1,3,4,2] Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n²).
There is only one duplicate number in the array, but it could be repeated more than once.

func findDuplicate(_ nums: [Int]) -> Int {
    let sn = nums.sorted()
    var i = 1
    while i < nums.count {
        if sn[i-1] == sn[i] { return sn[i] }
        i += 1
    }

    return -1
}

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

let sn = nums.sorted()

var i = 1

while i < nums.count {

if sn[i-1] == sn[i] { return sn[i] }

i += 1

}

return -1

}