iOS data structure and algorithm

1, Data structure

• 1. Set structure: an unordered and non repetitive element structure, which can be regarded as a special array (no order, and the data elements are not repeated)

• 2. Linear structure:
  a. There must be a unique first element in the set;
  b. There must be a unique last element in the set
  c. Except for the last element, all other elements have unique successors
  d. All elements except the first have unique precursors

• 3. Tree structure: the data structure with one to many tree relationship among elements is an important nonlinear data structure
  

• 4. Graph structure: there is no limit on the number of precursors and successors of nodes. Structures like this are called graph data structures
  

2, Storage of data structure

• 1. Sequential storage structure: continuous memory addresses, such as arrays

• 2. Chain storage structure
  a. Unidirectional linked list
  

b. Bidirectional linked list

c. Circular linked list

• 3. Binary tree / balanced binary tree (five forms of binary tree: a. no node, empty binary tree; b. only root node; c. only left subtree; d. only right subtree; e. left and right subtrees)
  

2, Algorithm example

• 1. Do not use intermediate variables to exchange the values of two variables

void exchangeWithPlus(int a,int b){
        a = a + b;
        b = a - b;
        a = a - b;
}
void exchangeWithXor(int a,int b){
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
}

• 2. Find the greatest common divisor
  a. Direct traversal method

//swift language
func normalMaxCommonDivisor(a:Int,b:Int) -> Int{
        let r = a > b ? b : a
        var result = 1
        for i in 2..<r+1{
            if a % i == 0 && b % i == 0{
                result = i
            }
        }
        return result
}

b. Rolling division method: (if a=b*r+q, gcd(a,b)=gcd(b,q), you can find and verify by yourself)

//swift language
func tossAndTurnDivisor(a:Int,b:Int) -> Int{
        var ta = a,tb = b
        var resullt = tb
        while ta % tb != 0 {
            resullt = ta % tb
            ta = tb
            tb = resullt
        }
        return resullt
}

c. Select Sorting: the most value appears at the beginning (the first pass: find the minimum / maximum value in N numbers and exchange with the first one; the second pass: find the minimum / maximum value in the remaining n-1 numbers and exchange with the second number; and so on)

//swift
func selectSort(arr:[Int]) -> [Int]{
        var tArr = arr
        let count = tArr.count
        for i in 0..<count{
            for j in i..<count{
                if tArr[i] > tArr[j]{
                    let temp = tArr[i]
                    tArr[i] = tArr[j]
                    tArr[j] = temp
                }
            }
        }
        return tArr
}

