Swift data structure and algorithm

An array of 1.

Array is the most basic data structure. In Swift, the previous practice of dividing NSMutableArray and NSArray was unified into a unique data structure Array.

// Declare immutable groups
let nums = [1.2.3]
let strs:[String] = ["1"."2"."3"];


// Declare a mutable array
var nums = [Int](repeating: 0, count: 5)
nums.append(4)
nums.append(contentsOf: [1.2.3])
// Sort the array in ascending order
nums.sort() 

let anotherNums = Array(nums[0..<nums.count - 1])
Copy the code

Implement stacks with arrays

class Stack<Element> {
    var stack: [Element]
    var isEmpty:Bool { return stack.isEmpty}
    var peek:Element? {return stack.last}
    
    init(a){
        stack = [Element]()
    }
    
    func push(object:Element) {
        stack.append(object)
    }
    
    func pop(a)->Element? {
        
        if(stack.isEmpty) {
            return nil
        } else {
            return stack.removeLast()
        }
    }
    
}
Copy the code

2. Dictionaries and collections

A collection of

let primeNums: Set = [3.5.7.11.13]
let oddNums: Set = [1.3.5.7.9]

// Intersection difference set
let primeAddOddNums = primeNums.intersection(oddNums)
let primeOrOddNums = primeNums.union(oddNums)
let oddNotPrimNums = oddNums.subtracting(oddNums)
Copy the code

Given an integer array and an object value, determine whether the sum of two numbers in the array equals the object value

func twoSum1(nums: [Int]._ target: Int) -> Bool {
    var set = Set<Int> ()for num in nums {
        if set.contains(target - num) {
            return true
        }
        set.insert(num)
    } 
    return false
}
Copy the code

Given an integer array with only two numbers whose sum equals the target value, find the ordinal number in the array

func twoSum2(nums: [Int]._ target: Int)- > [Int] {
    var dict = Dictionary<Int.Int> ()for (num, i) in nums.enumerated() {
        if let lastIndex = dict[target-num] {
            return [lastIndex,i]
        }
        dict[num] = i;
    }
    fatalError("No valid output!")}Copy the code

3. The string

Strings are extremely common in algorithms, and in Swift, unlike other languages, strings are a value type, not a reference type.

var str = "3"
let num = Int(str)
let number = 3
let string = String(describing: num)

// String length
let len = str.count

// Access a single character
//let char = str[str.index(str.startIndex, offsetBy: n)]
// Modify the string
//str.remove(at: n)
str.append("c")
str + = "hello world"

// Check whether the string consists of numbers
func isStrNum(str:String) ->Bool {
    return Int(str) ! = nil;
}
// Place strings in alphabetical order regardless of case
func sortStr(str:String) -> String {
    return String(str.sorted())
}
Copy the code

Give a string and ask to reverse it in word order.

func reverseString(_ s: inout [Character]) {
    if s.count = = 0 {
        return
    }
    s = s.reversed()
}

func reverseString1(_ s: inout [Character]) {
    if s.count = = 0 {
        return
    }
    var x = 0
    var y = s.count - 1
    while(x < y){
        s.swapAt(x, y)
        x + = 1
        y - = 1}}Copy the code

3. The linked list

Common data structures will not be repeated.

// List nodes
class ListNode {
    var val:Int
    var next:ListNode?
    init(_ val:Int) {
        self.val = val
        self.next = nil}}class List {
    var head:ListNode?
    var tail:ListNode?
    / / stern interpolation
    func appendToTail(_ val:Int) {
        if tail = = nil {
            tail = ListNode(val)
        } else {
            tail!.next = ListNode(val)
            tail = tail!.next; }}/ / head interpolation
    func appendToHead(_ val:Int) {
        if head = = nil {
            head = ListNode(val)
        } else {
            let temp = ListNode(val)
            temp.next = head
            head =temp; }}}Copy the code

Given a linked list and a value x, it is required to put all the values in the list less than x on the left and all the values greater than x on the right, and the original list of nodes in the same order.

For example 1->5->3->2->4->2 Given 2 returns 1->2->2->5->3->4

