136. Single Number

异或

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var result = 0;
        for i in 0..<nums.count {
            result ^= nums[i]
        }
        return result
    }
}

集合

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var result = Set<Int>()
        for item in nums {
            if (result.contains(item)) {
                result.remove(item)
            } else {
                result.insert(item)
            }
        }
        return result.popFirst()!
    }
}

字典

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var dict: [Int: Int] = [:]
        for num in nums {
            dict[num] = (dict[num] ?? 0) + 1
        }
        for num in dict.keys {
            if dict[num] == 1 {
                return num
            }
        }
        return 0
    }
}

226. Invert Binary Tree

递归

class Solution {
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        if root == nil {
            return nil
        }
        let left = invertTree(root?.left)
        let right = invertTree(root?.right)
        root!.left = right
        root!.right = left
        return root
    }
}

非递归(队列)

func invertTree_queue(_ root: TreeNode?) -> TreeNode? {
    guard let root = root else {
        return nil
    }
    var queue = [TreeNode]()
    queue.append(root)
    while !queue.isEmpty {
        let node = queue.removeFirst()
        swap(&node.left, &node.right)
        if let leftNode = node.left {
            queue.append(leftNode)
        }
        if let rightNode = node.right {
            queue.append(rightNode)
        }
    }
    return root
}

非递归(栈)

func invertTree_stack(_ root: TreeNode?) -> TreeNode? {
    guard let root = root else {
        return nil
    }
    
    var stack = [TreeNode]()
    stack.append(root)
    while !stack.isEmpty {
        let node = stack.removeLast()
        swap(&node.left, &node.right)
        if let leftNode = node.left {
            stack.append(leftNode)
        }
        if let rightNode = node.right {
            stack.append(rightNode)
        }
    }
    return root
}

283. Move Zeros

class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        let count = nums.count
        nums = nums.filter{$0 != 0}
        for _ in 0..<(count-nums.count) {nums.append(0)}
    }
}

448. Find All Numbers Disappeared in an Array

The basic idea is that we iterate through the input array and mark elements as negative using nums[nums[I] -1] = -nums[nums[I]-1]. In this way all the numbers that we have seen will be marked as negative. In the second iteration, if a value is not marked as negative, it implies we have never seen that index before, so just add it to the return list.

class Solution {
    func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
        var nums_copy = nums
        var result = [Int]()
        for i in 0..<nums_copy.count {
            let val = abs(nums_copy[i]) - 1
            if (nums_copy[val] > 0) {
                nums_copy[val] = -nums_copy[val]
            }
        }

        for i in 0..<nums_copy.count {
            if (nums_copy[i] > 0) {
                result.append(i+1)
            }
        }
        return result
    }
}

169. Majority Element

排序

排序后处于中间位置的一定是符合条件的

class Solution {
    func majorityElement(_ nums: [Int]) -> Int {
        var nums = nums
        nums.sort { $0 < $1 }
        return nums[nums.count / 2]
    }
}

Hash Map

class Solution {
    func majorityElement(_ nums: [Int]) -> Int {
        var temp: Dictionary<Int, Int> = [:]
        for i in 0..<nums.count {
            if (temp[nums[i]] == nil) {
                temp[nums[i]] = 1
            } else {
                temp[nums[i]] = temp[nums[i]]! + 1
            }
        }
        var major = nums[0]
        var count = 0
        for (key, value) in temp {
            if (value > count) {
                count = value
                major = key
            }
        }
        return major
    }
}

206. Reverse Linked List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        if (head == nil || head?.next == nil) {
            return head
        }
        var p = head
        var q = head?.next
        var r: ListNode?
        head?.next = nil
        while((q) != nil) {
            r = q?.next
            q?.next = p
            p = q
            q = r
        }
        return p
    }
}

538. Convert BST to Greater Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    var sum = 0
    func convertBST(_ root: TreeNode?) -> TreeNode? {
        guard let r = root else {
            return nil
        }
        convertBST(r.right)
        sum += r.val
        r.val = sum
        convertBST(r.left)
        return r
    }
}

543. Diameter of Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    var ans = 1
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
        ans = 1
        depth(root)
        return ans - 1
    }
    
    func depth(_ root: TreeNode?) -> Int {
        if (root == nil) { return 0 }
        var left = depth(root?.left)
        var right = depth(root?.right)
        ans = max(ans, left + right + 1)
        return max(left, right) + 1
    }
}

暴力

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var max = 0
        for i in 0..<prices.count {
            for j in i+1..<prices.count {
                if (prices[j] - prices[i] > max) {
                    max = prices[j] - prices[i]
                }
            }
        }
        return max
    }
}

One Pass

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var minPrice = Int.max
        var maxProfit = 0
        for i in 0..<prices.count {
            if (prices[i] < minPrice) {
                minPrice = prices[i]
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice
            }
        }
        return maxProfit
    }
}

21. Merge Two Sorted Lists

递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var result: ListNode? = nil
        if (l1 == nil) { return l2 }
        if (l2 == nil) { return l1 }

        if (l1!.val <= l2!.val) {
            result = l1
            result?.next = mergeTwoLists(l1?.next, l2)
        } else {
            result = l2
            result?.next = mergeTwoLists(l1, l2?.next)
        }
        return result
    }
}

