Summary of iOS Development (I) Data structures and algorithms

The data structure

How many data structures are commonly used for storage? What are the characteristics of each?

Sequential storage structure:

For example, arrays, 1-2-3-4-5-6-7-8-9-10, are stored sequentially. Like stacks and queues

Chain storage structure:

Arrays, for example, the 1-2-3-4-5-6-4-5-6-10, the chain store is different (address) (1-2 (address) to 7 (address) (address) – 4-5 (address) – 9 (address) to 8 (address) – 3-6 (address) (address) to 10 (address). Each number is followed by an address and is no longer stored in order
Set structure linear structure tree structure graph structure
- The collection structure
A set is just a circle with a bunch of elements that have nothing to do with each other and that’s pretty simple
- Linear structure
There are many people standing in a line. This line doesn’t have to be straight. It could be bent. It can also be straight like a line divided into segments (use your imagination). A linear structure is a one-to-one relationship
- A tree structure
Developers must know that XML parsing trees are more or less similar to him. You can also imagine a pyramid. The tree structure is a one-to-many relationship
- Graph structure
This is a little bit more complicated. He is infinite. You can think of many-to-many as kind of like the intersection of people
Unidirectional linked list bidirectional linked list circular list
- Singly linked listA->B->C->D->E->F->G-> h. This is A unidirectional linked list. H is the head and A is the tail. It’s like A train with only one head and can only be pulled by one head
- Two-way linked list
- Circular linked list
  
  Circular linked list is the same as unidirectional linked list, is a chain type storage structure, the difference is that the last node of the circular linked list pointer is pointing to the first node of the circular linked list or table head node, thus forming a circular chain. A->B->C->D->E->F->G->H->A. Make a circle. It’s like a snake eats its own. It’s a cycle. You don’t have to learn anything by rote.
The difference between arrays and lists
- An array of
Array elements are stored contiguously in memory and can be found by subscript; Inserting or deleting requires a large number of elements to be moved and is more suitable for situations where elements rarely change
- The list
The elements in the list are not stored sequentially in memory, the search is slow, and the insertion and deletion only need to re-assign the element pointer, which is highly efficient
What are heap, stack, and queue?
The heap
- A heap is a sorted tree data structure in which each node has a value. Usually we refer to the data structure of a heap as a binary tree. So the heap in the data structure can usually be thought of as an array of objects in a tree. And the heap needs to satisfy two properties:
  
  1) The value of a node in the heap is always no greater than or less than the value of its parent;
  
  2) The heap is always a complete binary tree. (Complete binary tree is a very efficient data structure, which is derived from full binary tree. A binary tree of depth K with n nodes is called a complete binary tree if and only if each node corresponds to a pair of nodes numbered from 1 to n in a full binary tree of depth K.
- There are two kinds of heaps. There is a maximum heap and a minimum heap. The root node of the largest heap is called the maximum heap or large root heap, the root node of the smallest heap is called the minimum heap or small root heap, in a set of elements in the minimum heap, the elements of the parent node must be smaller than the elements of the child node, but for the size of the left and right nodes is not specified who is big and who is small.
- Heap are commonly used to implement a priority queue, access to heap is random, it’s like we of the bookshelf in the library book, although the book put is sequential, but we want to take any one don’t have to be like a stack, first take out in front of all the books, bookshelves this mechanism is different from the box, we can directly take out we want to book.
The stack
- A stack is a linear table that is restricted to inserting and deleting only at the end of the table. We call the top of the stack the end that allows insertions and deletions, the bottom of the stack the end that does not contain any data elements, the empty stack. The special thing about the stack is that it restricts the insertion and deletion of this linear table, which is always at the top of the stack.
- Stack is a Last In First Out (LIFO) data structure, also known as Last In First Out (LIFO) linear table. That is to say, we take what is stored first, and we take what is stored first. This is similar to the way we take something at the bottom of the box (something put in earlier), we first have to remove something that is pressing on it (something put in later).
- There are operations defined in the stack. The two most important ones are PUSH and POP. The PUSH operation adds an element to the top of the stack. The POP operation, by contrast, removes an element at the top of the stack and reduces the size of the stack by one.
- Stack application – recursion
The queue
- A queue is a linear table that allows inserts at one end and deletes at the other. The end that allows insertion is called the end of the queue, and the end that allows deletion is called the head of the queue. It is a special kind of linear table. What makes it special is that it allows only deletes at the front end of the table and inserts at the back end of the table. Like a stack, a queue is a linear table with limited operations.
- Queue is a first-in, first-out (FIFO) data structure, also known as first-in, first-out (FIFO) linear table. This means that what goes in first comes out, and what goes in later comes out later. It’s like when you go through security, the luggage that goes in first comes out first at the other end, and the luggage that goes in later comes out at the back.
Take the root of a binary tree, and find the depth of the tree. Right?
The nodes of binary trees are defined as follows:
```
Struct BinaryTreeNode {int m_nValue; BinaryTreeNode* m_pLeft; BinarvTreeNode * m_pRight; }Copy the code
```
- If a tree has only one node, its depth is one.
- If the root has only a left subtree and no right subtree, then the depth of the tree should be the depth of the left subtree plus one; Similarly, if the root has only a right subtree and no left subtree, then the depth of the tree should be the depth of its right subtree plus one.
- If there are both right and left subtrees, the depth of the tree is the greater of the left and right subtree depths plus one.
```
int TreeDepth(TreeNode* pRoot)
{
    if(pRoot == nullptr)
        return 0;
    int left = TreeDepth(pRoot->left);
    int right = TreeDepth(pRoot->right);

    return (left>right) ? (left+1) : (right+1);
}
Copy the code
```
Input the root of a binary tree, and determine whether the tree is a balanced binary tree?

Repeat through the nodes

First, find the depth of the left and right subtrees of the root node, and then judge that their depth difference is not more than 1, if not, it is not a binary tree; If yes, then use the same method to determine whether the left subtree and the right subtree are balanced binary trees. If both are, then this is a balanced binary tree.

I’m going to go through the nodes

The depth of the node is recorded while traversing the node to avoid repeated visits.

Method 1:

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};
 