func partition(_ head:ListNode? ._ x:Int) ->ListNode? {
    // import Dummy node
    let preDummy = ListNode(1),postDummy = ListNode(0)
    var prev = preDummy, post = postDummy
    
    var node = head
    while node ! = nil {
        if (node!.val < x) {
            prev.next = node;
            prev = node!;
        }else {
            post.next = node;
            post = node!;
        }
        node = node!.next;
    }
    // Prevent ring formation
    post.next = nil
    // select * from left to right
    prev.next = postDummy.next;
    return preDummy.next
}
Copy the code

Fast and slow Pointers, how to detect if a linked list has a ring?

func hasCycle(_ head:ListNode?).-> Bool {
    var slow = head,fast = head
    while fast ! = nil && fast?.next ! = nil {
        fast = fast!.next!.next;
        slow = slow!.next
        if slow = = = fast {
            return true}}return false
}
Copy the code

3. Delete the list from the first k node example: 1 – > 2 – > 3 – > 4 – > 5, n = 2, return 1 – > 2 – > 4 – > 5: Fast and slow but the speed is the same, the first pointer starts n nodes behind the second pointer, and then they move at the same time, and when the second pointer moves to the end node, the next node of the first node is the node we want to delete

func removeNthFromEnd(_ head: ListNode? ._ n: Int)-> ListNode? {
    
    // Secure processing
    guard let head = head else {
        return nil
    }
    
    let dummy = ListNode(0)
    dummy.next = head
    var pre:ListNode? = dummy
    var post:ListNode? = dummy
    
    
    // 1. Take N steps ahead
    for _ in 0..<n {
        if post = = nil {
            break
        }
        post = post!.next
    }
    
    // 2. Move the speed pointer simultaneously
    while post ! = nil && post?.next ! = nil {
        post = post!.next
        pre = pre!.next
    }
    
    / / post = = nil | | or the last node
    // Delete the node
    pre!.next = pre!.next!.next
    return dummy.next
}
Copy the code

4. Stacks and queues

Stack is a very important data structure, for example, for some recursive algorithms, also through the stack to complete, through the stack, can also simulate the recursive call process. However, there are no built-in stacks and queues in Swift, and many extension libraries use Generic Types to implement stacks and queues.

In writing in both the interview and App, focusing on the stack of several basic operations: push, pop, isEmpty, peek, size.

protocol Stack {
    // The type of the element held
    associatedtype Element
    
    // Whether it is empty
    var isEmpty:Bool {get}
    var size:Int {get}
    var peek:Element? {get}
    / / into the stack
    mutating func push(_ newElement:Element)
    
    / / out of the stack
    mutating func pop(a) -> Element?
}


struct IntegerStack:Stack {
    typealias Element = Int

    var isEmpty: Bool { return stack.isEmpty }
    
    var size: Int { return stack.count }
    
    var peek: Int? { return stack.last}
    
    private var stack = [Element] ()mutating func push(_ newElement: Int) {
        stack.append(newElement)
    }
    
    mutating func pop(a) -> Int? {
        return stack.popLast()
    }
}
Copy the code

Focuses on the queue of several basic operations: the enqueue and dequeue, isEmpty, peek, size.

protocol Queue {
    // Holds the element type
    associatedtype Element
    
    // Whether it is empty
    var isEmpty:Bool {get}
    var size:Int {get}
    // Team leader element
    var peek:Element? {get}
    / / team
    mutating func enqueue(_ newElement:Element)
    / / out of the team
    mutating func dequeue(a) -> Element?
}

struct IntegerQueue: Queue {
    typealias Element = Int

    var isEmpty: Bool { return left.isEmpty && right.isEmpty }
    
    var size: Int { return left.count + right.count }
     
    var peek: Int? { return left.isEmpty ? right.first : left.last}
    
    private var left = [Element] ()private var right = [Element] ()mutating func enqueue(_ newElement: Int) {
        right.append(newElement)
    }
    
    mutating func dequeue(a) -> Int? {
        if left.isEmpty {
            left = right.reversed()
            right.removeAll()
        }
        return left.popLast()
    }
}
Copy the code

Give the absolute path to a file and ask it to be simplified. For example, the path is “/home” and simplified to “/home”.

Path is “/ a /. / / b.. /.. /c = /c; /c = /c; Equivalent to the POP operation, other cases are not processed

