快速排序
from typing import List
def quick_sort(arr: List, l: int, r: int):
if l >= r:
return
i = l - 1
j = r + 1
x = arr[(l + r) // 2]
while i < j:
while True:
i += 1
if arr[i] >= x:
break
while True:
j -= 1
if arr[j] <= x:
break
if i < j:
arr[i], arr[j] = arr[j], arr[i]
quick_sort(arr, l, j)
quick_sort(arr, j + 1, r)
n = int(input())
nums = list(map(int, input().split()))
quick_sort(nums, 0, n - 1)
print(" ".join(map(str, nums)))
def quick_choose(arr, l, r, k) -> int:
if l >= r:
return arr[l]
i = l - 1
j = r + 1
x = arr[(l + r) // 2]
while i < j:
while True:
i += 1
if arr[i] >= x:
break
while True:
j -= 1
if arr[j] <= x:
break
if i < j:
arr[i], arr[j] = arr[j], arr[i]
if k <= j:
return quick_choose(arr, l, j, k)
else:
return quick_choose(arr, j + 1, r, k)
n, k = map(int, input().split())
nums = list(map(int, input().split()))
# 第k个数下标为k-1
res = quick_choose(nums, 0, n - 1, k - 1)
print(res)
归并排序
def merge_sort(arr, l, r):
if l >= r:
return
mid = (l + r) // 2
merge_sort(arr, l, mid)
merge_sort(arr, mid + 1, r)
i = l
j = mid + 1
tmp = []
while i <= mid and j <= r:
if arr[i] <= arr[j]:
tmp.append(arr[i])
i += 1
else:
tmp.append(arr[j])
j += 1
tmp.extend(arr[i:mid + 1])
tmp.extend(arr[j: r + 1])
arr[l: r + 1] = tmp
n = int(input())
nums = list(map(int, input().split()))
merge_sort(nums, 0, n - 1)
print(" ".join(map(str, nums)))
def merge_sort(arr, l, r) -> int:
if l >= r:
return 0
mid = (l + r) // 2
res = 0
res += merge_sort(arr, l, mid) + merge_sort(arr, mid + 1, r)
i, j = l, mid + 1
tmp = []
while i <= mid and j <= r:
if arr[i] <= arr[j]:
tmp.append(arr[i])
i += 1
else:
tmp.append(arr[j])
res += mid - i + 1 # 记忆方法：这里用不变的量来计算，即j+=1不会影响i
j += 1
tmp.extend(arr[i:mid + 1])
tmp.extend(arr[j:r + 1])
arr[l:r + 1] = tmp
return res
n = int(input())
nums = list(map(int, input().split()))
print(merge_sort(nums, 0, n - 1))
二分
def number_range(nums, x):
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] >= x:
r = mid
else:
l = mid + 1
if nums[l] != x:
return -1, -1
left = l
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r + 1) // 2
if nums[mid] <= x:
l = mid
else:
r = mid - 1
return left, r
n, k = map(int, input().split())
nums = list(map(int, input().split()))
for _ in range(k):
x = int(input())
l, r = number_range(nums, x)
print(str(l) + " " + str(r))
def binary_search(f):
l = -10000.0
r = 10000.0
while r - l > 1e-8:
mid = (l + r) / 2
if mid * mid * mid > f:
r = mid
else:
l = mid
return l
f = float(input())
res = binary_search(f)
print("%.6f"%res)
前缀和与差分
n, m = map(int, input().split())
s = [0] + list(map(int, input().split()))
a = [0] * (n + 2)
for i in range(1, n + 1):
a[i] = s[i] - s[i - 1]
for _ in range(m):
l, r, c = map(int, input().split())
a[l] += c
a[r + 1] -=c
for i in range(1, n + 1):
s[i] = s[i - 1] + a[i]
print(" ".join(map(str, s[1:])))
def insert(diff, x1, y1, x2, y2, c):
diff[x1][y1] += c
diff[x2 + 1][y1] -= c
diff[x1][y2 + 1] -= c
diff[x2 + 1][y2 + 1] += c
n, m, q = map(int, input().split())
a = [[0] * (m + 2) for _ in range(n + 2)]
s = [[0] * (m + 2) for _ in range(n + 2)]
for i in range(1, n + 1):
row = list(map(int, input().split()))
for j in range(1, m + 1):
x = row[j - 1]
insert(a, i, j, i, j, x)
while q:
q -= 1
x1, y1, x2, y2, c = map(int, input().split())
insert(a, x1, y1, x2, y2, c)
for i in range(1, n + 1):
for j in range(1, m + 1):
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]
print(s[i][j], end=' ')
print()
双指针算法
n=int(input())
nums =list(map(int,input().split()))
temp = dict.fromkeys(set(nums),0)
l=0
res =0
for i in range(len(nums)):
temp[nums[i]]+=1
while temp[nums[i]]>1:
temp[nums[l]]-=1
l+=1
res = max(res,i-l+1)
print(res)
注意字典的初始化方式
n, m, s = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
i, j = 0, m - 1
while i < n and j > 0:
if a[i] + b[j] == s:
break
elif a[i] + b[j] < s:
i += 1
else:
j -= 1
print("%d %d" % (i, j))
位运算
def lowbit(x: int):
return x & -x
n = int(input())
for num in map(int, input().split()):
res = 0
while num:
res += 1
num -= lowbit(num)
print(res, end=' ')
离散化
n, m = map(int, input().split())
inserts = []
ranges = []
points = []
sums = [0] * (n + 2 * m + 2)
for _ in range(n):
x, c = map(int, input().split())
inserts.append([x, c])
points.append(x)
for _ in range(m):
l, r = map(int, input().split())
ranges.append([l, r])
points.append(l)
points.append(r)
points = list(set(points))
points.sort()
codebooks = {point : idx + 1 for idx, point in enumerate(points)}
for x, c in inserts:
sums[codebooks[x]] += c
for i in range(1, n + 2 * m + 2):
sums[i] += sums[i - 1]
for l, r in ranges:
print(sums[codebooks[r]] - sums[codebooks[l] - 1])
区间合并
n = int(input())
ranges = [list(map(int, input().split())) for _ in range(n)]
ranges.sort(key = lambda x : (x[0], x[1]))
merged_ranges = []
res = 0
st = ed = -float('inf')
for l, r in ranges:
if l > ed:
if ed != -float('inf'):
res += 1
merged_ranges.append([st, ed])
st, ed = l, r
else:
ed = max(ed, r)
if ed != -float('inf'):
merged_ranges.append([st, ed])
res += 1
print(res)
# print(merged_ranges)
如果只计数，用res即可，不需要merged_ranges
