高频算法面试题

001什么是贪心算法？

贪心算法，看着这个名字贪心、贪婪这两字的内在含义最为关键。这就好像一个贪婪的人，他事事都想要眼前看到最好的那个，看不到长远的东西，也不为最终的结果和将来着想，贪图眼前局部的利益最大化，有点走一步看一步的感觉。
贪心算法是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。
贪心算法的基本步骤：
步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时就根据局部最优策略，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来；

002找零钱问题

假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？
这里我们需要明确的几个点：
1.货币只能25分、10分、5分和1分四种硬币；
2.找给客户41分钱的硬币；
3.硬币最少化。
思考，能使用我们今天学到的贪婪算法吗？怎么做？（回顾下贪婪算法的步骤）
1.找给顾客钱sun_money=41分钱，可选择的是25分，10分，5分和1分四种硬币。能找25分的就不找10分的原则，初次先找给顾客25分；
2.还差顾客sum_money=41-25=16。然后从25分、10分、5分和1分四种硬币选取局部最优的给顾客，也就是选10分的，此时sum_money=16-10=6。重复迭代过程，还需要sum_money=6-5=1,sum_money=1-1=0。至此，顾客收到零钱，交易结束；
3.此时41分，分成1个25分，1个10分，1个5分，1个1分，总共四枚硬币。

public static void main(String[] args){
    // 不断尝试每种硬笔
    int num25, num10, num5, num1; 
    num25=num10=num5=num1=0;
    while(money >= 25){
        num25++;
        money -= 25;
    } 
    while(money >= 10){
        num10++;
        money -= 10;
    }
    while(money >=5){
        num5++;
        money -=5;
    }
    while(money >=1){
        num1++;
        money -= 1;
    }
    System.out.println("25分有 "+num25);
    System.out.println("10分有 "+num10);
    System.out.println("5分有 "+num5);
    System.out.println("1分有 "+num1);
    return 0;
}

003会议安排问题

如何在有限的时间内有召开多个会议，要求任何两个会议不能同时进行。
如下表是会议时间表

通过会议时间表可得到比较直观的下图

我们需要选出最多的不相交的时间段，可以尝试以下的贪心策略：
(1)每次从剩下未安排会议中选出最早开始且与已安排会议不冲突的会议；
(2)每次从剩下未安排会议中选出持续时间最短且与已安排会议不冲突的会议；
(3)每次从剩下未安排会议中选出最早结束且与已安排会议不冲突的会议；
我们简单地分析一下：
如果选择最早开始时间，如果会议持续时间很长，假如8点开始，却要持续12小时，这样每天只能安排一个会议，肯定不合理；如果选择持续时间最短，则可能开始时间很晚，也不合理。因此我们最好选择开始最早而且结束时间短的会议，即最早开始时间+持续时间最短，这不就等价于选最早结束时间嘛！是不是有点儿意思~。因此，我们采用第（3）种贪心策略。

public static int bestArrange(Program[] programs, int timePoint) {
    Arrays.sort(programs, new ProgramComparator());
    int result = 0;
    // 从左往右依次遍历所有的会议
	for (int i = 0; i < programs.length; i++) {
		if (timePoint <= programs[i].start) {
			result++;
			timePoint = programs[i].end;
		}
	}
	return result;
}

004区间调度问题

给你很多形如 [start, end] 的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。举个例子，intvs = [[1,3], [2,4], [3,6]]，这些区间最多有 2 个区间互不相交，即 [[1,3], [3,6]]，你的算法应该返回 2。注意边界相同并不算相交。
思路可以分成下面三步：
1)从区间集合中选择一个区间x，这个x是所有区间中结束最早的(end最小)。
2)把所有与x区间相交的区间从区间集合中删除掉。
3)重复1和2，直到区间集合为空。之前选出的那些x的集合就是最大的不想交子集。

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
        return 0;
    }
    Arrays.sort(
        intervals,
        new Comparator < int[] > () {@
            Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
    //排序后的第一个必然可用
    int count = 1;
    int x_end = intervals[0][1];
    for (int[] interval: intervals) {
        if (interval[0] >= x_end) {
            count++;
            x_end = interval[1];
        }
    }
    return count;
}

005背包问题

用贪心算法实现背包问题的求解。背包容量为20；最优解为装入背包的物品价值总和最大。

基本思想：
1)计算所有物品的性价比;
2)按物品性价比从高到低装入，只有当高一级的性价比物品全部装入后，才会装入下一级的性价比物品;
3)装到最后无法全部装入该物品时进行部分装入;

