Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit579ed13

Browse files
author
liningrui
committed
add new solution
1 parentbf49772 commit579ed13

8 files changed

+470
-0
lines changed
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
# 给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
2+
#
3+
#
4+
#
5+
# 示例 1：
6+
#
7+
#
8+
# 输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
9+
# 输出：6
10+
# 解释：[1,1,1,0,0,1,1,1,1,1,1]
11+
# 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
12+
#
13+
# 示例 2：
14+
#
15+
#
16+
# 输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
17+
# 输出：10
18+
# 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
19+
# 粗体数字从 0 翻转到 1，最长的子数组长度为 10。
20+
#
21+
#
22+
#
23+
# 提示：
24+
#
25+
#
26+
# 1 <= nums.length <= 10⁵
27+
# nums[i] 不是 0 就是 1
28+
# 0 <= k <= nums.length
29+
#
30+
# Related Topics 数组 二分查找 前缀和 滑动窗口 👍 441 👎 0
31+
32+
33+
# leetcode submit region begin(Prohibit modification and deletion)
34+
classSolution:
35+
deflongestOnes(self,nums:List[int],k:int)->int:
36+
counter=0
37+
maxl=0
38+
left=0
39+
fori,ninenumerate(nums):
40+
ifn==0:
41+
counter+=1
42+
whilecounter>kandleft<=i:
43+
ifnums[left]==0:
44+
counter-=1
45+
left+=1
46+
maxl=max(maxl,i-left+1)
47+
returnmaxl
48+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[264]丑数 II.py

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
# 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
2+
#
3+
# 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
4+
#
5+
#
6+
#
7+
# 示例 1：
8+
#
9+
#
10+
# 输入：n = 10
11+
# 输出：12
12+
# 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
13+
#
14+
#
15+
# 示例 2：
16+
#
17+
#
18+
# 输入：n = 1
19+
# 输出：1
20+
# 解释：1 通常被视为丑数。
21+
#
22+
#
23+
#
24+
#
25+
# 提示：
26+
#
27+
#
28+
# 1 <= n <= 1690
29+
#
30+
# Related Topics 哈希表 数学 动态规划 堆（优先队列） 👍 937 👎 0
31+
32+
33+
# leetcode submit region begin(Prohibit modification and deletion)
34+
classSolution:
35+
defnthUglyNumber(self,n:int)->int:
36+
dp= [1]*n
37+
index2,index3,index5=0,0,0
38+
foriinrange(1,n):
39+
val=min(dp[index2]*2,dp[index3]*3 ,dp[index5]*5)
40+
dp[i]=val
41+
# 注意这里不是if/else的关系， 以6为例要同时移动index2和index3
42+
ifval==dp[index2]*2:
43+
index2+=1
44+
ifval==dp[index3]*3:
45+
index3+=1
46+
ifval==dp[index5]*5:
47+
index5+=1
48+
returndp[-1]
49+
50+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[31]下一个排列.py

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
# 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
2+
#
3+
#
4+
# 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
5+
#
6+
#
7+
# 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就
8+
# 是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
9+
#
10+
#
11+
# 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
12+
# 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
13+
# 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
14+
#
15+
#
16+
# 给你一个整数数组 nums ，找出 nums 的下一个排列。
17+
#
18+
# 必须 原地 修改，只允许使用额外常数空间。
19+
#
20+
#
21+
#
22+
# 示例 1：
23+
#
24+
#
25+
# 输入：nums = [1,2,3]
26+
# 输出：[1,3,2]
27+
#
28+
#
29+
# 示例 2：
30+
#
31+
#
32+
# 输入：nums = [3,2,1]
33+
# 输出：[1,2,3]
34+
#
35+
#
36+
# 示例 3：
37+
#
38+
#
39+
# 输入：nums = [1,1,5]
40+
# 输出：[1,5,1]
41+
#
42+
#
43+
#
44+
#
45+
# 提示：
46+
#
47+
#
48+
# 1 <= nums.length <= 100
49+
# 0 <= nums[i] <= 100
50+
#
51+
# Related Topics 数组 双指针 👍 1822 👎 0
52+
53+
54+
# leetcode submit region begin(Prohibit modification and deletion)
55+
classSolution:
56+
defnextPermutation(self,nums:List[int])->None:
57+
"""
58+
Do not return anything, modify nums in-place instead.
59+
"""
60+
#第一个升序
61+
l=len(nums)
62+
pos=None
63+
foriinrange(l-1,0,-1):
64+
ifnums[i]>nums[i-1]:
65+
pos=i-1
66+
break
67+
ifposisNone:
68+
nums[:]=nums[::-1]
69+
return
70+
#后半部分都是降序所以从后向前搜索
71+
foriinrange(l-1,pos,-1):
72+
ifnums[i]>nums[pos]:
73+
nums[i],nums[pos]=nums[pos],nums[i]
74+
break
75+
76+
nums[(pos+1):]=nums[(pos+1):][::-1]
77+
78+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[647]回文子串.py

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
# 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
2+
#
3+
# 回文字符串 是正着读和倒过来读一样的字符串。
4+
#
5+
# 子字符串 是字符串中的由连续字符组成的一个序列。
6+
#
7+
# 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
8+
#
9+
#
10+
#
11+
# 示例 1：
12+
#
13+
#
14+
# 输入：s = "abc"
15+
# 输出：3
16+
# 解释：三个回文子串: "a", "b", "c"
17+
#
18+
#
19+
# 示例 2：
20+
#
21+
#
22+
# 输入：s = "aaa"
23+
# 输出：6
24+
# 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
25+
#
26+
#
27+
#
28+
# 提示：
29+
#
30+
#
31+
# 1 <= s.length <= 1000
32+
# s 由小写英文字母组成
33+
#
34+
# Related Topics 字符串 动态规划 👍 928 👎 0
35+
36+
37+
# leetcode submit region begin(Prohibit modification and deletion)
38+
classSolution:
39+
defcountSubstrings(self,s:str)->int:
40+
l=len(s)
41+
defvalid_count(pt1,pt2):
42+
counter=0
43+
whilept1>=0andpt2<lands[pt1]==s[pt2]:
44+
pt1-=1
45+
pt2+=1
46+
counter+=1
47+
returncounter
48+
counter=0
49+
foriinrange(l):
50+
counter+=valid_count(i,i)
51+
ifi>0:
52+
counter+=valid_count(i-1,i)
53+
returncounter
54+
55+
56+
57+
# leetcode submit region end(Prohibit modification and deletion)
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
# 给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
2+
#
3+
#
4+
# 示例 1：
5+
#
6+
#
7+
# 输入：nums = [10,5,2,6], k = 100
8+
# 输出：8
9+
# 解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
10+
# 需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
11+
#
12+
#
13+
# 示例 2：
14+
#
15+
#
16+
# 输入：nums = [1,2,3], k = 0
17+
# 输出：0
18+
#
19+
#
20+
#
21+
# 提示:
22+
#
23+
#
24+
# 1 <= nums.length <= 3 * 10⁴
25+
# 1 <= nums[i] <= 1000
26+
# 0 <= k <= 10⁶
27+
#
28+
# Related Topics 数组 滑动窗口 👍 574 👎 0
29+
30+
31+
# leetcode submit region begin(Prohibit modification and deletion)
32+
classSolution:
33+
defnumSubarrayProductLessThanK(self,nums:List[int],k:int)->int:
34+
prod=1
35+
left=0
36+
counter=0
37+
l=len(nums)
38+
fori,ninenumerate(nums):
39+
prod*=n
40+
whileprod>=kandleft<=i:
41+
prod/=nums[left]
42+
left+=1
43+
counter+= (i-left+1)
44+
returncounter
45+
46+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[75]颜色分类.py

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
# 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
2+
#
3+
# 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
4+
#
5+
#
6+
#
7+
#
8+
# 必须在不使用库的sort函数的情况下解决这个问题。
9+
#
10+
#
11+
#
12+
# 示例 1：
13+
#
14+
#
15+
# 输入：nums = [2,0,2,1,1,0]
16+
# 输出：[0,0,1,1,2,2]
17+
#
18+
#
19+
# 示例 2：
20+
#
21+
#
22+
# 输入：nums = [2,0,1]
23+
# 输出：[0,1,2]
24+
#
25+
#
26+
#
27+
#
28+
# 提示：
29+
#
30+
#
31+
# n == nums.length
32+
# 1 <= n <= 300
33+
# nums[i] 为 0、1 或 2
34+
#
35+
#
36+
#
37+
#
38+
# 进阶：
39+
#
40+
#
41+
# 你可以不使用代码库中的排序函数来解决这道题吗？
42+
# 你能想出一个仅使用常数空间的一趟扫描算法吗？
43+
#
44+
# Related Topics 数组 双指针 排序 👍 1341 👎 0
45+
46+
47+
# leetcode submit region begin(Prohibit modification and deletion)
48+
classSolution:
49+
defsortColors(self,nums:List[int])->None:
50+
"""
51+
Do not return anything, modify nums in-place instead.
52+
"""
53+
pt0=0
54+
pt1=0
55+
fori,ninenumerate(nums):
56+
ifn==1:
57+
nums[pt1],nums[i]=nums[i],nums[pt1]
58+
pt1+=1
59+
elifn==0:
60+
nums[pt0],nums[i]=nums[i],nums[pt0]
61+
pt0+=1
62+
#核心就是这个部分当ptr比1的ptr更高的时候，把被误换出去的1给重新换回来
63+
ifi>pt1:
64+
nums[pt1],nums[i]=nums[i],nums[pt1]
65+
pt1+=1
66+
returnnums
67+
68+
69+
70+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[763]划分字母区间.py

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
# 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
2+
#
3+
#
4+
#
5+
# 示例：
6+
#
7+
#
8+
# 输入：S = "ababcbacadefegdehijhklij"
9+
# 输出：[9,7,8]
10+
# 解释：
11+
# 划分结果为 "ababcbaca", "defegde", "hijhklij"。
12+
# 每个字母最多出现在一个片段中。
13+
# 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
14+
#
15+
#
16+
#
17+
#
18+
# 提示：
19+
#
20+
#
21+
# S的长度在[1, 500]之间。
22+
# S只包含小写字母 'a' 到 'z' 。
23+
#
24+
# Related Topics 贪心 哈希表 双指针 字符串 👍 769 👎 0
25+
26+
27+
# leetcode submit region begin(Prohibit modification and deletion)
28+
classSolution:
29+
defpartitionLabels(self,s:str)->List[int]:
30+
pos=dict()
31+
fori,ninenumerate(s):
32+
pos[n]=i
33+
34+
result= []
35+
left=0
36+
right=0
37+
fori,ninenumerate(s):
38+
right=max(right,pos[n])
39+
ifi==right:
40+
result.append(right-left+1)
41+
left=right+1
42+
returnresult
43+
44+
# leetcode submit region end(Prohibit modification and deletion)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp