全方位剖析iOS高级技术问题(十一)之算法

本文主要内容

一.字符串回转
二.链表回转
三.有序数组兼并
四.Hash算法
五.查找两个子视图的共同父视图
六.求无序数组傍边的中位数

一.字符串回转

标题一：给定字符串“Hello, SwiftUI”，完成将其回转

输出成果：IUtfiwS，olleH

分析思路：假定有一个字符数组中存储了“Hello, SwiftUI”，经过设置两个指针，其一begin指针指向字符数组的开头，另一个end指针指向字符数组的成果。在遍历过程中，逐渐交流begin和end指针所指内容，交流之后将指针移动到下一个方位。直到begin大于等于end。

代码完成

// CharReverse.h
#import CharReverse: NSObject
// 字符串回转
void char_reverse(char* cha);
@end

// CharReverse.m
#import "CharReverse.h"
@implementation CharReverse: 
void char_reverse(char* cha) {
    // 指向榜首个字符
    char* begin = cha;
    // 指向最后一个字符
    char* end = cha + strlen(cha) - 1;
    while (begin < end) {
        // 交流前后两个字符，一起移动指针
        char temp = *begin;
        *(begin++) = *end;
        *(end--) = temp;
    }
}
@end

// 调用
// 字符串回转
char ch[] = "Hello, SwiftUI";
char_reverse(ch);
printf("reverse result is %s \n", ch);

成果：reverse result is IUtfiwS ,olleH

二.链表回转⭐️⭐️⭐️

标题二：单链表回转前1->2->3->4->NULL，回转后4->3->2->1->NULL

代码完成

// ReverseList.h
#import <Foundation/Foundation.h>
// 界说一个链表
struct Node {
    int data;
    struct Node *next;
};
@interface ReverseList: NSObject
// 链表回转
struct Node* reverseList(struct Node *head);
// 结构一个链表
struct Node* constructList(void);
// 打印链表中的数据
void printList(struct Node *head);
@end