public class GreedyBag { // 贪心算法解决的背包问题是可以部分装载的问题，不是0-1
    static float maxV = 20; // 最大容量
    float V; // 体积
    float worth; // 价值
    int i; // 物品编号
    float cost; // 性价比,单位体积价值
    static GreedyBag[] thing = new GreedyBag[6]; // 根据实际情况调整
    static float[] x = new float[thing.length]; // 物品i对应的数量在下标i-1
    public GreedyBag(int num, float V, float w) { // 物品信息初始化
        i = num;
        worth = w;
        this.V = V;
        cost = w / V;
        thing[i - 1] = this; // 添加进数组
    }
    public static void sort() { // 初始化满了再用的冒泡排序,性价比最小的沉底
        float smaller; // 存储更小的价值比
        for (int i = 0; i < thing.length; i++) {
            for (int j = 0; j < thing.length - i - 1; j++) {
                smaller = thing[j].cost;
                if (smaller < thing[j + 1].cost) { // 后面更大就交换
                    GreedyBag bigger = thing[j + 1];
                    thing[j + 1] = thing[j];
                    thing[j] = bigger;
                }
            }
        }
    }
    public static float knapsack() {
        float maxValue = 0;
        float v = 0; // 已装载体积
        int i;
        for (int j = 0; j < x.length; j++)
            x[j] = 0; // 物品的装载初始化为0
        for (i = 0; i < thing.length; i++) {
            if (v + thing[i].V > maxV)
                break; // 下标i的物品没法全部装下
            x[thing[i].i - 1] = thing[i].V; // 性价比高的全部装下
            v += thing[i].V;
            maxValue += thing[i].worth;
        }
        if (i < thing.length) { // 由break跳出的，部分装载
            float elseV = maxV - v;
            x[thing[i].i - 1] = elseV; // 部分装载
            v = maxV;
            maxValue += elseV / thing[i].V * thing[i].worth;
        }
        return maxValue;
    }
    public static void printX() { // 打印装载情况
        for (int i = 0; i < x.length; i++) {
            if (x[i] == 0)
                continue;
            System.out.println("物品编号" + (i + 1) + "装了体积" + x[i]);
        }
    }
    public static void main(String args[]) {
        GreedyBag i1 = new GreedyBag(1, 3, 6);
        GreedyBag i2 = new GreedyBag(2, 2, 5);
        GreedyBag i3 = new GreedyBag(3, 5, 10);
        GreedyBag i4 = new GreedyBag(4, 1, 2);
        GreedyBag i5 = new GreedyBag(5, 6, 16);
        GreedyBag i6 = new GreedyBag(6, 4, 8);
        sort(); // 根据性价比排序
        float maxValue = knapsack();
        System.out.println("最大能装价值" + maxValue + "的物品");
        printX();
    }
}

006什么是暴力递归？

暴力递归是把问题转化为规模缩小的同类问题的子问题 ，有明确的不需要继续进行递归的条件(base case)，有当得到了子问题的结果之后的决策过程并且不记录每一个子问题的解。

007汉诺塔问题

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。
游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。
操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

思想
假设只有一个盘子

如果有两个盘子

// 1~i 圆盘 目标是from -> to， other是另外一个
public static void func(int N, String from, String to, String other) {
    if (N == 1) { // base
        System.out.println("Move 1 from " + from + " to " + to);
    } else {
        func(N - 1, from, other, to);
        System.out.println("Move " + N + " from " + from + " to " + to);
        func(N - 1, other, to, from);
    }
}

