代码随想录第十五天|贪心算法（1）_算法

贪心算法其实就是没有什么规律可言，所以大家了解贪心算法就了解它没有规律的本质就够了。不用花心思去研究其规律， 没有思路就立刻看题解。基本贪心的题目有两个极端，要不就是特简单，要不就是死活想不出来。但今天自己做出来的题就一两道，挺打击人的。

leetcode 455. 分发饼干

题目链接：leetcode 455. 分发饼干

思想：本题的话可以使用贪心算法，就是把大饼干喂给大胃口的小孩，或者小饼干喂给小胃口的小孩。可以把胃口和饼干尺寸分别重新排序，遍历饼干尺寸数组，如果满足当前饼干尺寸刚好大于等于小孩胃口值的话，就令指向胃口数组的下标+1，最后返回指向胃口数组的下标。

代码如下：

    int findcontentchildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index = 0;
        for(int i = 0; i < s.size(); i++) { // 饼干
            if(index < g.size() && g[index] <= s[i]){ // 胃口
                index++;
            }
        }
        return index;
    }

时间复杂度：o(nlogn)，空间复杂度：o(1)。

leetcode 376. 摆动序列

题目链接：leetcode 376. 摆动序列

思想：本题最主要的一句话是“子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序”。也就是这个子序列可以不用连续，在整个数组里，只要后一个数的变化趋势与前一个不同就行了。

那么这里就引入峰和谷的概念，峰就是一个数值的旁边两个数值都小于它；而谷就是一个数值的旁边两个数值都大于它。那么这题就只需要数峰和谷的数量就行了。峰就是前一个变化的数值是大于0的，后一个变化的数值是小于0的；谷就是前一个变化的数值是小于0的，后一个变化的数值是大于0的。

代码如下：

    int wigglemaxlength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        int curdiff = 0;
        int prediff = 0;
        int result = 1;
        for (int i = 0; i < nums.size() - 1; i++) {
            curdiff = nums[i + 1] - nums[i];
            if ( (prediff <= 0 && curdiff > 0) || (prediff >= 0 && curdiff < 0)) {
                result++;
                prediff = curdiff;
            }
        }
        return result;
    }

时间复杂度：o(n)，空间复杂度：o(1)。

leetcode 53. 最大子数组和

题目链接：leetcode 53. 最大子数组和

思想：本题的话，采用贪心策略，如果说当前子数组和为负数的话就不要，在下一个数组重新计算子数组和。大概就是这样一个思想。

代码如下：

    int maxsubarray(vector<int>& nums) {
        int result = int_min;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (sum > result) {
                result = sum;
            }
            if (sum <= 0) {
                sum = 0;
            }
        }
        return result;
    }

时间复杂度：o(n)，空间复杂度：o(1)。

leetcode 122. 买卖股票的最佳时机 ii

题目链接：leetcode 122. 买卖股票的最佳时机 ii

思想：本题有一个重要的思想，就是第一天买入，第四天卖出的利润——prices[3]-prices[0]=(prices[3]-prices[2])+(prices[2]-prices[1])+(prices[1]-prices[0])，也就是说总利润可以看做每一天的利润之和，那要总利润最大，只要每天的利润都是正的就行了。也就是说只要今天的股票价格大于昨天的就在昨天做出购入，今天卖出。

代码如下：

    int maxprofit(vector<int>& prices) {
        int price = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] - prices[i - 1] > 0) {
                price += prices[i] - prices[i - 1];
            }
        }
        return price;
    }

时间复杂度：o(n)，空间复杂度：o(1)。

leetcode 55. 跳跃游戏

题目链接：leetcode 55. 跳跃游戏

思想：本题确实比较难，主要思想就是这个数值就好比一个覆盖范围，在这个覆盖范围里面的下标都能达到，每次更新cover的话就采取，max(i + nums[i], cover)的方式，如果cover大于数组最后一个下标的话，就返回true。

代码如下：

    bool canjump(vector<int>& nums) {
        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = max(i + nums[i], cover);
            if ( cover >= nums.size() - 1) {
                return true;
            }
        }
        return false;
    }

时间复杂度：o(n)，空间复杂度：o(1)。

leetcode 45. 跳跃游戏 ii

题目链接：leetcode 45. 跳跃游戏 ii

思想：跟上一题差不多，这次就覆盖范围越大，就更新。

代码如下：

    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int curdistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextdistance = 0;   // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i++) {
            nextdistance = max(nums[i] + i, nextdistance);  // 更新下一步覆盖最远距离下标
            if (i == curdistance) {                         // 遇到当前覆盖最远距离下标
                ans++;                                  // 需要走下一步
                curdistance = nextdistance;             // 更新当前覆盖最远距离下标（相当于加油了）
                if (nextdistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点，不用做ans++操作了，直接结束
            }
        }
        return ans;
    }

时间复杂度：o(n)，空间复杂度：o(1)。

leetcode 1005. k次取反后最大化的数组和

题目链接：leetcode 1005. k次取反后最大化的数组和

思想：本题首先按升序排序数组，然后遍历数组，遇到负数就取反，同时记录最小的数组值和当前数组和。如果剩下的k值余2等于0的话，就直接返回当前数组，因为取偶数次反，每个数都还是原来的样子。如果剩下的k值余2等于1的话，就取反最小值，然后返回数组和-2*最小值就行了。

代码如下：

    int largestsumafterknegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        int min = int_max;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
            sum += nums[i];
            if (nums[i] < min) {
                min = nums[i];
            }
        }
        if (k % 2 == 0) {
            return sum;
        } else {
            return (sum - 2 * min);
        }
    }

时间复杂度：o(n)，空间复杂度：o(1)。