int TreeDepth(TreeNode* pRoot){
    if(pRoot==NULL)
        return 0;
    int left=TreeDepth(pRoot->left);
    int right=TreeDepth(pRoot->right);
    returnleft>right? (left+1):(right+1); } bool IsBalanced(TreeNode* pRoot){if(pRoot==NULL)
        return true;
    int left=TreeDepth(pRoot->left);
    int right=TreeDepth(pRoot->right);
    int diff=left-right;
    if(diff>1 || diff<-1)
        return false;
    return IsBalanced(pRoot->left) && IsBalanced(pRoot->right);
}

Copy the code

Method 2:

bool IsBalanced_1(TreeNode* pRoot,int& depth){
    if(pRoot==NULL){
        depth=0;
        return true;
    }
    int left,right;
    int diff;
    if(IsBalanced_1(pRoot->left,left) && IsBalanced_1(pRoot->right,right)){
        diff=left-right;
        if(diff<=1 || diff>=-1){ depth=left>right? left+1:right+1;return true; }}return false;
}
 
bool IsBalancedTree(TreeNode* pRoot){
    int depth=0;
    return IsBalanced_1(pRoot,depth);
} 
Copy the code

algorithm

Time complexity/space complexity
- Time frequency
  
  The time it takes for an algorithm to execute cannot be calculated theoretically, but only by running tests on a computer. But we can’t and we don’t need to test every algorithm on the computer, just know which algorithm takes more time and which algorithm takes less time. And the amount of time an algorithm takes is directly proportional to the number of statements executed in the algorithm. Whichever algorithm executes more statements, it takes more time. The number of statements executed in an algorithm is called statement frequency or time frequency. Notes for T (n).
- Time complexity
  
  In general, the number of repeated execution of basic operations in the algorithm is a function of problem size N, expressed by T(n). If there is some auxiliary function F (n), such that when n approaches infinity, the limit value of T(n) /f(n) is a constant that is not equal to zero, then f(n) is a function of the same order of magnitude of T(n). T(n)=O(f(n)), O(f(n)) is the asymptotic time complexity of the algorithm, or time complexity for short.