008字符串打印

打印一个字符串的全部子序列，包括空字符串
有字符串“abc”，字符串长度为3，下标分别是0,1,2。则决策的过程一共有三个，令初始序列为空字符串。分别是：
0：此时有两种情况，要不要'a'，如果要，子序列变为“a”；如果不要则还是空字符串；
1：此时有两种情况，要不要‘b’，加上上一步的两种这里就有4种情况，这里不一一列举；
2：此时有两种情况，要不要‘c’，加上上一步的四种情况这里就有8种情况。

public class PrintAllSubsquences {
    public static void pringAllSub(char[] str, int i, String res) {
        if (i == str.length) {
            System.out.println(res);
            return;
        }
        //两种情况
        pringAllSub(str, i + 1, res);
        pringAllSub(str, i + 1, res + str[i]);
    }
    public static void main(String[] args) {
        String str = "abc";
        pringAllSub(str.toCharArray(), 0, "");
    }
}

009N皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。

思路
1. 准备一个数组record[i]，record[i] 表示 i行的皇后，放在了第几列
2. 如果第一个皇后的在i1行j1列，第二个皇后在i1行j2列，那么应该满足的条件是
       不能共斜线：|i1-i2|不等于|j1-j2|   
       不能共行： i1不等于i2   
       不能共列：j1不等于j2

public class NQueens {
    public static int num1(int n) {
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n]; // record[i] -> i行的皇后，放在了第几列
        return process1(0, record, n);
    }
    // 返回值是，摆完所有的皇后，合理的摆法有多少种
    public static int process1(int i, int[] record, int n) {
        if (i == n) { // 终止行
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) { // 当前行在i行，尝试i行所有的列  -> j
            // 当前i行的皇后，放在j列，会不会和之前(0..i-1)的皇后，不共行共列或者共斜线，
            // 如果是，认为有效
            // 如果不是，认为无效
            if (isValid(record, i, j)) {
                record[i] = j;
                res += process1(i + 1, record, n);
            }
        }
        return res;
    }
    // 返回i行皇后，放在了j列，是否有效
    public static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) { // 之前的某个k行的皇后
            if ((j == record[k]) ||(Math.abs(record[k] - j) == Math.abs(i - k))) {
                return false;
            }
        }
        return true;
    }
}

010爬楼梯问题

小明走楼梯，一次可以跨两个台阶，也可以跨一个台阶，求有n个台阶，一共有多少种跨发？
从问题中我们可以分析出，如果迈上最后一个台阶，可以是一步，也可以是两步。

分析：

