001什么是貪心算法？

貪心算法，看著這個(gè)名字貪心、貪婪這兩字的內(nèi)在含義最為關(guān)鍵。這就好像一個(gè)貪婪的人，他事事都想要眼前看到最好的那個(gè)，看不到長(zhǎng)遠(yuǎn)的東西，也不為最終的結(jié)果和將來(lái)著想，貪圖眼前局部的利益最大化，有點(diǎn)走一步看一步的感覺(jué)。
貪心算法是尋找最優(yōu)解問(wèn)題的常用方法，這種方法模式一般將求解過(guò)程分成若干個(gè)步驟，但每個(gè)步驟都應(yīng)用貪心原則，選取當(dāng)前狀態(tài)下最好/最優(yōu)的選擇（局部最有利的選擇），并以此希望最后堆疊出的結(jié)果也是最好/最優(yōu)的解。
貪心算法的基本步驟：
步驟1：從某個(gè)初始解出發(fā)；
步驟2：采用迭代的過(guò)程，當(dāng)可以向目標(biāo)前進(jìn)一步時(shí)就根據(jù)局部最優(yōu)策略，得到一部分解，縮小問(wèn)題規(guī)模；
步驟3：將所有解綜合起來(lái)；

002找零錢問(wèn)題

假設(shè)你開(kāi)了間小店，不能電子支付，錢柜里的貨幣只有 25 分、10 分、5 分和 1 分四種硬幣，如果你是售貨員且要找給客戶 41 分錢的硬幣，如何安排才能找給客人的錢既正確且硬幣的個(gè)數(shù)又最少？
這里我們需要明確的幾個(gè)點(diǎn)：
1.貨幣只能25分、10分、5分和1分四種硬幣；
2.找給客戶41分錢的硬幣；
3.硬幣最少化。
思考，能使用我們今天學(xué)到的貪婪算法嗎？怎么做？（回顧下貪婪算法的步驟）
1.找給顧客錢sun_money=41分錢，可選擇的是25分，10分，5分和1分四種硬幣。能找25分的就不找10分的原則，初次先找給顧客25分；
2.還差顧客sum_money=41-25=16。然后從25分、10分、5分和1分四種硬幣選取局部最優(yōu)的給顧客，也就是選10分的，此時(shí)sum_money=16-10=6。重復(fù)迭代過(guò)程，還需要sum_money=6-5=1,sum_money=1-1=0。至此，顧客收到零錢，交易結(jié)束；
3.此時(shí)41分，分成1個(gè)25分，1個(gè)10分，1個(gè)5分，1個(gè)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會(huì)議安排問(wèn)題

如何在有限的時(shí)間內(nèi)有召開(kāi)多個(gè)會(huì)議，要求任何兩個(gè)會(huì)議不能同時(shí)進(jìn)行。
如下表是會(huì)議時(shí)間表

通過(guò)會(huì)議時(shí)間表可得到比較直觀的下圖

我們需要選出最多的不相交的時(shí)間段，可以嘗試以下的貪心策略：
(1)每次從剩下未安排會(huì)議中選出最早開(kāi)始且與已安排會(huì)議不沖突的會(huì)議；
(2)每次從剩下未安排會(huì)議中選出持續(xù)時(shí)間最短且與已安排會(huì)議不沖突的會(huì)議；
(3)每次從剩下未安排會(huì)議中選出最早結(jié)束且與已安排會(huì)議不沖突的會(huì)議；
我們簡(jiǎn)單地分析一下：
如果選擇最早開(kāi)始時(shí)間，如果會(huì)議持續(xù)時(shí)間很長(zhǎng)，假如8點(diǎn)開(kāi)始，卻要持續(xù)12小時(shí)，這樣每天只能安排一個(gè)會(huì)議，肯定不合理；如果選擇持續(xù)時(shí)間最短，則可能開(kāi)始時(shí)間很晚，也不合理。因此我們最好選擇開(kāi)始最早而且結(jié)束時(shí)間短的會(huì)議，即最早開(kāi)始時(shí)間+持續(xù)時(shí)間最短，這不就等價(jià)于選最早結(jié)束時(shí)間嘛！是不是有點(diǎn)兒意思~。因此，我們采用第（3）種貪心策略。

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

