第十四篇：Objective-C 知识回顾架算法

主要算法大纲

问题一： 请实现字符串反转的算法。

主要思路：两个指针分别指向字符串的一头一尾地址，然后交换两个指针的内容，交换完毕后，指针从两端向中间移动，重复交换和移动操作。直到 begin 指针的地址大于等于 end 指针，就结束程序完成交互。

// code 
void characterReverse(char* cha) {
    char* begin = &cha[0];
    char* end = cha + strlen(cha) - 1;
    
    while (begin < end) {
        char temp = *begin;
        *(begin++) = *end;
        *(end--) = temp;
    }
}

// usage
- (void)learnCharacterReverse {
    char cha[]= "Hello,World";
    characterReverse(cha);
    printf("reverse result is %s \n", cha);
}

问题二： 请实现链表的反转。

主要思路：创建两个指针，一个用来存放反转的新链表，一个用来存当前链表。利用头插法，把旧链表上的数据一个个插入新链表的头部。特别注意一点在于，要先存链表的下一个结点，不然插入之后会丢失链表数据。

// .h
#import <Foundation/Foundation.h>
struct Node {
    int data;
    struct Node* next;
};
@interface ChainReverse : NSObject
// 链表反转
struct Node* chain_reverse(struct Node* head);
// 构建一个列表
struct Node* constructionChains(void);
// 打印链表
void printChain(struct Node *head);
@end


// .m文件
#import "ChainReverse.h"
@implementation ChainReverse
// 链表反转
struct Node* chain_reverse(struct Node* head) {
    // 定义遍历指针,初始化头结点
    struct Node* p = head;
    // 反转后的链表头部
    struct Node *newH = NULL;
    
    // 遍历链表
    while (p != NULL) {
        // 先记录下一个结点
        struct Node* temp = p->next;
        // 当前结点的 nex 执行新链表的头部
        p->next = newH;
        // 更改新链表头部为当前结点
        newH = p;
        // 移动 p 指针
        p = temp;
    }
    return newH;
};
// 构建一个列表
struct Node* constructionChains(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;
        node->next = NULL;
        
        if (head == NULL) {
            head = node;
        } else {
            cur->next = node;
        }
        cur = node;
    }
    return head;
}
// 打印链表
void printChain(struct Node *head) {
    struct Node* cur = NULL;
    cur = head;
    
    while (cur != NULL) {
        printf("%i \n", cur->data);
        cur = cur->next;
    };
    printf("===============\n");
}

@end


// 用法

- (void)learnChainReverse {
    struct Node* head = constructionChains();
    printChain(head);
    struct Node* newHead = chain_reverse(head);
    printChain(newHead);
}

问题三：请实现两个有序数组合并成一个有序数据的算法。

算法思路：分别从两个有序数组头部开始取数组，对比大小，把小的值插入新数组，然后小的值所在数据角标+1，如此重复，直到其中一方数组没有数据了，把另一个数组剩余的值全部插入新数组，完成合并。

// 将有序数据 a 和 b 的值合并到一个数据 result当中,且仍然保持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]) {
    int p = 0; // 记录数组 a 的位置
    int q = 0; // j遍历数组 b 的位置
    int i = 0; // 记录当前存储 z 位置
    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 算法，就是利用哈希函数做一个映射，从而由 key 经过 f(key) 高效的找到结果。所以我们可以把字符当成 ASCII 码作为 key 并且当成一个数组的脚本，数组的 value 就是出现的次数。

char findFirstChar(char *cha) {
    // 用来移动的指针
    char *p = cha;
    // 初始化一个数组
    int array[256];
    for (int i = 0 ; i < 256; i++) {
        array[i] = 0;
    }
    // 结果存放处
    char result = '\0';
    // 遍历并且给数组赋值
    while (*p != '\0') {
        array[*(p++)]++;
    }
    p = cha;
    // 查找value 为 1 的字符
    while (*p != '\0') {
        if (array[*p] == 1) {
            result = *p;
            break;
        }
        p++;
    }
    return result;
}

问题五：查找两个子视图的共同父视图。

算法思路：先遍历找出两个子视图的所有父视图，存于两个数组；将两个数组进行反序，然后从下标 0 的位置开始对比两个数组，将相同的视图存在另一个新数组中，直到两个数组第一次出现不同视图，就可以终止循环。

- (void)learnFindCommonSupperView {
    NSMutableArray *mutableArray_A = [NSMutableArray new];
    NSMutableArray *mutableArray_B = [NSMutableArray new];
    NSMutableArray *mutableArray_Common = [NSMutableArray new];
    
    UIView *currentA = self.labelA;
    while (currentA.superview != nil) {
        [mutableArray_A addObject:currentA.superview];
        currentA = currentA.superview;
    }
    
    UIView *currentB = self.labelB;
    while (currentB.superview != nil) {
        [mutableArray_B addObject:currentB.superview];
        currentB = currentB.superview;
    }
    // 步骤的关键在于反序查找,直到第一个不同的视图终止
    mutableArray_A = [[[mutableArray_A reverseObjectEnumerator] allObjects] mutableCopy];
    mutableArray_B = [[[mutableArray_B reverseObjectEnumerator] allObjects] mutableCopy];
    
    for (int i = 0; i < mutableArray_A.count && i < mutableArray_B.count; i++) {
        UIView *a = mutableArray_A[i];
        UIView *b = mutableArray_B[i];
        
        if (a == b) {
            [mutableArray_Common addObject:a];
            // 为了标记已经找到的共同父视图,标记为红色
            a.backgroundColor = [UIColor redColor];
            a.layer.borderWidth = 1;
            a.layer.borderColor = [UIColor whiteColor].CGColor;
        } else {
            break;
        }
    }
    
    NSLog(@"一共有 %lu 个父视图", (unsigned long)mutableArray_Common.count);
}