add new solution

liningrui · liningrui · commit 579ed13f5af7 · 2022-07-18T21:50:56.000+08:00
diff --git a/script/[1004]最大连续1的个数 III.py b/script/[1004]最大连续1的个数 III.py
@@ -0,0 +1,48 @@
+# 给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。 
+# 
+#  
+# 
+#  示例 1： 
+# 
+#  
+# 输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
+# 输出：6
+# 解释：[1,1,1,0,0,1,1,1,1,1,1]
+# 粗体数字从 0 翻转到 1，最长的子数组长度为 6。 
+# 
+#  示例 2： 
+# 
+#  
+# 输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
+# 输出：10
+# 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
+# 粗体数字从 0 翻转到 1，最长的子数组长度为 10。 
+# 
+#  
+# 
+#  提示： 
+# 
+#  
+#  1 <= nums.length <= 10⁵ 
+#  nums[i] 不是 0 就是 1 
+#  0 <= k <= nums.length 
+#  
+#  Related Topics 数组 二分查找 前缀和 滑动窗口 👍 441 👎 0
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def longestOnes(self, nums: List[int], k: int) -> int:
+        counter = 0
+        maxl = 0
+        left = 0
+        for i,n in enumerate(nums):
+            if n==0:
+                counter+=1
+            while counter>k and left<=i:
+                if nums[left]==0:
+                    counter-=1
+                left+=1
+            maxl = max(maxl, i-left+1)
+        return maxl
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/script/[264]丑数 II.py b/script/[264]丑数 II.py
@@ -0,0 +1,50 @@
+# 给你一个整数 n ，请你找出并返回第 n 个 丑数 。 
+# 
+#  丑数 就是只包含质因数 2、3 和/或 5 的正整数。 
+# 
+#  
+# 
+#  示例 1： 
+# 
+#  
+# 输入：n = 10
+# 输出：12
+# 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
+#  
+# 
+#  示例 2： 
+# 
+#  
+# 输入：n = 1
+# 输出：1
+# 解释：1 通常被视为丑数。
+#  
+# 
+#  
+# 
+#  提示： 
+# 
+#  
+#  1 <= n <= 1690 
+#  
+#  Related Topics 哈希表 数学 动态规划 堆（优先队列） 👍 937 👎 0
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def nthUglyNumber(self, n: int) -> int:
+        dp = [1] * n
+        index2, index3, index5 = 0,0,0
+        for i in range(1, n):
+            val = min(dp[index2] *2, dp[index3] * 3 , dp[index5]*5)
+            dp[i] = val
+            # 注意这里不是if/else的关系， 以6为例要同时移动index2和index3
+            if val == dp[index2]*2:
+                index2+=1
+            if val ==dp[index3]*3:
+                index3+=1
+            if val ==dp[index5]*5:
+                index5+=1
+        return dp[-1]
+
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/script/[31]下一个排列.py b/script/[31]下一个排列.py
@@ -0,0 +1,78 @@
+# 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 
+# 
+#  
+#  例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 
+#  
+# 
+#  整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就
+# 是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。 
+# 
+#  
+#  例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。 
+#  类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。 
+#  而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。 
+#  
+# 
+#  给你一个整数数组 nums ，找出 nums 的下一个排列。 
+# 
+#  必须 原地 修改，只允许使用额外常数空间。 
+# 
+#  
+# 
+#  示例 1： 
+# 
+#  
+# 输入：nums = [1,2,3]
+# 输出：[1,3,2]
+#  
+# 
+#  示例 2： 
+# 
+#  
+# 输入：nums = [3,2,1]
+# 输出：[1,2,3]
+#  
+# 
+#  示例 3： 
+# 
+#  
+# 输入：nums = [1,1,5]
+# 输出：[1,5,1]
+#  
+# 
+#  
+# 
+#  提示： 
+# 
+#  
+#  1 <= nums.length <= 100 
+#  0 <= nums[i] <= 100 
+#  
+#  Related Topics 数组 双指针 👍 1822 👎 0
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def nextPermutation(self, nums: List[int]) -> None:
+        """
+        Do not return anything, modify nums in-place instead.
+        """
+        #第一个升序
+        l = len(nums)
+        pos = None
+        for i in range(l-1,0,-1):
+            if nums[i]>nums[i-1]:
+                pos = i-1
+                break
+        if pos is None:
+            nums[:] = nums[::-1]
+            return
+        #后半部分都是降序所以从后向前搜索
+        for i in range(l-1, pos,-1):
+            if nums[i]> nums[pos]:
+                nums[i], nums[pos] = nums[pos], nums[i]
+                break
+
+        nums[(pos+1):] = nums[(pos+1):][::-1]
+
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/script/[647]回文子串.py b/script/[647]回文子串.py
@@ -0,0 +1,57 @@
+# 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 
+# 
+#  回文字符串 是正着读和倒过来读一样的字符串。 
+# 
+#  子字符串 是字符串中的由连续字符组成的一个序列。 
+# 
+#  具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。 
+# 
+#  
+# 
+#  示例 1： 
+# 
+#  
+# 输入：s = "abc"
+# 输出：3
+# 解释：三个回文子串: "a", "b", "c"
+#  
+# 
+#  示例 2： 
+# 
+#  
+# 输入：s = "aaa"
+# 输出：6
+# 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 
+# 
+#  
+# 
+#  提示： 
+# 
+#  
+#  1 <= s.length <= 1000 
+#  s 由小写英文字母组成 
+#  
+#  Related Topics 字符串 动态规划 👍 928 👎 0
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def countSubstrings(self, s: str) -> int:
+        l = len(s)
+        def valid_count(pt1,pt2):
+            counter  =0
+            while pt1>=0 and pt2<l and s[pt1]==s[pt2]:
+                pt1-=1
+                pt2+=1
+                counter+=1
+            return counter
+        counter =0
+        for i in range(l):
+            counter += valid_count(i,i)
+            if i>0:
+                counter+= valid_count(i-1,i)
+        return counter
+
+
+
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/script/[713]乘积小于 K 的子数组.py b/script/[713]乘积小于 K 的子数组.py
@@ -0,0 +1,46 @@
+# 给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
+#  
+# 
+#  示例 1： 
+# 
+#  
+# 输入：nums = [10,5,2,6], k = 100
+# 输出：8
+# 解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
+# 需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
+#  
+# 
+#  示例 2： 
+# 
+#  
+# 输入：nums = [1,2,3], k = 0
+# 输出：0 
+# 
+#  
+# 
+#  提示: 
+# 
+#  
+#  1 <= nums.length <= 3 * 10⁴ 
+#  1 <= nums[i] <= 1000 
+#  0 <= k <= 10⁶ 
+#  
+#  Related Topics 数组 滑动窗口 👍 574 👎 0
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
+        prod =1
+        left =0
+        counter = 0
+        l = len(nums)
+        for i,n in enumerate(nums):
+            prod *=n
+            while prod >= k and left<=i:
+                prod/=nums[left]
+                left+=1
+            counter += (i-left+1)
+        return counter
+
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/script/[75]颜色分类.py b/script/[75]颜色分类.py
@@ -0,0 +1,70 @@
+# 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 
+# 
+#  我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 
+# 
+#  
+#  
+# 
+#  必须在不使用库的sort函数的情况下解决这个问题。 
+# 
+#  
+# 
+#  示例 1： 
+# 
+#  
+# 输入：nums = [2,0,2,1,1,0]
+# 输出：[0,0,1,1,2,2]
+#  
+# 
+#  示例 2： 
+# 
+#  
+# 输入：nums = [2,0,1]
+# 输出：[0,1,2]
+#  
+# 
+#  
+# 
+#  提示： 
+# 
+#  
+#  n == nums.length 
+#  1 <= n <= 300 
+#  nums[i] 为 0、1 或 2 
+#  
+# 
+#  
+# 
+#  进阶： 
+# 
+#  
+#  你可以不使用代码库中的排序函数来解决这道题吗？ 
+#  你能想出一个仅使用常数空间的一趟扫描算法吗？ 
+#  
+#  Related Topics 数组 双指针 排序 👍 1341 👎 0
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def sortColors(self, nums: List[int]) -> None:
+        """
+        Do not return anything, modify nums in-place instead.
+        """
+        pt0 = 0
+        pt1 = 0
+        for i,n in enumerate(nums):
+            if n==1:
+                nums[pt1], nums[i] = nums[i],nums[pt1]
+                pt1+=1
+            elif n==0:
+                nums[pt0], nums[i] = nums[i],nums[pt0]
+                pt0+=1
+                #核心就是这个部分当ptr比1的ptr更高的时候，把被误换出去的1给重新换回来
+                if i> pt1:
+                    nums[pt1],nums[i] = nums[i],nums[pt1]
+                    pt1+=1
+        return nums
+
+
+
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/script/[763]划分字母区间.py b/script/[763]划分字母区间.py
@@ -0,0 +1,44 @@
+# 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。 
+# 
+#  
+# 
+#  示例： 
+# 
+#  
+# 输入：S = "ababcbacadefegdehijhklij"
+# 输出：[9,7,8]
+# 解释：
+# 划分结果为 "ababcbaca", "defegde", "hijhklij"。
+# 每个字母最多出现在一个片段中。
+# 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
+#  
+# 
+#  
+# 
+#  提示： 
+# 
+#  
+#  S的长度在[1, 500]之间。 
+#  S只包含小写字母 'a' 到 'z' 。 
+#  
+#  Related Topics 贪心 哈希表 双指针 字符串 👍 769 👎 0
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def partitionLabels(self, s: str) -> List[int]:
+        pos = dict()
+        for i,n in enumerate(s):
+            pos[n] = i
+
+        result = []
+        left = 0
+        right = 0
+        for i,n in enumerate(s):
+            right = max(right, pos[n])
+            if i==right:
+                result.append(right-left+1)
+                left = right+1
+        return result
+
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/script/[904]水果成篮.py b/script/[904]水果成篮.py
