iOS面试中最简单的算法问题(不断更新)

又一次好久没有更新文章了，真的是太不好了。但是这段时间以来我也不是没有收获，学了一段时间的swift，这两天又迷上了数据结构和算法，也稍微看了两眼。今天先总结下面试中可能被问到的算法问题。

1、不使用第三个变量，交换两个变量的值(这两个变量是int类型)

这个问题有两种方法
第一种：使用异或
int a = 1;
int b = 2;
    
a = a^b;
b = a^b;
a = a^b;

第二种：两数相加减
a = a + b;
b = a - b;
a = a - b;

2、假设有一个池塘种满荷花并且荷花都没有开放,当第一天的时候开出了第一朵荷花,第二天开出了两朵,第三天开出了四朵,第四天开出了八朵...荷花以每一天开放的朵数都是前一天开放的二倍,如果当第三十天的时候,池塘内的所有荷花都开放了,问哪一天的时候,这个池塘中正好有一半的荷花开放了？

答案是第二十九天的时候，池塘中正好一半的荷花开放了。

3、假设有一段由129个电线杆链接起来的128段电线,某一天这128段电线当中的一段电线断掉了,如何使用电流计快速找到断掉的位置位于哪两个电线杆之间?

利用二分法,首先整体测量第一段到第六十四段电线能不能测量到电流,
若能检测到,则这些段的电线都能排除故障,同理再去检测第六十四到第九十六段电线能不能测量到电流,利用这个方法,每次都能排除一半的几率，
用这个方法，最多只需要7次就能找到断点在哪两个电线杆之间

4、假设有十枚硬币,九枚真币和一枚假币掺杂在一起,假币和真币的重量不同,可能比真币轻,也可能比真币重,问用一个天平如何只称量三次就能找出这枚假币？

解决方法是将这十枚硬币分成四组,前三组中每一组三枚硬币,最后一组一枚硬币,先将第一组个第二组分别放在天平的两边进行称量,这时会有两种情况:
1.若天平两边重量相等,则假币没有在这六枚硬币之中,取下任意一边的一组硬币,换下第三组硬币,若此时依旧相等,那么剩下的最后一枚硬币就是假币,若此天平两边不相等,则假币在第三组中,再将第三组中的硬币依次进行称量就可以了.
2.若天平两边重量不相等,则将第二组组硬币取下,称量第三组,此时若两边重量相等,则假币在第二组硬币中,然后将第二组中的硬币依次进行称量就可以了,若两边重量不相等,则假币在第一组硬币中,然后将第一组中的硬币依次进行称量就可以了.

5、(从鸡兔同笼谈数学思维)有若干只鸡和兔在同个笼子里，从上面数，有35个头；从下面数，有94只脚。求笼中各有几只鸡和兔？需要想多种方法求解这个问题

1.列表法
没错，就是列举，暴力破解，也是计算机中解决问题常有的思路。当第一组没有鸡有35只兔子的时候，一共有140只脚，跟94差的有点多，可以5只甚至10只的增加鸡的数量，根据脚的数量再进行微调……
2.金鸡独立法
让每只鸡和兔子都做一个动作：用一半的脚站立。那么，地上还剩94/2=47只脚，每只鸡有一个脑袋一只脚，每个兔子有一个脑袋两只脚，47比35多出来的就是兔子的数，共12只兔子，也就知道23只鸡了。
3.听口令法
听口令：所有小动物抬起一只脚。地上还剩94-35=59只脚；
听口令：所有小动物再抬起一只脚。地上还剩59-35=24只脚。
鸡已经腾空，兔子双脚站立。于是24/2=12只兔子，鸡23只。
4.可乐鸡翅法
鸡有2只脚，兔子有4只脚，鸡比兔子少两只，但鸡有2个翅膀啊，假设把2个翅膀变成2只脚，那么鸡和兔子都是4只脚了，应该有35*4=140只脚，可实际只有94只，多出的140-94=46就是翅膀数，46/2=23只鸡，也就知道12只兔子了。
5.利用最常见额二元一次方程组
x+y=35;
2x+4y=94;
然后进行求解就好了

求解这道题的方法有13种不止。巧妙地利用头、脚数量之间的关系，加上各种假设和想象，能够组合出多种不同的思路。但说来说去都是数、数与数之间的关系，在数学上有集合有函数，在计算机上有数据结构有算法，更多的大千世界都是基于这最本质的数和关系，而我们认识世界也是从这些开始的，编程本身就是用数据结构和算法去描述现实世界里的逻辑。

6、假设有10层台阶,每次能走1级或者两级,问走到10级能有多少种走法？