func simplifyPath(path:String) -> String {
    var pathStack = [String] ()let paths = path.components(separatedBy: "/")
    for path in paths {
        guard path ! = "." else {
            continue
        }
        if path = = ".." {
            if (pathStack.count > 0) {
                pathStack.removeLast()
            }
        } else if path ! = "" {
            pathStack.append(path)
        }
    }
    // Convert the contents of the stack to a new optimized path
    let res = pathStack.reduce("") { total, dir in "\(total)\(dir)"}
    
    // Note that the empty path result is "/"
    return res.isEmpty ? "/" : res
}
Copy the code

5. Binary tree

Node definition

public class TreeNode {
    var left:TreeNode?
    var right:TreeNode?
    var val: Int
    init(_ val:Int) {
        self.val = val
    }
}
Copy the code

Recursively computes the maximum depth of the tree

func maxDepth(root:TreeNode?). -> Int {
    guard let root = root else {
        return 0
    }
    return 1+max(maxDepth(root: root.left),maxDepth(root: root.right))
}
Copy the code

Stack to implement binary tree forward traversal

func preorderTraversal(root: TreeNode?).- > [Int] {
    
    var res = [Int] ()var stack = [TreeNode] ()var node = root
    while !stack.isEmpty || node ! = nil {
        if node ! = nil {
            // Go through yourself first
            res.append(node!.val)
            stack.append(node!)
            // node traverses the left subtree node
            node = node!.left
        } else {
            node = stack.removeLast().right
        }
    }
    return res
}
Copy the code

The queue realizes binary tree sequence traversal

func levelOrder(root: TreeNode?).- > [[Int]] {
    var res = [[Int]] ()var queue = [TreeNode] ()if let root = root {
        queue.append(root)
    }
    
    while queue.count > 0 {
        let size = queue.count
        var level = [Int] ()for _ in 0..<size {
            / / out of the team
            let node = queue.removeFirst()
            level.append(node.val)
             / / team
            if let left = node.left {
                queue.append(left)
            }
            if let right = node.right {
                queue.append(right)
            }
        }
        res.append(level)
    }
    return res
}
Copy the code

algorithm

1. Sort and search

Merge sort

func mergeSort(_ array: [Int])- > [Int] {
    var helper = [Int](repeating: 0, count: array.count),array = array
    mergeSort(&array, &helper, 0, array.count-1)
    return array
    
}

func mergeSort(_ array: inout [Int]._ helper : inout [Int]._ low: Int ,_ high:Int) {
    guard low < high else {
        return
    }
    let middle = (high - low)/2 + low
    mergeSort(&array, &helper, low, middle)
    mergeSort(&array, &helper, middle+1, high)
    

}


func merge(_ array: inout [Int]._ helper : inout [Int]._ low: Int , _ middle:Int._ high:Int) {
    // copy both halves int a helper array
    for i in low . high {
        helper[i] = array[i]
    }
    
    var helperLeft = low, helperRight = middle+1,current = low
    //iterate through helper array and copy the right one to orignial array
    while helperLeft< =middle && helperRight < = high {
        if helper[helperLeft] < = helper[helperRight] {
            array[current] = helper[helperLeft];
            helperLeft + = 1
        } else {
            array[current] = helper[helperRight];
            helperRight + = 1
        }
        current + = 1
    }
    // handle the rest
    guard middle - helperLeft > = 0 else {
        return
    }
    for i in 0 . middle - helperLeft {
        array[current+i] = helper[helperLeft + i]
    }
    
}
Copy the code

Quick sort

func quickSort(_ array: [Int])- > [Int] {
    guard array.count > 1 else {
        return array
    }
    let priot = array[array.count/2]
    let left = array.filter{ $0 < priot }
    let middle  = array.filter{ $0 = = priot }
    let right  = array.filter{ $0 > priot }
    return quickSort(left) + middle + quickSort(right)
}

Copy the code

An array of 1.

2. Dictionaries and collections

3. The string

3. The linked list

4. Stacks and queues

5. Binary tree

algorithm

1. Sort and search

Related Posts

OC – Underlying dynamic method resolution

This article takes you through WWDC21 core (new) technology points

WWDC 2018: Metal Development Guide for OpenGL developers