算法：

1、字符串反轉(zhuǎn)
2、鏈表反轉(zhuǎn)
3、有序數(shù)組合并
4、hash算法
5、查找兩個自視圖的共同父視圖
6、求無序數(shù)組當中的中位數(shù)

字符串反轉(zhuǎn)

例： 給定字符串 “hello,worlld ”，實現(xiàn)將其反轉(zhuǎn)
輸出 “dllrow,olleh”

void char_reverse(char* cha)
{
    // 指向第一個字符
    char* begin = cha;
    // 指向最后一個字符
    char* end = cha + strlen(cha) - 1;
    
    while (begin < end) {
        // 交換前后兩個字符,同時移動指針
        char temp = *begin;
        *(begin++) = *end;
        *(end--) = temp;
    }
}

鏈表反轉(zhuǎn)

屏幕快照 2018-11-20 上午10.54.48.png

struct Node* reverseList(struct Node *head)
{
    // 定義遍歷指針，初始化為頭結(jié)點
    struct Node *p = head;
    // 反轉(zhuǎn)后的鏈表頭部
    struct Node *newH = NULL;
    
    // 遍歷鏈表
    while (p != NULL) {
        
        // 記錄下一個結(jié)點
        struct Node *temp = p->next;
        // 當前結(jié)點的next指向新鏈表頭部
        p->next = newH;
        // 更改新鏈表頭部為當前結(jié)點
        newH = p;
        // 移動p指針
        p = temp;
    }
    
    // 返回反轉(zhuǎn)后的鏈表頭結(jié)點
    return newH;
}

struct Node* constructList(void)
{
    // 頭結(jié)點定義
    struct Node *head = NULL;
    // 記錄當前尾結(jié)點
    struct Node *cur = NULL;
    
    for (int i = 1; i < 5; i++) {
        struct Node *node = malloc(sizeof(struct Node));
        node->data = i;
        
        // 頭結(jié)點為空，新結(jié)點即為頭結(jié)點
        if (head == NULL) {
            head = node;
        }
        // 當前結(jié)點的next為新結(jié)點
        else{
            cur->next = node;
        }
        
        // 設(shè)置當前結(jié)點為新結(jié)點
        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;
    }
}

有序數(shù)組合并

void mergeList(int a[], int aLen, int b[], int bLen, int result[])
{
    int p = 0; // 遍歷數(shù)組a的指針
    int q = 0; // 遍歷數(shù)組b的指針
    int i = 0; // 記錄當前存儲位置
    
    // 任一數(shù)組沒有到達邊界則進行遍歷
    while (p < aLen && q < bLen) {
        // 如果a數(shù)組對應(yīng)位置的值小于b數(shù)組對應(yīng)位置的值
        if (a[p] <= b[q]) {
            // 存儲a數(shù)組的值
            result[i] = a[p];
            // 移動a數(shù)組的遍歷指針
            p++;
        }
        else{
            // 存儲b數(shù)組的值
            result[i] = b[q];
            // 移動b數(shù)組的遍歷指針
            q++;
        }
        // 指向合并結(jié)果的下一個存儲位置
        i++;
    }
    
    // 如果a數(shù)組有剩余
    while (p < aLen) {
        // 將a數(shù)組剩余部分拼接到合并結(jié)果的后面
        result[i] = a[p++];
        i++;
    }
    
    // 如果b數(shù)組有剩余
    while (q < bLen) {
        // 將b數(shù)組剩余部分拼接到合并結(jié)果的后面
        result[i] = b[q++];
        i++;
    }
}

驗證 :

    //// 有序數(shù)組歸并
    int a[5] = {1,4,6,7,9};
    int b[8] = {2,3,5,6,8,10,11,12};
    
    //// 用于存儲歸并結(jié)果
    int result[13];
    //// 歸并操作
    mergeList(a, 5, b, 8, result);
    //// 打印歸并結(jié)果
    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算法

例： 再一個字符串中找到第一個只出現(xiàn)一次的字符
如： 輸入“gabaccdeff”
算法思路：
char 為長度為8的數(shù)據(jù)類型 因此有256中可能
每個字母根據(jù) ASCII 碼值作為數(shù)組下標對應(yīng)數(shù)組的一個數(shù)字
數(shù)組中存儲的每個字符出現(xiàn)的次數(shù)

給定值字母 a 對應(yīng)ASCII值為 97 數(shù)組索引下標為97

算法實現(xiàn)：

char findFirstChar(char* cha)
{
    char result = '\0';
    // 定義一個數(shù)組 用來存儲各個字母出現(xiàn)次數(shù)
    int array[256];
    // 對數(shù)組進行初始化操作
    for (int i=0; i<256; i++) {
        array[i] =0;
    }
    // 定義一個指針 指向當前字符串頭部
    char* p = cha;
    // 遍歷每個字符
    while (*p != '\0') {
        // 在字母對應(yīng)存儲位置 進行出現(xiàn)次數(shù)+1操作
        array[*(p++)]++;
    }
    // 將P指針重新指向字符串頭部
    p = cha;
    // 遍歷每個字母的出現(xiàn)次數(shù)
    while (*p != '\0') {
        // 遇到第一個出現(xiàn)次數(shù)為1的字符，打印結(jié)果
        if (array[*p] == 1)
        {
            result = *p;
            break;
        }
        // 反之繼續(xù)向后遍歷
        p++;
    }
    
    return result;
}

5、(* 重要 *)面試題查找兩個自視圖的共同父視圖

- (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++;
        }
        // 如果不相等，則結(jié)束遍歷
        else{
            break;
        }
    }
    
    return result;
}

- (NSArray <UIView *> *)findSuperViews:(UIView *)view
{
    // 初始化為第一父視圖
    UIView *temp = view.superview;
    // 保存結(jié)果的數(shù)組
    NSMutableArray *result = [NSMutableArray array];
    while (temp) {
        [result addObject:temp];
        // 順著superview指針一直向上查找
        temp = temp.superview;
    }
    return result;
}

6、求無需數(shù)組當中的中位數(shù)

1 排序算法 + 中位數(shù)
2 利用快排思想（分治思想）

排序算法：
冒泡 快速 堆排序 ···
中位數(shù)：
當n為奇數(shù) （n + 1）/2
當n為偶數(shù) （n/2 + (n/2 + 1)）/ 2