使用貪心來解決的一些問題

作者：Grey

原文地址：

部落格園：使用貪心來解決的一些問題

CSDN：使用貪心來解決的一些問題

貪心的使用方法

1. 分析業務

2. 根據業務邏輯找到不同的貪心策略

3. 對於能舉出反例的策略直接跳過，不能舉出反例的策略要證明有效性

4. 使用對數器來驗證貪心策略的正確性與否

拼接所有的字串產生字典序最小的字串

先考慮暴力解法：使用動態規劃，列舉所有字串，得到字典序最小的那個即可

貪心解法：使用排序，排序策略是

如果（字串1 + 字串2）的字典序小於（字串2 + 字串1）的字典序，則將(字串1 + 字串2)放在前面。

完整程式碼如下（使用暴力作為對數器驗證貪心解法）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

//[程式設計題]拼接所有的字串產生字典序最小的字串
//https://www.nowcoder.com/questionTerminal/f1f6a1a1b6f6409b944f869dc8fd3381
public class NowCoder_LowestString {

    public static String minString(String[] strs) {
        Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s);
        }
        return sb.toString();
    }

    // 暴力解
    public static String minString2(String[] strs) {
        HashSet<Integer> used = new HashSet<>();
        ArrayList<String> all = new ArrayList<>();
        String path = "";
        process(strs, used, path, all);
        String min = all.get(0);
        for (String s : all) {
            if (min.compareTo(s) > 0) {
                min = s;
            }
        }
        return min;
    }

    // 已經用過的字串在used中登記了
    // 已經用過的字串拼接的結果是path
    // 所有拼接的方式存在all裡面
    public static void process(String[] strs, HashSet<Integer> used, String path, ArrayList<String> all) {
        if (used.size() == strs.length) {
            all.add(path);
        } else {
            for (int i = 0; i < strs.length; i++) {
                if (!used.contains(i)) {
                    used.add(i);
                    process(strs, used, path + strs[i], all);
                    used.remove(i);
                }
            }
        }
    }

    public static void main(String[] args) {

        int arrLen = 6;
        int strLen = 5;
        int times = 100000;
        for (int i = 0; i < times; i++) {
            String[] arr = generateRandomStringArray(arrLen, strLen);
            String[] arr1 = copyStringArray(arr);
            String[] arr2 = copyStringArray(arr);
            String ans1 = minString(arr1);
            String ans2 = minString2(arr2);

            if (!ans1.equals(ans2)) {
                printArray(arr);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

    private static void printArray(String[] arr) {
        for (String s : arr) {
            System.out.print(s + ",");
        }
        System.out.println();

    }

    private static String[] copyStringArray(String[] arr1) {
        if (null == arr1) {
            return null;
        }
        String[] arr2 = new String[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr2[i] = String.valueOf(arr1[i]);
        }
        return arr2;
    }

    private static String[] generateRandomStringArray(int arrLen, int strLen) {
        int len = (int) (Math.random() * (arrLen + 1));
        String[] arr = new String[len];
        for (int i = 0; i < len; i++) {
            arr[i] = generateString(strLen);
        }
        return arr;
    }

    private static String generateString(int strLen) {
        int len = (int) (Math.random() * (strLen)) + 1;
        char[] arr = new char[len];
        for (int i = 0; i < arr.length; i++) {
            int v = 97 + (int) (Math.random() * 26);
            arr[i] = (char) v;
        }
        return String.valueOf(arr);
    }

}

會議室安排問題

一些專案要佔用一個會議室宣講，會議室不能同時容納兩個專案的宣講。給你每一個專案開始的時間和結束的時間，你來安排宣講的日程，要求會議室進行的宣講的場次最多。返回最多的宣講場次。

完整程式碼如下（使用暴力作為對數器驗證貪心解法）：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;


public class Code_BestArrange {
    public static class Program {
        public int start;
        public int end;

        public Program(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "start:" + start + " end:" + end;
        }
    }

    public static int bestArrange0(Program[] programs) {
        if (null == programs || programs.length < 1) {
            return 0;
        }
        List<Program> ans = new ArrayList<>();
        return p(programs, 0, ans);
    }

    public static int p(Program[] programs, int start, List<Program> ans) {
        if (programs.length == 0 || !enough(programs, start)) {
            return ans.size();
        } else {
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < programs.length; i++) {
                if (start <= programs[i].start) {
                    ans.add(programs[i]);
                    max = Math.max(p(copyExcept(programs, i), programs[i].end, ans), max);
                    ans.remove(programs[i]);
                }
            }
            return max;
        }
    }

    private static boolean enough(Program[] programs, int start) {
        boolean enough = false;
        for (Program p : programs) {
            if (start <= p.start) {
                enough = true;
                break;
            }
        }
        return enough;
    }

    public static Program[] copyExcept(Program[] p, int i) {
        int ind = 0;
        Program[] n = new Program[p.length - 1];
        for (int j = 0; j < p.length; j++) {
            if (j != i) {
                n[ind++] = p[j];
            }
        }
        return n;
    }


    public static int bestArrange1(Program[] programs) {
        if (programs == null || programs.length == 0) {
            return 0;
        }
        return process(programs, 0, 0);
    }

    // 還剩什麼會議都放在programs裡
    // done 之前已經安排了多少會議，數量
    // timeLine目前來到的時間點是什麼

    // 目前來到timeLine的時間點，已經安排了done多的會議，剩下的會議programs可以自由安排
    // 返回能安排的最多會議數量
    public static int process(Program[] programs, int done, int timeLine) {
        if (programs.length == 0) {
            return done;
        }
        // 還有會議可以選擇
        int max = done;
        // 當前安排的會議是什麼會，每一個都列舉
        for (int i = 0; i < programs.length; i++) {
            if (programs[i].start >= timeLine) {
                Program[] next = copyButExcept(programs, i);
                max = Math.max(max, process(next, done + 1, programs[i].end));
            }
        }
        return max;
    }

    public static Program[] copyButExcept(Program[] programs, int i) {
        Program[] ans = new Program[programs.length - 1];
        int index = 0;
        for (int k = 0; k < programs.length; k++) {
            if (k != i) {
                ans[index++] = programs[k];
            }
        }
        return ans;
    }

    public static int bestArrange2(Program[] programs) {
        Arrays.sort(programs, Comparator.comparingInt(o -> o.end));
        int timeLine = 0;
        int result = 0;
        for (Program program : programs) {
            if (timeLine <= program.start) {
                result++;
                timeLine = program.end;
            }
        }
        return result;
    }


    // for test
    public static Program[] generatePrograms(int programSize, int timeMax) {
        Program[] ans = new Program[(int) (Math.random() * (programSize + 1))];
        for (int i = 0; i < ans.length; i++) {
            int r1 = (int) (Math.random() * (timeMax + 1));
            int r2 = (int) (Math.random() * (timeMax + 1));
            if (r1 == r2) {
                ans[i] = new Program(r1, r1 + 1);
            } else {
                ans[i] = new Program(Math.min(r1, r2), Math.max(r1, r2));
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int programSize = 12;
        int timeMax = 20;
        int timeTimes = 1000000;
        for (int i = 0; i < timeTimes; i++) {
            Program[] programs = generatePrograms(programSize, timeMax);
            int ans0 = bestArrange0(programs);
            int ans1 = bestArrange1(programs);
            int ans2 = bestArrange2(programs);
            if (ans1 != ans2 || ans1 != ans0 || ans0 != ans2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }



}

分金條的最小花費

霍夫曼演演算法，貪心的策略為：

準備一個小根堆，把所有金條的價值加入小根堆，每次彈出堆頂兩個（當下排名最小的兩個值）相加存入cost變數，然後把相加後的和繼續放入小根堆，反覆上述操作，一直到大根堆只有一個資料。返回 cost 就是最小代價。

完整程式碼如下（使用暴力作為對數器驗證貪心解法）：

import java.util.PriorityQueue;

/**
 * 一塊金條切成兩半，是需要花費和長度數值一樣的銅板的。 比如長度為20的金條， 不管怎麼切，都要花費20個銅板。 一群人想整分整塊金條，怎麼分最省銅板?
 * 例如,給定陣列{10,20,30}，代表一共三個人，整塊金條長度為60，金條要分成10，20，30三個部分。
 * 如果先把長度60的金條分成10和50，花費60; 再把長度50的金條分成20和30，花費50; 一共花費110銅板。
 * 但如果先把長度60的金條分成30和30，花費60;再把長度30金條分成10和20， 花費30; 一共花費90銅板。 輸入一個陣列，返回分割的最小代價。
 * <p>
 *     
 * 注：堆和排序是解決貪心問題的最常用的兩種方案
 */
// https://www.nowcoder.com/questionTerminal/418d2fcdf7f24d6f8f4202e23951c0da
// https://www.lintcode.com/problem/minimum-cost-to-connect-sticks/description
public class NowCoder_SplitGolden {
    public static long lessMoney(long[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0;
        }
        if (arr.length == 2) {
            return arr[0] + arr[1];
        }

        PriorityQueue<Long> queue = new PriorityQueue<>();
        for (long i : arr) {
            queue.add(i);
        }
        long cost = 0;
        while (queue.size() > 1) {
            long i = queue.poll();
            long j = queue.poll();
            cost += (i + j);
            queue.offer(i + j);
        }
        return cost;
    }

    // 暴力遞迴版本
    public static long lessMoney0(long[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0;
        }
        return process0(arr, 0);
    }

    private static long process0(long[] arr, long s) {
        if (arr.length == 1) {
            return s;
        } else {
            long min = Long.MAX_VALUE;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    min = Math.min(process0(copyExcept(arr, i, j), s + (arr[i] + arr[j])), min);
                }
            }
            return min;
        }
    }


    private static long[] copyExcept(long[] arr, int i1, int i2) {
        int m = 0;
        long[] nArr = new long[arr.length - 1];
        long t = 0;
        for (int j = 0; j < arr.length; j++) {
            if (j != i1 && j != i2) {
                nArr[m++] = arr[j];
            } else {
                t += arr[j];
            }
        }
        nArr[arr.length - 2] = t;
        return nArr;
    }

    public static long[] generateRandomArr(int maxSize, long maxValue) {
        int size = (int) (Math.random() * maxSize) + 1;
        long[] arr = new long[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (long) (Math.random() * (maxValue + 1)) - (long) (Math.random() * (maxValue + 1));
        }
        return arr;
    }

    public static void main(String[] args) {
        int times = 50000;
        long maxValue = 9;
        int maxSize = 7;
        for (int i = 0; i < times; i++) {
            long[] arr = generateRandomArr(maxSize, maxValue);
            if (lessMoney(arr) != lessMoney0(arr)) {
                System.out.println("Ops!");
            }
        }
        System.out.println("Nice!");
    }
}

IPO 問題

貪心策略：

設定兩個堆（一個大根堆，一個小根堆）來實現獲取收益的最大值，由於本金為 W ，我們先把所有專案加入到小根堆中，將成本比 W 小或等於的專案加入到大根堆中，那麼大根堆的堆頂元素就是但當前能獲取收益最大的專案，然後將獲取的收益和本金相加，重複這個過程直到做了 k 個專案為止。最終整體的最大收益即為每次的區域性最大收益。

完整程式碼如下（使用暴力作為對數器驗證貪心解法）：

class Solution {
    public static class Project {
        public int profit;
        public int capital;

        public Project(int profit, int capital) {
            this.profit = profit;
            this.capital = capital;
        }
    }

    // k專案個數
    // W初始資金
    // Profits收益
    // Capital花費
    // 所有花費可以cover的專案中，取最大收益的專案
    public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        if (k == 0) {
            return W;
        }
        if (Profits.length == 0) {
            return W;
        }
        k = Math.min(Profits.length, k); // 因為專案無法重複做，所以k最大隻能是專案個數
        Project[] projects = initProjects(Profits, Capital);
        PriorityQueue<Project> min = new PriorityQueue<>(Comparator.comparingInt((Project o) -> o.capital));
        PriorityQueue<Project> max = new PriorityQueue<>((o1, o2) -> o2.profit - o1.profit);

        for (Project project : projects) {
            min.offer(project);
        }
        int maxProfit = W;
        while (k > 0) {
            while (!min.isEmpty() && min.peek().capital <= W) {
                max.offer(min.poll());
            }
            if (!max.isEmpty()) {
                maxProfit += max.poll().profit;
                k--;
                W = maxProfit;
            } else {
                break;
            }
        }
        return maxProfit;
    }

    private static Project[] initProjects(int[] profits, int[] capital) {
        Project[] projects = new Project[profits.length];
        for (int i = 0; i < profits.length; i++) {
            projects[i] = new Project(profits[i], capital[i]);
        }
        return projects;
    }
}

放置路燈問題

貪心策略：如果 i 位置有點，且 i+1 位置也是點，那麼 i 位置一定不需要放燈，等到 i+1 號位置來放燈即可。

完整程式碼如下（使用暴力作為對數器驗證貪心解法）：

import java.util.HashSet;
import java.util.Set;

/**
 * 給定一個字串str，只由‘X’和‘.’兩種字元構成。 ‘X’表示牆，不能放燈，也不需要點亮 ‘.’表示居民點，可以放燈，需要點亮
 * 如果燈放在i位置，可以讓i-1，i和i+1三個位置被點亮 返回如果點亮str中所有需要點亮的位置，至少需要幾盞燈
 * <p>
 * 暴力方法 可以放燈的點，有放燈不放燈兩種情況，在這兩種情況下，摘出照亮所有點的情況， 然後再在這些情況中選出燈最少的方案
 */

// https://www.nowcoder.com/questionTerminal/45d20d0e59d94e7d8879f19a5755c177
// 貪心解法
public class NowCoder_Light {
    public static int minLight1(String str) {
        if (str == null || str.length() < 1) {
            return 0;
        }
        return p(str.toCharArray(), 0, new HashSet<>());
    }

    // i及其往後最少的放燈數
    // i之前的放燈情況存在set裡面
    public static int p(char[] str, int i, Set<Integer> set) {
        if (i == str.length) {
            for (int s = 0; s < str.length; s++) {
                if (str[s] == '.' && (!set.contains(s - 1) && !set.contains(s) && !set.contains(s + 1))) {
                    return Integer.MAX_VALUE;
                }
            }
            return set.size();
        }
        int no = p(str, i + 1, set);
        if (str[i] == '.') {
            set.add(i);
            int yes = p(str, i + 1, set);
            set.remove(i);
            return Math.min(yes, no);
        }
        return no;
    }

    // 貪心解法
    // i位置有點，且i+1位置也是點，那麼i位置一定不需要放燈，等到i+1號位置來放燈
    public static int minLight2(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        char[] str = s.toCharArray();
        int ans = 0;
        int i = 0;
        while (i < str.length) {
            if (str[i] == 'X') {
                i++;
            } else {
                // 無論如何都要
                ans++;
                if (i + 1 < str.length) {
                    if (str[i + 1] == '.') {
                        i += 3;
                    } else {
                        // str[i+1] == 'X'
                        i += 2;
                    }
                } else {
                    // i+1==str.length
                    i++;
                }

            }
        }
        return ans;
    }


    // for test
    public static String randomString(int len) {
        char[] res = new char[(int) (Math.random() * len) + 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = Math.random() < 0.5 ? 'X' : '.';
        }
        return String.valueOf(res);
    }

    public static void main(String[] args) {
        int len = 20;
        int testTime = 100000;
        for (int i = 0; i < testTime; i++) {
            String test = randomString(len);
            int ans1 = minLight1(test);
            int ans2 = minLight2(test);
            if (ans1 != ans2) {
                System.out.println("oops!");
            }
        }
        System.out.println("finish!");

    }
}

更多

演演算法和資料結構筆記

參考資料

演演算法和資料結構體系班-左程雲