Hash 算法

所在一個字符串中找到第一個只出現(xiàn)一次的字符
如：輸入"sadagqeqsf" ,則輸出 d。

算法思路：
ASCII碼值有256種。
每個字母根據(jù)其ASCII碼作為數(shù)組對的下標(biāo)對應(yīng)數(shù)組的一個數(shù)字
數(shù)組中存儲的是每個字符出現(xiàn)的次數(shù)

代碼

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;
    }
    // 定義一個指針 指向當(dāng)前字符串頭部
    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;
}

字符串反轉(zhuǎn)

比如 給定字符串 "hello,world",輸出 "dlrow,olleh"

在遍歷過程中逐步交換 begin 和 end 倆個指針指向的內(nèi)容,實現(xiàn)內(nèi)容翻轉(zhuǎn)

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

查找倆個子視圖的共同父視圖

這個和iOS 本身聯(lián)系就非常緊密了, 首先需要獲取到倆個子視圖的所有父視圖，然后倒序比較找到第一個不一樣的

如 X視圖的 D->C->B->A
Y視圖 B->A
循環(huán)遍歷， 找到共同視圖 B->A

- (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 1 2 7 9 3 4 5 10 8”兩端開始“探測”。先從右往左找一個小于6的數(shù)，再從左往右找一個大于6的數(shù)，然后交換他們。這里可以用兩個變量i和j，分別指向序列最左邊和最右邊。我們?yōu)檫@兩個變量起個好聽的名字“哨兵i”和“哨兵j”。剛開始的時候讓哨兵i指向序列的最左邊（即i=1），指向數(shù)字6。讓哨兵j指向序列的最右邊（即=10），指向數(shù)字。

首先哨兵j開始出動。因為此處設(shè)置的基準(zhǔn)數(shù)是最左邊的數(shù)，所以需要讓哨兵j先出動，這一點非常重要（請自己想一想為什么）。哨兵j一步一步地向左挪動（即j--），直到找到一個小于6的數(shù)停下來。接下來哨兵i再一步一步向右挪動（即i++），直到找到一個數(shù)大于6的數(shù)停下來。最后哨兵j停在了數(shù)字5面前，哨兵i停在了數(shù)字7面前。

現(xiàn)在交換哨兵i和哨兵j所指向的元素的值。交換之后的序列如下：

6 1 2 5 9 3 4 7 10 8

到此，第一次交換結(jié)束。接下來開始哨兵j繼續(xù)向左挪動（再友情提醒，每次必須是哨兵j先出發(fā)）。他發(fā)現(xiàn)了4（比基準(zhǔn)數(shù)6要小，滿足要求）之后停了下來。哨兵i也繼續(xù)向右挪動的，他發(fā)現(xiàn)了9（比基準(zhǔn)數(shù)6要大，滿足要求）之后停了下來。此時再次進行交換，交換之后的序列如下：

6 1 2 5 4 3 9 7 10 8

第二次交換結(jié)束，“探測”繼續(xù)。哨兵j繼續(xù)向左挪動，他發(fā)現(xiàn)了3（比基準(zhǔn)數(shù)6要小，滿足要求）之后又停了下來。哨兵i繼續(xù)向右移動，糟啦！此時哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。說明此時“探測”結(jié)束。我們將基準(zhǔn)數(shù)6和3進行交換。交換之后的序列如下：

3 1 2 5 4 6 9 7 10 8

到此第一輪“探測”真正結(jié)束。此時以基準(zhǔn)數(shù)6為分界點，6左邊的數(shù)都小于等于6，6右邊的數(shù)都大于等于6?；仡櫼幌聞偛诺倪^程，其實哨兵j的使命就是要找小于基準(zhǔn)數(shù)的數(shù)，而哨兵i的使命就是要找大于基準(zhǔn)數(shù)的數(shù)，直到i和j碰頭為止。

