iOS常用算法总结

一 字符串反转

字符串反转指示图.png

核心代码:

void char_reverse(char *cha) {
    char *begin = cha;//指向第一个字符
    char *end = cha + strlen(cha) - 1;//指向最后一个字符
    while (begin < end) {//交换字符,同时移动指针
        char temp = *begin;
        *begin = *end;
        *end = temp;
        begin++;
        end--;
    }
}

二 链表反转

核心代码 [头插法核心思想]

struct Node* reverseList(struct Node *head) {
    struct Node *p = head;//遍历指针,初始值为列表的头结点
    struct Node *newH = NULL;//反转后的列表头部
    while (p != NULL) {
        struct Node *temp = p->next;//暂存下一个节点
        p->next = newH;//指向新列表的头结点
        newH = p;//更改新列表的头部为当前节点
        p = temp;//移动p指针
    }
    return newH;
}

三 有序数组合并

有序数组合并指示图.png

核心代码:

void mergeList(int a[], int aLen, int b[], int bLen, int result[]) {
    int p = 0;
    int q = 0;
    int i = 0;//记录当前的存储位置
    while (p < aLen && q < bLen) {
        if (a[p] < b[q]) {
            result[i] = a[p];
            p++;
        }else {
            result[i] = b[q];
            q++;
        }
        i++;
    }
    while (p < aLen) {
        result[i] = a[p];
        p++;
        i++;
    }
    while (q < bLen) {
        result[i] = b[q];
        q++;
        i++;
    }
}

四 Hash算法

例:在一个字符串中找到第一个只出现一次的字符[核心思想:生成一个数组,数组中存储每个字符出现的次数]

char findFirstChar(char *cha) {
    char result = '\0';
    int array[128];//定义数组,用来记录各个字母出现的次数,初始值均为0
    for (int i = 0; i < 128; i++) {
        array[i] = 0;
    }
    char *p = cha;//指针p指向字符串的头部遍历字符串
    while (*p != '\0') {
        array[*p]++;
        p++;
    }
    p = cha;//再次指向头部遍历字符串,找到次数为1的字符
    while (*p != '\0') {
        if (array[*p] == 1) {
            result = *p;
            break;
        }
        p++;
    }
    return result;
}

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

倒叙比较不一样的父试图

- (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;
    // 越界限制条件
    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;
    }
    return result;
}

六 求无序数组当中的中位数

可以有两种解法:(1. 排序算法+中位数)(2.利用快排思想)
核心相关代码:

int findMedia(int a[],int aLen) {
    int low = 0;
    int high = aLen - 1;
    int mid = (aLen - 1)/2;//中位点
    int tempMedia = 0;
    while (tempMedia != mid) {
        tempMedia = partSort(a, low, high);
        if (tempMedia > mid) {//快排的思想确定当前基准数
            high = tempMedia - 1;
        }else if (tempMedia < mid) {
            low = tempMedia + 1;
        }else {
            break;
        }
    }
    return a[tempMedia];
}

int partSort(int a[],int start, int end) {
    int low = start;
    int high = end;
    int key = a[end];
    while (low < high) {
        while (low < high) {//左边找比key大的值
            if (a[low] <= key) {
                low++;
            }else {
                int temp = a[low];
                a[high] = temp;
                break;
            }
        }
        while (low < high) {//右边找比key小的值
            if (a[high] >= key) {
                high--;
            }else {
                int temp = a[high];
                a[low] = temp;
                break;
            }
        }
    }
    a[low] = key;
    return low;
}

七 两个数n、m 如果是n= 2 m=5，用递归实现2 3 4 5相加等于14

int sum(int n, int m) {
    if (m == n) {
        return n;
    }else {
        return m + sum(n, m-1);
    }
}