我们可以这样想，假设我们现在还有最后一步要走，可能的情况有哪些？
 
 1.我们站在第9级上，一步1级后到达顶端；
 2.我们站在第8级上，一步2级后到达顶端；
 
 所以，最后一步可以走1级或者2级，不外乎两种情况。
 再假设，已知从0级到9级的走法有M种，从0级到8级的走法有N种，那么思考一下，从0到10级的走法和M、N有什么关系呢？从0到10级的走法一共是多少种呢？答案是M+N。
 
 也就是说，用F(n)来表示从0级到n级的走法，可得出
 F(9)=M；
 F(8)=N；
 F(10)=M+N；
 F(10)=F(9)+F(8);
 
 如果已知从0到9级的走法和从0到8级的走法，问题就有答案了，那从0级到9级的走法有多少种呢？
  我们依然这样想，还有一步就到9级，可能的情况有两种，从8到9和从7到9，已知了从0级到8级的走法有N种，如果再知道从0到7的走法有P种，那么从0到9级的走法就是N+P，那么可得出
 
 F(8)=N；
 F(7)=P；
 F(9)=N+P；
 F(9)=F(8)+F(7);
 
 把一个复杂的问题，逐步简化成简单的问题，我们继续推断，当只剩下2级台阶和1级台阶时的走法分别是2和1。不难归纳出：
 
 F(1)=1;
 F(2)=2;
 F(n)=F(n-1)+F(n-2);(n>=3)
 
 这是一个递归，有了公式和递归结束条件，就可以写出程序了。
