Skip to content

Commit 1357b0d

Browse files
linwtlinwt
authored
Add files via upload
1 parent d0d434d commit 1357b0d

16 files changed

+255
-0
lines changed

‎leetcode/011.盛最多水的容器.py

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
# 双指针移动
2+
class Solution(object):
3+
def maxArea(self, height):
4+
l, r, m = 0, len(height)-1, 0
5+
while l < r:
6+
# 记录当前最大面积
7+
hl, hr = height[l], height[r]
8+
cur = min(hl, hr) * (r-l)
9+
m = max(m, cur)
10+
# 高度较小一端向内移动，获得可能更大的面积
11+
if hl < hr:
12+
l += 1
13+
else:
14+
r -= 1
15+
return m

‎leetcode/015.三数之和.py

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
# 数组排序后，先固定一个数，再用双指针从头尾向内移动确定另外两个数
2+
class Solution(object):
3+
def threeSum(self, nums):
4+
n = len(nums)
5+
nums.sort()
6+
res = set()
7+
for i in range(n-2):
8+
x, y = i+1, n-1
9+
while x < y:
10+
if nums[i] + nums[x] + nums[y] == 0:
11+
# 去重
12+
res.add((nums[i], nums[x], nums[y]))
13+
x += 1
14+
y -= 1
15+
if nums[i] + nums[x] + nums[y] > 0:
16+
y -= 1
17+
if nums[i] + nums[x] + nums[y] < 0:
18+
x += 1
19+
# 还原为列表
20+
return [list(l) for l in res]

‎leetcode/018.四数之和.py

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
# 数组排序后，先固定两个数，再用双指针从头尾向内移动确定另外两个数
2+
class Solution(object):
3+
def fourSum(self, nums, target):
4+
n = len(nums)
5+
nums.sort()
6+
res = set()
7+
for i in range(n-3):
8+
for j in range(i+1, n-2):
9+
l, r = j+1, n-1
10+
while l < r:
11+
temp = nums[i] + nums[j] + nums[l] + nums[r]
12+
if temp == target:
13+
# 去重
14+
res.add((nums[i], nums[j], nums[l], nums[r]))
15+
l += 1
16+
r -= 1
17+
# 结果比目标值大，右指针左移减小数值
18+
if temp > target:
19+
r -= 1
20+
# 结果比目标值小，左指针右移增大数值
21+
if temp < target:
22+
l += 1
23+
return [list(t) for t in res]

‎leetcode/043.字符串相乘.py

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
class Solution(object):
2+
def multiply(self, num1, num2):
3+
return str(int(num1)*int(num2))

‎leetcode/050.Pow(x, n).py

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
# 折半计算，每次将n缩小一半
2+
class Solution(object):
3+
def myPow(self, x, n):
4+
if n < 0:
5+
n, x = abs(n), 1/x
6+
res = 1
7+
while n:
8+
# n为奇数则需要乘一个x
9+
if n % 2:
10+
res *= x
11+
# x翻倍
12+
x *= x
13+
# n缩小一半
14+
n //= 2
15+
return res

‎leetcode/151.翻转字符串里的单词.py

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
# 按空格切分单词再反转
2+
class Solution(object):
3+
def reverseWords(self, s):
4+
return ' '.join(s.split()[::-1])

‎leetcode/215.数组中的第K个最大元素.py

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
# 遍历数组，用一个长度为k的列表存放最大的k个数，返回列表中的最小值即为第k大的数
2+
class Solution(object):
3+
def findKthLargest(self, nums, k):
4+
res = []
5+
for num in nums:
6+
if len(res) < k:
7+
res.append(num)
8+
elif num > min(res):
9+
res[res.index(min(res))] = num
10+
return min(res)

‎leetcode/238.除自身以外数组的乘积.py

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
# 方法一：分类讨论
2+
class Solution(object):
3+
def productExceptSelf(self, nums):
4+
z = nums.count(0)
5+
# 大于1个0的情况，累积结果全部为0
6+
if z > 1:
7+
return [0]*len(nums)
8+
# 1个0的情况，除了0位置，其他都为0
9+
if z == 1:
10+
res = [0]*len(nums)
11+
index = nums.index(0)
12+
nums.pop(index)
13+
r = 1
14+
for num in nums:
15+
r *= num
16+
res[index] = r
17+
return res
18+
# 没有0的情况，先算累积，再用总积去除逐个位置的数
19+
res = 1
20+
for num in nums:
21+
res *= num
22+
return [res/i for i in nums]
23+
24+
25+
# 方法二：当前数 = 左边的乘积 x 右边的乘积
26+
class Solution(object):
27+
def productExceptSelf(self, nums):
28+
n = len(nums)
29+
l, r, res = 1, 1, [1]*n
30+
for i in range(n):
31+
res[i] *= l
32+
l *= nums[i]
33+
res[n-1-i] *= r
34+
r *= nums[n-1-i]
35+
return res