// ReverseList.m
#import "ReverseList.h"
@implementation ReverseList
// 回转链表
// 输入参数：本来链表的头结点
// 回来值：新的链表的头结点
struct Node* reverseList(struct Node *head) {
    // 界说遍历指针，初始化为头结点
    struct Node *p = head;
    // 回转后的链表头部
    struct Node *newH = NULL;
    // 遍历链表
    while (p != NULL) {
        // 记载下一个结点
        struct Node *temp = p->next;
        // 当时结点的next指向链表头部
        p->next = newH;
        // 更改新链表头部为当时结点
        newH = p;
        // 移动p指针
        p = temp;
    }
    // 回来回转后的链表头结点
    return newH;
}
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;
        // 头结点为空，新结点即为头结点
        if (head == NULL) {
            head = node;
        }
        // 当时结点的next为新结点
        else {
            cur->next = 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

// 单链表回转
struct Node* head = constructList();
printList(head);
printf("----------\n");
struct Node* newHead = reverseList(head);
printList(newHead);

输出成果：
node is 6
node is 7
node is 8
node is 9
node is 10
-----------
node is 10
node is 9
node is 8
node is 7
node is 6

三.有序数组兼并(高频⭐️⭐️⭐️)

标题三：两个有序数组兼并，兼并后依然是有序数组

算法思路：界说两个临时变量指针p和q，p指向榜首个数组的首方位，q指向第二个数组的榜首个方位，遍历比较p方位
数组元素和q方位数组元素的巨细。假如p方位的数组数据小，就把其所指向的数据添加到新的兼并数组中，然后移动被
添加了对应数据的指针的方位，继续比照数据巨细，直到某个数组表数据全部移出，再将另一个数组数据剩下元素再添
加到兼并数组尾部。

代码完成

// MergeSortedList.h
#import <Foundation/Foundation.h>
@interface MergeSortedList: NSObject
// 将有序数组a和b的值兼并到一个数组result傍边，且依然坚持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]);
@end

// MergeSortedList.m
#import "MergeSortedList.h"
@implementation MergeSortedList
void mergeList(int a[], int aLen, int b[], int bLen, int result[]) {
    int p = 0; // 遍历数组a的指针
    int q = 0; // 遍历数组b的指针
    int i = 0; 记载当时存储方位
    //任一数组没有抵达鸿沟则继续遍历
    while (p < aLen && q < bLen) {
        // 假如a数组对应方位的值小于b数组对应方位的值
        if (a[p] <= b[q]) {
            // 存储a数组的值
            result[i] = a[p];
            // 移动a数组的遍历指针
            p++;
        } else {
            // 存储b数组的值
            result[i] = b[q];
            // 移动b数组的遍历指针
            q++;
        }
        // 指向兼并成果的下一个存储方位
        i++;
    }
    // 假如a数组有剩下
    while (p < aLen) {
        // 将a数组剩下部分拼接到兼并成果的后边
        result[i] = a[p++];
        i++;
    }
    // 假如b数组有剩下
    while (q > bLen) {
        // 将b数组剩下部分拼接到兼并成果的后边
        result[i] = b[q++];
        i++;
    }
}
@end

// 调用
// 有序数组归并
int a[5] = {1,4,6,7,9};
int b[8] = {2,3,5,6,8,10,11,12};
// 用于存储归并成果
int result[13];
// 归并操作
mergeList(a, 5, b, 8, result);
// 打印归并成果
printf("merge result is ");
for (int i = 0; i < 13; i++) {
    printf("%d ", result[i]);
}

输出成果：merge result is 1 2 3 4 5 6 6 7 8 9 10 11 12

四.Hash算法

标题四：在一个字符串中找到榜首个只呈现一次的字符。比方：输入“abaccdeff”,则输出b

算法思路：字符(char)是一个长度为8的数据类型，因而总共有或许256种或许。每个字母依据其ASCII码值作为数组的下标对应数组的一个数字。

哈希表

• 例：给定值是字母a，对应ASCII值是97，数组索引下标为97。

树立一个字符(char)到所存储方位index的映射联系，界说为哈希函数，记为f(key)。此哈希函数就是经过给定字符转化为对应ASCII码值来确定其在数组中的存储方位。存储和查找都是经过该函数，有效提高查找功率。

算法完成

// HashFind.h
#import <Foundation/Foundation.h>
@interface HashFind : NSObject
// 查找榜首个只呈现一次的字符
char findFirstChar(char* cha);
@end

// HashFind.h
#import "HashFind.h"
char findFirstChar(char* cha) {
    char result = '\0'; // 空字符
    // 界说一个数组，用来存储各个字母呈现次数
    int array[256];
    // 对数组进行初始化操作
    for (int i = 0; i < 256; i++) {
        array[i] = 0;
    }
    // 界说一个指针，指向当时字符串头部
    char* p = cha;
    // 遍历每个字母
    while (*p != '\0') { // 遍历到字符串结束
        // 在字母对应存储方位，进行呈现次数+1操作
        // 先对p所指向对应字母作为数组下标进行++操作，即次数➕1；再将p指针向后移动(p++)
        array[*(p++)]++;
    }
    // 如上已经将每个字符呈现的次数存在数组中
    // 将p指针重新指向字符串头部
    p = cha;
    // 遍历每个字母的呈现次数
    while (*p != '\0') {
        // 遇到榜首个呈现次数为1的字符，打印成果
        if (array[*p] == 1) {
            result = *p;
            break;
        }
        // 反之继续向后遍历
        p++;
    }
    return result;
}

// 调用
// 查找榜首个只呈现一次的字符
char cha[] = "abaccdeff";
char fc = findFirstChar(cha);
printf("this char is %c \n", fc);

输出成果：this char is b

五.查找两个子视图的共同父视图

算法分析：查找View A和View B一切的父视图，然后倒叙找到榜首个不一样的。

算法完成

// CommonSuperFind.h
#import <Foundation/Foundation.h>
#import <UIKit/UIKit.h>
@interface CommonSuperFind : NSObject
// 查找两个视图的共同父视图
- (NSArray<UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther;
@end

// CommonSuperFind.m
#import "CommonSuperFind.h"
@implementation CommonSuperFind
- (NSArray<UIView *> *)findCommonSuperView:(UIView *)view other:(UIView *)viewOther {
    NSMutableArray *result = [NSMutableArray array];
    // 查找榜首个视图的一切父视图
    NSArray *arrayOne = [self findSuperViews: viewOne];
    // 查找第二个视图的一切父视图
    NSArray *arrayOther = [self findSuperViews: viewOther];
    int i = 0;
    // 越界约束条件
    while (i < MIN((int)arrayOne.count, (int)arrayOther.count)) {
        // 倒序方式获取各个视图的父视图
        UIView *superOne = [arrayOne objectAtIndex: arrayOne.count - i - 1];
        UIView *superOther = [arrayOther objectAtIndex: arrayOther.count - i - 1];
        // 比较假如持平，则为共同父视图
        if (superOne == superOther) {
            [result addObject: superOne];
            i++;
        }
        // 假如不持平，则结束遍历
        else {
            break;
        }
    }
    return result;
}
- (NSArray <UIView *> *)findSuperViews:(UIView *)view {
    // 初始化为榜首父视图
    UIView *temp = view.superview;
    // 保存成果的数组
    NSMutableArray *result = [NSMutableArray array];
    while (temp) {
        [result addObject: temp];
        // 顺着superview指针一向向上查找
        temp = temp.superview;
    }
    retuen result;
}
@end

六.求无序数组傍边的中位数

• 排序算法 + 中位数

• 使用快排思想(分治思想)
  选取关键字，高低交替扫描。

  `选完支点元素，使得其左边的元素都小于支点元素，右边的都大于支点元素。`
  

排序演示
假定一开始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。 （1）此刻，ref=5，i=1，j=11，从后往前找，榜首个比5小的数是x8=2，因而序列为：2，3，7，6，4，1，0，5，9，10，8。 此刻i=1，j=8，早年往后找，榜首个比5大的数是x3=7，因而序列为：2，3，5，6，4，1，0，7，9，10，8。

（2）此刻，i=3，j=8，从第8位往前找，榜首个比5小的数是x7=0，因而：2，3，0，6，4，1，5，7，9，10，8。

（3）此刻，i=3，j=7，从第3位往后找，榜首个比5大的数是x4=6，因而：2，3，0，5，4，1，6，7，9，10，8。

（4）此刻，i=4，j=7，从第7位往前找，榜首个比5小的数是x6=1，因而：2，3，0，1，4，5，6，7，9，10，8。

（5）此刻，i=4，j=6，从第4位往后找，直到第6位才有比5大的数，这时，i=j=6，ref成为一条分界线，它之前的数都比它小，之后的数都比它大，对于前后两部分数，可以选用同样的方法来排序。

用快排思想找中位数：

恣意挑一个元素，以该元素为支点，区分集合为两部分：
假如左侧集合长度刚好为(n-1)/2,那么支点恰为中位数；
假如左侧长度<(n-1)/2，那么中位点在右侧，反之，中位数在左侧；
进入相应的一侧继续寻找中位点。

算法完成

// MedianFind.h
#import <Foundation/Foundation.h>
@interface MedianFind: NSObject
// 无序数组中位数查找
int findMedian(int a[], int aLen);
@end

// MedianFind.m
#import <MedianFind.h>
@implementation MedianFind
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) {
        if (mid < div) {
            // 左半区间找
            div = PartSort(a, low, div - 1);
        } else {
            // 右半区间找
            div = PartSort(a, div + 1, high);
        }
    }
    // 找到了
    return a[mid];
}
int PartSort(int a[], int start, int end) {
    int low = start;
    int high = end;
    // 选取关键字
    int key = a[end];
    while (low < high) {
        // 左边找比key大的值
        while (low < high && a[low] <= key) {
            ++low;
        }
        // 右边找比key小的值
        while (low < high && a[high] >= key) {
            --high;
        }
        if (low < high) {
            // 找到之后交流左右的值
            int temp = a[low];
            a[low] = a[high];
            a[high] = temp;
        }
    }
    int temp = a[high];
    a[high] = a[end];
    a[end] = temp;
    return low;
}
@end

// 调用
// 无序数组中位数查找
int list[] = {12,3,10,8,6,7,11,13,9,4};
int median = findMedian(list, 9);
printf("the median is %d\n", median);

本文总结

链表回转：头插法⭐️⭐️⭐️

有序数组兼并

Hash算法

查找两个子视图的共同父视图⭐️⭐️⭐️

有任何问题，欢迎各位谈论指出！觉得博主写的还不错的费事点个赞喽