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; }
};