- In different algorithms, if the number of statements executed in the algorithm is a constant, the time complexity is O(1). In addition, the time complexity may be the same when the time frequency is not the same. For example, T(n)=n2+3n+4 and T(n)=4n2+2n+1, their frequency is different but the time complexity is the same, which is O(n2).
- In order of magnitude, the common time complexity is:
  
  O(1) is called constant level, and the time complexity of the algorithm is a constant.
  
  O(n) is called a linear order, and the time complexity is a linear function of the amount of data n.
  
  O(n²) is called the square order and is of the same order of magnitude as the quadratic polynomial function of the data volume N.
  
  O(n³) is called the cubic order, and is a cubic polynomial function of n.
  
  Order logn is called the logarithmic level, which is a logarithmic function of n.
  
  O(nlogn) is said to be an order of magnitude between the linear order and the square order
  
  O(2 n) is called exponential and is on the order of magnitude of the exponential function of the data volume N.
  
  O(n!) It’s called the factorial level, and it’s the same order of magnitude as the factorial of the data volume n.
  
  The relationship between them is: O (1) < O (logn) < O (n) < O (nlogn) < O (n squared) < O (n) after < O (2 ⁿ) < O (n!) With the increasing of problem size n, the time complexity above increases, and the execution efficiency of the algorithm becomes lower.
2. Space complexity
- Evaluate the storage space required to execute the program. You can estimate how much your program is using the computer’s memory. It does not include the space occupied by the algorithm program code and the data itself. It is usually represented by the number of bytes of extra space used. Its algorithm is relatively simple, denoted as S(n)=O(f(n)), where n represents the size of the problem.

What are the common sorting algorithms?

Selection sort, bubble sort, insertion sort three sort algorithms can be summarized as follows:

Both divide the array into sorted and unsorted parts.

Select sort defines the sorted part on the left, and then selects the smallest element of the unsorted part to be swapped with the first element of the unsorted part.

Bubble sort defines the sorted part at the right end and performs an exchange during the process of traversing the unsorted part, swapping the largest element to the right end.

Insertion sort defines the sorted part on the left and inserts the first element of the unsorted part into the appropriate place for the sorted part.

/ * * * "selection" : the most value in between * * trip 1: in the n number found in (large) number of minimum 2 trips to swap places with the first number * : in the remaining find the minimum number n - 1 (large) number of swap places with the second number * repeat operation... The third, the fourth... The number exchange position * n-1 trip, finally can realize the ascending (descending) order of data. * */ void selectSort(int *arr, int length) {for(int i = 0; i < length - 1; I++) {// number of tripsfor(int j = i + 1; j < length; J++) {// compare timesif(arr[i] > arr[j]) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}}} /** * [Bubble sort] : Compare the two adjacent elements in pairs, after the comparison, the most value appears at the end * the first time: compare the two adjacent numbers in turn, constantly swap (before the decimal, after the large number put) advance one by one, the most value finally appears at the NTH element position * the second time: Compare the two adjacent numbers in turn, constantly switching (before the decimal number, after the large number) advance one by one, the most value finally appears in the n-1 element position *...... ... */ void bublleSort(int *arr, int length) {void bublleSort(int *arr, int length) {for(int i = 0; i < length - 1; I++) {// number of tripsfor(int j = 0; j < length - i - 1; J++) {// compare timesif(arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; }}}} /** * Split search: Optimize the search time (without traversing all the data) ** The principle of split search: * 1> Array must be ordered * 2> Must know min and Max (know range) * 3> Dynamically calculate mid and fetch mid for comparison * 4> If mid is greater than the value we are looking for, So Max is going to be smaller than mid-1 * 5> if mid is less than the value we're looking for, Int int (int *arr, int length, int key) {int min = 0, int (int *arr, int length, int key) {int min = 0, max = length - 1, mid;while(min <= max) { mid = (min + max) / 2; // Calculate the median valueif (key > arr[mid]) {
            min = mid + 1;
        } else if (key < arr[mid]) {
            max = mid - 1;
        } else {
            returnmid; }}return- 1; }Copy the code

String inversion

Void char_reverse (char *cha) {// Define header pointer char *begin = cha; Char *end = cha + strlen(cha) -1;while (begin < end) {
        
        char temp = *begin;
        *(begin++) = *end;//*crash
        *(end--) = temp;
    }
}Copy the code

Linked List Inversion (head insertion)

implementation

#import "ReverseList.h"Struct Node {int data; struct Node *next; }; Struct Node* head (struct Node* head); Struct Node* constructList(void); // Print the data in the list voidprintList(struct Node *head); @implementation struct Node* ReverseList (struct Node* head) {struct Node* p = head; // Struct Node *newH = NULL; // Traverse the listwhile(p ! Struct Node *temp = p->next; P ->next = newH; // Change the new list header to the current node newH = p; P = temp; } // Return the inverted list header nodereturnnewH; } struct Node* constructList(void) {struct Node* head = NULL; Struct Node *cur = NULL;for(int i = 1; i < 5; i++) { struct Node *node = malloc(sizeof(struct Node)); node->data = i; // The head node is null, and the new node is the head nodeif(head == NULL) { head = node; } // Next of the current node is the new nodeelse{ cur->next = node; } // Set current node to new node cur = node; }return head;
}