-(int) getResultMrthod:(int)n{
    if (n < 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    return [self getResultMrthod:n - 1] + [self getResultMrthod:n-2];
    //时间复杂度为2的n次方
    //本质就是一颗二叉树
}

7、有五个海盗:老大老二老三老四老五,抢到了100个一模一样的金币,他们决定这么分:

1.首先,由老大提出分配方案,然后大家5人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则老大将被扔入大海喂鲨鱼。

2.如果老大死亡,则由老二再提出分配方案,然后大家4人进行表決,当且仅当超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。

3.以次类推,假设每个海盗都是很聪明的人,都能很理智的判断得失,从而做出选择。(即符合博弈论假设)

那么问题来了:老大该提出怎样的分配方案才能够使自己免于下海喂鱼又能获得最多的金币呢?

老大分给老三1枚金币,老四或者老五2枚金币,自己则独得97枚金币,即分配方案为(97,0
1,2,0)或(97,0,1,0,2)。五人的理性分析如下:
首先从老五开始,因为他是最安全的,没有被扔下大海的风险,因此他的策略也最为简单,即即最好前面的人全都死光光,那么他就可以独得这100枚金币了。
然后是老四,他的生存机会完全取決于前面是否还有人存活着,因为如果老大老二老三全都喂了鲨鱼,那么在只剩老四老五的情况下,不管老四提出怎样的分配方案,老五一定都会投反对票来让老四去喂鲨鱼,以独吞全部的金币。(注意题设条件:必须超过一半的人同意)因此理性的老四是不会把希望寄托在老五身上,他惟有支持老三才能绝对保证自身的性命。
接着是老三,他同样经过了上述的逻辑推理,而他将提出(100,0,0)这样的分配方案,(即
自己老三100枚金币,老四老五都是0枚)因为他知道老四哪怕一无所获,为了活命,也还是会无
条件的支持他而投赞成票的,那么再加上自己的1票就可以使他稳获这100金币了。
但是,老二也经过推理得知了老三的分配方案,那么他就会提出(98,0,1,1)的方案。因为
这个方案相对于老三的分配方案,老四和老五至少可以获得1枚金币,理性的老四和老五自然会觉得此方案对他们来说更有利而支持老二,不希望老二出局而由老三来进行分配。这样,老二就可以拿走98枚金币了。
不过!老大毕竟是老大,他也推理出了老二的分配方案。那么,他只要放弃老二,拉拢老三老四
或者老三老五即可。即提出(97,0,1,2,0)或(97,0,1,0,2)的分配方案。由于老大
的分配方案对于老三与老四老五来说,相比老二的方案可以获得更多的利益,所以他们将会投票支持老大,再加上老大自身的1票,97枚金币就都是老大的了。

8、求两个数的最大公约数

/** 1.直接遍历法 */
int maxCommonDivisor1(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 maxCommonDivisor2(int a, int b) {
    int r;
    while(a % b > 0) {
        r = a % b;
        a = b;
        b = r;
        
    }
    return b;
} // 扩展：最小公倍数 = (a * b)/最大公约数

9、模拟栈操作

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

//保护全局变量：在全局变量前加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;
}

9、有15个瓶子，其中最多有一瓶有毒，现在有四只老鼠，喝了有毒的水之后，第二天就会死。如何在第二天就可以判断出哪个瓶子有毒

我觉得大部分人首先想到的是常规思路二分法，717，但是转念一想，肯定会发现四只老鼠根本不够，其实正确的想法应该是从老鼠面去想。
一个老鼠有死和不死两种状态，也就0和1两个状态，四只老鼠有16个组合，正好是足够的。
瓶子按照1-15的二进制编码给四个老鼠喝，如8就是1110，1表示这只老鼠喝了这瓶水，0代表没有喝，最后老鼠如果死了就是0，没死还是1。
给所有瓶编上序号，第1瓶喂给第一只老鼠，第二瓶喂给第二只老鼠，第三瓶喂给第一第二只老鼠，以此类推，第十五瓶喂给所有老鼠。
根据老鼠死亡情况就能推断出有毒那瓶的序号。
总共会有以下几种情况：
0 0 0 1
    0 0 1 0
    0 0 1 1
    0 1 0 0
    0 1 0 1
    0 1 1 0
    0 1 1 1
    1 0 0 0
    1 0 0 1
    1 0 1 0
    1 0 1 1
    1 1 0 0
    1 1 0 1
    1 1 1 0
    1 1 1 1

10、给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。(序列不是有序的)。例： 例子

解法一使用集合
创建一个数组,循环 0~n 将数据添加进数组
然后通过这个数组创建集合,将得到的集合和给定的集合序列进行异或,就会得到缺失的那个数字
解放二 求和法
求出 0 到 n 之间所有的数字之和
遍历数组计算出原始数组中数字的累积和
两和相减，差值就是丢失的那个数字
解法三：二分法
将数组进行排序后，利用二分查找的方法来找到缺少的数字，注意搜索的范围为 0 到 n。
首先对数组进行排序
用元素值和下标值之间做对比，如果元素值大于下标值，则说明缺失的数字在左边，此时将 right 赋为 mid ，反之则将 left 赋为 mid + 1 。
注：由于一开始进行了排序操作，因此使用二分法的性能是不如上面两种方法。
public class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length;
        while (left < right){
            int mid = (left + right) / 2;
            if (nums[mid] > mid){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}

11、约瑟夫环问题

问题描述：编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3…这样依次报），数到 m 的 士兵会被杀死出列，之后的士兵再从 1 开始报数。直到最后剩下一士兵，求这个士兵的编号。

这道题还可以用递归来解决，递归是思路是每次我们删除了某一个士兵之后，我们就对这些士兵重新编号，然后我们的难点就是找出删除前和删除后士兵编号的映射关系。

我们定义递归函数 f(n，m) 的返回结果是存活士兵的编号，显然当 n = 1 时，f(n, m) = 1。假如我们能够找出 f(n，m) 和 f(n-1，m) 之间的关系的话，我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为

…
1
…
m - 2

m - 1

m

m + 1

m + 2
…
n
…

进行了一次删除之后，删除了编号为 m 的节点。删除之后，就只剩下 n - 1 个节点了，删除前和删除之后的编号转换关系为：

删除前     ---     删除后

…          ---      …

m - 2     ---     n - 2

m - 1    ---      n - 1

m         ----    无(因为编号被删除了)

m + 1     ---     1(因为下次就从这里报数了)

m + 2     ----     2

…         ----         …

新的环中只有 n - 1 个节点。且删除前编号为 m + 1, m + 2, m + 3 的节点成了删除后编号为 1， 2， 3 的节点。

假设 old 为删除之前的节点编号， new 为删除了一个节点之后的编号，则 old 与 new 之间的关系为 old = (new + m - 1) % n + 1。

这样，我们就得出 f(n, m) 与 f(n - 1, m)之间的关系了，而 f(1, m) = 1.所以我们可以采用递归的方式来做。
int f(int n, int m){
    if(n == 1)   return n;
    return (f(n - 1, m) + m - 1) % n + 1;
}
我去，两行代码搞定，而且时间复杂度是 O(n)，空间复杂度是O(1)，牛逼！那如果你想跟别人说，我想一行代码解决约瑟夫问题呢？答是没问题的，如下：

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}
卧槽，以后面试官让你手写约瑟夫问题，你就扔这一行代码给它。

12、Nim 游戏

游戏规则是这样的：你和你的朋友面前有一堆石子，你们轮流拿，一次至少拿一颗，最多拿三颗，谁拿走最后一颗石子谁获胜。
假设你们都很聪明，由你第一个开始拿，请你写一个算法，输入一个正整数 n，返回你是否能赢（true 或 false）。

比如现在有 4 颗石子，算法应该返回 false。因为无论你拿 1 颗 2 颗还是 3 颗，对方都能一次性拿完，拿走最后一颗石子，所以你一定会输。

首先，这道题肯定可以使用动态规划，因为显然原问题存在子问题，且子问题存在重复。但是因为你们都很聪明，涉及到你和对手的博弈，动态规划会比较复杂。

我们解决这种问题的思路一般都是反着思考：

如果我能赢，那么最后轮到我取石子的时候必须要剩下 1~3 颗石子，这样我才能一把拿完。

如何营造这样的一个局面呢？显然，如果对手拿的时候只剩 4 颗石子，那么无论他怎么拿，总会剩下 1~3 颗石子，我就能赢。

如何逼迫对手面对 4 颗石子呢？要想办法，让我选择的时候还有 5~7 颗石子，这样的话我就有把握让对方不得不面对 4 颗石子。

如何营造 5~7 颗石子的局面呢？让对手面对 8 颗石子，无论他怎么拿，都会给我剩下 5~7 颗，我就能赢。

这样一直循环下去，我们发现只要踩到 4 的倍数，就落入了圈套，永远逃不出 4 的倍数，而且一定会输。所以这道题的解法非常简单：

bool canWinNim(int n) {
    // 如果上来就踩到 4 的倍数，那就认输吧
    // 否则，可以把对方控制在 4 的倍数，必胜
    return n % 4 != 0;
}

PS：其实这个问题是一个简化版的 Nim 游戏，真正的 Nim 游戏比较复杂，不只有一堆石子，不限制一次拿的石子数。但是，这个问题最终的解法却出奇的巧妙，和异或运算有关。

13、汉诺塔问题

从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

// 将 n 个圆盘从 a 经由 b 移动到 c 上
public void hanoid(int n, char a, char b, char c) {
    if (n <= 0) {
        return;
    }
    // 将上面的  n-1 个圆盘经由 C 移到 B
    hanoid(n-1, a, c, b);
    // 此时将 A 底下的那块最大的圆盘移到 C
    move(a, c);
    // 再将 B 上的 n-1 个圆盘经由A移到 C上
    hanoid(n-1, b, a, c);
}

public void move(char a, char b) {
    printf("%c->%c\n", a, b);
}

14、细胞分裂 有一个细胞 每一个小时分裂一次，一次分裂一个子细胞，第三个小时后会死亡。那么n个小时候有多少细胞？

public int allCells(int n) {
    return aCell(n) + bCell(n) + cCell(n);
}

/**
 * 第 n 小时 a 状态的细胞数
 */
public int aCell(int n) {
    if(n==1){
        return 1;
    }else{
        return aCell(n-1)+bCell(n-1)+cCell(n-1);
    }
}

/**
 * 第 n 小时 b 状态的细胞数
 */
public int bCell(int n) {
    if(n==1){
        return 0;
    }else{
        return aCell(n-1);
    }
}
/**
 * 第 n 小时 c 状态的细胞数
 */
public int cCell(int n) {
    if(n==1 || n==2){
        return 0;
    }else{
        return bCell(n-1);
    }
}

15、反证法的运用例子

生日
先说下答案是 9.1
首先：
小明说：“我不知道老师的生日是什么时候，小强也不可能知道”
可以得出：
不可能是6.7和12.2这两个日子，原因：
反证法，因为作为day，7和2只出现1次，如果是6.7或12.2，小强知道日子，也就可以知道老师生日，小明说小强也不可能知道，故排除这两天
所以出现7日和2日的6月和12月也可以排除
还剩下3月和9月5个日子
然后小强说：“原来我不知道，但现在我知道了”
据此，剩下5个日子里，5日出现两次，小强既然知道了，也就不可能是5日的日子，3.5和9.5排出
还剩三个备选答案，3月2个，9月1个，所以9.1
在这个问题的关键点中,6月和12月的排除原因至关重要,原因:
小明说：“我不知道老师的生日是什么时候，小强也不可能知道”
“也不可能“意味着小明可以绝对的肯定，如果老师告诉他的是6月或12月，那小强是有可能知道的，既然他说不可能，那就不是这两个月份
质数
首先这个问题的答案肯定是以下几个质数中的其中一个：
11，13，17，19，
23，29，
31，37，
41，43，47，
53，59，
61，67，
71，73，79，
83，89，
97。
第一句说不知道，那表明肯定不是97，因为整个质数集合中，就97是唯一选项。所以首先排除
由此间接可知，尾数是7的数字，肯定也不是结果，所以排除
17，37，47，67
得到：
11，13，19，
23，29，
31，
41，43，
53，59，
61，
71，73，79，
83，89，
第三句说还是不知道，说明尾数是1的肯定也不是，因为存在31，61, 两个2干扰项，只有唯一项，才能顺利锁定答案。
所以排除尾数带1的。
得到：
13，19，
23，29，
43，
53，59，
73，79，
83，89，
第五句说知道了，那说明他没有任何干扰项，那就只可能是只有1项的43了