1、计算1-2020间的素数个数
def is_composite(num):
if num <= 1:
return False
# 从 2 开始到 num 的平方根进行遍历
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return True
return False
cnt = 0
for num in range(1, 2021):
if is_composite(num):
cnt += 1
print(cnt)
2、 1900 ～ 9999 年有多少天日历上包含 2？
# 被4整除但不能被100整除，或者能被400整除，闰年
def is_leap_year(year):
return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)
count = 0
for year in range(1900, 10000):
for month in range(1, 13):
if month in [1, 3, 5, 7, 8, 10, 12]:
days = 31
elif month == 2:
if is_leap_year(year):
days = 29
else:
days = 28
else:
days = 30
for day in range(1, days + 1):
# 前填充0
date_str = str(year) + str(month).zfill(2) + str(day).zfill(2)
if '2' in date_str:
count += 1
print(count)
3、从m*n 矩阵的左下角到右上角的走法数量（dp）
def f(m, n):
# 初始化m*n矩阵dp，用于存储到达每个位置的走法数量
dp = [[0] * n for _ in range(m)]
# 将第一列设置为1
for i in range(m):
dp[i][0] = 1
# 将最后一行设置为1
for j in range(n):
dp[m - 1][j] = 1
# 从倒数第二行开始，从左到右填充 dp 数组
for i in range(m - 2, -1, -1):
for j in range(1, n):
# 状态转移方程：下边和左边的走法数量之和
dp[i][j] = dp[i + 1][j] + dp[i][j - 1]
# 右上角位置的走法数量
return dp[0][n - 1]
print(f(4, 4)) # 20
4、验证一个括号序列是否完整且匹配
def f(sequence):
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in sequence:
if char in mapping.values():
# 遇到左括号，压入栈中
stack.append(char)
elif char in mapping.keys():
if not stack or stack.pop() != mapping[char]:
# 栈为空或者栈顶元素与当前右括号不匹配
return False
return len(stack) == 0
print(f("([{}])")) # True
5、输出杨辉三角的前n行
def f(n):
triangle = []
for i in range(n):
row = [1] * (i + 1) # 初始化行为1
for j in range(1, i):
# 将 (左上, 上) 相加
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
triangle.append(row)
return triangle
result = f(5)
for row in result:
print(row)
6、给定一颗含节点权重的完全二叉树，计算权重和最大的层的深度
# 计算每一层的权重和，保存在字典里，求字典最大值
def f(N, weights):
# 初始化每个深度的权值和
depth_sums = {}
for i in range(N):
# 对于节点索引 i，深度 = (i).bit_length()
depth = (1+i).bit_length()
# 累加该深度的权值
if depth in depth_sums:
depth_sums[depth] += weights[i]
else:
depth_sums[depth] = weights[i]
# 找出权值和最大的深度
max_weight = max(depth_sums.values())
for depth in sorted(depth_sums.keys()):
if depth_sums[depth] == max_weight:
return depth
N = int(input())
weights = list(map(int, input().split()))
print(f(N, weights))
7、构造长度为 10000 的数字字符串，要求不含0且包含 3 和 7，求满足条件的数字字符串个数，结果对(10^9 + 7)取余
MOD = 10**9 + 7
n = 10000
# 计算 9^n, 8^n, 7^n 并取模
# pow(9, n, MOD) 不考虑0的情况数 (9^10000)
# pow(8, n, MOD) 不含3或7的情况数 (8^10000)
# pow(7, n, MOD) 不含3和7的情况数 (7^10000)
result = pow(9, n, MOD) - 2 * pow(8, n, MOD) + pow(7, n, MOD)
print(result % MOD)