可以理解为：
f(n)=f(n-1)+f(n-2)
同理：
f(n-1)=f(n-1-1）+f(n-1-2)
f(n-2)=f(n-2-1)+f(n-2-2）
. …
…
f(4)=f(3)+f(2)
f(3)=f(2)+f(1)
f(2)=2
f(1)=1

int getNum(int n) {
    if (n <= 0)return 0;	
    if (n == 1) return 1;
    if (n == 2) return 2;
    int arr = new int[n+1];
    arr[1] = 1;
    arr[2] = 2;
    for (int i = 3; i <= n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    int ret = arr[n];
    return ret;
}

011分割金条问题

你让工人为你工作7天，给工人的回报是一根金条。金条平分成相连的7段，你必须在每天结束时给他们一段金条，如果只许你两次把金条弄断，你如何给你的工人付费?
将金条分成1段、2段和4段
第⼀天给1段金条
第⼆天把1段金条要回，给2段金条
第三天给1段金条
第四天把1段和2段金条要回，给4段金条
第五天给1段金条
第六天把1段金条要回，给2段金条
第七天给1段金条

012称球问题

12个球和一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球? (注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑)
首先，把12个小球分成三等份，每份四只。
拿出其中两份放到天平两侧称（第一次）
情况1：天平是平衡的。
            那么那八个拿上去称的小球都是正常的，特殊的在四个里面。
            把剩下四个小球拿出三个放到一边，另一边放三个正常的小球（第二次）
            如天平平衡，特殊的是剩下那个。
            如果不平衡，在天平上面的那三个里。而且知道是重了还是轻了。
            剩下三个中拿两个来称，因为已经知道重轻，所以就可以知道特殊的了。（第三次）
情况2：天平倾斜。
            特殊的小球在天平的那八个里面。
            把重的一侧四个球记为A1A2A3A4，轻的记为B1B2B3B4。
            剩下的确定为四个正常的记为C。
            把A1B2B3B4放到一边，B1和三个正常的C小球放一边。（第二次）
            情况2.1：天平平衡了。
                    特殊小球在A2A3A4里面，而且知道特殊小球比较重。
                    把A2A3称一下，就知道三个里面哪个是特殊的了。（第三次）
            情况2.2：天平依然是A1的那边比较重。
                    特殊的小球在A1和B1之间。
                    随便拿一个和正常的称，就知道哪个特殊了。（第三次）
            情况2.3：天平反过来，B1那边比较重了。
                    特殊小球在B2B3B4中间，而且知道特殊小球比较轻。
                    把B2B3称一下，就知道哪个是特殊的了。（第三次）

013燃绳问题

烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢?
取3根绳
先将第一根的两头都点燃，同时将第二根的某一头点燃。(t=0)
待第一根烧尽，点燃第二根的另一头。(t=30min)
待第二根烧尽，点燃第三根的两头。(t=45min)
待第三根烧尽，t=75min。

014喝汽水问题

1元钱一瓶汽水，喝完后两个空瓶换一瓶汽水，问: 你有20元钱，最多可以喝到几瓶汽水?
最多可以喝40瓶 
首先20空瓶可以换10瓶水，10空瓶可以换5瓶水，4空瓶可以换2瓶水,2空瓶可以换1瓶水,1个空瓶加上(5-4)那个空瓶又可以换1瓶水，然后一个空瓶加借一个瓶再喝一瓶还一个瓶子。总共喝了20+10+5+2+1+1+1=40

015舀酒难题

据说有人给酒肆的老板娘出了一个难题: 此人明明知道店里只有两个舀酒的勺子，分别能舀7两和11两酒，却硬要老板娘卖给他2两酒。聪明的老板娘毫不含糊，用这两个勺子在酒缸里舀酒，并倒来倒去，居然量出了2两酒，聪明的你能做到吗?
将7装满，倒入11，再装满，倒满11两勺子。---》此时7两勺子那个里面是3。
将11倒空，7中3倒入11，再装满7倒入11。---》此时11两那个里面是10。
将7再次装满，倒满11。---》此时7两那个里面是6。
将11再次倒空，7中6倒入11。---》此时7两那个里面是0,11两里面是6两
将7再次装满，倒满11。---》此时7两那个里面是2

016拿苹果问题

桌上有100个苹果，你和另一个人一起拿，一人一次，每次拿的数量大于等于1小于等于5，问：如何拿能保证最后一个苹果由你来拿？
解答：只需要你先拿，第一次拿4个，以后看对方拿的个数，根据对方拿的个数，保证每轮对方和你拿的加起来是6就行了，其实就是保证你拿到4，还要拿到10,16...直到94。

017蛋糕切8份问题

请把一盒蛋糕切成8份，分给8个人，但蛋糕盒里还必须留有一份。
解答：面对这样的怪题，有些应聘者绞尽脑汁也无法分成；而有些应聘者却感到此题实际很简单，把切成的8份蛋糕先拿出7份分给7人，剩下的1份连蛋糕盒一起分给第8个人。

018拿最大钻石问题

一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到最大的一颗？
解答：一楼门打开，拿钻石，然后到二楼之后比较二楼和手里的钻石，谁大拿哪个，
然后到三楼之后比较三楼和手里的钻石，谁大拿哪个....依次类推，到十楼的时候就可以拿到最大的那个钻石。