贪心算法 Greedy Algorithm

1) 贪心例子

  v2已经不会更新v3因为v3更新过了

几个贪心的例子

dijkstra

// ...
while (!list.isempty()) {
    // 选取当前【距离最小】的顶点
    vertex curr = choosemindistvertex(list);
    // 更新当前顶点邻居距离
    updateneighboursdist(curr);
    // 移除当前顶点
    list.remove(curr);
    // 标记当前顶点已经处理过
    curr.visited = true;
}

prim

// ...
while (!list.isempty()) {
    // 选取当前【距离最小】的顶点
    vertex curr = choosemindistvertex(list);
    // 更新当前顶点邻居距离
    updateneighboursdist(curr);
    // 移除当前顶点
    list.remove(curr);
    // 标记当前顶点已经处理过
    curr.visited = true;
}

kruskal

// ...
while (list.size() < size - 1) {
    // 选取当前【距离最短】的边
    edge poll = queue.poll();
    // 判断两个集合是否相交
    int i = set.find(poll.start);
    int j = set.find(poll.end);
    if (i != j) { // 未相交
        list.add(poll);
        set.union(i, j); // 相交
    }
}

2) 零钱兑换问题

有几个解（零钱兑换 ii）leetcode 518

[1,2,5]  5  暴力递归

public int rec(int index,int[] coins,int remainder){
        //1.情况1:剩余金额 < 0 - 无解
        //2.情况2:剩余金额 > 0 - 继续递归
        //3.情况3:剩余金额 = 0 - 有解
        if(remainder < 0){
            return 0;
        }
        else if(remainder == 0){
            return 1;
        }
        else{
            int count = 0;
            for(int i = index;i<coins.length;i++){
                count+=rec(i,coins,remainder-coins[i]);
            }
            return count;
        }
    }

那这个递归是怎么运作的呢?

import java.util.arraylist;
import java.util.linkedlist;
import java.util.listiterator;

/**
 * 零钱兑换
 * 可以凑成总金额所需的所有组合可能数
 */
public class leetcode518 {
    public int coinchange(int[] coins, int amount) {
        return rec(0, coins, amount, new linkedlist<>(), true);
    }

    /**
     * 求凑成剩余金额的解的个数
     *
     * @param index     当前硬币索引
     * @param coins     硬币面值数组
     * @param remainder 剩余金额
     * @param stack     -
     * @param first     -
     * @return 解的个数
     */
    public int rec(int index, int[] coins, int remainder, linkedlist<integer> stack, boolean first) {
        if(!first) {//第一次不压栈
            stack.push(coins[index]);
        }
        // 情况1：剩余金额 < 0 - 无解
        int count = 0;
        if (remainder < 0) {
            print("无解：", stack);
//            if(!stack.isempty()){
//                stack.pop();
//            }
        }
        // 情况2：剩余金额 == 0 - 有解
        else if (remainder == 0) {
            print("有解：", stack);
//            if(!stack.isempty()){
//                stack.pop();
//            }
            count = 1;
        }
        // 情况3：剩余金额 > 0 - 继续递归
        else {
            for (int i = index; i < coins.length; i++) {
                count += rec(i, coins, remainder - coins[i], stack, false);
            }
        }
        if (!stack.isempty()) {
            stack.pop();
        }
        return count;
    }

    private static void print(string prompt, linkedlist<integer> stack) {
        arraylist<integer> print = new arraylist<>();
        listiterator<integer> iterator = stack.listiterator(stack.size());
        while (iterator.hasprevious()) {
            print.add(iterator.previous());
        }
        system.out.println(prompt + print);
    }

    public static void main(string[] args) {
        leetcode518 leetcode = new leetcode518();
//        int count = leetcode.coinchange(new int[]{1, 5, 10, 25}, 41);
//        int count = leetcode.coinchange(new int[]{25, 10, 5, 1}, 41);
//        int count = leetcode.coinchange(new int[]{5, 2, 1}, 5);
        int count = leetcode.coinchange(new int[]{1, 2, 5}, 5);
//        int count = leetcode.change(new int[]{15, 10, 1}, 21);
        system.out.println(count);
    }
}

但是这个代码放在leetcode上面跑会超时,因为重复处理了很多次相同的操作

我们可以考虑用记忆法 & 动态规划来优化

我们也可以考虑顺序优化 ==>规模下降明显

但即使是这样写在leetcode上也是会 stackoverflowerror

class solution {
    public int change(int amount, int[] coins1) {
        int[] coins = sort(coins1);
        return rec(0,coins,amount);

    }
    int rec(int index,int[] coins,int remainder){
        int count = 0;
        if(remainder == 0){
            return 1;
        }else if(remainder<0){
            return 0;
        }else{
            for(int i = index;i<coins.length;i++){
                count+=rec(index,coins,remainder);
            }
            return count;
        }
    }
    /**
    *传入一个有序的数组a(从小到大排序),返回一个从大到小的数组
    *@param a 传入的数组(有序)
    *@return 返回一个数组(从大到小)
     */
    