OK，解釋完畢?，F(xiàn)在基準(zhǔn)數(shù)6已經(jīng)歸位，它正好處在序列的第6位。此時我們已經(jīng)將原來的序列，以6為分界點拆分成了兩個序列，左邊的序列是“3 1 2 5 4”，右邊的序列是“9 7 10 8”。接下來還需要分別處理這兩個序列。因為6左邊和右邊的序列目前都還是很混亂的。不過不要緊，我們已經(jīng)掌握了方法，接下來只要模擬剛才的方法分別處理6左邊和右邊的序列即可?，F(xiàn)在先來處理6左邊的序列現(xiàn)吧。

左邊的序列是“3 1 2 5 4”。請將這個序列以3為基準(zhǔn)數(shù)進行調(diào)整，使得3左邊的數(shù)都小于等于3，3右邊的數(shù)都大于等于3。好了開始動筆吧

如果你模擬的沒有錯，調(diào)整完畢之后的序列的順序應(yīng)該是：

2 1 3 5 4

OK，現(xiàn)在3已經(jīng)歸位。接下來需要處理3左邊的序列“2 1”和右邊的序列“5 4”。對序列“2 1”以2為基準(zhǔn)數(shù)進行調(diào)整，處理完畢之后的序列為“1 2”，到此2已經(jīng)歸位。序列“1”只有一個數(shù)，也不需要進行任何處理。至此我們對序列“2 1”已全部處理完畢，得到序列是“1 2”。序列“5 4”的處理也仿照此方法，最后得到的序列如下：

1 2 3 4 5 6 9 7 10 8

對于序列“9 7 10 8”也模擬剛才的過程，直到不可拆分出新的子序列為止。最終將會得到這樣的序列，如下

1 2 3 4 5 6 7 8 9 10

到此，排序完全結(jié)束
代碼

//求一個無序數(shù)組的中位數(shù)
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)
        {
            //左半?yún)^(qū)間找
            div = PartSort(a, low, div - 1);
        }
        else
        {
            //右半?yún)^(qū)間找
            div = PartSort(a, div + 1, high);
        }
    }
    //找到了
    return a[mid];
}

int PartSort(int a[], int start, int end)
{
    int low = start;
    int high = end;
    
    //選取關(guān)鍵字
    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;
}

單鏈表反轉(zhuǎn)

定義一個新的頭結(jié)點指針NewH -> NULL,之后定義一個臨時變量 P 指針用來進行原有鏈表的遍歷動作

比如一開始p指向的是頭結(jié)點 1 ，遍歷之后 p 移動到第二個位置2.然后把 NewH 指向節(jié)點 1，1的next指向NULL。( 一定是先移動 p 指針，否則會把原鏈表的后面部分弄丟)

接下來 p 指針移動到位置 3 ， NewH 指向節(jié)點 2 ，2的Next是原來的節(jié)點1。 一直遍歷直到 Next 為NULL

代碼的算法實現(xiàn)

.h文件

// 定義一個鏈表
struct Node {
    int data;
    struct Node *next;
};

@interface ReverseList : NSObject
// 鏈表反轉(zhuǎn)
struct Node* reverseList(struct Node *head);
// 構(gòu)造一個鏈表
struct Node* constructList(void);
// 打印鏈表中的數(shù)據(jù)
void printList(struct Node *head);

.m文件

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;
        // 當(dāng)前結(jié)點的next指向新鏈表頭部
        p->next = newH;
        // 更改新鏈表頭部為當(dāng)前結(jié)點
        newH = p;
        // 移動p指針
        p = temp;
    }
    
    // 返回反轉(zhuǎn)后的鏈表頭結(jié)點
    return newH;
}

struct Node* constructList(void)
{
    // 頭結(jié)點定義
    struct Node *head = NULL;
    // 記錄當(dāng)前尾結(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;
        }
        // 當(dāng)前結(jié)點的next為新結(jié)點
        else{
            cur->next = node;
        }
        
        // 設(shè)置當(dāng)前結(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;
    }
}


void char_reverse(char* cha)
{
    char *begin = cha;
    int a = StrLength(cha);
    char end = cha + a +1;
    
}