Update

youngyangyang04 · youngyangyang04 · commit 8b640430deec · 2020-11-27T09:40:03.000+08:00
diff --git a/README.md b/README.md
@@ -173,6 +173,7 @@
     * [关于贪心算法，你该了解这些！](https://mp.weixin.qq.com/s/O935TaoHE9Eexwe_vSbRAg)
     * [贪心算法：分发饼干](https://mp.weixin.qq.com/s/YSuLIAYyRGlyxbp9BNC1uw)
     * [贪心算法：摆动序列](https://mp.weixin.qq.com/s/Xytl05kX8LZZ1iWWqjMoHA)
+    * [贪心算法：最大子序和](https://mp.weixin.qq.com/s/DrjIQy6ouKbpletQr0g1Fg)
 
 
 * 动态规划
@@ -333,12 +334,16 @@
 |[0973.最接近原点的K个点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0973.最接近原点的K个点.md) |优先级队列 |中等|**优先级队列**|
 |[0977.有序数组的平方](https://github.com/youngyangyang04/leetcode/blob/master/problems/0977.有序数组的平方.md) |数组 |中等|**双指针** 还是比较巧妙的|
 |[1002.查找常用字符](https://github.com/youngyangyang04/leetcode/blob/master/problems/1002.查找常用字符.md) |栈 |简单|**栈**|
+|[1005.K次取反后最大化的数组和](https://github.com/youngyangyang04/leetcode/blob/master/problems/1005.K次取反后最大化的数组和.md) |贪心/排序 |**贪心算法** 贪心基础题目|
 |[1047.删除字符串中的所有相邻重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/1047.删除字符串中的所有相邻重复项.md) |哈希表 |简单|**哈希表/数组**|
 |[1049.最后一块石头的重量II](https://github.com/youngyangyang04/leetcode/blob/master/problems/1049.最后一块石头的重量II.md) |动态规划 |中等|**01背包**|
 |[1207.独一无二的出现次数](https://github.com/youngyangyang04/leetcode/blob/master/problems/1207.独一无二的出现次数.md) |哈希表 |简单|**哈希** 两层哈希|
+|[1221.分割平衡字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/1221.分割平衡字符串.md) |贪心 |简单|**贪心算法** 基础题目|
 |[1356.根据数字二进制下1的数目排序](https://github.com/youngyangyang04/leetcode/blob/master/problems/1356.根据数字二进制下1的数目排序.md) |位运算 |简单|**位运算** 巧妙的计算二进制中1的数量|
 |[1365.有多少小于当前数字的数字](https://github.com/youngyangyang04/leetcode/blob/master/problems/1365.有多少小于当前数字的数字.md) |数组、哈希表 |简单|**哈希** 从后遍历的技巧很不错|
 |[1382.将二叉搜索树变平衡](https://github.com/youngyangyang04/leetcode/blob/master/problems/1047.删除字符串中的所有相邻重复项.md) |二叉搜索树 |中等|**递归** **迭代** 98和108的组合题目|
+|[1403.非递增顺序的最小子序列](https://github.com/youngyangyang04/leetcode/blob/master/problems/1403.非递增顺序的最小子序列.md) | 贪心算法|简单|**贪心算法** 贪心基础题目|
+|[1518.换酒问题](https://github.com/youngyangyang04/leetcode/blob/master/problems/1518.换酒问题.md) | 贪心算法|简单|**贪心算法** 贪心基础题目|
 |[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md) |字符串 |简单|**双指针**|
 |[ 剑指Offer58-I.翻转单词顺序](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md) |字符串 |简单|**模拟/双指针**|
 |[剑指Offer58-II.左旋转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer58-II.左旋转字符串.md) |字符串 |简单|**反转操作**|
diff --git a/problems/0322.零钱兑换.md b/problems/0322.零钱兑换.md
@@ -0,0 +1,58 @@
+
+[1]  0  ，输出的是0，不是-1啊，这颗真是天坑j
+
+```
+// dp初始化很重要
+class Solution {
+public:
+    int coinChange(vector<int>& coins, int amount) {
+        //int dp[10003] = {0}; // 并没有给所有元素赋值0
+        if (amount == 0) return 0; // 这个要注意
+        vector<int> dp(10003, 0);
+        // 不能这么初始化啊，[2147483647]，2 这种例子 直接gg，但是这种初始化有助于理解
+        for (int i = 0; i < coins.size(); i++) {
+            if (coins[i] <= amount) // 还必须要加这个判断
+            dp[coins[i]] = 1;
+        }
+        for (int i = 1; i <= amount; i++) {
+            for (int j = 0; j < coins.size(); j++) {
+                if (i - coins[j] >= 0 && dp[i - coins[j]]!=0 ) {
+                    if (dp[i] == 0) dp[i] = dp[i - coins[j]] + 1;
+                    else dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
+                }
+
+
+            }
+            //for (int k = 0 ; k<= amount; k++) {
+            //    cout << dp[k] << " ";
+            //}
+            //cout << endl;
+        }
+        if (dp[amount] == 0) return -1;
+        return dp[amount];
+
+    }
+};
+```
+
+这种标记d代码简短，但思路有点绕
+```
+class Solution {
+public:
+    int coinChange(vector<int>& coins, int amount) {
+        //int dp[10003] = {0}; // 并没有给所有元素赋值0
+        // if (amount == 0) return 0; 这个都可以省略了，但很多同学不知道 还需要注意这个
+        vector<int> dp(10003, 0);
+        for (int i = 1; i <= amount; i++) {
+            dp[i] = INT_MAX;
+            for (int j = 0; j < coins.size(); j++) {
+                if (i - coins[j] >= 0 && dp[i - coins[j]]!=INT_MAX ) {
+                    dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
+                }
+            }
+        }
+        if (dp[amount] == INT_MAX) return -1;
+        return dp[amount];
+    }
+};
+```
diff --git a/problems/1005.K次取反后最大化的数组和.md b/problems/1005.K次取反后最大化的数组和.md
@@ -0,0 +1,22 @@
+
+```
+class Solution {
+static bool cmp(int a, int b) {
+    return abs(a) < abs(b);
+}
+public:
+    int largestSumAfterKNegations(vector<int>& A, int K) {
+        sort(A.begin(), A.end(), cmp);
+        for (int i = A.size() - 1; i >= 0; i--) {
+            if (A[i] < 0 && K > 0) {
+                A[i] *= -1;
+                K--;
+            }
+        }
+        while (K--) A[0] *= -1;
+        int result = 0;
+        for (int a : A) result += a;
+        return result;
+    }
+};
+```
diff --git a/problems/1221.分割平衡字符串.md b/problems/1221.分割平衡字符串.md
@@ -0,0 +1,19 @@
+
+这是贪心啊，LRLR 这本身就是平衡子串 , 但要LR这么分割，这是贪心
+
+
+```
+class Solution {
+public:
+    int balancedStringSplit(string s) {
+        int result = 0;
+        int count = 0;
+        for (int i = 0; i < s.size(); i++) {
+            if (s[i] == 'R') count++;
+            else count--;
+            if (count == 0) result++;
+        }
+        return result;
+    }
+};
+```
diff --git a/problems/1403.非递增顺序的最小子序列.md b/problems/1403.非递增顺序的最小子序列.md
@@ -0,0 +1,25 @@
+
+你说这是简单题吧，也是这就使用了贪心算法
+
+```
+class Solution {
+private:
+    static bool cmp(int a, int b) {
+        return a > b;
+    }
+public:
+    vector<int> minSubsequence(vector<int>& nums) {
+        sort(nums.begin(), nums.end(), cmp);
+        int sum = 0;
+        for (int i = 0; i < nums.size(); i++) sum += nums[i];
+        vector<int> result;
+        int resultSum = 0;
+        for (int i = 0; i < nums.size(); i++) {
+            resultSum += nums[i];
+            result.push_back(nums[i]);
+            if (resultSum > (sum - resultSum)) break;
+        }
+        return result;
+    }
+};
+```
diff --git a/problems/1518.换酒问题.md b/problems/1518.换酒问题.md
@@ -0,0 +1,16 @@
+
+```
+// 这道题还是有陷阱啊，15 4 这个例子，答案应该是19 而不是18
+class Solution {
+public:
+    int numWaterBottles(int numBottles, int numExchange) {
+        int result = numBottles;
+        while (numBottles / numExchange) {
+            result += numBottles / numExchange;
+            // 所以不是 numBottles = (numBottles / numExchange)
+            numBottles = (numBottles / numExchange) + (numBottles % numExchange);
+        }
+        return result;
+    }
+};
+```
