算法刷题记录

贪心算法

• 概念

  所谓的贪心算法，即在对一个问题进行求解的时候，总是选择在当时情况下看来最好的一个选择，即不从整体最优上考虑，而是选择局部最优解

  这个算法没有一个固定的模板，主要是选择对应的贪心策略.

  需要注意的是,贪心算法不一定能得到整体最优解，且选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的过程，只与当前的状态有关

  所以我认识，贪心算法最大的难点在于，什么时候我们才要用贪心，那这个没有什么好的方法，如果数学好那可以用数学方法来进行推导，不行的话则用几个特例来进行尝试，至于怎么选择例子，只能多刷题了

• 基本思路

  将求解的问题分成若干个子问题，再对每个子问题一一进行求解，得到子问题的局部最优解，最后将子问题的解合并成原来解中的一个解

接下来直接先照常看看Leecode的题目

Leecode 605 种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

js
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

题目其实很好理解，简单来说，就是在数组中，1的左右两边不能有两个1，在满足这个条件的情况下，尽可能的把0反转为1

在这里的话贪心就在于，我从左往右遍历，只要能种花就一定会种,因为对于每个位置来说，他的局部最优解就是在满足条件下种花

数学的角度可能不会推，只能大概猜想一下，即拆成n个子问题就是在当前位置是否要种花

那我们从左往右遍历，在当前位置我们只需要考虑右边的情况，如果我们在当前位置可以种花的情况下不种花的话，在后一个位置你无法保证其一定可以种花，在后一个位置种花的概率不为100%，即可能得到的花会比之前少，那我还是选择在前面尽可能的增加花的数量比较好，且你后面不管如何选择，都对我前面是没有影响的，我前面一定是得到了我在当前长度的花坛里得到的最优解，那就顺着这个情况下去，我们总能得到一个在最终长度下的最优解

java
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int i =0;
        while(i<flowerbed.length) {
            // 分为几种情况
            // 如果当前没有花
            if(flowerbed[i] == 0) {
                // 如果没有下个位置了，则直接种花
                if(i+1 == flowerbed.length) {
                    n--;
                    i++;
                }
                //如果下一个位置没种花
                else if(flowerbed[i+1]==0){
                    //则在当前位置种花
                    n--;
                    // 跳过一个位置
                    i += 2;
                    // continue;
                }
                // 如果下一个位置种花了
                else if(flowerbed[i+1]==1){
                    // 即010情况，则直接到0的后一个
                    i += 3;
                }
            }else if(flowerbed[i] == 1) {
                i += 2;
            }
            if(n <= 0) return true;
        }
        return false;
    }
}

换一道题试试看，还是简单题先试一下

Leecode 561 数组拆分

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。

js
入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

题意就是如何进行两两分组得到多个最小值，且这些最小值的总和最大

如果是想要总和最小就很明显了，那样的话就是每次选择一个最小的和一个最大的为一组就可以，其实就是等价于选择数组种最小的几个数相加

但是总和最大的话就要考虑别的情况了，那我们分成多个子问题，这里的子问题就是分成多个分组，每次分组怎么选择，那我们就先排个序吧，其实最需要注意的就是我们需要减小较小值的影响，例如[6,2,6,5,1,2]先排序[1,2,2,5,6,6],然后从左往右开始找，我的贪心策略就是每次找一个最接近当前值的，即当前索引的下一位，即[1,2],[2,5],[5,6]

至于如何证明这个贪心策略是正确的，其实我还没想好,还是老样子，数学推导不会，那我们就靠猜来试一下.

我们要最大值，那么其实肯定得减小最小值的影响，类似于田忌赛马，我们不能拿最大值去和最小值一组的，这点就不需要证明了，那我们就是拿剩下的值里的下等马去和当前取出来的值来进行分组。

或者换个思路，其实求这个最大值的话，就是在数组所有数的总和-(每组的损失值的总和)，每组的损失值就是|a1-a2|，那我们要使得最后的值最大，那就是将使得损失最小，最自然是选择一个最接近的

java
class Solution {
    public int arrayPairSum(int[] nums) {
        // 策略就是排序后，每次都选择一个最接近
        Arrays.sort(nums);
        int result = 0;
        for(int i =0;i<nums.length;i+=2 ){
            result+=nums[i];
        }
        return result;
    }
}

这两道题都是属于一眼能看出来的.接下来就再试一下难一点的题是什么样的