注意：本文主讲算法相关面试问题，包括字符串反转、链表反转、有序数组合并、Hash算法、查找两个子视图的共同父视图、求无序数组当中的中位数。

一、字符串反转

问题:给定字符串”hello, world”, 实现将其反转.输出结果: dlrow,oleh

答:

void char_reverse(char* cha) {
    // 指向第一个字符
    char* begin = cha;
    // 指向最后一个字符
    char* end = cha + strlen(cha) - 1;

    while (begin < end) {
        // 交换前后两个字符,同时移动指针
        char temp = *begin;
        *(begin++) = *end;
        *(end--) = temp;
    }
}

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

二、链表反转

链表头插法思想

ReverseList.h

//ReverseList.h
// 定义一个链表
struct Node {
    int data;
    struct Node *next;
};
@interface ReverseList : NSObject
// 链表反转
struct Node* reverseList(struct Node *head);
// 构造一个链表
struct Node* constructList(void);
// 打印链表中的数据
void printList(struct Node *head);
@end

ReverseList.m

//ReverseList.m
@implementation ReverseList
struct Node* reverseList(struct Node *head) {
    // 定义遍历指针，初始化为头结点
    struct Node *p = head;
    // 反转后的链表头部
    struct Node *newH = NULL;

    // 遍历链表
    while (p != NULL) {

        // 记录下一个结点
        struct Node *temp = p->next;
        // 当前结点的next指向新链表头部
        p->next = newH;
        // 更改新链表头部为当前结点
        newH = p;
        // 移动p指针
        p = temp;
    }
    // 返回反转后的链表头结点
    return newH;
}

struct Node* constructList(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;

        // 头结点为空，新结点即为头结点
        if (head == NULL) {
            head = node;
        }
        // 当前结点的next为新结点
        else{
            cur->next = node;
        }
        // 设置当前结点为新结点
        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

执行调用

//单链表反转
struct Node* head = constructList();
printList(head);
printf("-----------\n");
struct Node* newHead = reverseList(head);
printList(newHead); 

三、有序数组合并

// 将有序数组a和b的值合并到一个数组result当中，且仍然保持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]) {
    int p = 0; // 遍历数组a的指针
    int q = 0; // 遍历数组b的指针
    int i = 0; // 记录当前存储位置

    // 任一数组没有到达边界则进行遍历
    while (p < aLen && q < bLen) {
        // 如果a数组对应位置的值小于b数组对应位置的值
        if (a[p] <= b[q]) {
            // 存储a数组的值
            result[i] = a[p];
            // 移动a数组的遍历指针
            p++;
        }else{
            // 存储b数组的值
            result[i] = b[q];
            // 移动b数组的遍历指针
            q++;
        }
        // 指向合并结果的下一个存储位置
        i++;
    }

    // 如果a数组有剩余
    while (p < aLen) {
        // 将a数组剩余部分拼接到合并结果的后面
        result[i] = a[p++];
        i++;
    }

    // 如果b数组有剩余
    while (q < bLen) {
        // 将b数组剩余部分拼接到合并结果的后面
        result[i] = b[q++];
        i++;
    }
}

执行调用

int a[5] = {1,4,6,7,9};
int b[8] = {2,3,5,6,8,10,11,12};

//用于存储归并结果
int result[13];
//归并操作
mergeList(a, 5, b, 8, result);
//打印归并结果
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算法

问题:在一个字符串中找到第一个只出现一次的字符
如:输入”abaccdeff” , 则输出b

算法思想:

• 字符(char)是一个长度为8的数据类型,因此总共有可能256中可能.
• 每个字母根据其ASCII码值作为数组的下标对应数组的一个数字.
• 数组中存储的是每个字符出现的次数.

哈希表
例: 给定值是字母a, 对应ASCII值是97, 数组索引下标为97.
哈希函数: 建立字母或字符到它所存储位置index的一个映射关系. f(key)
存储和查找都通过该函数, 有效提高查找效率.
f(char) => index

//查找第一个只出现一次的字符
char findFirstChar(char* cha) {
    char result = '\0';
    // 定义一个数组 用来存储各个字母出现次数
    int array[256];
    // 对数组进行初始化操作
    for (int i=0; i<256; i++) {
        array[i] =0;
    }
    // 定义一个指针 指向当前字符串头部
    char* p = cha;
    // 遍历每个字符
    while (*p != '\0') {
        // 在字母对应存储位置 进行出现次数+1操作
        array[*(p++)]++;
    }

    // 将P指针重新指向字符串头部
    p = cha;
    // 遍历每个字母的出现次数
    while (*p != '\0') {
        // 遇到第一个出现次数为1的字符，打印结果
        if (array[*p] == 1) {
            result = *p;
            break;
        }
        // 反之继续向后遍历
        p++;
    }
    return result;
}

执行结果

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

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

倒序比较找到第一个不一样的

- (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>利用快排思想(分治思想)

排序算法+中位数

• 排序算法: 冒泡排序, 快速排序, 堆排序…
• 中位数:
  当n为奇数时, (n+1)/2 ;
  当n为偶数时, (n/2 + (n/2 + 1)) / 2 ;

快排思想

快排思想: 选取关键字, 高低交替扫描

任意挑一个元素, 以该元素为支点, 划分集合为两部分.
如果左侧集合长度恰为 (n- 1)/2, 那么支点恰为中位数.
如果左侧长度恰 < (n- 1)/2, 那么中位点在右侧; 反之, 中位数在左侧.
进入相应的一侧继续寻找中位点

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){
            //左半区间找
            div = PartSort(a, low, div - 1);
        }
        else{
            //右半区间找
            div = PartSort(a, div + 1, high);
        }
    }
    //找到了
    return a[mid];
}

int PartSort(int a[], int start, int end) {
    int low = start;
    int high = end;

    //选取关键字
    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;
}

执行调用

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