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

Commit4c8562a

Browse files
committed
add new solution
1 parent924c03b commit4c8562a

File tree

61 files changed

+3229
-18
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

61 files changed

+3229
-18
lines changed

‎script/[1035]不相交的线.py

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
# 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
2+
#
3+
# 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
4+
#
5+
#
6+
# nums1[i] == nums2[j]
7+
# 且绘制的直线不与任何其他连线（非水平线）相交。
8+
#
9+
#
10+
# 请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
11+
#
12+
# 以这种方法绘制线条，并返回可以绘制的最大连线数。
13+
#
14+
#
15+
#
16+
# 示例 1：
17+
#
18+
#
19+
# 输入：nums1 = [1,4,2], nums2 = [1,2,4]
20+
# 输出：2
21+
# 解释：可以画出两条不交叉的线，如上图所示。
22+
# 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相
23+
# 交。
24+
#
25+
#
26+
#
27+
# 示例 2：
28+
#
29+
#
30+
# 输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
31+
# 输出：3
32+
#
33+
#
34+
#
35+
# 示例 3：
36+
#
37+
#
38+
# 输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
39+
# 输出：2
40+
#
41+
#
42+
#
43+
#
44+
#
45+
# 提示：
46+
#
47+
#
48+
# 1 <= nums1.length, nums2.length <= 500
49+
# 1 <= nums1[i], nums2[j] <= 2000
50+
#
51+
#
52+
#
53+
# Related Topics 数组 动态规划
54+
# 👍 346 👎 0
55+
56+
57+
# leetcode submit region begin(Prohibit modification and deletion)
58+
classSolution:
59+
defmaxUncrossedLines(self,nums1:List[int],nums2:List[int])->int:
60+
l1=len(nums1)
61+
l2=len(nums2)
62+
dp= [[0]* (l2+1)foriinrange(l1+1)]
63+
foriinrange(1,l1+1):
64+
forjinrange(1,l2+1):
65+
ifnums1[i-1]==nums2[j-1]:
66+
dp[i][j]=dp[i-1][j-1]+1
67+
else:
68+
dp[i][j]=max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
69+
returndp[-1][-1]
70+
# leetcode submit region end(Prohibit modification and deletion)
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
# 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
2+
#
3+
# 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
4+
#
5+
#
6+
# 如果 x == y，那么两块石头都会被完全粉碎；
7+
# 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
8+
#
9+
#
10+
# 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
11+
#
12+
#
13+
#
14+
# 示例 1：
15+
#
16+
#
17+
# 输入：stones = [2,7,4,1,8,1]
18+
# 输出：1
19+
# 解释：
20+
# 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
21+
# 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
22+
# 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
23+
# 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
24+
#
25+
#
26+
# 示例 2：
27+
#
28+
#
29+
# 输入：stones = [31,26,33,21,40]
30+
# 输出：5
31+
#
32+
#
33+
#
34+
#
35+
# 提示：
36+
#
37+
#
38+
# 1 <= stones.length <= 30
39+
# 1 <= stones[i] <= 100
40+
#
41+
# Related Topics 数组 动态规划
42+
# 👍 499 👎 0
43+
44+
45+
# leetcode submit region begin(Prohibit modification and deletion)
46+
classSolution:
47+
deflastStoneWeightII(self,stones:List[int])->int:
48+
total=sum(stones)
49+
l=total//2
50+
dp= [0]* (l+1)
51+
forsinstones:
52+
foriinrange(l,s-1,-1):
53+
dp[i]=max(dp[i],dp[i-s]+s)
54+
returntotal-2*dp[-1]
55+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[1143]最长公共子序列.py

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
# 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
2+
#
3+
# 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
4+
#
5+
#
6+
# 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
7+
#
8+
#
9+
# 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
10+
#
11+
#
12+
#
13+
# 示例 1：
14+
#
15+
#
16+
# 输入：text1 = "abcde", text2 = "ace"
17+
# 输出：3
18+
# 解释：最长公共子序列是 "ace" ，它的长度为 3 。
19+
#
20+
#
21+
# 示例 2：
22+
#
23+
#
24+
# 输入：text1 = "abc", text2 = "abc"
25+
# 输出：3
26+
# 解释：最长公共子序列是 "abc" ，它的长度为 3 。
27+
#
28+
#
29+
# 示例 3：
30+
#
31+
#
32+
# 输入：text1 = "abc", text2 = "def"
33+
# 输出：0
34+
# 解释：两个字符串没有公共子序列，返回 0 。
35+
#
36+
#
37+
#
38+
#
39+
# 提示：
40+
#
41+
#
42+
# 1 <= text1.length, text2.length <= 1000
43+
# text1 和 text2 仅由小写英文字符组成。
44+
#
45+
# Related Topics 字符串 动态规划
46+
# 👍 1065 👎 0
47+
48+
49+
# leetcode submit region begin(Prohibit modification and deletion)
50+
classSolution:
51+
deflongestCommonSubsequence(self,text1:str,text2:str)->int:
52+
l1=len(text1)
53+
l2=len(text2)
54+
dp= [[0]* (l2+1)foriinrange(l1+1)]
55+
foriinrange(1,l1+1):
56+
forjinrange(1,l2+1):
57+
iftext1[i-1]==text2[j-1]:
58+
dp[i][j]=dp[i-1][j-1]+1
59+
else:
60+
dp[i][j]=max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
61+
returndp[-1][-1]
62+
# leetcode submit region end(Prohibit modification and deletion)
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
# 这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
2+
#
3+
# 给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。
4+
#
5+
# 答案可能很大，你需要对 109 + 7 取模 。
6+
#
7+
#
8+
#
9+
# 示例 1：
10+
#
11+
#
12+
# 输入：n = 1, k = 6, target = 3
13+
# 输出：1
14+
# 解释：你扔一个有6张脸的骰子。
15+
# 得到3的和只有一种方法。
16+
#
17+
#
18+
# 示例 2：
19+
#
20+
#
21+
# 输入：n = 2, k = 6, target = 7
22+
# 输出：6
23+
# 解释：你扔两个骰子，每个骰子有6个面。
24+
# 得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1。
25+
#
26+
#
27+
# 示例 3：
28+
#
29+
#
30+
# 输入：n = 30, k = 30, target = 500
31+
# 输出：222616187
32+
# 解释：返回的结果必须是对 109 + 7 取模。
33+
#
34+
#
35+
#
36+
# 提示：
37+
#
38+
#
39+
# 1 <= n, k <= 30
40+
# 1 <= target <= 1000
41+
#
42+
# Related Topics 动态规划
43+
# 👍 140 👎 0
44+
45+
46+
# leetcode submit region begin(Prohibit modification and deletion)
47+
classSolution:
48+
defnumRollsToTarget(self,n:int,k:int,target:int)->int:
49+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[115]不同的子序列.py

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
# 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
2+
#
3+
# 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列
4+
# ，而 "AEC" 不是）
5+
#
6+
# 题目数据保证答案符合 32 位带符号整数范围。
7+
#
8+
#
9+
#
10+
# 示例 1：
11+
#
12+
#
13+
# 输入：s = "rabbbit", t = "rabbit"
14+
# 输出：3
15+
# 解释：
16+
# 如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
17+
# rabbbit
18+
# rabbbit
19+
# rabbbit
20+
#
21+
# 示例 2：
22+
#
23+
#
24+
# 输入：s = "babgbag", t = "bag"
25+
# 输出：5
26+
# 解释：
27+
# 如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
28+
# babgbag
29+
# babgbag
30+
# babgbag
31+
# babgbag
32+
# babgbag
33+
#
34+
#
35+
#
36+
#
37+
# 提示：
38+
#
39+
#
40+
# 0 <= s.length, t.length <= 1000
41+
# s 和 t 由英文字母组成
42+
#
43+
# Related Topics 字符串 动态规划
44+
# 👍 823 👎 0
45+
46+
47+
# leetcode submit region begin(Prohibit modification and deletion)
48+
classSolution:
49+
defnumDistinct(self,s:str,t:str)->int:
50+
ls=len(s)
51+
lt=len(t)
52+
dp= [[1]+ [0]*ltforiinrange(ls+1)]# t=''的时候出现1次
53+
# dp[i][j]是前i个s里面有几个前j个t字符= 前i-1个s有多少个j-1个t+ 前i-个s有多少个j个t
54+
foriinrange(1,ls+1):
55+
forjinrange(1,lt+1):
56+
ifs[i-1]==t[j-1]:
57+
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
58+
else:
59+
dp[i][j]=dp[i-1][j]
60+
returndp[-1][-1]
61+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[139]单词拆分.py

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
# 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
2+
#
3+
# 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
4+
#
5+
#
6+
#
7+
# 示例 1：
8+
#
9+
#
10+
# 输入: s = "leetcode", wordDict = ["leet", "code"]
11+
# 输出: true
12+
# 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
13+
#
14+
#
15+
# 示例 2：
16+
#
17+
#
18+
# 输入: s = "applepenapple", wordDict = ["apple", "pen"]
19+
# 输出: true
20+
# 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
21+
#   注意，你可以重复使用字典中的单词。
22+
#
23+
#
24+
# 示例 3：
25+
#
26+
#
27+
# 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
28+
# 输出: false
29+
#
30+
#
31+
#
32+
#
33+
# 提示：
34+
#
35+
#
36+
# 1 <= s.length <= 300
37+
# 1 <= wordDict.length <= 1000
38+
# 1 <= wordDict[i].length <= 20
39+
# s 和 wordDict[i] 仅有小写英文字母组成
40+
# wordDict 中的所有字符串 互不相同
41+
#
42+
# Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划
43+
# 👍 1725 👎 0
44+
45+
46+
# leetcode submit region begin(Prohibit modification and deletion)
47+
classSolution:
48+
defwordBreak(self,s:str,wordDict:List[str])->bool:
49+
ls=len(s)
50+
dp= [False]* (ls+1)
51+
dp[0]=True
52+
wordDict=set(wordDict)
53+
foriinrange(1,ls+1):
54+
forssinwordDict:
55+
lw=len(ss)
56+
ifi>=lw:
57+
dp[i]=dp[i]or (dp[i-lw]ands[(i-lw):i]==ss)
58+
returndp[-1]
59+
# leetcode submit region end(Prohibit modification and deletion)

0 commit comments

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