004區(qū)間調(diào)度問(wèn)題

給你很多形如 [start, end] 的閉區(qū)間，請(qǐng)你設(shè)計(jì)一個(gè)算法，算出這些區(qū)間中最多有幾個(gè)互不相交的區(qū)間。舉個(gè)例子，intvs = [[1,3], [2,4], [3,6]]，這些區(qū)間最多有 2 個(gè)區(qū)間互不相交，即 [[1,3], [3,6]]，你的算法應(yīng)該返回 2。注意邊界相同并不算相交。
思路可以分成下面三步：
1)從區(qū)間集合中選擇一個(gè)區(qū)間x，這個(gè)x是所有區(qū)間中結(jié)束最早的(end最小)。
2)把所有與x區(qū)間相交的區(qū)間從區(qū)間集合中刪除掉。
3)重復(fù)1和2，直到區(qū)間集合為空。之前選出的那些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];
            }
        });
    //排序后的第一個(gè)必然可用
    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背包問(wèn)題

用貪心算法實(shí)現(xiàn)背包問(wèn)題的求解。背包容量為20；最優(yōu)解為裝入背包的物品價(jià)值總和最大。

基本思想：
1)計(jì)算所有物品的性價(jià)比;
2)按物品性價(jià)比從高到低裝入，只有當(dāng)高一級(jí)的性價(jià)比物品全部裝入后，才會(huì)裝入下一級(jí)的性價(jià)比物品;
3)裝到最后無(wú)法全部裝入該物品時(shí)進(jìn)行部分裝入;

public class GreedyBag { // 貪心算法解決的背包問(wèn)題是可以部分裝載的問(wèn)題，不是0-1
    static float maxV = 20; // 最大容量
    float V; // 體積
    float worth; // 價(jià)值
    int i; // 物品編號(hào)
    float cost; // 性價(jià)比,單位體積價(jià)值
    static GreedyBag[] thing = new GreedyBag[6]; // 根據(jù)實(shí)際情況調(diào)整
    static float[] x = new float[thing.length]; // 物品i對(duì)應(yīng)的數(shù)量在下標(biāo)i-1
    public GreedyBag(int num, float V, float w) { // 物品信息初始化
        i = num;
        worth = w;
        this.V = V;
        cost = w / V;
        thing[i - 1] = this; // 添加進(jìn)數(shù)組
    }
    public static void sort() { // 初始化滿了再用的冒泡排序,性價(jià)比最小的沉底
        float smaller; // 存儲(chǔ)更小的價(jià)值比
        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; // 下標(biāo)i的物品沒(méi)法全部裝下
            x[thing[i].i - 1] = thing[i].V; // 性價(jià)比高的全部裝下
            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("物品編號(hào)" + (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(); // 根據(jù)性價(jià)比排序
        float maxValue = knapsack();
        System.out.println("最大能裝價(jià)值" + maxValue + "的物品");
        printX();
    }
}

006什么是暴力遞歸？

暴力遞歸是把問(wèn)題轉(zhuǎn)化為規(guī)模縮小的同類問(wèn)題的子問(wèn)題 ，有明確的不需要繼續(xù)進(jìn)行遞歸的條件(base case)，有當(dāng)?shù)玫搅俗訂?wèn)題的結(jié)果之后的決策過(guò)程并且不記錄每一個(gè)子問(wèn)題的解。

007漢諾塔問(wèn)題

相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號(hào)A、B、C)，在A桿自下而上、由大到小按順序放置64個(gè)金盤。
游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。
操作規(guī)則：每次只能移動(dòng)一個(gè)盤子，并且在移動(dòng)過(guò)程中三根桿上都始終保持大盤在下，小盤在上，操作過(guò)程中盤子可以置于A、B、C任一桿上。

思想
假設(shè)只有一個(gè)盤子

如果有兩個(gè)盤子

// 1~i 圓盤 目標(biāo)是from -> to， other是另外一個(gè)
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字符串打印

