简单
3 数字字符串格式化
问题
小M在工作时遇到了一个问题，他需要将用户输入的不带千分位逗号的数字字符串转换为带千分位逗号的格式，并且保留小数部分。小M还发现，有时候输入的数字字符串前面会有无用的 0，这些也需要精简掉。请你帮助小M编写程序，完成这个任务。
学语法
def solution(s: str) -> str:
# 移除前导零
s = s.lstrip('0')
# 如果字符串为空或仅包含小数点，则视为0
if not s or s == '.':
return '0'
# 检查是否有小数点，并分离整数和小数部分
if '.' in s:
integer_part, decimal_part = s.split('.')
else:
integer_part, decimal_part = s, ''
# 对整数部分进行千分位分隔
formatted_integer_part = '{:,}'.format(int(integer_part))
# 将整数和小数部分合并
result = formatted_integer_part + (f'.{decimal_part}' if decimal_part else '')
return result
if __name__ == '__main__':
print(solution("1294512.12412") == '1,294,512.12412')
print(solution("0000123456789.99") == '123,456,789.99')
print(solution("987654321") == '987,654,321')
8 找出整型数组中占比超过一半的数
问题
小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。
思路
摩尔投票法（Boyer–Moore majority vote algorithm），也被称作「多数投票法」，算法解决的问题是：如何在任意多的候选人中（选票无序），选出获得票数最多的那个。
算法可以分为两个阶段：
对抗阶段：分属两个候选人的票数进行两两对抗抵消
计数阶段：计算对抗结果中最后留下的候选人票数是否有效
https://cloud.tencent.com/developer/article/1600607
def solution(array):
count = 0
candidate = None
# 第一次遍历寻找候选者
for num in array:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
# 第二次遍历确认候选者是否为多数元素
if array.count(candidate) > len(array) // 2:
return candidate
else:
return None # 根据题设，这里实际上不会返回None，因为题目保证了存在一个数出现次数超过一半
if __name__ == "__main__":
# Add your test cases here
print(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)
中等
11 观光景点组合得分问题
问题
小R正在研究一组观光景点，每个景点都有一个评分，保存在数组 values 中，其中 values[i] 表示第 i 个观光景点的评分。同时，景点之间的距离由它们的下标差 j - i 表示。
一对景点 (i < j) 的观光组合得分为 values[i] + values[j] + i - j，也就是两者评分之和减去它们之间的距离。
小R想知道，在哪种情况下能够获得观光景点组合的最高得分。
约束条件：
2 <= values.length
1 <= values[i] <= 1000
思路
将得分公式拆分为：
values[i] + values[j] + i - j = (values[i] + i) + (values[j] - j)
遍历景点 j：对于每个景点 j，我们需要找到一个景点 i（i < j），使得 values[i] + i 最大。
维护最大值：在遍历过程中，维护一个变量 max_left，记录当前景点 j 左侧的最大 values[i] + i。
计算得分：对于每个景点 j，计算当前得分 max_left + values[j] - j，并更新全局最大得分。
def solution(values: list) -> int:
max_score = 0 # 初始化最大得分为负无穷
max_left = values[0] + 0 # 初始化左侧的最大 values[i] + i
# 遍历景点 j
for j in range(1, len(values)):
# 计算当前得分
current_score = max_left + values[j] - j
# 更新最大得分
if current_score > max_score:
max_score = current_score
# 更新左侧的最大 values[i] + i
if values[j] + j > max_left:
max_left = values[j] + j
return max_score
if __name__ == '__main__':
print(solution(values=[8, 3, 5, 5, 6]) == 11)
print(solution(values=[10, 4, 8, 7]) == 16)
print(solution(values=[1, 2, 3, 4, 5]) == 8)
16 最大矩形面积问题
问题
小S最近在分析一个数组 h1,h2,…,hNh1,h2,…,hN，数组的每个元素代表某种高度。小S对这些高度感兴趣的是，当我们选取任意 kk 个相邻元素时，如何计算它们所能形成的最大矩形面积。
对于 kk 个相邻的元素，我们定义其矩形的最大面积为：
R(k)=k×min(h[i],h[i+1],…,h[i+k−1])R(k)=k×min(h[i],h[i+1],…,h[i+k−1])
即，R(k)R(k) 的值为这 kk 个相邻元素中的最小值乘以 kk。现在，小S希望你能帮他找出对于任意 kk，R(k)R(k) 的最大值。
思路
滑动窗口：我们可以遍历数组，对于每个位置 i，找到以 h[i] 为最小值的最长子数组的长度 L，然后计算 h[i] * L，并更新最大值。
单调栈：使用单调栈来高效地找到每个元素左边和右边第一个比它小的元素的位置，从而确定以当前元素为最小值的最大子数组的长度。
def solution(n, array):
if not array or n == 0:
return 0
# 找到每个元素左边第一个比它小的元素的位置
left = [-1] * n
stack = []
for i in range(n):
while stack and array[stack[-1]] >= array[i]:
stack.pop()
if stack:
left[i] = stack[-1]
else:
left[i] = -1
stack.append(i)
# 找到每个元素右边第一个比它小的元素的位置
right = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and array[stack[-1]] >= array[i]:
stack.pop()
if stack:
right[i] = stack[-1]
else:
right[i] = n
stack.append(i)
# 计算最大面积
max_area = 0
for i in range(n):
width = right[i] - left[i] - 1
area = array[i] * width
if area > max_area:
max_area = area
return max_area
if __name__ == "__main__":
# 测试用例
print(solution(5, [1, 2, 3, 4, 5]) == 9) # 输出: True
print(solution(6, [2, 1, 5, 6, 2, 3]) == 10) # 输出: True
print(solution(4, [1, 1, 1, 1]) == 4) # 输出: True
print(solution(1, [5]) == 5) # 输出: True
if __name__ == "__main__":
# Add your test cases here
print(solution(5, [1, 2, 3, 4, 5]) == 9)
63 视频推荐的算法
问题
西瓜视频正在开发一个新功能，旨在将访问量达到80百分位数以上的视频展示在首页的推荐列表中。实现一个程序，计算给定数据中的80百分位数。
例如：假设有一个包含从1到100的整数数组，80百分位数的值为80，因为按升序排列后，第80%位置的数字就是80。
99 百分位数：假如有 N 个数据，将数据从小到大排列，99 百分位数是第 N99%位置处的数据（遇到小数时四舍五入获取整数）。一般计算逻辑是先排序，定位到 N99%的位置。返回该位置处的数据。同理，80 百分位数就是第 N*80%位置处的数据。
学语法
def solution(data):
# Please write your code here
numbers = [int(num) for num in data.split(",")]
numbers.sort()
l = len(numbers)
index = round(l * 0.8)
percentile_value = numbers[index - 1]
return percentile_value
if __name__ == "__main__":
# You can add more test cases here
print(solution("10,1,9,2,8,3,7,4,6,5") == 8 )
print(solution("1,0,8,7,3,9,12,6,4,15,17,2,14,5,10,11,19,13,16,18") == 15)
print(solution("76,100,5,99,16,45,18,3,81,65,102,98,36,4,2,7,22,66,112,97,68,82,37,90,61,73,107,104,79,14,52,83,27,35,93,21,118,120,33,6,19,85,49,44,69,53,67,110,47,91,17,55,80,78,119,15,11,70,103,32,9,40,114,26,25,87,74,1,30,54,38,50,8,34,28,20,24,105,106,31,92,59,116,42,111,57,95,115,96,108,10,89,23,62,29,109,56,58,63,41,77,84,64,75,72,117,101,60,48,94,46,39,43,88,12,113,13,51,86,71") == 96)
154 小C的点菜问题
问题
小C来到了一家餐馆，准备点一些菜。
已知该餐馆有 nn 道菜，第 ii 道菜的售价为 wiwi。
小C准备点一些价格相同的菜，但小C不会点单价超过 mm 的菜。
小C想知道，自己最多可以点多少道菜？
学语法
from collections import Counter
def solution(m: int, w: list) -> int:
# PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
# write code here
count = Counter(w)
ans = 0
for a, cnt in count.items():
if a <= m:
ans = max(ans, cnt)
# print(ans)
return ans
if __name__ == '__main__':
print(solution(6, [2, 3, 3, 6, 6, 6, 9, 9, 23]) == 3)
print(solution(4, [1, 2, 4, 4, 4]) == 3)
print(solution(5, [5, 5, 5, 5, 6, 7, 8]) == 4)
157 小C的偶数喜好
问题
小C特别喜欢偶数，但她的喜好程度依赖于一个数中包含多少个偶数因子。具体来说，对于一个数 x，我们可以将其表示为几个因数相乘，例如 x = p1 × p2 × … × pk，如果所有的 p 都是偶数，那么因子的数量 k 就是小C对这个数的喜好程度。现在，小C想知道，在区间 [l, r] 中，哪个数是她最喜欢的，意味着这个数的偶数因子数量最多。你能帮她找出最喜欢的那个数的喜好程度吗？
疑问
这个方法在区间比较短且区间端点设计很巧妙的时候可能比暴力还复杂？
def solution(l, r):
# PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
# write code here
k = 0
now = 1
while now * 2 <= r:
now = now * 2
k += 1
# print(k)
# print(now)
p = 1
while True:
if now * p > r:
now //= 2
k -= 1
elif now * p < l:
p += 2
else:
break
# print(k)
# print(now)
return k
if __name__ == '__main__':
print(solution(3, 10) == 3)
print(solution(1, 16) == 4)
print(solution(10, 20) == 4)
344 农场摘水果问题
问题
小U正在探访一座农场，农场的果树排成一列，用整数数组 fruits 表示，每个元素 fruits[i] 是第 i 棵树上的水果种类。
小U有两个篮子，每个篮子只能装一种类型的水果，而且每个篮子可以装无限量的水果。小U从任意一棵树开始，必须从每棵树上恰好采摘一个水果，并且只能装入符合篮子中水果类型的果实。如果某棵树上的水果类型不符合篮子中的水果类型，则必须停止采摘。
请你帮助小U计算他最多可以采摘多少个水果。
例如：当 fruits = [1,2,3,2,2] 时，小U最多可以采摘的树是从第2棵开始，采摘到最后的 4 棵树，结果为 [2,3,2,2]。
学语法
def solution(fruits: list) -> int:
# PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
# write code here
from collections import defaultdict
if not fruits:
return 0
left = 0 # 窗口左边界
max_length = 0 # 最大窗口长度
fruit_count = defaultdict(int) # 记录当前窗口中每种水果的数量
for right in range(len(fruits)):
fruit_count[fruits[right]] += 1 # 将当前水果加入窗口
# 如果窗口中的水果类型超过 2 种，移动左边界
while len(fruit_count) > 2:
fruit_count[fruits[left]] -= 1
if fruit_count[fruits[left]] == 0:
del fruit_count[fruits[left]]
left += 1
# 更新最大窗口长度
max_length = max(max_length, right - left + 1)
return max_length
if __name__ == '__main__':
print(solution([1, 2, 1, 2]) == 4)
print(solution([2, 0, 1, 2, 2]) == 3)
print(solution([1, 2, 3, 2, 2, 4]) == 4)
困难
149 小A的移动点
问题
小M有n个点，每个点的坐标为(xi,yi)(xi,yi)。她可以从一个点出发，平行于坐标轴移动，直到到达另一个点。具体来说，她可以从 (x1,y1)(x1,y1) 直接到达 (x2,y1)(x2,y1) 或者 (x1,y2)(x1,y2)，但无法直接到达 (x2,y2)(x2,y2)。为了使得任意两个点之间可以互相到达，小M可以选择增加若干个新的点。
你的任务是计算最少需要增加多少个点，才能保证任意两个点之间可以通过平行于坐标轴的路径互相到达。
学语法
def solution(n: int, points: list) -> int:
# 初始化 parent 和 rank
parent = list(range(n))
rank = [1] * n
# 查找函数
def find(u):
if parent[u] != u:
parent[u] = find(parent[u]) # 路径压缩
return parent[u]
# 合并函数
def union(u, v):
root_u = find(u)
root_v = find(v)
if root_u != root_v:
if rank[root_u] > rank[root_v]:
parent[root_v] = root_u
elif rank[root_u] < rank[root_v]:
parent[root_u] = root_v
else:
parent[root_v] = root_u
rank[root_u] += 1
# 按 x 坐标和 y 坐标分别合并
x_map = {}
y_map = {}
for i, (x, y) in enumerate(points):
if x in x_map:
union(i, x_map[x])
else:
x_map[x] = i
if y in y_map:
union(i, y_map[y])
else:
y_map[y] = i
# 统计连通分量的数量
roots = set()
for i in range(n):
roots.add(find(i))
# 最小新增点数等于连通分量数减一
return len(roots) - 1
# 测试用例
print(solution(2, [[1, 1], [2, 2]]) == 1) # 输出: True
print(solution(3, [[1, 2], [2, 3], [4, 1]]) == 2) # 输出: True
print(solution(4, [[3, 4], [5, 6], [3, 6], [5, 4]]) == 0) # 输出: True
170 小C的数字倍数问题
问题
小U对数字倍数问题很感兴趣，她想知道在区间[l,r][l,r]内，有多少个数是aa的倍数，或者是bb的倍数，或者是cc的倍数。你需要帮小U计算出这些数的个数。
学语法
import math
from functools import reduce
def lcm_multiple(*args):
"""计算多个数的最小公倍数"""
return reduce(lcm, args)
def lcm(a, b):
"""计算两个数的最小公倍数"""
return abs(a * b) // math.gcd(a, b)
def f(l: int, r: int, x: int) -> int:
# print(f"f([{l}, {r}], {x}) = {cal(r, x) - cal(l - 1, x)}")
return cal(r, x) - cal(l - 1, x)
def cal(l: int, x: int) -> int:
return l // x
def solution(a: int, b: int, c: int, l: int, r: int) -> int:
# PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
# write code here
ans = f(l, r, a) + f(l, r, b) + f(l, r, c) - f(l, r, lcm(a, b)) - f(l, r, lcm(c, b)) - f(l, r, lcm(a, c)) + f(l, r, lcm_multiple(a, b, c))
return ans
if __name__ == "__main__":
print(solution(2, 3, 4, 1, 10) == 7)
print(solution(5, 7, 11, 15, 100) == 34)
print(solution(1, 1, 1, 1, 1000) == 1000)
279 最长连续交替字串问题
问题
小C拿到了一个长度为n的二进制串。他发现通过一些操作可以得到一个很有趣的效果。每次操作是将这个字符串按顺序分为两部分，分别将两部分各自翻转后再按原顺序拼接。小C想知道，通过进行任意次数的操作后，能够得到的最长的连续交替01子串的长度是多少。
例如：当前的二进制串是 01001，可以先将其分为 010 和 01 两部分，分别翻转得到 010 和 10，按原顺序拼接后得到 01010，此时最长的连续交替子串是 01010，长度为 5。
思路
首尾相连，看作一个环，这个操作对环没有任何影响。进而通过复制一份字符串把环的问题转化为普通的数组问题。
双指针O(n)
def solution(s: str) -> int:
# PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
# write code here
n = len(s)
s = s + s
r = 0
ans = 1
for i in range(n):
r = max(i, r)
while r + 1 - i + 1 <= n and s[r] != s[r + 1]:
r += 1
# print(r)
ans = max(ans, r - i + 1)
return ans