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

Commit64845f4

Browse files
committed
add new script
1 parent0f90258 commit64845f4

5 files changed

+324
-0
lines changed
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
# 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
2+
#
3+
# 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
4+
#
5+
#
6+
#
7+
# 示例 1:
8+
#
9+
#
10+
# 输入: [3,2,1,5,6,4], k = 2
11+
# 输出: 5
12+
#
13+
#
14+
# 示例 2:
15+
#
16+
#
17+
# 输入: [3,2,3,1,2,4,5,5,6], k = 4
18+
# 输出: 4
19+
#
20+
#
21+
#
22+
# 提示：
23+
#
24+
#
25+
# 1 <= k <= nums.length <= 105
26+
# -104 <= nums[i] <= 104
27+
#
28+
# Related Topics 数组 分治 快速选择 排序 堆（优先队列）
29+
# 👍 1787 👎 0
30+
31+
32+
# leetcode submit region begin(Prohibit modification and deletion)
33+
classSolution:
34+
deffindKthLargest(self,nums:List[int],k:int)->int:
35+
defpartition(nums,left,right):
36+
key=left
37+
whileleft<right:
38+
whileleft<rightandnums[key]<=nums[right]:
39+
right-=1
40+
whileleft<rightandnums[left]<=nums[key]:
41+
left+=1
42+
nums[left],nums[right]=nums[right],nums[left]
43+
nums[left],nums[key]=nums[key],nums[left]
44+
returnleft
45+
46+
defsort(nums,left,right):
47+
ifleft>=right:
48+
return
49+
mid=partition(nums,left,right)
50+
ifmid==k:
51+
return
52+
elifmid<k:
53+
sort(nums,mid+1,right)
54+
else:
55+
sort(nums,left,mid-1)
56+
57+
l=len(nums)
58+
k=l-k
59+
sort(nums,0,len(nums)-1)
60+
returnnums[k]
61+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[28]实现 strStr().py

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
# 实现 strStr() 函数。
2+
#
3+
# 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如
4+
# 果不存在，则返回 -1 。
5+
#
6+
# 说明：
7+
#
8+
# 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
9+
#
10+
# 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
11+
#
12+
#
13+
#
14+
# 示例 1：
15+
#
16+
#
17+
# 输入：haystack = "hello", needle = "ll"
18+
# 输出：2
19+
#
20+
#
21+
# 示例 2：
22+
#
23+
#
24+
# 输入：haystack = "aaaaa", needle = "bba"
25+
# 输出：-1
26+
#
27+
#
28+
#
29+
#
30+
# 提示：
31+
#
32+
#
33+
# 1 <= haystack.length, needle.length <= 104
34+
# haystack 和 needle 仅由小写英文字符组成
35+
#
36+
# Related Topics 双指针 字符串 字符串匹配
37+
# 👍 1520 👎 0
38+
39+
40+
# leetcode submit region begin(Prohibit modification and deletion)
41+
classSolution:
42+
defstrStr(self,haystack:str,needle:str)->int:
43+
defgetnext(needle):
44+
l=len(needle)
45+
ptr1=0
46+
ptr2=-1
47+
next= [-1]*l#相同前缀长度
48+
whileptr1<(l-1):
49+
ifptr2==-1orneedle[ptr1]==needle[ptr2]:
50+
# 每一步更新的是下一个字符的前缀长度
51+
ptr1+=1#下一个字符
52+
ptr2+=1# 从哪一个位置开始匹配
53+
next[ptr1]=ptr2
54+
else:
55+
# 上一个字符匹配到的位置重新开始匹配
56+
ptr2=next[ptr2]
57+
returnnext
58+
next=getnext(needle)
59+
l1=len(haystack)
60+
l2=len(needle)
61+
ptr1=0
62+
ptr2=0
63+
whileptr1<l1andptr2<l2:
64+
ifptr2==-1orhaystack[ptr1]==needle[ptr2]:
65+
ptr1+=1
66+
ptr2+=1
67+
else:
68+
ptr2=next[ptr2]
69+
ifptr2==l2:
70+
returnptr1-ptr2
71+
else:
72+
return-1
73+
74+
# leetcode submit region end(Prohibit modification and deletion)
75+
76+
Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
# 给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格 。
2+
#
3+
# 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
4+
#
5+
#
6+
# 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
7+
#
8+
#
9+
# 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
10+
#
11+
#
12+
#
13+
# 示例 1:
14+
#
15+
#
16+
# 输入: prices = [1,2,3,0,2]
17+
# 输出: 3
18+
# 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
19+
#
20+
# 示例 2:
21+
22+
#
23+
#
24+
# 输入: prices = [1]
25+
# 输出: 0
26+
#
27+
#
28+
#
29+
#
30+
# 提示：
31+
#
32+
#
33+
# 1 <= prices.length <= 5000
34+
# 0 <= prices[i] <= 1000
35+
#
36+
# Related Topics 数组 动态规划
37+
# 👍 1272 👎 0
38+
39+
40+
# leetcode submit region begin(Prohibit modification and deletion)
41+
classSolution:
42+
defmaxProfit(self,prices:List[int])->int:
43+
#状态买入，T卖出，T-1卖出，T-2卖出
44+
l=len(prices)
45+
b= [0]*l
46+
s1= [0]*l# 当天卖出
47+
s2= [0]*l# T-1卖出
48+
s3= [0]*l# T-2之前卖出
49+
b[0]=-prices[0]
50+
foriinrange(1,l):
51+
b[i]=max(b[i-1],s3[i-1]-prices[i],s2[i-1]-prices[i])
52+
s1[i]=b[i-1]+prices[i]
53+
s2[i]=s1[i-1]
54+
s3[i]=max(s3[i-1],s2[i-1])
55+
returnmax(s1[-1],s2[-1],s3[-1])
56+
57+
58+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[347]前 K 个高频元素.py

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
# 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
2+
#
3+
#
4+
#
5+
# 示例 1:
6+
#
7+
#
8+
# 输入: nums = [1,1,1,2,2,3], k = 2
9+
# 输出: [1,2]
10+
#
11+
#
12+
# 示例 2:
13+
#
14+
#
15+
# 输入: nums = [1], k = 1
16+
# 输出: [1]
17+
#
18+
#
19+
#
20+
# 提示：
21+
#
22+
#
23+
# 1 <= nums.length <= 105
24+
# k 的取值范围是 [1, 数组中不相同的元素的个数]
25+
# 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
26+
#
27+
#
28+
#
29+
#
30+
# 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
31+
# Related Topics 数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列）
32+
# 👍 1275 👎 0
33+
34+
35+
# leetcode submit region begin(Prohibit modification and deletion)
36+
classSolution:
37+
deftopKFrequent(self,nums:List[int],k:int)->List[int]:
38+
importcollections
39+
counter=collections.Counter(nums)
40+
counter=list(counter.items())
41+
42+
defpartition(nums,left,right):
43+
key=left
44+
whileleft<right:
45+
whileleft<rightandnums[key][1]<=nums[right][1]:
46+
right-=1
47+
whileleft<rightandnums[key][1]>=nums[left][1]:
48+
left+=1
49+
nums[left],nums[right]=nums[right],nums[left]
50+
nums[left],nums[key]=nums[key],nums[left]
51+
returnleft
52+
53+
defsort(nums,k,left,right):
54+
ifleft>=right:
55+
return
56+
mid=partition(nums,left,right)
57+
ifmid==k:
58+
return
59+
elifmid>k:
60+
sort(nums,k,left,mid-1)
61+
else:
62+
sort(nums,k,mid+1,right)
63+
64+
l=len(counter)
65+
sort(counter,l-k,0,l-1)
66+
return [i[0]foriincounter[-k:]]
67+
68+
69+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[605]种花问题.py

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
# 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
2+
#
3+
# 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则
4+
# 的情况下种入 n 朵花？能则返回 true ，不能则返回 false。
5+
#
6+
#
7+
#
8+
# 示例 1：
9+
#
10+
#
11+
# 输入：flowerbed = [1,0,0,0,1], n = 1
12+
# 输出：true
13+
#
14+
#
15+
# 示例 2：
16+
#
17+
#
18+
# 输入：flowerbed = [1,0,0,0,1], n = 2
19+
# 输出：false
20+
#
21+
#
22+
#
23+
#
24+
# 提示：
25+
#
26+
#
27+
# 1 <= flowerbed.length <= 2 * 104
28+
# flowerbed[i] 为 0 或 1
29+
# flowerbed 中不存在相邻的两朵花
30+
# 0 <= n <= flowerbed.length
31+
#
32+
# Related Topics 贪心 数组
33+
# 👍 467 👎 0
34+
35+
36+
# leetcode submit region begin(Prohibit modification and deletion)
37+
classSolution:
38+
defcanPlaceFlowers(self,flowerbed:List[int],n:int)->bool:
39+
prepos=-1
40+
counter=0
41+
l=len(flowerbed)
42+
foriinrange(l):
43+
ifflowerbed[i]==1:
44+
ifprepos<0:
45+
counter+= (i-prepos-1)//2
46+
else:
47+
counter+= (i-prepos-2)//2
48+
prepos=i
49+
ifprepos<0:
50+
counter+=(l-prepos)//2
51+
else:
52+
counter+=(l-prepos-1)//2
53+
print(counter)
54+
ifcounter>=n:
55+
returnTrue
56+
else:
57+
returnFalse
58+
59+
60+
# leetcode submit region end(Prohibit modification and deletion)

0 commit comments

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