打印一個(gè)字符串的全部子序列，包括空字符串
有字符串“abc”，字符串長(zhǎng)度為3，下標(biāo)分別是0,1,2。則決策的過(guò)程一共有三個(gè)，令初始序列為空字符串。分別是：
0：此時(shí)有兩種情況，要不要'a'，如果要，子序列變?yōu)?ldquo;a”；如果不要?jiǎng)t還是空字符串；
1：此時(shí)有兩種情況，要不要‘b’，加上上一步的兩種這里就有4種情況，這里不一一列舉；
2：此時(shí)有兩種情況，要不要‘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皇后問(wèn)題

n 皇后問(wèn)題研究的是如何將 n 個(gè)皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊（同一行、同一列、同一斜線上的皇后都會(huì)自動(dòng)攻擊）。

思路
1. 準(zhǔn)備一個(gè)數(shù)組record[i]，record[i] 表示 i行的皇后，放在了第幾列
2. 如果第一個(gè)皇后的在i1行j1列，第二個(gè)皇后在i1行j2列，那么應(yīng)該滿足的條件是
       不能共斜線：|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++) { // 當(dāng)前行在i行，嘗試i行所有的列  -> j
            // 當(dāng)前i行的皇后，放在j列，會(huì)不會(huì)和之前(0..i-1)的皇后，不共行共列或者共斜線，
            // 如果是，認(rèn)為有效
            // 如果不是，認(rèn)為無(wú)效
            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++) { // 之前的某個(gè)k行的皇后
            if ((j == record[k]) ||(Math.abs(record[k] - j) == Math.abs(i - k))) {
                return false;
            }
        }
        return true;
    }
}

010爬樓梯問(wèn)題

小明走樓梯，一次可以跨兩個(gè)臺(tái)階，也可以跨一個(gè)臺(tái)階，求有n個(gè)臺(tái)階，一共有多少種跨發(fā)？
從問(wèn)題中我們可以分析出，如果邁上最后一個(gè)臺(tái)階，可以是一步，也可以是兩步。

分析：

可以理解為：
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分割金條問(wèn)題

你讓工人為你工作7天，給工人的回報(bào)是一根金條。金條平分成相連的7段，你必須在每天結(jié)束時(shí)給他們一段金條，如果只許你兩次把金條弄斷，你如何給你的工人付費(fèi)?
將金條分成1段、2段和4段
第?天給1段金條
第?天把1段金條要回，給2段金條
第三天給1段金條
第四天把1段和2段金條要回，給4段金條
第五天給1段金條
第六天把1段金條要回，給2段金條
第七天給1段金條

012稱球問(wèn)題

12個(gè)球和一個(gè)天平，現(xiàn)知道只有一個(gè)和其它的重量不同，問(wèn)怎樣稱才能用三次就找到那個(gè)球? (注意此題并未說(shuō)明那個(gè)球的重量是輕是重，所以需要仔細(xì)考慮)
首先，把12個(gè)小球分成三等份，每份四只。
拿出其中兩份放到天平兩側(cè)稱（第一次）
情況1：天平是平衡的。
            那么那八個(gè)拿上去稱的小球都是正常的，特殊的在四個(gè)里面。
            把剩下四個(gè)小球拿出三個(gè)放到一邊，另一邊放三個(gè)正常的小球（第二次）
            如天平平衡，特殊的是剩下那個(gè)。
            如果不平衡，在天平上面的那三個(gè)里。而且知道是重了還是輕了。
            剩下三個(gè)中拿兩個(gè)來(lái)稱，因?yàn)橐呀?jīng)知道重輕，所以就可以知道特殊的了。（第三次）
情況2：天平傾斜。
            特殊的小球在天平的那八個(gè)里面。
            把重的一側(cè)四個(gè)球記為A1A2A3A4，輕的記為B1B2B3B4。
            剩下的確定為四個(gè)正常的記為C。
            把A1B2B3B4放到一邊，B1和三個(gè)正常的C小球放一邊。（第二次）
            情況2.1：天平平衡了。
                    特殊小球在A2A3A4里面，而且知道特殊小球比較重。
                    把A2A3稱一下，就知道三個(gè)里面哪個(gè)是特殊的了。（第三次）
            情況2.2：天平依然是A1的那邊比較重。
                    特殊的小球在A1和B1之間。
                    隨便拿一個(gè)和正常的稱，就知道哪個(gè)特殊了。（第三次）
            情況2.3：天平反過(guò)來(lái)，B1那邊比較重了。
                    特殊小球在B2B3B4中間，而且知道特殊小球比較輕。
                    把B2B3稱一下，就知道哪個(gè)是特殊的了。（第三次）

