Merge branch 'main' of https://github.com/jaredliw/algorithm-base

jaredliw · jaredliw · commit 1b247df1fd10 · 2021-07-23T21:19:29.000+08:00
diff --git a/animation-simulation/剑指offer/1的个数.md b/animation-simulation/剑指offer/1的个数.md
@@ -4,7 +4,7 @@
 >
 > 感谢支持，该仓库会一直维护，希望对各位有一丢丢帮助。
 >
-> 另外希望手机阅读的同学可以来我的 <u>[**公众号：袁厨的算法小屋**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。 
+> 另外希望手机阅读的同学可以来我的 <u>[**公众号：袁厨的算法小屋**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。
 
 今天我们来看一道贼棒的题目，题目不长，很经典，也很容易理解，我们一起来看一哈吧，
 
@@ -87,7 +87,7 @@
 
 那我们将**当前位左边的定义为高位**，**当前位右边的定义位低位**。
 
-> 例：n = 1004 ，此时指针指向十位（当前位）num = 10，高位为百位，千位，低位为个位 
+> 例：n = 1004 ，此时指针指向十位（当前位）num = 10，高位为百位，千位，低位为个位
 
 而且我们某一位的取值范围为 0 ~ 9,那么我们可以将这 10 个数分为 3 类，小于 1 （当前位数字为 0 ），等于 1（当前位数字为 1 ） ，大于 1（当前位上数字为 2 ~ 9），下面我们就来分别考虑三种情况。
 
@@ -139,7 +139,7 @@
 
 可以继续想到密码盘，求第二段时，把前 3 位固定，只能改变最后一位。最后一位最大能到 4 ，那么共有几种情况？
 
-### n = 1024 
+### n = 1024
 
 我们想要计算出**小于等于 1024 的非负整数中**，十位上出现 1 的次数。
 
@@ -187,12 +187,12 @@ class Solution {
         while (high != 0 || cur != 0) {
             cur = high % 10;
             high /= 10;
-            //这里我们可以提出 high * num 因为我们发现无论为几，都含有它 
+            //这里我们可以提出 high * num 因为我们发现无论为几，都含有它
             if (cur == 0) count += high * num;
-            else if (cur == 1) count += high * num + 1 + low; 
+            else if (cur == 1) count += high * num + 1 + low;
             else count += (high + 1) * num;
             //低位
-            low = cur * num + low;                  
+            low = cur * num + low;
             num *= 10;
         }
         return count;
@@ -209,10 +209,10 @@ class Solution {
         while high != 0 || cur != 0 {
             cur = high % 10
             high /= 10
-            //这里我们可以提出 high * num 因为我们发现无论为几，都含有它 
+            //这里我们可以提出 high * num 因为我们发现无论为几，都含有它
             if cur == 0 {
                 count += high * num
-            } else if cur == 1 { 
+            } else if cur == 1 {
                 count += high * num + 1 + low
             } else {
                 count += (high + 1) * num
@@ -227,5 +227,37 @@ class Solution {
 
 时间复杂度 : O(logn)  空间复杂度 O(1)
 
-
-
+C++ Code:
+
+```C++
+class Solution
+{
+public:
+    int countDigitOne(int n)
+    {
+        //  高位,      低位,    当前位
+        int high = n, low = 0, cur = 0;
+        int count = 0, num = 1;
+
+        //数字是0的时候完全没必要继续计算
+        while (high != 0)
+        {
+            cur = high % 10;
+            high /= 10;
+            //这里我们可以提出 high * num 因为我们发现无论为几，都含有它
+            if (cur == 0)
+                count += (high * num);
+            else if (cur == 1)
+                count += (high * num + 1 + low);
+            else
+                count += ((high + 1) * num);
+            //低位
+            low = cur * num + low;
+            //提前检查剩余数字, 以免溢出
+            if (high != 0)
+                num *= 10;
+        }
+        return count;
+    }
+};
+```
diff --git a/animation-simulation/数组篇/leetcode1052爱生气的书店老板.md b/animation-simulation/数组篇/leetcode1052爱生气的书店老板.md
@@ -4,7 +4,7 @@
 >
 > 感谢支持，该仓库会一直维护，希望对各位有一丢丢帮助。
 >
-> 另外希望手机阅读的同学可以来我的 <u>[**公众号：袁厨的算法小屋**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。 
+> 另外希望手机阅读的同学可以来我的 <u>[**公众号：袁厨的算法小屋**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。
 
 #### [1052. 爱生气的书店老板](https://leetcode-cn.com/problems/grumpy-bookstore-owner/)
 
@@ -48,7 +48,7 @@ rightsum 是窗口右区间的值，和左区间加和方式一样。那么我
 
 我们此时移动了窗口，
 
-则左半区间范围扩大，但是 leftsum 的值没有变，这时因为新加入的值，所对应的 grumpy[i] == 1，所以其值不会发生改变，因为我们只统计 grumpy[i] == 0 的值， 
+则左半区间范围扩大，但是 leftsum 的值没有变，这时因为新加入的值，所对应的 grumpy[i] == 1，所以其值不会发生改变，因为我们只统计 grumpy[i] == 0 的值，
 
 右半区间范围减少，rightsum 值也减少，因为右半区间减小的值，其对应的 grumpy[i] == 0，所以 rightsum -=  grumpy[i]。
 
@@ -72,15 +72,15 @@ class Solution {
             }
         }
         //窗口的值
-        for (int i = 0; i < X; ++i) {        
-              winsum += customers[i];          
+        for (int i = 0; i < X; ++i) {
+              winsum += customers[i];
         }
         int leftsum = 0;
         //窗口左边缘
         int left = 1;
         //窗口右边缘
         int right = X;
-        int maxcustomer = winsum + leftsum + rightsum;     
+        int maxcustomer = winsum + leftsum + rightsum;
         while (right < customers.length) {
             //重新计算左区间的值，也可以用 customer 值和 grumpy 值相乘获得
             if (grumpy[left-1] == 0) {
@@ -97,7 +97,7 @@ class Solution {
             //移动窗口
             left++;
             right++;
-        }        
+        }
         return maxcustomer;
     }
 }
@@ -151,8 +151,54 @@ class Solution {
             left += 1
             right += 1
         }
-        
+
         return maxCustomer
     }
 }
 ```
+
+C++ Code
+
+```C++
+class Solution
+{
+public:
+    int maxSatisfied(vector<int> &customers, vector<int> &grumpy, int minutes)
+    {
+        for_each(grumpy.begin(), grumpy.end(), [](auto &g){ g = !g; });
+        vector<int> osum(customers.size(), 0);
+
+        //先初始化第一个元素
+        osum[0] = customers[0] * grumpy[0];
+        //计算前缀和, osum是origin sum
+        for (int i = 1; i < osum.size(); i++)
+        {
+            osum[i] = osum[i - 1] + customers[i] * grumpy[i];
+        }
+
+        //计算连续minutes的和
+        vector<int> msum(customers.size() - minutes + 1, 0);
+        for (int i = 0; i < minutes; i++)
+        {
+            msum[0] += customers[i];
+        }
+        for (int i = 1; i < msum.size(); i++)
+        {
+            msum[i] = msum[i - 1] - customers[i - 1] + customers[i + minutes - 1];
+        }
+
+        //分成三段计算
+        int result = 0;
+        for (int i = 0; i < msum.size(); i++)
+        {
+            //左                                         中         右
+            //注意左的边界条件, 可以使用边界测试
+            int sum = ((i - 1 >= 0) ? osum[i - 1] : 0) + msum[i] + osum[osum.size() - 1] - osum[i + minutes - 1];
+            if (sum > result)
+                result = sum;
+        }
+
+        return result;
+    }
+};
+```
diff --git a/animation-simulation/数组篇/leetcode41缺失的第一个正数.md b/animation-simulation/数组篇/leetcode41缺失的第一个正数.md
@@ -2,7 +2,7 @@
 >
 > 感谢支持，该仓库会一直维护，希望对各位有一丢丢帮助。
 >
-> 另外希望手机阅读的同学可以来我的 <u>[**公众号：袁厨的算法小屋**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。 
+> 另外希望手机阅读的同学可以来我的 <u>[**公众号：袁厨的算法小屋**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。
 
 #### [41. 缺失的第一个正数](https://leetcode-cn.com/problems/first-missing-positive/)
 
@@ -53,15 +53,15 @@ class Solution {
         for (int x : nums) {
             if (x > 0 && x < res.length) {
                res[x] = x;
-            }       
+            }
         }
         //遍历查找,发现不一样时直接返回
         for (int i = 1; i < res.length; i++) {
             if (res[i] != i) {
                 return i;
-            }           
+            }
         }
-        //缺少最后一个，例如 1，2，3此时缺少 4 ，细节2 
+        //缺少最后一个，例如 1，2，3此时缺少 4 ，细节2
         return res.length;
     }
 }
@@ -85,7 +85,7 @@ class Solution:
         for i in range(1, len(res)):
             if res[i] != i:
                 return i
-        # 缺少最后一个，例如 1，2，3此时缺少 4 ，细节2 
+        # 缺少最后一个，例如 1，2，3此时缺少 4 ，细节2
         return len(res)
 ```
 
@@ -145,7 +145,7 @@ class Solution {
         for (int i = 0; i < len; ++i) {
             //需要考虑指针移动情况，大于0，小于len+1，不等与i+1，两个交换的数相等时，防止死循环
             while (nums[i] > 0 && nums[i] < len + 1 && nums[i] != i+1 && nums[i] != nums[nums[i]-1]) {
-                swap(nums,i,nums[i] - 1);               
+                swap(nums,i,nums[i] - 1);
             }
         }
         //遍历寻找缺失的正整数
@@ -207,10 +207,10 @@ class Solution {
         for i in 0..<len {
             // 需要考虑指针移动情况，大于0，小于len+1，不等与i+1，
             // 两个交换的数相等时，防止死循环
-            while nums[i] > 0 
-                  && nums[i] < len + 1 
+            while nums[i] > 0
+                  && nums[i] < len + 1
                   && nums[i] != i + 1
-                  && nums[i] != nums[nums[i] - 1] 
+                  && nums[i] != nums[nums[i] - 1]
             {
                 //nums.swapAt(i, (nums[i] - 1)) // 系统方法
                 self.swap(&nums, i, (nums[i] - 1)) // 自定义方法
@@ -232,3 +232,44 @@ class Solution {
     }
 }
 ```
+
+C++ Code
+
+```C++
+class Solution
+{
+public:
+    int firstMissingPositive(vector<int> &nums)
+    {
+        int size = nums.size();
+        //判断范围是否符合要求
+        auto inRange = [](auto s, auto e)
+        {
+            return [s, e](auto &n)
+            {
+                return e >= n && n >= s;
+            };
+        };
+        auto cusInRange = inRange(1, size);
+        //增加数组长度, 便于计算, 不需要再转换
+        nums.push_back(0);
+
+        for (int i = 0; i < size; i++)
+        {
+            //将不在正确位置的元素放到正确位置上
+            while (cusInRange(nums[i]) && nums[i] != i && nums[nums[i]] != nums[i])
+            {
+                swap(nums[i], nums[nums[i]]);
+            }
+        }
+
+        //找出缺失的元素
+        for (int i = 1; i <= size; i++)
+        {
+            if (nums[i] != i)
+                return i;
+        }
+        return size + 1;
+    }
+};
+```
diff --git a/animation-simulation/数组篇/leetcode485最大连续1的个数.md b/animation-simulation/数组篇/leetcode485最大连续1的个数.md
@@ -2,7 +2,7 @@
 >
 > 感谢支持，该仓库会一直维护，希望对各位有一丢丢帮助。
 >
-> 另外希望手机阅读的同学可以来我的 <u>[**公众号：袁厨的算法小屋**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。 
+> 另外希望手机阅读的同学可以来我的 <u>[**公众号：袁厨的算法小屋**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。
 
 #### [485. 最大连续 1 的个数](https://leetcode-cn.com/problems/max-consecutive-ones/)
 
@@ -16,7 +16,7 @@
 
 我的这个方法比较奇怪，但是效率还可以，战胜了 100% , 尽量减少了 Math.max()的使用，我们来看一下具体思路，利用 right 指针进行探路，如果遇到 1 则继续走，遇到零时则停下，求当前 1 的个数。
 
-这时我们可以通过 right - left 得到 1 的 个数，因为此时我们的 right 指针指在 0 处，所以不需要和之前一样通过 right - left + 1 获得窗口长度。 
+这时我们可以通过 right - left 得到 1 的 个数，因为此时我们的 right 指针指在 0 处，所以不需要和之前一样通过 right - left + 1 获得窗口长度。
 
 然后我们再使用 while 循环，遍历完为 0 的情况，跳到下一段为 1 的情况，然后移动 left 指针。 left = right，站在同一起点，继续执行上诉过程。
 
@@ -125,7 +125,7 @@ class Solution {
 
         int count = 0;
         int maxcount = 0;
-        
+
         for (int i = 0; i < nums.length; ++i) {
             if (nums[i] == 1) {
                 count++;
@@ -172,8 +172,43 @@ class Solution {
                 maxCount = max(maxCount, count)
                 count = 0
             }
-        }        
+        }
         return max(maxCount, count)
     }
 }
 ```
+
+C++ Code
+
+```C++
+class Solution
+{
+public:
+    int findMaxConsecutiveOnes(vector<int> &nums)
+    {
+        int s = 0;
+        int e = 0;
+        int result = 0;
+        int size = nums.size();
+
+        while (s < size && e < size)
+        {
+            while (s < size && nums[s++] == 1)
+            {
+                e = s;
+                while (e < size && nums[e] == 1)
+                {
+                    e++;
+                };
+                //注意需要加1, 可以使用极限条件测试
+                int r = e - s + 1;
+                if (r > result)
+                    result = r;
+                s = e;
+            }
+        }
+
+        return result;
+    }
+};
+```
diff --git a/animation-simulation/数组篇/leetcode560和为K的子数组.md b/animation-simulation/数组篇/leetcode560和为K的子数组.md
