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

Commitcdb5fa6

Browse files
committed
add new solutions
1 parentda1e870 commitcdb5fa6

15 files changed

+764
-1
lines changed

‎script/[1155]掷骰子的N种方法.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,4 +46,15 @@
4646
# leetcode submit region begin(Prohibit modification and deletion)
4747
classSolution:
4848
defnumRollsToTarget(self,n:int,k:int,target:int)->int:
49+
dp= [[0]* (target+1)foriinrange(n+1)]
50+
dp[0][0]=1
51+
foriinrange(1,n+1):
52+
fortinrange(1,target+1):
53+
forjinrange(1,min(t,k)+1):
54+
dp[i][t]+=dp[i-1][t-j]
55+
dp[i][t]%=1000000007
56+
returndp[-1][-1]
57+
58+
59+
4960
# leetcode submit region end(Prohibit modification and deletion)

‎script/[135]分发糖果.py

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
# n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
2+
#
3+
# 你需要按照以下要求，给这些孩子分发糖果：
4+
#
5+
#
6+
# 每个孩子至少分配到 1 个糖果。
7+
# 相邻两个孩子评分更高的孩子会获得更多的糖果。
8+
#
9+
#
10+
# 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
11+
#
12+
#
13+
#
14+
# 示例 1：
15+
#
16+
#
17+
# 输入：ratings = [1,0,2]
18+
# 输出：5
19+
# 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
20+
#
21+
#
22+
# 示例 2：
23+
#
24+
#
25+
# 输入：ratings = [1,2,2]
26+
# 输出：4
27+
# 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
28+
# 第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
29+
#
30+
#
31+
#
32+
# 提示：
33+
#
34+
#
35+
# n == ratings.length
36+
# 1 <= n <= 2 * 104
37+
# 0 <= ratings[i] <= 2 * 104
38+
#
39+
# Related Topics 贪心 数组
40+
# 👍 934 👎 0
41+
42+
43+
# leetcode submit region begin(Prohibit modification and deletion)
44+
classSolution:
45+
defcandy(self,ratings:List[int])->int:
46+
l=len(ratings)
47+
dp= [1]*l
48+
foriinrange(1,l):
49+
ifratings[i]>ratings[i-1]:
50+
dp[i]=max(dp[i],dp[i-1]+1)
51+
foriinrange(l-2,-1,-1):
52+
ifratings[i]>ratings[i+1]:
53+
dp[i]=max(dp[i],dp[i+1]+1)
54+
returnsum(dp)
55+
56+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[169]多数元素.py

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
# 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
2+
#
3+
# 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
4+
#
5+
#
6+
#
7+
# 示例 1：
8+
#
9+
#
10+
# 输入：nums = [3,2,3]
11+
# 输出：3
12+
#
13+
# 示例 2：
14+
#
15+
#
16+
# 输入：nums = [2,2,1,1,1,2,2]
17+
# 输出：2
18+
#
19+
#
20+
#
21+
# 提示：
22+
#
23+
#
24+
# n == nums.length
25+
# 1 <= n <= 5 * 104
26+
# -109 <= nums[i] <= 109
27+
#
28+
#
29+
#
30+
#
31+
# 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
32+
# Related Topics 数组 哈希表 分治 计数 排序
33+
# 👍 1509 👎 0
34+
35+
36+
# leetcode submit region begin(Prohibit modification and deletion)
37+
classSolution:
38+
defmajorityElement(self,nums:List[int])->int:
39+
val=nums[0]
40+
counter=1
41+
foriinrange(1,len(nums)):
42+
ifnums[i]==val:
43+
counter+=1
44+
else:
45+
counter-=1
46+
ifcounter==0:
47+
counter=1
48+
val=nums[i]
49+
returnval
50+
51+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[179]最大数.py

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
# 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
2+
#
3+
# 注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
4+
#
5+
#
6+
#
7+
# 示例 1：
8+
#
9+
#
10+
# 输入：nums = [10,2]
11+
# 输出："210"
12+
#
13+
# 示例 2：
14+
#
15+
#
16+
# 输入：nums = [3,30,34,5,9]
17+
# 输出："9534330"
18+
#
19+
#
20+
#
21+
#
22+
# 提示：
23+
#
24+
#
25+
# 1 <= nums.length <= 100
26+
# 0 <= nums[i] <= 109
27+
#
28+
# Related Topics 贪心 字符串 排序
29+
# 👍 978 👎 0
30+
31+
32+
# leetcode submit region begin(Prohibit modification and deletion)
33+
classSolution:
34+
deflargestNumber(self,nums:List[int])->str:
35+
defcmp(a,b):
36+
ifa+b<b+a:
37+
return-1
38+
elifa+b==b+a:
39+
return0
40+
else:
41+
return1
42+
nums=sorted([str(i)foriinnums],key=functools.cmp_to_key(cmp),reverse=True)
43+
ifnums[0]=='0':
44+
return'0'
45+
else:
46+
return''.join(nums)
47+
# leetcode submit region end(Prohibit modification and deletion)
Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
# 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i
2+
# 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
3+
#
4+
# 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第
5+
# j 个人的属性（queue[0] 是排在队列前面的人）。
6+
#
7+
#
8+
#
9+
#
10+
#
11+
#
12+
# 示例 1：
13+
#
14+
#
15+
# 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
16+
# 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
17+
# 解释：
18+
# 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
19+
# 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
20+
# 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
21+
# 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
22+
# 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
23+
# 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
24+
# 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
25+
#
26+
#
27+
# 示例 2：
28+
#
29+
#
30+
# 输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
31+
# 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
32+
#
33+
#
34+
#
35+
#
36+
# 提示：
37+
#
38+
#
39+
# 1 <= people.length <= 2000
40+
# 0 <= hi <= 106
41+
# 0 <= ki < people.length
42+
# 题目数据确保队列可以被重建
43+
#
44+
# Related Topics 贪心 树状数组 线段树 数组 排序
45+
# 👍 1347 👎 0
46+
47+
48+
# leetcode submit region begin(Prohibit modification and deletion)
49+
classSolution:
50+
defreconstructQueue(self,people:List[List[int]])->List[List[int]]:
51+
people=sorted(people,key=lambdax:(x[0],-x[1]),reverse=True)
52+
ans= []
53+
forpinpeople:
54+
ans.insert(p[1],p)
55+
returnans
56+
57+
58+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[435]无重叠区间.py

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
# 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重
2+
# 叠 。
3+
#
4+
#
5+
#
6+
# 示例 1:
7+
#
8+
#
9+
# 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
10+
# 输出: 1
11+
# 解释: 移除 [1,3] 后，剩下的区间没有重叠。
12+
#
13+
#
14+
# 示例 2:
15+
#
16+
#
17+
# 输入: intervals = [ [1,2], [1,2], [1,2] ]
18+
# 输出: 2
19+
# 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
20+
#
21+
#
22+
# 示例 3:
23+
#
24+
#
25+
# 输入: intervals = [ [1,2], [2,3] ]
26+
# 输出: 0
27+
# 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
28+
#
29+
#
30+
#
31+
#
32+
# 提示:
33+
#
34+
#
35+
# 1 <= intervals.length <= 105
36+
# intervals[i].length == 2
37+
# -5 * 104 <= starti < endi <= 5 * 104
38+
#
39+
# Related Topics 贪心 数组 动态规划 排序
40+
# 👍 751 👎 0
41+
42+
43+
# leetcode submit region begin(Prohibit modification and deletion)
44+
classSolution:
45+
deferaseOverlapIntervals(self,intervals:List[List[int]])->int:
46+
intervals=sorted(intervals,key=lambdax:x[1])
47+
right=intervals[0][1]
48+
tmp=intervals[0]
49+
counter=0
50+
foriinrange(1,len(intervals)):
51+
ifintervals[i][0]<right:
52+
counter+=1
53+
else:
54+
right=intervals[i][1]
55+
returncounter
56+
57+
58+
# leetcode submit region end(Prohibit modification and deletion)
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
# 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示
2+
# 水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
3+
#
4+
# 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xs
5+
# tart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
6+
#
7+
# 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
8+
#
9+
#
10+
# 示例 1：
11+
#
12+
#
13+
# 输入：points = [[10,16],[2,8],[1,6],[7,12]]
14+
# 输出：2
15+
# 解释：气球可以用2支箭来爆破:
16+
# -在x = 6处射出箭，击破气球[2,8]和[1,6]。
17+
# -在x = 11处发射箭，击破气球[10,16]和[7,12]。
18+
#
19+
# 示例 2：
20+
#
21+
#
22+
# 输入：points = [[1,2],[3,4],[5,6],[7,8]]
23+
# 输出：4
24+
# 解释：每个气球需要射出一支箭，总共需要4支箭。
25+
#
26+
# 示例 3：
27+
#
28+
#
29+
# 输入：points = [[1,2],[2,3],[3,4],[4,5]]
30+
# 输出：2
31+
# 解释：气球可以用2支箭来爆破:
32+
# - 在x = 2处发射箭，击破气球[1,2]和[2,3]。
33+
# - 在x = 4处射出箭，击破气球[3,4]和[4,5]。
34+
#
35+
#
36+
#
37+
#
38+
#
39+
# 提示:
40+
#
41+
#
42+
# 1 <= points.length <= 105
43+
# points[i].length == 2
44+
# -231 <= xstart < xend <= 231 - 1
45+
#
46+
# Related Topics 贪心 数组 排序
47+
# 👍 637 👎 0
48+
49+
50+
# leetcode submit region begin(Prohibit modification and deletion)
51+
classSolution:
52+
deffindMinArrowShots(self,points:List[List[int]])->int:
53+
counter=1
54+
# sort了左边界，所以只用判断右边界
55+
points=sorted(points,key=lambdax:x[0])
56+
right=points[0][1]
57+
foriinrange(1,len(points)):
58+
ifpoints[i][0]<=right:
59+
right=min(right,points[i][1])
60+
else:
61+
counter+=1
62+
right=points[i][1]
63+
returncounter
64+
# leetcode submit region end(Prohibit modification and deletion)

0 commit comments

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