Skip to content

Commit bf49772

Browse files
author
liningrui
committed
add plugin solution
1 parent fc6f788 commit bf49772

File tree

54 files changed

+3234
-0
lines changed

Some content is hidden

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

54 files changed

+3234
-0
lines changed

‎script/[11]盛最多水的容器.py

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
# 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
2+
#
3+
# 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
4+
#
5+
# 返回容器可以储存的最大水量。
6+
#
7+
# 说明：你不能倾斜容器。
8+
#
9+
#
10+
#
11+
# 示例 1：
12+
#
13+
#
14+
#
15+
#
16+
# 输入：[1,8,6,2,5,4,8,3,7]
17+
# 输出：49
18+
# 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
19+
#
20+
# 示例 2：
21+
#
22+
#
23+
# 输入：height = [1,1]
24+
# 输出：1
25+
#
26+
#
27+
#
28+
#
29+
# 提示：
30+
#
31+
#
32+
# n == height.length
33+
# 2 <= n <= 10⁵
34+
# 0 <= height[i] <= 10⁴
35+
#
36+
# Related Topics 贪心 数组 双指针 👍 3641 👎 0
37+
38+
39+
# leetcode submit region begin(Prohibit modification and deletion)
40+
class Solution:
41+
def maxArea(self, height: List[int]) -> int:
42+
area =0
43+
left =0
44+
right = len(height)-1
45+
while left<right:
46+
area = max(area, (right-left) * min(height[left], height[right]))
47+
if height[left]<height[right]:
48+
left +=1
49+
else:
50+
right-=1
51+
return area
52+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[125]验证回文串.py

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
# 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
2+
#
3+
# 说明：本题中，我们将空字符串定义为有效的回文串。
4+
#
5+
#
6+
#
7+
# 示例 1:
8+
#
9+
#
10+
# 输入: "A man, a plan, a canal: Panama"
11+
# 输出: true
12+
# 解释："amanaplanacanalpanama" 是回文串
13+
#
14+
#
15+
# 示例 2:
16+
#
17+
#
18+
# 输入: "race a car"
19+
# 输出: false
20+
# 解释："raceacar" 不是回文串
21+
#
22+
#
23+
#
24+
#
25+
# 提示：
26+
#
27+
#
28+
# 1 <= s.length <= 2 * 10⁵
29+
# 字符串 s 由 ASCII 字符组成
30+
#
31+
# Related Topics 双指针 字符串 👍 550 👎 0
32+
33+
34+
# leetcode submit region begin(Prohibit modification and deletion)
35+
class Solution:
36+
def isPalindrome(self, s: str) -> bool:
37+
left= 0
38+
right = len(s)-1
39+
while left<right:
40+
if not s[left].isalnum():
41+
left+=1
42+
continue
43+
if not s[right].isalnum():
44+
right-=1
45+
continue
46+
if s[left].lower()!=s[right].lower():
47+
return False
48+
else:
49+
left+=1
50+
right-=1
51+
return True
52+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[131]分割回文串.py

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
# 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
2+
#
3+
# 回文串 是正着读和反着读都一样的字符串。
4+
#
5+
#
6+
#
7+
# 示例 1：
8+
#
9+
#
10+
# 输入：s = "aab"
11+
# 输出：[["a","a","b"],["aa","b"]]
12+
#
13+
#
14+
# 示例 2：
15+
#
16+
#
17+
# 输入：s = "a"
18+
# 输出：[["a"]]
19+
#
20+
#
21+
#
22+
#
23+
# 提示：
24+
#
25+
#
26+
# 1 <= s.length <= 16
27+
# s 仅由小写英文字母组成
28+
#
29+
# Related Topics 字符串 动态规划 回溯 👍 1194 👎 0
30+
31+
32+
# leetcode submit region begin(Prohibit modification and deletion)
33+
class Solution:
34+
def partition(self, s: str) -> List[List[str]]:
35+
result = []
36+
37+
def is_valid(ss):
38+
l = len(ss)
39+
if l==1:
40+
return True
41+
for i in range(int(l)//2):
42+
if ss[i]!= ss[l-i-1]:
43+
return False
44+
return True
45+
46+
def backtrace(s, tmp):
47+
nonlocal result
48+
if not s:
49+
result.append(tmp)
50+
return
51+
52+
for i in range(1, len(s)+1):
53+
if is_valid(s[:i]):
54+
backtrace(s[i:], tmp+[s[:i]])
55+
backtrace(s, [])
56+
return result
57+
58+
59+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[153]寻找旋转排序数组中的最小值.py

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
# 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变
2+
# 化后可能得到：
3+
#
4+
# 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
5+
# 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
6+
#
7+
#
8+
# 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2],
9+
# ..., a[n-2]] 。
10+
#
11+
# 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
12+
#
13+
# 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
14+
#
15+
#
16+
#
17+
# 示例 1：
18+
#
19+
#
20+
# 输入：nums = [3,4,5,1,2]
21+
# 输出：1
22+
# 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
23+
#
24+
#
25+
# 示例 2：
26+
#
27+
#
28+
# 输入：nums = [4,5,6,7,0,1,2]
29+
# 输出：0
30+
# 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
31+
#
32+
#
33+
# 示例 3：
34+
#
35+
#
36+
# 输入：nums = [11,13,15,17]
37+
# 输出：11
38+
# 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
39+
#
40+
#
41+
#
42+
#
43+
# 提示：
44+
#
45+
#
46+
# n == nums.length
47+
# 1 <= n <= 5000
48+
# -5000 <= nums[i] <= 5000
49+
# nums 中的所有整数 互不相同
50+
# nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
51+
#
52+
# Related Topics 数组 二分查找 👍 784 👎 0
53+
54+
55+
# leetcode submit region begin(Prohibit modification and deletion)
56+
class Solution:
57+
def findMin(self, nums: List[int]) -> int:
58+
left =0
59+
right = len(nums)-1
60+
while left<right:
61+
mid = (left+right)//2
62+
if nums[mid]< nums[right]:
63+
right = mid
64+
else:
65+
left = mid+1
66+
return nums[left]
67+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[15]三数之和.py

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
# 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重
2+
# 复的三元组。
3+
#
4+
# 注意：答案中不可以包含重复的三元组。
5+
#
6+
#
7+
#
8+
# 示例 1：
9+
#
10+
#
11+
# 输入：nums = [-1,0,1,2,-1,-4]
12+
# 输出：[[-1,-1,2],[-1,0,1]]
13+
#
14+
#
15+
# 示例 2：
16+
#
17+
#
18+
# 输入：nums = []
19+
# 输出：[]
20+
#
21+
#
22+
# 示例 3：
23+
#
24+
#
25+
# 输入：nums = [0]
26+
# 输出：[]
27+
#
28+
#
29+
#
30+
#
31+
# 提示：
32+
#
33+
#
34+
# 0 <= nums.length <= 3000
35+
# -10⁵ <= nums[i] <= 10⁵
36+
#
37+
# Related Topics 数组 双指针 排序 👍 4982 👎 0
38+
39+
40+
# leetcode submit region begin(Prohibit modification and deletion)
41+
class Solution:
42+
def threeSum(self, nums: List[int]) -> List[List[int]]:
43+
if len(nums)<3:
44+
return []
45+
nums = sorted(nums)
46+
result = []
47+
for i in range(len(nums)-2):
48+
a = nums[i]
49+
left = i+1
50+
right = len(nums)-1
51+
if a>0:
52+
continue
53+
if i>0 and nums[i]==nums[i-1]:
54+
continue
55+
while left<right:
56+
b = nums[left]
57+
c = nums[right]
58+
if left != i+1 and nums[left]==nums[left-1]:
59+
left +=1
60+
continue
61+
if right != len(nums)-1 and nums[right]==nums[right+1]:
62+
right-=1
63+
continue
64+
if a+b+c==0:
65+
result.append([a,b,c])
66+
right-=1
67+
left +=1
68+
elif a+b+c>0:
69+
right-=1
70+
else:
71+
left+=1
72+
return result
73+
74+
75+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[162]寻找峰值.py

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
# 峰值元素是指其值严格大于左右相邻值的元素。
2+
#
3+
# 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
4+
#
5+
# 你可以假设 nums[-1] = nums[n] = -∞ 。
6+
#
7+
# 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
8+
#
9+
#
10+
#
11+
# 示例 1：
12+
#
13+
#
14+
# 输入：nums = [1,2,3,1]
15+
# 输出：2
16+
# 解释：3 是峰值元素，你的函数应该返回其索引 2。
17+
#
18+
# 示例 2：
19+
#
20+
#
21+
# 输入：nums = [1,2,1,3,5,6,4]
22+
# 输出：1 或 5
23+
# 解释：你的函数可以返回索引 1，其峰值元素为 2；
24+
#   或者返回索引 5， 其峰值元素为 6。
25+
#
26+
#
27+
#
28+
#
29+
# 提示：
30+
#
31+
#
32+
# 1 <= nums.length <= 1000
33+
# -2³¹ <= nums[i] <= 2³¹ - 1
34+
# 对于所有有效的 i 都有 nums[i] != nums[i + 1]
35+
#
36+
# Related Topics 数组 二分查找 👍 848 👎 0
37+
38+
39+
# leetcode submit region begin(Prohibit modification and deletion)
40+
class Solution:
41+
def findPeakElement(self, nums: List[int]) -> int:
42+
left =0
43+
right = len(nums)-1
44+
def get_val(index):
45+
if index<0 or index == len(nums):
46+
return -float('inf')
47+
else:
48+
return nums[index]
49+
50+
while left <=right:
51+
mid = (left+right)//2
52+
if nums[mid]> get_val(mid-1) and nums[mid]>get_val(mid+1):
53+
return mid
54+
elif nums[mid]<get_val(mid+1):
55+
left = mid+1
56+
else:
57+
right = mid-1
58+
#不会在这里退出因为单调递增递减到边界也会在上面退出
59+
60+
# leetcode submit region end(Prohibit modification and deletion)

0 commit comments

Comments
 (0)