Code – 第76页

[swift] LeetCode 538. Convert BST to Greater Tree

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
5
/ \
2 13

Output: The root of a Greater Tree like this:
18
/ \
20 13

private var sum = 0
func convertBST(_ root: TreeNode?) -> TreeNode? {
    if let root = root {
        convertBST(root.right)
        sum += root.val
        root.val = sum
        convertBST(root.left)
    }

    return root
}

private var sum = 0

func convertBST(_ root: TreeNode?) -> TreeNode? {

if let root = root {

convertBST(root.right)

sum += root.val

root.val = sum

convertBST(root.left)

}

return root

}

[swift] LeetCode 461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 2^31.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

The above arrows point to positions where the corresponding bits are different.

return (x ^ y).nonzeroBitCount

1	return (x ^ y).nonzeroBitCount

[swift] LeetCode 448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

return nums.count > 1 ? Array(Set(1...nums.count).subtracting(nums)) : []

1	return nums.count > 1 ? Array(Set(1...nums.count).subtracting(nums)) : []

[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()

}