非递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var l1 = l1, l2 = l2
        let head = ListNode(0)
        var current = head
        while let val1 = l1?.val, let val2 = l2?.val {
            if val1 > val2 {
                current.next = l2
                l2 = l2?.next
            } else {
                current.next = l1
                l1 = l1?.next
            }
            current = current.next!
        }
        if l1 == nil {
            current.next = l2
        } else {
            current.next = l1
        }
        return head.next
    }
}

70. Climbing Stairs

class Solution {
    func climbStairs(_ n: Int) -> Int {
        var memo = [Int: Int]()
        return climb_stairs(n, &memo)
    }

    func climb_stairs(_ n: Int, _ memo: inout [Int: Int]) -> Int {
        if n <= 1 { return 1 }
        if memo[n] != nil { return memo[n]! }
        memo[n] = climb_stairs(n-1, &memo) + climb_stairs(n-2, &memo)
        return memo[n]!
    }
}

53. Maximum Subarray

DP

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        guard nums.count > 1 else { return nums.first ?? 0 }

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

        return theMax
    }
}

101. Symmetric Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        guard let root = root else {
            return true
        }
        return isMirror(root, root)
    }

    func isMirror(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil { return true }
        if let q = q, let p = p {
            return q.val == p.val && isMirror(q.left, p.right) && isMirror(q.right, p.left)
        }
        return false
    }
}

437. Path Sum III

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
        guard let root = root else {
            return 0
        }
        return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)
    }

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

        var result = 0
        if sum == root.val {
            result += 1
        }
        result += findPath(root.left, sum - root.val)
        result += findPath(root.right, sum - root.val)
        return result
    }
}

572. Subtree of Another Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func isSubtree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
        if s == nil || t == nil {
            return false
        }
        if s?.val == t?.val {
            if isSametree(s, t) {
                return true
            }
        }
        return isSubtree(s?.left, t) || isSubtree(s?.right, t)
    }

    func isSametree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
        if s == nil || t == nil { return s == t }
        if s?.val != t?.val {
            return false
        }
        return isSametree(s?.left, t?.left) && isSametree(s?.right, t?.right)
    }

}

extension TreeNode: Equatable {
    public static func == (lhs: TreeNode, rhs: TreeNode) -> Bool {
        if (lhs == nil && rhs == nil) { return true }
        else { return false }
    }
}

198. House Robber

递归

超时

class Solution {
    func rob(_ nums: [Int]) -> Int {
        return robi(nums, nums.count - 1)
    }

    func robi(_ nums: [Int], _ i: Int) -> Int {
        if (i < 0) {
            return 0
        }
        return max(robi(nums, i - 2) + nums[i], robi(nums, i - 1))
    }
}

递归 + 记忆

faster than 100%

class Solution {
    var memo = [Int]()

    func rob(_ nums: [Int]) -> Int {
        memo = Array<Int>(repeating: -1, count: nums.count + 1)
        return robi(nums, nums.count - 1)
    }

    func robi(_ nums: [Int], _ i: Int) -> Int {
        if (i < 0) {
            return 0
        }
        if (memo[i] >= 0) {
            return memo[i]
        }
        let result = max(robi(nums, i - 2) + nums[i], robi(nums, i - 1))
        memo[i] = result
        return result
    }
}

20. Valid Parentheses

class Solution {
    func isValid(_ s: String) -> Bool {
        if s.characters.count == 0 {
            return true
        }

        let characters = Array(s.characters)
        var stack = [Character]()

        for character in characters {
            if character == "[" || character == "(" || character == "{" {
                stack.append(character)
            } else {
                if character == "]" && stack.last == "[" || character == ")" && stack.last == "(" || character == "}" && stack.last == "{" {
                    stack.removeLast()
                } else {
                    return false
                }
            }
        }
        return stack.isEmpty
    }
}

141. Linked List Cycle

快慢指针

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

155. Min Stack

class MinStack {

    /** initialize your data structure here. */
    var stack: [Int]
    var minStack: [Int]
    
    init() {
        stack = []
        minStack = []
    }
    
    func push(_ x: Int) {
        stack.append(x)
        if minStack.count == 0 {
            minStack.append(x)
        } else {
            minStack.append(min(x, minStack.last!))
        }
    }
    
    func pop() {
        stack.removeLast()
        minStack.removeLast()
    }
    
    func top() -> Int {
        return stack.last!
    }
    
    func getMin() -> Int {
        return minStack.last!
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * let obj = MinStack()
 * obj.push(x)
 * obj.pop()
 * let ret_3: Int = obj.top()
 * let ret_4: Int = obj.getMin()
 */

234. Palindrome Linked List

把后半部分翻转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        if head == nil {
            return true
        }

        var fast = head, slow = head
        while fast != nil {
            fast = fast?.next?.next
            slow = slow?.next
        }

        var pre: ListNode?
        var cur = slow
        while cur != nil {
            let next = cur?.next
            cur?.next = pre
            pre = cur
            cur = next
        }

        var p = head
        while p != nil && pre != nil {
            if p!.val != pre!.val {
                return false
            }
            p = p?.next
            pre = pre?.next
        }
        return true
    }
}

160. Intersection of Two Linked Lists

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}

581. Shortest Unsorted Continuous Subarray

排序后与原数组不同的部分则为需要排序的子数组

class Solution {
    func findUnsortedSubarray(_ nums: [Int]) -> Int {
        let n = nums.count
        let temp = nums.sorted()
        var start = 0
        var end = n - 1

        while start < n && nums[start] == temp[start] {
            start += 1
        }

        while end > start && nums[end] == temp[end] {
            end -= 1
        }
        return end - start + 1
    }
}