赞
踩
class Solution:
def constructRectangle(self, area: int) -> List[int]:
'''
w = 1
for i in range(1, int(area**0.5)+1):
if area % i == 0: w = i
'''
w = int(area ** 0.5)
while area % w: w -= 1
return [area//w, w]
Leetcode
知识点: while // % == != 条件可不断的变化,for 范围不变。
class Solution:
def checkPerfectNumber(self, num: int) -> bool:
if num == 1: return False # 1 特别处理,不是完美数。
x, i = 1, 2
while i*i < num:
if num % i == 0:
x += i # 累计正因子和
if i != num // i: # 相同避免加两次
x += num // i
i += 1
return x == num
Leetcode
知识点: 集合 set set.add,去重功能,无序,分类。// 整除、/ 除法。
class Solution:
def distributeCandies(self, candyType: List[int]) -> int:
n = len(candyType)//2
s = set()
for c in candyType:
s.add(c)
return len(s) if len(s) <= n else n
#return min(len(candyType)//2, len(set(candyType)))
Leetcode
知识点: 条件语句 分支的实现
class Solution: def lemonadeChange(self, bills: List[int]) -> bool: five, ten = 0, 0 for i in bills: if i == 5: five += 1 if i == 10: ten += 1 five -= 1 if i == 20: if ten > 0: # 先找 10 元的 ten -= 1 five -= 1 else: five -= 3 if five < 0: return False return True
Leetcode
知识点: sum set 总体差的一半通过交换重新分配
class Solution:
def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
a, b = sum(aliceSizes), sum(bobSizes)
c, d = aliceSizes, set(bobSizes)
for i in c:
j = (b - a)//2 + i
if j in d:
return [i, j]
class Solution:
def validMountainArray(self, arr: List[int]) -> bool:
n = len(arr)
if n < 3: return False
i, j = 0, n-1
while i < n-2 and arr[i+1] > arr[i]: # 从左向右,至多到倒数第二个。
i += 1
while j > 1 and arr[j] < arr[j-1]: # 从右向左,至少到第二个
j -= 1
return i == j
class Solution: def duplicateZeros(self, arr: List[int]) -> None: """ Do not return anything, modify arr in-place instead. """ ''' # 方法一:insert pop i = 0 while i < len(arr): if not arr[i]: arr.insert(i, 0) i += 1 arr.pop() i += 1 ''' ''' # 方法二:添加标记 n = len(arr) flag = True for i in range(n): if not arr[i] and flag: flag = False j = n - 1 while j > i: arr[j] = arr[j-1] j -= 1 else:flag = True ''' ''' # 方法三: n = len(arr) i = j = 0 while j <= n-1: if arr[j]:i += 1 j += 1 j -= 1 i -= 1 while i > 0: if arr[i]: arr[j] = arr[i] else: arr[j] = 0 j -= 1 arr[j] = 0 i -= 1 j -= 1 ''' n = len(arr) i = j = 0 while j < n: if arr[i] == 0: j += 1 i += 1 j += 1 i -= 1 # i 回到最后一次合法的位置 j -= 1 # j 同理,但 j 仍可能等于 n(例如输入 [0]) while i >= 0: if j < n: arr[j] = arr[i] if arr[i] == 0: j -= 1 arr[j] = arr[i] i -= 1 j -= 1
class Solution:
def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
if destination < start: # 交换出发点和目的地距离相等
start, destination = destination, start
d = sum(distance[start:destination]) # 出发点到目的地距离
return min(d, sum(distance) - d)
class Solution: def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]: res, n, tmp = [], len(arr), inf for i in range(n-1): for j in range(i+1,n): a, b = arr[i], arr[j] if a > b: a, b = b, a x = b - a if x == tmp: res.append([a, b]) elif x < tmp: tmp = x res = [[a, b]] res.sort() return res
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
arr.sort()
min_, res, n = inf, [], len(arr)
for i in range(1, n):
a, b = arr[i-1], arr[i]
if (x := b - a) < min_: # 因为有序, x >= 0
res = [[a, b]]
min_ = x
elif x == min_:
res.append([a, b])
return res
class Solution:
def subtractProductAndSum(self, n: int) -> int:
s, p = 0, 1
while n:
n, rem = divmod(n, 10)
s += rem
p *= rem
return p - s
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
n = len(arr)
m = max(arr)
for i in range(n):
if i < n-1 and arr[i] == m:
m = max(arr[i+1:])
arr[i] = m
arr[-1] = -1
return arr
class Solution: def checkIfExist(self, arr: List[int]) -> bool: ''' n = len(arr) for i in range(n-1): for j in range(i+1,n): if arr[i] == 2 * arr[j] or 2 * arr[i] == arr[j]: return True return False ''' zero = False for i, e in enumerate(arr): if not e: if zero:return True zero = True if e%2 == 0 and e != 0: if e//2 in arr: return True return False
Leetcode
知识点: 列表 list,append。
教程:Python 1-14 列表
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
start, end = [], []
for s, e in paths:
start.append(s)
end.append(e)
for x in end:
if x not in start:
return x
**知识点:**推导式,生成器,next。
教程:Python 推导式
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
citiesA = {path[0] for path in paths}
return next(path[1] for path in paths if path[1] not in citiesA)
class Solution:
def kLengthApart(self, nums: List[int], k: int) -> bool:
tmp = k
for i in range(len(nums)):
if nums[i] == 1:
if k > tmp:return False
tmp = 0
else:
tmp += 1
return True
class Solution: def countStudents(self, students: List[int], sandwiches: List[int]) -> int: # n = 0 # while n < len(students): # if students[0] == sandwiches[0]: # students.pop(0) # sandwiches.pop(0) # n = 0 # else: # students = students[1:] + [students[0]] # n += 1 # return n cnt = [0, 0] # 统计喜欢圆形和方形三明治学生数量 for i in students: cnt[i] += 1 for i in sandwiches: # 依次取出栈顶三明治,直到没有学生喜欢 i。 if cnt[i] == 0: break cnt[i] -= 1 return sum(cnt)
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
res = inf
for i in range(len(nums) - k + 1):
res = min(res, nums[i + k - 1] - nums[i])
return res
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
res = 0
n = len(nums)
for i in range(n-3):
for j in range(i+1,n-2):
for k in range(j+1,n-1):
for l in range(k+1,n):
if nums[i]+nums[j]+nums[k] == nums[l]:
res += 1
return res
class Solution: def countKDifference(self, nums: List[int], k: int) -> int: ''' res, n = 0, len(nums) for i in range(n): for j in range(i+1, n): if abs(nums[i]-nums[j]) == k: res += 1 return res ''' res, d = 0, defaultdict(int) for i in nums: d[k+i] += 1 for i in nums: res += d[i] return res
class Solution: def finalValueAfterOperations(self, operations: List[str]) -> int: x = 0 for i in operations: # if i in ["++X", "X++"]: # if '+' in i: # x += 1 # else: # x -= 1 x += 1 if '+' in i else -1 return x # return sum(1 if "+" in op else -1 for op in operations)
class Solution:
def maximumDifference(self, nums: List[int]) -> int:
res, n = -1, len(nums)
#for i in range(n-1):
#for j in range(i+1, n):
#if nums[i] < nums[j]:
#res = max(res, nums[j]-nums[i])
for i in range(1, n):
res = max(res, nums[i] - min(nums[:i]))
return res if res else -1
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。