全方位剖析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算法

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

有任何问题，欢迎?各位评论指出！觉得博主写的还不错的麻烦点个赞喽?