d. Bubble sorting: two adjacent elements are compared in pairs. After the comparison, the maximum value appears at the end (the first time: compare the two adjacent numbers in turn, and constantly exchange (before the decimal number and after the large number) one by one. The maximum value finally appears at the position of the nth element; The second trip: compare the two adjacent numbers in turn, constantly exchange (before decimal, after large) and advance one by one, and the maximum value finally appears at the position of the n-1 element; (and so on)

//swift
func bubbleSort(arr:[Int]) -> [Int]{
        var tArr = arr
        let count = tArr.count
        for i in 0..<count{
            for j in 1..<count-i{
                if tArr[j-1] > tArr[j]{
                    let temp = tArr[j-1]
                    tArr[j-1] = tArr[j]
                    tArr[j] = temp
                }
            }
        }
        return tArr
}

e. Quick sort: pick out an element from the sequence, which is called "pivot"; Reorder the sequence. All elements smaller than the benchmark value are placed in front of the benchmark, and all elements larger than the benchmark value are placed behind the benchmark (the same number can be on either side). After the partition exits, the benchmark is in the middle of the sequence. This is called a partition operation; Recursively sort the subsequence less than the reference value element and the subsequence greater than the reference value element;

//swift
//Usage example: quickSort(arr: arr, start: 0, end: arr.count-1)
func quickSort(arr:[Int],start:Int,end:Int) -> [Int]{
        if start >= end{
            return arr
        }
        var tArr = arr
        var base = start
        var offsetI=start,offsetJ=end
        while offsetI<offsetJ {
            while offsetJ >= offsetI && tArr[offsetJ] >= tArr[base] {
                offsetJ = offsetJ - 1
            }
            if offsetJ>=offsetI{
                let temp = tArr[offsetJ]
                tArr[offsetJ] = tArr[base]
                tArr[base] = temp
                base = offsetJ
                offsetJ = offsetJ - 1
            }
            while offsetJ >= offsetI && tArr[offsetI] <= tArr[base] {
                offsetI = offsetI + 1
            }
            if offsetI <= offsetJ{
                let temp = tArr[base]
                tArr[base] = tArr[offsetI]
                tArr[offsetI] = temp
                base = offsetI
                offsetI = offsetI + 1
            }
        }
        let ttarr = quickSort(arr: tArr, start: start, end: base-1)
        let rarr = quickSort(arr: ttarr, start: base+1, end: end)
        return rarr
}

f. Split search (split search): split search: optimize the search time (without traversing all data). The principle of split search: 1 > the array must be orderly; 2> Min and max must be known (know the range); 3> Dynamically calculate the value of mid and take out the corresponding value of mid for comparison; 4> If the value corresponding to mid is greater than the value to be searched, max will be reduced to mid-1; 5> If the value corresponding to mid is less than the value to be searched, min should be increased to mid+1;

//swif
// Given an ordered array and a key, it is required to find the index position corresponding to the key from the array
//Usage example: binarySearch(arr: arr, start: 0, end: result.count, key: keyValue)
func binarySearch(arr:[Int],start:Int,end:Int,key:Int){
        if start >= end{
            print("The location of the value could not be found")
            return
        }
        let midle = (start + end) / 2
        let midleValue = arr[midle]
        if midleValue < key{
            binarySearch(arr: arr, start: midle+1, end: end, key: key)
        }else if midleValue > key{
            binarySearch(arr: arr, start: start, end: midle-1, key: key)
        }else{
            print("index:\(midle)")
            return
        }
}

g. String inversion

//swift
func reverseString(originalString:String) -> String{
        var arr = Array(originalString)
        let count = arr.count
        for i in 0..<count/2{
            arr.swapAt(i, count-1-i)
        }
        return String(arr)
}

h. Ordered array merge

//swift
func sortArrayCombine(arrA:[Int],arrB:[Int]) -> [Int]{
        if arrA.count <= 0{
            return arrB
        }
        if arrB.count <= 0{
            return arrA
        }
        var resultArr = [Int]()
        var i = 0, j = 0
        let aCount = arrA.count,bCount = arrB.count
        while i < aCount && j < bCount {
            while j < bCount && arrA[i] >= arrB[j] {
                resultArr.append(arrB[j])
                j = j + 1
            }
            while i < aCount && arrA[i] <= arrB[j] {
                resultArr.append(arrA[i])
                i = i + 1
            }
        }
        if i >= aCount{
            while j < bCount {
                resultArr.append(arrB[j])
                j = j + 1
            }
        }
        if j >= bCount{
            while i < aCount {
                resultArr.append(arrA[i])
                i = i + 1
            }
        }
        return resultArr
}

i. Hash algorithm: hash table example: the given value is the letter A, the corresponding ASCII code value is 97, and the array index subscript is 97. The ASCII code here, even if it is a hash function, is stored and searched through this function to effectively improve the search efficiency. Find the first character that appears only once in a string. If you enter "abaccdef", the output 'b' character (char) is a data type with a length of 8, so there are 256 possibilities in total. Each letter is a number corresponding to the array type according to its ASCII code value as the array subscript. The array stores the number of occurrences of each character.

//swift
func hashFindFindFisrtOneCharacter(string:String) -> String{
        let strArr = Array(string)
        var sult = [Int]()
        for _ in 0..<256{
            sult.append(0)
        }
        for ch in strArr{
            let tStr = String(ch)
            let index = tStr.unicodeScalars.first!.value
            sult[Int(index)] = sult[Int(index)] + 1
        }
        for i in 0..<sult.count{
            if sult[i] == 1{
                let ch = Character(UnicodeScalar(i)!)
                return String(ch)
            }
        }
        return ""
}

j. Find the common parent view of the two views: record all the parent views of the two child views and save them to the array, and then search in reverse order until the first different parent view is found

func findFaterView(subView:UIView) -> [UIView]{
        var resultArr = [UIView]()
        var temp = subView.superview
        while temp != nil {
            resultArr.append(temp!)
            temp = temp!.superview
        }
        return resultArr
    }
    
    func findTwoViewCommonFathers(viewOne:UIView,viewTwo:UIView) -> [UIView]{
        let viewOneFathers = findFaterView(subView: viewOne)
        let viewTwoFathers = findFaterView(subView: viewTwo)
        var i = 0
        let oneCount = viewOneFathers.count,twoCount = viewTwoFathers.count
        let count = min(oneCount, twoCount)
        var result = [UIView]()
        while i < count {
            let view1 = viewOneFathers[oneCount-i-1]
            let view2 = viewTwoFathers[twoCount-i-1]
            if view1 == view2{
                result.append(view1)
            }else{
                break
            }
            i = i + 1
        }
        return result
    }