013燃繩問(wèn)題

燒一根不均勻的繩，從頭燒到尾總共需要1個(gè)小時(shí)。現(xiàn)在有若干條材質(zhì)相同的繩子，問(wèn)如何用燒繩的方法來(lái)計(jì)時(shí)一個(gè)小時(shí)十五分鐘呢?
取3根繩
先將第一根的兩頭都點(diǎn)燃，同時(shí)將第二根的某一頭點(diǎn)燃。(t=0)
待第一根燒盡，點(diǎn)燃第二根的另一頭。(t=30min)
待第二根燒盡，點(diǎn)燃第三根的兩頭。(t=45min)
待第三根燒盡，t=75min。

014喝汽水問(wèn)題

1元錢一瓶汽水，喝完后兩個(gè)空瓶換一瓶汽水，問(wèn): 你有20元錢，最多可以喝到幾瓶汽水?
最多可以喝40瓶 
首先20空瓶可以換10瓶水，10空瓶可以換5瓶水，4空瓶可以換2瓶水,2空瓶可以換1瓶水,1個(gè)空瓶加上(5-4)那個(gè)空瓶又可以換1瓶水，然后一個(gè)空瓶加借一個(gè)瓶再喝一瓶還一個(gè)瓶子。總共喝了20+10+5+2+1+1+1=40

015舀酒難題

據(jù)說(shuō)有人給酒肆的老板娘出了一個(gè)難題: 此人明明知道店里只有兩個(gè)舀酒的勺子，分別能舀7兩和11兩酒，卻硬要老板娘賣給他2兩酒。聰明的老板娘毫不含糊，用這兩個(gè)勺子在酒缸里舀酒，并倒來(lái)倒去，居然量出了2兩酒，聰明的你能做到嗎?
將7裝滿，倒入11，再裝滿，倒?jié)M11兩勺子。---》此時(shí)7兩勺子那個(gè)里面是3。
將11倒空，7中3倒入11，再裝滿7倒入11。---》此時(shí)11兩那個(gè)里面是10。
將7再次裝滿，倒?jié)M11。---》此時(shí)7兩那個(gè)里面是6。
將11再次倒空，7中6倒入11。---》此時(shí)7兩那個(gè)里面是0,11兩里面是6兩
將7再次裝滿，倒?jié)M11。---》此時(shí)7兩那個(gè)里面是2

016拿蘋果問(wèn)題

桌上有100個(gè)蘋果，你和另一個(gè)人一起拿，一人一次，每次拿的數(shù)量大于等于1小于等于5，問(wèn)：如何拿能保證最后一個(gè)蘋果由你來(lái)拿？
解答：只需要你先拿，第一次拿4個(gè)，以后看對(duì)方拿的個(gè)數(shù)，根據(jù)對(duì)方拿的個(gè)數(shù)，保證每輪對(duì)方和你拿的加起來(lái)是6就行了，其實(shí)就是保證你拿到4，還要拿到10,16...直到94。

017蛋糕切8份問(wèn)題

請(qǐng)把一盒蛋糕切成8份，分給8個(gè)人，但蛋糕盒里還必須留有一份。
解答：面對(duì)這樣的怪題，有些應(yīng)聘者絞盡腦汁也無(wú)法分成；而有些應(yīng)聘者卻感到此題實(shí)際很簡(jiǎn)單，把切成的8份蛋糕先拿出7份分給7人，剩下的1份連蛋糕盒一起分給第8個(gè)人。

018拿最大鉆石問(wèn)題

一樓到十樓的每層電梯門口都放著一顆鉆石，鉆石大小不一。你乘坐電梯從一樓到十樓，每層樓電梯門都會(huì)打開(kāi)一次，只能拿一次鉆石，問(wèn)怎樣才能拿到最大的一顆？
解答：一樓門打開(kāi)，拿鉆石，然后到二樓之后比較二樓和手里的鉆石，誰(shuí)大拿哪個(gè)，
然后到三樓之后比較三樓和手里的鉆石，誰(shuí)大拿哪個(gè)....依次類推，到十樓的時(shí)候就可以拿到最大的那個(gè)鉆石。