Leetcode刷题. 贪心算法

贪心算法：

        比较传统的解释：将整个问题拆解为几个小问题，找到小问题的最优解，加起来就是整个问题的全局最优解。对于现在的我理解贪心就是一种感觉，给出证明很难，解题思路一般就是认真读题，发掘题目的条件，然后尝试给出算法。

11. 盛最多水的容器

         一个显而易见的条件：水的面积取决于底边的长度和水池两边的最短边，因此可以首先选择最长的底边，然后在此基础上在选较高的水池的一边，在这个过程中计算面积最大值，保存即可。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        for (int i = 0, j = height.size() - 1; i < j; ) {
            if (height[i] <= height[j]) {
                maxArea = max((j - i) * height[i], maxArea);
                i++;
            } else {
                maxArea = max((j - i) * height[j], maxArea);
                j--;
            }
        }
        return maxArea;
    }
};

122. 买卖股票的最佳时机 II

        求解思路：累加每天股票变化的增加的部分，比如1和5是涨的，那么最后的结果肯定是涨的，所以需要把该部分累加。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (int i = 0; i < prices.size(); i++) {
            for (int j = i + 1; j < prices.size() && prices[j] - prices[i] >= 0; j++, i++) {
                profit += prices[j] - prices[i];
            }
        }
        return profit;
    }
};

680. 验证回文串 II

        这道题的思路还是比较直观的，就是双指针判断然后处理删除的情况，关键在于怎么处理删除的情况需要重点理解，这里体现了根据局部解推出全局解的思想。

class Solution {
public:
    bool validPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }

    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true; 
    }
};