‎leetcode/376.摆动序列.py

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
# 贪心算法
2+
class Solution(object):
3+
def wiggleMaxLength(self, nums):
4+
# 边界条件
5+
n = len(nums)
6+
if n < 2:
7+
return n
8+
9+
# 以正/负结尾时的最长摆动序列长度
10+
up = down = 1
11+
# 正负性相同则长度不变，相反则加1
12+
for i in range(1, n):
13+
if nums[i-1] < nums[i]:
14+
up = down + 1
15+
if nums[i-1] > nums[i]:
16+
down = up + 1
17+
return max(up, down)

‎leetcode/402.移掉K位数字.py

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
# 利用栈弹出元素，使前面的数字尽可能小
2+
class Solution(object):
3+
def removeKdigits(self, num, k):
4+
res = []
5+
for n in num:
6+
while res:
7+
if not k or n >= res[-1]:
8+
res.append(n)
9+
break
10+
else:
11+
res.pop()
12+
k -= 1
13+
else:
14+
if n != '0':
15+
res.append(n)
16+
res = res[:len(res)-k]
17+
return ''.join(res) if res else '0'

‎leetcode/825.适龄的朋友.py

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
class Solution(object):
2+
def numFriendRequests(self, ages):
3+
count = [0]*121
4+
for age in ages:
5+
count[age] += 1
6+
res = 0
7+
for ageB in range(1, 121):
8+
for ageA in range(ageB, 121):
9+
if (ageB <= 0.5*ageA+7) or (ageB > ageA) or (ageB > 100 and ageA < 100):
10+
continue
11+
res += count[ageA] * count[ageB]
12+
if ageA == ageB:
13+
res -= count[ageA]
14+
return res

‎leetcode/870.优势洗牌.py

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
class Solution(object):
2+
def advantageCount(self, A, B):
3+
n = len(B)
4+
A.sort()
5+
# 记录元素的值和索引
6+
B = [(B[i], i) for i in range(n)]
7+
B.sort()
8+
# 使用左右指针指向B的左右两端
9+
l, r, k, res = 0, n-1, 0, [0]*n
10+
for a in A:
11+
# A的元素大于B的元素，则将A的元素放到B的元素对应的索引位置上
12+
if a > B[l][0]:
13+
res[B[l][1]] = a
14+
l += 1
15+
# 否则放到B最后一个元素对应的索引位置上
16+
else:
17+
res[B[r][1]] = a
18+
r -= 1
19+
return res

‎leetcode/910.最小差值 II.py

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
# 数组排序后分成两部分，前一部分全部加K，后一部分全部减K
2+
# 取出两部分的第一个元素的更小者，最后一个元素的更大者，得到变化后的数组的最大最小值
3+
class Solution(object):
4+
def smallestRangeII(self, A, K):
5+
n = len(A)
6+
if n < 2:
7+
return 0
8+
A.sort()
9+
res = A[n-1] - A[0]
10+
for i in range(1, n):
11+
minu = min(A[0] + K, A[i] - K)
12+
maxu = max(A[i-1] + K, A[n-1] - K)
13+
res = min(res, maxu - minu)
14+
return res

‎leetcode/921.使括号有效的最少添加.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
# 最坏情况下需要添加次数等于字符串长度，利用栈存放左括号，当遇到右括号时栈中有左括号配对，则弹出一个左括号并且减少两次添加
2+
class Solution(object):
3+
def minAddToMakeValid(self, S):
4+
res = len(S)
5+
stack = []
6+
for s in S:
7+
if s == '(':
8+
stack.append(s)
9+
if s == ')' and stack:
10+
stack.pop()
11+
res -= 2
12+
return res

‎leetcode/984.不含 AAA 或 BBB 的字符串.py

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
class Solution(object):
2+
def strWithout3a3b(self, A, B):
3+
# 使A大于B
4+
a, b = 'a', 'b'
5+
if A < B:
6+
a, b = b, a
7+
A, B = B, A
8+
9+
res = ''
10+
# A的数量多于B时构造 'aab'，否则构造 'ab'
11+
while A > 0 or B > 0:
12+
if A > 0:
13+
res += a
14+
A -= 1
15+
if A > B:
16+
res += a
17+
A -= 1
18+
if B > 0:
19+
res += b
20+
B -= 1
21+
return res

‎leetcode/991.坏了的计算器.py

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
# 逆向求解，对Y进行除、加逐步逼近X
2+
class Solution(object):
3+
def brokenCalc(self, X, Y):
4+
if X > Y:
5+
return X - Y
6+
res = 0
7+
while X < Y:
8+
# Y为奇数时除后非整所以只能加
9+
if Y % 2:
10+
Y += 1
11+
# Y为偶数时就除，逼近X
12+
else:
13+
Y /= 2
14+
res += 1
15+
# Y比X小后逐步加直到等于X
16+
return X - Y + res

0 commit comments

Comments
 (0)