iOS面试题：算法与数据结构

1、不用中间变量,用两种方法交换A和B的值

// 1.中间变量
void swap(int a, int b) {
   int temp = a;
   a = b;
   b = temp;
}

// 2.加法
void swap(int a, int b) {
   a = a + b;
   b = a - b;
   a = a - b;
}

// 3.异或（相同为0，不同为1. 可以理解为不进位加法）
void swap(int a, int b) {
   a = a ^ b;
   b = a ^ b;
   a = a ^ b;
}

2、求最大公约数

/** 1.直接遍历法 */
int maxCommonDivisor(int a, int b) {
    int max = 0;
    for (int i = 1; i <=b; i++) {
        if (a % i == 0 && b % i == 0) {
            max = i;
        }
    }
    return max;
}
/** 2.辗转相除法 */
int maxCommonDivisor(int a, int b) {
    int r;
    while(a % b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return b;
}

// 扩展：最小公倍数 = (a * b)/最大公约数

3、模拟栈操作

• 栈是一种数据结构，特点：先进后出 -
• 练习：使用全局变量模拟栈的操作

#include <stdio.h>
#include <stdbool.h>
#include <assert.h>

//保护全局变量：在全局变量前加static后，这个全局变量就只能在本文件中使用
static int data[1024];//栈最多能保存1024个数据
static int count = 0;//目前已经放了多少个数(相当于栈顶位置)

//数据入栈 push
void push(int x){
    assert(!full());//防止数组越界
    data[count++] = x;
}
//数据出栈 pop
int pop(){
    assert(!empty());
    return data[--count];
}
//查看栈顶元素 top
int top(){
    assert(!empty());
    return data[count-1];
}

//查询栈满 full
bool full() {
    if(count >= 1024) {
        return 1;
    }
     return 0; 
}

//查询栈空 empty
bool empty() {
    if(count <= 0) {
        return 1;
    }
    return 0;
}

int main(){
    //入栈
    for (int i = 1; i <= 10; i++) {
        push(i);
    }
  
    //出栈
    while(!empty()){
        printf("%d ", top()); //栈顶元素
        pop(); //出栈
    }
    printf("\n");
    
    return 0;
}

4、排序算法

选择排序、冒泡排序、插入排序三种排序算法可以总结为如下：
都将数组分为已排序部分和未排序部分。

1.选择排序将已排序部分定义在左端，然后选择未排序部分的最小元素和未排序部分的第一个元素交换。

2.冒泡排序将已排序部分定义在右端，在遍历未排序部分的过程执行交换，将最大元素交换到最右端。

3.插入排序将已排序部分定义在左端，将未排序部分元的第一个元素插入到已排序部分合适的位置。

4.1、选择排序

• 【选择排序】：最值出现在起始端
• 第1趟：在n个数中找到最小(大)数与第一个数交换位置
• 第2趟：在剩下n-1个数中找到最小(大)数与第二个数交换位置
• 重复这样的操作...依次与第三个、第四个...数交换位置
• 第n-1趟，最终可实现数据的升序（降序）排列。

void selectSort(int *arr, int length) {
    for (int i = 0; i < length - 1; i++) { //趟数
        for (int j = i + 1; j < length; j++) { //比较次数
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

4.2、冒泡排序

• 【冒泡排序】：相邻元素两两比较，比较完一趟，最值出现在末尾
• 第1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n个元素位置
• 第2趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n-1个元素位置
• …… ……
• 第n-1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第2个元素位置

void bublleSort(int *arr, int length) {
    for(int i = 0; i < length - 1; i++) { //趟数
        for(int j = 0; j < length - i - 1; j++) { //比较次数
            if(arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        } 
    }
}

文章篇幅有限，需要更多的iOS最新面试题及答案文档，点击下载即可！

5、折半查找（二分查找）

折半查找：优化查找时间（不用遍历全部数据）
折半查找的原理：

• 1> 数组必须是有序的
• 2> 必须已知min和max（知道范围）
• 3> 动态计算mid的值，取出mid对应的值进行比较
• 4> 如果mid对应的值大于要查找的值，那么max要变小为mid-1
• 5> 如果mid对应的值小于要查找的值，那么min要变大为mid+1

// 已知一个有序数组, 和一个key, 要求从数组中找到key对应的索引位置

int findKey(int *arr, int length, int key) {
    int min = 0, max = length - 1, mid;
    while (min <= max) {
        mid = (min + max) / 2; //计算中间值
        if (key > arr[mid]) {
            min = mid + 1;
        } else if (key < arr[mid]) {
            max = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

6、集合结构 线性结构 树形结构 图形结构

• 1.1、集合结构 说白了就是一个集合，就是一个圆圈中有很多个元素，元素与元素之间没有任何关系 这个很简单
• 1.2、线性结构 说白了就是一个条线上站着很多个人。 这条线不一定是直的。也可以是弯的。也可以是值的 相当于一条线被分成了好几段的样子 （发挥你的想象力）。 线性结构是一对一的关系
• 1.3、树形结构 说白了 做开发的肯定或多或少的知道xml 解析 树形结构跟他非常类似。也可以想象成一个金字塔。树形结构是一对多的关系
• 1.4、图形结构 这个就比较复杂了。他呢 无穷。无边 无向（没有方向）图形机构 你可以理解为多对多 类似于我们人的交集关系

7、数据结构的存储

数据结构的存储一般常用的有两种 顺序存储结构 和 链式存储结构

• 2.1 顺序存储结构

发挥想象力啊。 举个列子。数组。1-2-3-4-5-6-7-8-9-10。这个就是一个顺序存储结构 ，存储是按顺序的 举例说明啊。 栈。做开发的都熟悉。栈是先进后出 ，后进先出的形式 对不对 ？！他的你可以这样理解

hello world 在栈里面从栈底到栈顶的逻辑依次为 h-e-l-l-o-w-o-r-l-d 这就是顺序存储 再比如 队列 ，队列是先进先出的对吧，从头到尾 h-e-l-l-o-w-o-r-l-d 就是这样排对的

• 2.2 链式存储结构

再次发挥想象力 这个稍微复杂一点 这个图片我一直弄好 ，回头找美工问问，再贴上 例如 还是一个数组

1-2-3-4-5-6-7-8-9-10 链式存储就不一样了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每个数字后面跟着一个地址 而且存储形式不再是顺序 ，也就说顺序乱了，1（地址） 1后面跟着的这个地址指向的是2，2后面的地址指向的是3，3后面的地址指向是谁你应该清楚了吧。他执行的时候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存储的时候就是完全随机的。明白了？！

8、单向链表\双向链表\循环链表

还是举例子。理解最重要。不要去死记硬背 哪些什么。定义啊。逻辑啊。理解才是最重要滴

• 3.1 单向链表

A->B->C->D->E->F->G->H. 这就是单向链表 H 是头 A 是尾 像一个只有一个头的火车一样 只能一个头拉着跑

• 3.2 双向链表

数组和链表区别：
数组：数组元素在内存上连续存放，可以通过下标查找元素；插入、删除需要移动大量元素，比较适用于元素很少变化的情况
链表：链表中的元素在内存中不是顺序存储的，查找慢，插入、删除只需要对元素指针重新赋值，效率高

• 3.3 循环链表

循环链表是与单向链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。发挥想象力 A->B->C->D->E->F->G->H->A. 绕成一个圈。就像蛇吃自己的这就是循环 不需要去死记硬背哪些理论知识。

9、二叉树／平衡二叉树

• 9.1 什么是二叉树

树形结构下,两个节点以内 都称之为二叉树 不存在大于2 的节点 分为左子树 右子树 有顺序 不能颠倒 ，懵逼了吧，你肯定会想这是什么玩意，什么左子树右子树 ，都什么跟什么鬼？ 现在我以普通话再讲一遍，你把二叉树看成一个人 ，人的头呢就是树的根 ，左子树就是左手，右子树就是右手，左右手可以都没有（残疾嘛，声明一下，绝非歧视残疾朋友，勿怪，勿怪就是举个例子，i am very sorry） , 左右手呢可以有一个，就是不能颠倒。这样讲应该明白了吧

二叉树有五种表现形式

1.空的树（没有节点）可以理解为什么都没 像空气一样
2.只有根节点。 （理解一个人只有一个头 其他的什么都没，说的有点恐怖）
3.只有左子树 （一个头 一个左手 感觉越来越写不下去了）
4.只有右子树
5.左右子树都有

二叉树可以转换成森林 树也可以转换成二叉树。这里就不介绍了 你做项目绝对用不到
数据结构大致介绍这么多吧。理解为主, 别死记，死记没什么用

10、算法-------过河问题

题目来源POJ 题号为1700 http://poj.org/problem?id=1700

描述

一群N人希望用一条船过河，这条船最多只能载两个人。因此，必须安排某种穿梭安排，才能来回划船，以便所有人都能过关。每个人都有不同的划船速度；一对选手的速度取决于速度较慢的人的速度。你的工作是确定一个策略，尽量减少这些人的过河时间。

输入

输入的第一行包含一个整数T(1<=T<=20)，测试用例数。接下来是T个案例。每个案例的第一行包含N，第二行包含N个整数，给出每个人过河的时间。每个案例前面都有一个空白行。不会有超过1000人，没有人需要超过100秒的跨越。

输出量

对于每个测试用例，打印一行，其中包含所有N个人过河所需的总秒数。

样本输入

1
4
1 2 5 10

样本输出

17

===========

问题分析

（以下N人速度分别用abcd…表示，且按速度升序排序）

1.当n= 1时，time则为a
2.当n= 2时，time则为b
3.当n= 3时，time则为a+b+c（a与任意一个人过河，a再回来，再和剩下的人过河）
4.当n>= 4 时，问题就复杂很多，因为任意两人过河，再在过了河中其中一个再回来有很多情况，我们这里需要进行分析

观察题目我们可以发现过河中有两个最为重要的点：
方案【1】过河的两个人，花费时间是由最长的人决定
针对这一点，我们可以把最慢d的和次慢c的放一起，这样次慢的时间c就被忽略。
方案【2】回来的一个人，花费时间只由他一个人决定
针对这一点，我们可以让最快的a把其他人一一送过去，再由最快的a把船送回来

将上面的方案实现

当n = 4时（以下N人速度分别用abcd…表示，且按速度升序排序）（）内表示花费时间
方案【1】abcd
ab（b）过去
a （a）回来
cd（d）过去
b（b）回来
ab（b）过去
所花费时间：a+3b+d

方案【2】abcd
ad（d）过去
a（a）回来
ac（c）过去
a（a）回来
ab（b）过去
所花费时间：2a+b+c+d

计算样例

现在我们导入题目样例{1，2，5，10}
方案【1】时间 = 17
方案【2】时间 = 19
所以用方案【1】花费时间最短，时间为17

但如果我们修改一下数据{1，2，2，10}
方案【1】时间 = 17
方案【2】时间 = 16
这次却是方案【2】花费的时间最短，时间为16；

如果我们将两个方案的所花费时间约一下则
方案【1】：2b
方案【2】：a+c
可以看出所花费的时间 决定性因素 在于最快的a和次快的b和次慢的c，我们只需要将2b和a+c进行比较，选择花费时间最小的方案即可。

当n > 4 时我们可以表示为用最快的前两个人运送最慢的后两个人便可，运送完人数就减少2。

11、字符串反转

给定字符串 "hello,world",实现将其反转。输出结果：dlrow,olleh

- (void)charReverse
{
    NSString * string = @"hello,world";
    
    NSLog(@"%@",string);
    
    NSMutableString * reverString = [NSMutableString stringWithString:string];
    
    for (NSInteger i = 0; i < (string.length + 1)/2; i++) {
        
        [reverString replaceCharactersInRange:NSMakeRange(i, 1) withString:[string substringWithRange:NSMakeRange(string.length - i - 1, 1)]];
        
        [reverString replaceCharactersInRange:NSMakeRange(string.length - i - 1, 1) withString:[string substringWithRange:NSMakeRange(i, 1)]];
    }
    
    NSLog(@"reverString:%@",reverString);
    
    //C
    char ch[100];
    
    memcpy(ch, [string cStringUsingEncoding:NSUTF8StringEncoding], [string length]);

   //设置两个指针，一个指向字符串开头，一个指向字符串末尾
    char * begin = ch;
    
    char * end = ch + strlen(ch) - 1;
   
//遍历字符数组，逐步交换两个指针所指向的内容，同时移动指针到对应的下个位置，直至begin>=end 
    while (begin < end) {
        
        char temp = *begin;
        
        *(begin++) = *end;
        
        *(end--) = temp;
    }
    
    NSLog(@"reverseChar[]:%s",ch);
}

12、序数组合并

将有序数组 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合并为
{1,2,3,4,5,6,6,7,8,9,9,10,11,12}

- (void)orderListMerge
{
    int aLen = 5,bLen = 9;
    
    int a[] = {1,4,6,7,9};
    
    int b[] = {2,3,5,6,8,9,10,11,12};
    
    [self printList:a length:aLen];
    
    [self printList:b length:bLen];
    
    int result[14];
    
    int p = 0,q = 0,i = 0;//p和q分别为a和b的下标，i为合并结果数组的下标
    
    //任一数组没有达到s边界则进行遍历
    while (p < aLen && q < bLen) {
        
        //如果a数组对应位置的值小于b数组对应位置的值,则存储a数组的值，并移动a数组的下标与合并结果数组的下标
        if (a[p] < b[q]) result[i++] = a[p++];
        
        //否则存储b数组的值，并移动b数组的下标与合并结果数组的下标
        else result[i++] = b[q++];
    }
    
    //如果a数组有剩余，将a数组剩余部分拼接到合并结果数组的后面
    while (++p < aLen) {
        
        result[i++] = a[p];
    }
    
    //如果b数组有剩余，将b数组剩余部分拼接到合并结果数组的后面
    while (q < bLen) {
        
        result[i++] = b[q++];
    }
    
    [self printList:result length:aLen + bLen];
}
- (void)printList:(int [])list length:(int)length
{
    for (int i = 0; i < length; i++) {
        
        printf("%d ",list[i]);
    }
    
    printf("\n");
}

13、HASH算法

• 哈希表
  例：给定值是字母a，对应ASCII码值是97，数组索引下标为97。
  这里的ASCII码，就算是一种哈希函数，存储和查找都通过该函数，有效地提高查找效率。

• 在一个字符串中找到第一个只出现一次的字符。如输入"abaccdeff"，输出'b'字符(char)是一个长度为8的数据类型，因此总共有256种可能。每个字母根据其ASCII码值作为数组下标对应数组种的一个数字。数组中存储的是每个字符出现的次数。

- (void)hashTest
{
    NSString * testString = @"hhaabccdeef";
    
    char testCh[100];
    
    memcpy(testCh, [testString cStringUsingEncoding:NSUTF8StringEncoding], [testString length]);
    
    int list[256];
    
    for (int i = 0; i < 256; i++) {
        
        list[i] = 0;
    }
    
    char *p = testCh;
    
    char result = '\0';
    
    while (*p != result) {
        
        list[*(p++)]++;
    }
    
    p = testCh;
    
    while (*p != result) {
        
        if (list[*p] == 1) {

            result = *p;
            
            break;
        }
        
        p++;
    }
    
    printf("result:%c",result);
}

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

思路:分别记录两个子视图的所有父视图并保存到数组中，然后倒序寻找,直至找到第一个不一样的父视图。

- (void)findCommonSuperViews:(UIView *)view1 view2:(UIView *)view2
{
    NSArray * superViews1 = [self findSuperViews:view1];
    
    NSArray * superViews2 = [self findSuperViews:view2];
    
    NSMutableArray * resultArray = [NSMutableArray array];
    
    int i = 0;
    
    while (i < MIN(superViews1.count, superViews2.count)) {
        
        UIView *super1 = superViews1[superViews1.count - i - 1];
        
        UIView *super2 = superViews2[superViews2.count - i - 1];
        
        if (super1 == super2) {
            
            [resultArray addObject:super1];
            
            i++;
            
        }else{
            
            break;
        }
    }
    
    NSLog(@"resultArray:%@",resultArray);
    
}
- (NSArray <UIView *>*)findSuperViews:(UIView *)view
{
    UIView * temp = view.superview;
    
    NSMutableArray * result = [NSMutableArray array];
    
    while (temp) {
        
        [result addObject:temp];
        
        temp = temp.superview;
    }
    
    return result;
}

15、求无序数组中的中位数

中位数：当数组个数n为奇数时，为(n + 1)/2，即是最中间那个数字；当n为偶数时，为(n/2 + (n/2 + 1))/2,即是中间两个数字的平均数。
首先要先去了解一些几种排序算法:iOS排序算法
思路:

• 1.排序算法+中位数
  首先用冒泡排序、快速排序、堆排序、希尔排序等排序算法将所给数组排序，然后取出其中位数即可。
• 2.利用快排思想

好啦，目前总结的就只有这么多了，不过小编有自己的iOS交流群，群内已经上传好了一些完整的面试题以及答案，还有学习资料，需要的点击下载即可！