注意：本文主講算法相關(guān)面試問題，包括字符串反轉(zhuǎn)、鏈表反轉(zhuǎn)、有序數(shù)組合并、Hash算法、查找兩個(gè)子視圖的共同父視圖、求無序數(shù)組當(dāng)中的中位數(shù)。

一、字符串反轉(zhuǎn)

問題:給定字符串"hello, world", 實(shí)現(xiàn)將其反轉(zhuǎn).輸出結(jié)果: dlrow,oleh

字符串反轉(zhuǎn)

答:

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

//1.字符串反轉(zhuǎn)
char ch[] = "hello,world";
char_reverse(ch);
printf("reverse result is %s \n", ch);
//打印 reverse result is dlrow,olleh

二、鏈表反轉(zhuǎn)

鏈表頭插法思想

鏈表反轉(zhuǎn)

• ReverseList.h

//ReverseList.h
// 定義一個(gè)鏈表
struct Node {
    int data;
    struct Node *next;
};
@interface ReverseList : NSObject
// 鏈表反轉(zhuǎn)
struct Node* reverseList(struct Node *head);
// 構(gòu)造一個(gè)鏈表
struct Node* constructList(void);
// 打印鏈表中的數(shù)據(jù)
void printList(struct Node *head);
@end

• ReverseList.m

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

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

• 執(zhí)行調(diào)用

//單鏈表反轉(zhuǎn)
struct Node* head = constructList();
printList(head);
printf("-----------\n");
struct Node* newHead = reverseList(head);
printList(newHead); 

三、有序數(shù)組合并

有序數(shù)組合并

// 將有序數(shù)組a和b的值合并到一個(gè)數(shù)組result當(dāng)中，且仍然保持有序
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; // 記錄當(dāng)前存儲位置
    
    // 任一數(shù)組沒有到達(dá)邊界則進(jìn)行遍歷
    while (p < aLen && q < bLen) {
        // 如果a數(shù)組對應(yīng)位置的值小于b數(shù)組對應(yīng)位置的值
        if (a[p] <= b[q]) {
            // 存儲a數(shù)組的值
            result[i] = a[p];
            // 移動(dòng)a數(shù)組的遍歷指針
            p++;
        }else{
            // 存儲b數(shù)組的值
            result[i] = b[q];
            // 移動(dòng)b數(shù)組的遍歷指針
            q++;
        }
        // 指向合并結(jié)果的下一個(gè)存儲位置
        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++;
    }
}

• 執(zhí)行調(diào)用

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算法

問題:在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符
如:輸入"abaccdeff" , 則輸出b

算法思想:

• 字符(char)是一個(gè)長度為8的數(shù)據(jù)類型,因此總共有可能256中可能.
• 每個(gè)字母根據(jù)其ASCII碼值作為數(shù)組的下標(biāo)對應(yīng)數(shù)組的一個(gè)數(shù)字.
• 數(shù)組中存儲的是每個(gè)字符出現(xiàn)的次數(shù).

哈希表
例: 給定值是字母a, 對應(yīng)ASCII值是97, 數(shù)組索引下標(biāo)為97.
哈希函數(shù): 建立字母或字符到它所存儲位置index的一個(gè)映射關(guān)系. f(key)
存儲和查找都通過該函數(shù), 有效提高查找效率.
f(char) => index

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

• 執(zhí)行結(jié)果

char cha[] = "abaccdeff";
char fc = findFirstChar(cha);
printf("this char is %c \n", fc);
//輸出this char is b

五、查找兩個(gè)子視圖的共同父視圖

• 倒序比較找到第一個(gè)不一樣的

- (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther {
    NSMutableArray *result = [NSMutableArray array];
    
    // 查找第一個(gè)視圖的所有父視圖
    NSArray *arrayOne = [self findSuperViews:viewOne];
    // 查找第二個(gè)視圖的所有父視圖
    NSArray *arrayOther = [self findSuperViews:viewOther];
    
    int i = 0;
    // 越界限制條件
    while (i < MIN((int)arrayOne.count, (int)arrayOther.count)) {
        // 倒序方式獲取各個(gè)視圖的父視圖
        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;
}

六、求無序數(shù)組當(dāng)中的中位數(shù)

方案:

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

排序算法+中位數(shù)

• 排序算法: 冒泡排序, 快速排序, 堆排序...
• 中位數(shù):
  當(dāng)n為奇數(shù)時(shí), (n+1)/2 ;
  當(dāng)n為偶數(shù)時(shí), (n/2 + (n/2 + 1)) / 2 ;

快排思想

快排思想

• 快排思想: 選取關(guān)鍵字, 高低交替掃描

任意挑一個(gè)元素, 以該元素為支點(diǎn), 劃分集合為兩部分.
如果左側(cè)集合長度恰為 (n- 1)/2, 那么支點(diǎn)恰為中位數(shù).
如果左側(cè)長度恰 < (n- 1)/2, 那么中位點(diǎn)在右側(cè); 反之, 中位數(shù)在左側(cè).
進(jìn)入相應(yīng)的一側(cè)繼續(xù)尋找中位點(diǎn)

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;
}

• 執(zhí)行調(diào)用

int list[9] = {12,3,10,8,6,7,11,13,9};
// 3 6 7 8 9 10 11 12 13
//             ^
int median = findMedian(list, 9);
printf("the median is %d \n", median);
// the median is 9