void printList(struct Node *head)
{
    struct Node* temp = head;
    while(temp ! = NULL) {printf("node is %d \n", temp->data);
        temp = temp->next;
    }
}

@end
Copy the code

How to find the first character that occurs only once (Hash lookup)

char findFirstChar(char* cha)
{
    char result = '\ 0'; Int array[256]; // Define an array to store the number of occurrences of each letter. // Initialize the arrayfor(int i=0; i<256; i++) { array[i] =0; } // Define a pointer to the current string header char* p = cha; // Iterate over each characterwhile(*p ! ='\ 0') {array[*(p++)]++; array[*(p++)]++; } // redirect the P pointer to the string header P = cha; // Iterates over the number of occurrences of each letterwhile(*p ! ='\ 0') {// Prints the first character that occurs 1 timesif (array[*p] == 1)
        {
            result = *p;
            break; } // iterates backwards to p++; }return result;
}
Copy the code

How do I find the common superview of two child views?

- (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther { NSMutableArray *result = [NSMutableArray array]; NSArray *arrayOne = [self findSuperViews:viewOne]; NSArray *arrayOther = [self findSuperViews:viewOther]; int i = 0; // Out of bounds restrictionswhile(i < MIN((int)arrayOne.count, (int) arrayOther. Count)) {/ / reverse way to obtain various views of parent UIView * superOne = [arrayOne objectAtIndex: arrayOne. Count - I - 1]. UIView *superOther = [arrayOther objectAtIndex:arrayOther.count - i - 1]; // If the comparison is equal, it is the common parent viewif(superOne == superOther) { [result addObject:superOne]; i++; } // If they are not equal, the traversal endselse{
            break; }}returnresult; } - (NSArray <UIView *> *)findSuperViews (UIView *)view {// initialize the first superview UIView *temp = view.superview; NSMutableArray *result = [NSMutableArray array];while(temp) { [result addObject:temp]; // Select temp = temp. Superview; }return result;
}

Copy the code

Median in an unordered array (quicksort idea)

Median: The number in the middle of a set of data from smallest to largest. The middle of an odd number of data, and the average of the two for an even number of data

Int findMedian(int a[], int aLen) {int low = 0; int high = aLen - 1; int mid = (aLen - 1) / 2; int div = PartSort(a, low, high);while(div ! = mid) {ifDiv = PartSort(a, low, div-1); }else{div = PartSort(a, div + 1, high); }} // Foundreturna[mid]; } int PartSort(int a[], int start, int end) { int low = start; int high = end; Int key = a[end];while(low < high) {// Find a value greater than key on the leftwhile(low < high && a[low] <= key) { ++low; } // Find a value smaller than key on the rightwhile (low < high && a[high] >= key)
        {
            --high;
        }
        
        ifInt temp = a[low]; int temp = a[low]; a[low] = a[high]; a[high] = temp; } } int temp = a[high]; a[high] = a[end]; a[end] = temp;return low;
}
Copy the code

Given an array of integers and a target value, find the two numbers in the array and the target value. The time complexity of this algorithm is O(n2)O(n^2)O(n 2) and the space complexity is O(1). The time complexity of this algorithm is O(n2)O(n^2)O(n 2). It works, but it’s not optimal

- (BOOL)twoNumSumWithTarget:(int)target Array:(NSArray<NSNumber *> *)array {
    
    NSMutableArray *finalArray = [NSMutableArray array];
    
    for (int i = 0; i < array.count; i++) {
        
        for (int j = i + 1; j < array.count; j++) {
            
            if ([array[i] intValue] + [array[j] intValue] == target) {
                
                [finalArray addObject:array[i]];
                [finalArray addObject:array[j]];
                NSLog(@"% @",finalArray);
                
                returnYES; }}}return NO;
}
Copy the code

Summary of iOS Development (I) Data structures and algorithms

The data structure

The heap

The stack

The queue

The nodes of binary trees are defined as follows:

Method 1:

Method 2:

algorithm

2. Space complexity

Selection sort, bubble sort, insertion sort three sort algorithms can be summarized as follows:

implementation

Related Posts

PullUpController: a multi-section pull-up search box interface control component similar to iOS maps

0.0.0, memory related: iOS interview questions memory aid

iOS — Autorelease & AutoreleasePool