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 Truereturn Falsecnt = 0
for num in range(1, 2021):if is_composite(num):cnt += 1print(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 = 31elif month == 2:if is_leap_year(year):days = 29else:days = 28else:days = 30for day in range(1, days + 1):# 前填充0date_str = str(year) + str(month).zfill(2) + str(day).zfill(2)if '2' in date_str:count += 1print(count)
3、从m*n 矩阵的左下角到右上角的走法数量（dp）
def f(m, n):# 初始化m*n矩阵dp，用于存储到达每个位置的走法数量dp = [[0] * n for _ in range(m)]# 将第一列设置为1for i in range(m):dp[i][0] = 1# 将最后一行设置为1for 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 Falsereturn len(stack) == 0print(f("([{}])")) # True
5、输出杨辉三角的前n行
def f(n):triangle = []for i in range(n):row = [1] * (i + 1) # 初始化行为1for j in range(1, i):# 将 (左上, 上) 相加row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]triangle.append(row)return triangleresult = 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 depthN = 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)