    int[] sort(int[] a){
        int[] temp = a;
        if(temp.length % 2 ==0){
            //数组里面的个数为偶数
            for(int i = 0;i<=temp.length/2;i++){
                int temp1 = a[i];
                temp[i] = temp[temp.length-1-i];
                temp[temp.length-1] = temp1;
            }
        }else{
            //数组里面的个数为奇数
            for(int i = 0;i<temp.length/2;i++){
                int temp1 = a[i];
                temp[i]=temp[temp.length-1-i];
                temp[temp.length-1-i] = temp1;
            }
        }
        return temp;
    }
}

import java.util.arrays;

public class main {
    public static void main(string[] args) {
        int[] arr = sort(new int[]{1,2,3});
        system.out.println(arrays.tostring(arr));
        //为什么我这么选择是因为用arrays.sort要将数组转化为integer[]
    }
    /**
     *传入一个有序的数组a（从小到大排序），返回一个从大到小的数组
     * @param a 传入的数组（有序）
     * @return 返回一个数组（从大到小）
     */
    public static int[] sort(int[] a){
        int[] temp = a;

        if(temp.length%2==0){
            //数组里面的个数为偶数
            for (int i = 0; i <= temp.length/ 2; i++) {
                int temp1 = a[i];
                temp[i]=temp[temp.length-1-i];
                temp[temp.length - 1-i] = temp1;
            }
        }else{
            //数组里面的个数为奇数
            for (int i = 0; i < temp.length / 2; i++) {
                int temp1 = a[i];
                temp[i]=temp[temp.length-1-i];
                temp[temp.length - 1-i] = temp1;
            }
        }
        return  temp;
    }
}

 动态规划->会在动态规划章节说明

最优解（零钱兑换）- 穷举法 leetcode 322

import java.util.linkedlist;
import java.util.concurrent.atomic.atomicinteger;

public class leetcode322 {
    static int min = -1; // 需要的最少硬币数  2 3

    public int coinchange(int[] coins, int amount) {
        rec(0, coins, amount, new atomicinteger(-1), new linkedlist<>(), true);
        return min;
    }

    // count 代表某一组合 钱币的总数 可变的整数对象
    public void rec(int index, int[] coins, int remainder, atomicinteger count, linkedlist<integer> stack, boolean first) {
        if (!first) {
            stack.push(coins[index]);
        }
        count.incrementandget(); // count++
        if (remainder == 0) {
            system.out.println(stack);
            if (min == -1) {
                min = count.get();
            } else {
                min = integer.min(min, count.get());
            }
        } else if (remainder > 0) {
            for (int i = index; i < coins.length; i++) {
                rec(i, coins, remainder - coins[i], count, stack, false);
            }
        }
        count.decrementandget(); // count--
        if (!stack.isempty()) {
            stack.pop();
        }
    }

    public static void main(string[] args) {
        leetcode322 leetcode = new leetcode322();
//        int count = leetcode.coinchange(new int[]{5, 2, 1}, 5);
        int count = leetcode.coinchange(new int[]{25, 10, 5, 1}, 41);
//        int count = leetcode.coinchange(new int[]{2}, 3);
//        int count = leetcode.coinchange(new int[]{15, 10, 1}, 21);
        system.out.println(count);
    }
}

最优解（零钱兑换）- 贪心法 leetcode 322

自己看看就行因为有些测试样例过不了

假定传过来的数据就是从大到小排序,因为java对int数组从大到小排序比较麻烦

public class leetcode322 {
    public int coinchange(int[] coins, int amount) {
        int remainder = amount;
        int count = 0;
        for (int coin : coins) {
            while (remainder - coin > 0) {
                remainder -= coin;
                count++;
            }
            if (remainder - coin == 0) {
                remainder = 0;
                count++;
                break;
            }
        }
        if (remainder > 0) {
            return -1;
        } else {
            return count;
        }
    }

    public static void main(string[] args) {
        leetcode322 leetcode = new leetcode322();
        int count = leetcode.coinchange(new int[]{5, 2, 1}, 5);
//        int count = leetcode.coinchange(new int[]{25, 10, 5, 1}, 41);
//        int count = leetcode.coinchange(new int[]{2}, 3);
        
        // 问题1 没有回头，导致找到更差的解
//        int count = leetcode.coinchange(new int[]{15, 10, 1}, 21);  
        // 问题2 没有回头，导致无解
//        int count = leetcode.coinchange(new int[]{15, 10}, 20);  
        system.out.println(count);
    }
}