算法练习——贪心算法

贪心算法 贪心算法（又称贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。 不从整体最优上加以考虑，仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解 但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 在贪心算法中，我们总是做出当时看来最佳的选择，然后再求解剩下唯一的子问题。 贪心算法做出选择时可能会依赖于之前的选择或者子问题的解，但是绝对不依赖于将来的选择或者子问题的解。 力扣322零钱兑换

想要总硬币数最少，肯定是优先用大面值硬币，所以对 coins 按从大到小排序

先丢大硬币，再丢会超过总额时，就可以递归下一层丢的是稍小面值的硬币

优先丢大硬币进去尝试，也没必要一个一个丢，可以用乘法算一下最多能丢几个

如果因为丢多了导致最后无法凑出总额，再回溯减少大硬币数量

考虑到有 [1,7,10] 这种用例，按照贪心思路 10 + 1 + 1 + 1 + 1 会比 7 + 7 更早找到

需要把所有情况都递归完

class Solution {
    int minCount=Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) { 
        Arrays.sort(coins); 
        dfs(coins,amount,0,coins.length-1); 
        if (minCount == Integer.MAX_VALUE) return -1; 
        return minCount; 
    }
    public void dfs (int[] coins,int amount,int selectedCount,int startIndex) { 
        if (amount==0) { 
            if (selectedCount < minCount) { 
                minCount = selectedCount; 
            }
            return; 
        }
        if (startIndex<0) { 
            return; 
        }
        int maxCount = amount / coins[startIndex]; 
        for (int i=maxCount;i>=0 && i+selectedCount < minCount ;i--) { 
            int resAmount = amount - i*coins[startIndex]; 
            dfs(coins,resAmount,selectedCount+i,startIndex-1);  
 
        } 
    }
}

力扣1217玩筹码

将position[i]往前移动两格到position[i] - 2，或向后移动两格移动到position[i] + 2，移动开销为0

先将尽量多的筹码移动到一起

移动到同一位置的时候，尽量使用最少次数

将position[i]往前移动一格到position[i] - 1，或向后移动一格移动到position[i] + 1，移动开销为1

class Solution {
    public int minCostToMoveChips(int[] position) {
        int odd = 0, even = 0;
        for (int num : position) {
            if ((num & 1) == 0) even++;
            else odd++;
        }
        return Math.min(odd, even);
    }
}

力扣55跳跃游戏

依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x + 1，x+2,x=+3…x+xnums[x]

public class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}