一、生成字符串所有不同子串

例题一：

一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成 的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。 注意在计算时，只算本质不同的串的个数。 请问，字符串0100110001010001 有多少个不同的非空子串？

s = '0100110001010001'
subs = []

for i in range(len(s)+1):
    for j in range(i+1, len(s)+1):
        if(s[i:j] not in subs):
            subs.append(s[i:j])
print(len(subs))

优化方法：可以使用集合（set）来替代列表存储子串，因为集合的查找操作时间复杂度为 O(1)

s = '0100110001010001'
subs = set()

for i in range(len(s)+1):
    for j in range(i+1, len(s)+1):
        subs.add(s[i:j])

print(len(subs))

---

二、求列表中位数

中位数是将一组数据按照从小到大（或从大到小）的顺序排列，如果数据的个数是奇数，则处于中间位置的数为这组数据的中位数；如果数据的个数是偶数，则中间两个数据的平均数为这组数据的中位数。

例题一：

一家商店记录了连续 12 个月的销售额（单位：万元），数据为 [23, 25, 21, 27, 24, 26, 22, 28, 20, 29, 30, 19]。商店经理想要了解销售额的中间水平，以便制定合理的销售目标，帮助经理计算出这 12 个月销售额的中位数。

def find_median(lst):
    sorted_lst = sorted(lst)
    n = len(sorted_lst)
    if n % 2 == 1:
        return sorted_lst[n // 2]
    else:
        return (sorted_lst[n // 2 - 1] + sorted_lst[n // 2]) / 2


sales = [23, 25, 21, 27, 24, 26, 22, 28, 20, 29, 30, 19]
median = find_median(sales)
print(f"这12个月销售额的中位数是: {median} 万元")

---

三、斐波那契数列

斐波那契数列是指这样一个数列：0、1、1、2、3、5、8、13、21、34、……

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


# 示例用法
n = 10
print(f"斐波那契数列的第 {n} 项是: {fibonacci_recursive(n)}")

例题一：

给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求 第 20190324 项的最后 4 位数字。

def find_last_four(n):
    if n <= 2:
        return 1
    a, b, c = 1, 1, 1
    for _ in range(3, n):
        # 每一步只保留结果的后四位
        a, b, c = b, c, (a + b + c) % 10000
    return c


num = 20190324
print(find_last_four(num))

---

四、整数拆分

将一个给定的整数拆分成若干个满足特定条件的整数之和，需要找出所有可能的拆分方式或计算拆分方式的数量。

例题一：

将 2019 拆分成 3 个各不相同的正整数之和，并且交换顺序视为同一种方法。例如 1000+1001+18 和 1001+1000+18 被视为同一种。

num = 2019
count = 0
# 第一个数从 1 开始
for i in range(1, num):
    # 第二个数要比第一个数大，避免重复
    for j in range(i + 1, num):
        # 计算第三个数
        k = num - i - j
        # 确保第三个数大于第二个数且为正整数
        if k > j and k > 0:
            count = count + 1
print(count)
  

增加条件：要求每个正整数都不包 含数字 2 和 4

num = 2019
count = 0


def check_num(n):
    num_str = str(n)
    return '2' not in num_str and '4' not in num_str


# 第一个数从 1 开始
for i in range(1, num):
    if not check_num(i):
        continue
    # 第二个数要比第一个数大，避免重复
    for j in range(i + 1, num):
        if not check_num(j):
            continue
        # 计算第三个数
        k = num - i - j
        # 确保第三个数大于第二个数且为正整数，同时第三个数不包含 2 和 4
        if k > j and k > 0 and check_num(k):
            count = count + 1

print(count)

---

五、进制转换

例题一：

小明用字母 A 对应数字1，B 对应2，以此类推，用 Z 对应26。对于27以上的数字，小明用两位或更长位的字符串来对应，例如AA 对应 27，AB 对应28，AZ 对应52，LQ 对 329。请问2019 对应的字符串是什么？

进制转换是指将一个数从一种进制表示转换为另一种进制表示。常见的进制有二进制（满 2 进 1）、十进制（满 10 进 1）、十六进制（满 16 进 1）等。在本题里，使用字母 A - Z 来表示数字，本质上是一种特殊的 26 进制。

word = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
num = 2019
result = ''

while num > 0:
    # 计算当前位对应的字母索引
    remainder = (num - 1) % 26
    # 将对应的字母添加到结果字符串的前面
    result = word[remainder] + result
    # 更新数字，准备计算下一位
    num = (num - 1) // 26

print(result)

例题二：

请找到一个大于 2022 的最小数，这个数转换成十六进制之后，所有的数位（不含前导 0）都为字母（A 到 F）。请将这个数的十进制形式作为答案提交。

import re

n = 2023
while n > 2022:
    result = format(n,'X')
    if re.search(r'\d',str(result)):
        n += 1
    else:
        print(n)
        break

例题三：

在Excel中，列的名称使用英文字母的组合。前 26 列用一个字母，依次为 A 到 Z，接下来 26*26 列使用两个字母的组合，依次为 AA 到 ZZ。请问第 2022 列的名称是什么？

word = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
num = 2022
result = ''

while num > 0:
    digit = (num - 1) % 26
    result = word[digit] + result
    num = (num - 1) // 26
  
print(result)

---

六、日期问题

例题一：日期遍历与条件统计类

小明坚持每天跑步，正常情况下每天跑一公里，如果这一天是周一或者月初（每月的一号），那么小明就会跑两公里（如果这一天既是周一，又是月初，小明也是跑两公里），小明从2000年1月1日一直坚持到了2020年10月1日，请你计算一下小明共跑了多少公里？

from datetime import date, timedelta

start = date(2000,1,1)
end = date(2020,10,1)
count = 0

while start <= end:
    if start.day == 1 or start.weekday() == 0:
        count += 1
    count += 1
    start = start + timedelta(days=1)

print(count)

例题二：时间戳转换

小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 1970 年 1 月 1 日 00:00:00 到当前时刻经过的毫秒数。现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

【输入格式】
输入一行包含一个整数，表示时间。

【输出格式】
输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 HH 表示时，值为 0 到 23，MM 表示分，值为 0 到 59，SS 表示秒，值为 0 到 59。时、分、秒不足两位时补前导 0。

from datetime import datetime

def timestamp_to_hms(timestamp):
    # 将时间戳转换为 datetime 对象
    dt = datetime.utcfromtimestamp(timestamp)
    # 格式化 datetime 对象，只获取时分秒
    return dt.strftime("%H:%M:%S")


# 示例时间戳（单位：秒）
timestamp = 46800999 // 1000
print(timestamp_to_hms(timestamp))

例题三：回文日期

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。
有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。
也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。算不上 “千年一遇”，顶多算 “千年两遇”。
给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入格式

输入包含一个八位整数 N，表示日期。

输出格式

输出两行，每行 1 个八位数。第一行表示下一个回文日期，第二行表示下一个 ABABBABA 型的回文日期。

样例输入

20200202

样例输出

20211202
21211212

from datetime import datetime,timedelta

n = str(int(input())+1)
time_n = datetime.strptime(n,'%Y%m%d').date()

times = []
ba_times = []

while True:
    n = datetime.strftime(time_n,'%Y%m%d')
    revers_date = n[::-1]
    if revers_date == n:
        times.append(n)
    ba_date = n[:4][::-1]
    if ba_date[:2] == ba_date[2:] and n[4:6] == n[6:]:
        if ba_date == n[4:]:
            ba_times.append(n)
  
    if len(times) > 1 and len(ba_times) > 1:
        break
    time_n = datetime.strptime(n,'%Y%m%d').date()
    time_n = time_n + timedelta(days=1)

print(times[0])
print(ba_times[0])

例题四：求完全平方数

若一个数是完全平方数，那么它的平方根是一个整数。从2001年1月1日到2021年12月31日中，一共有多少日期中的年月日的数字之和是完全平方数

from datetime import date, timedelta
import math

start = date(2001, 1, 1)
end = date(2021, 12, 31)
count = 0

while start < end:
    total = start.year + start.month + start.day
    sqrt = math.sqrt(total)
    if sqrt ** 2 == total:
        count += 1
    start = start + timedelta(days=1)

print(count)

例题五：扩展数字与汉字对应转换

小蓝决定根据日期的笔画数来安排自己的练习。首先，他会将当天的日期按照 “YYYYMMDD“ 的格式转换成一个 8 位数，然后将这 8 位数对应到汉字上，计算这些汉字的总笔画数。如果总笔画数超过 50，他就去练习篮球；如果总笔画数不超过 50，他就去练习书法。

例如，在 2024 年 1 月 1 日这天，日期可表示为一个 8 位数字 20240101，其转换为汉字是“二零二四零一零一”。日期的总笔画数为 2+13+2+5+13+1+13+1=50，因此在这天，小蓝会去练习书法。

汉字	笔画数
零	13
一	1
二	2
三	3
四	5
五	4
六	4
七	2
八	2
九	2

现在，请你帮助小蓝统计一下，在 2000 年 1 月 1 日到 2024 年 4 月 13 日这段时间内，小蓝有多少天是在练习篮球？

from datetime import datetime,date,timedelta

num_to_chinese = {
    0: '零', 1: '一', 2: '二', 3: '三', 4: '四',
    5: '五', 6: '六', 7: '七', 8: '八', 9: '九'
}

pen_counts = {}
pen_draw = [13,1,2,3,5,4,4,2,2,2]

for i,v in enumerate(num_to_chinese.values()):
    pen_counts[v] = pen_draw[i]

basket = 0

start = date(2000,1,1)
end = date(2024,4,13)
while start <= end:
    dates = start.strftime('%Y%m%d')
    result = ''
    for j in dates:
        for k in num_to_chinese:
            if int(j) == k:
                result = result + num_to_chinese[k]

    count = 0
    for cn in result:
        for pens in pen_counts:
            if cn == pens:
                count += pen_counts[pens]
    if count > 50:
        basket += 1
  
  
    start = start + timedelta(days=1)

print(basket)

例题六：寻找日期中的 1

小蓝计划在某天的日期中出现 1 时跑 5 千米，否则只跑 1 千米。注意日期中出现 1 不仅指年月日也指星期。

请问按照小蓝的计划，2023 年小蓝总共会跑步锻炼多少千米?例如，5 月 1 日、1 月 13 日、11 月 5 日、4 月 3 日 (星期一) 小蓝会跑 5 千米，而 5 月 23 日小蓝会跑 11 千米 (示例日期均为 2023 年)

from datetime import date,datetime,timedelta

start = date(2023,1,1)
end = date(2024,1,1) - timedelta(days=1)


run = 0
while start <= end:
  
    if '1' in start.strftime('%Y%m%d') or start.weekday() == 0:
        run += 4
    run += 1
    start = start + timedelta(days=1)

print(run)

例题七：求输入日期是今年的第几天

from datetime import date,timedelta

in_date = list(map(int,input().split()))

dates = date(*in_date)
print(dates.timetuple().tm_yday)

---

七、求质数

质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数

def is_prime(num):
    # 质数定义要求大于 1
    if num < 2:
        return False
    # 从 2 开始到 num - 1 进行遍历
    for i in range(2, num):
        # 如果 num 能被 i 整除，说明 num 不是质数
        if num % i == 0:
            return False
    # 若都不能整除，则 num 是质数
    return True

# 测试示例
test_num = 17
if is_prime(test_num):
    print(f"{test_num} 是质数")
else:
    print(f"{test_num} 不是质数")

例题一：

求300以内的所有质数

def find_primes_brute_force(n):
    primes = []
    for num in range(2, n + 1):
        is_prime = True
        for i in range(2, num):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

# 测试示例
limit = 30
prime_numbers = find_primes_brute_force(limit)
print(f"小于等于 {limit} 的质数有: {prime_numbers}")

---

八、正则表达式

例题一：

先找出20210605的所有素数，然后判断这些数的十进制位是否都是素数

import re

primes = []
for i in range(2, 20210605 + 1):
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            break
    else:
        primes.append(i)

pattern = r'^[2357]+$'

count = 0
for value in primes:
    result = re.search(pattern, str(value))
    if result:
        count += 1

print(count)

埃拉托斯特尼筛法

# 埃拉托斯特尼筛法筛选素数
def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    primes = []
    for p in range(2, n + 1):
        if is_prime[p]:
            primes.append(p)
    return primes


# 判断一个数是否仅由 2、3、5、7 组成
def is_valid_digits(num):
    num_str = str(num)
    valid_digits = {'2', '3', '5', '7'}
    for digit in num_str:
        if digit not in valid_digits:
            return False
    return True



upper_bound = 20210605
primes = sieve_of_eratosthenes(upper_bound)
count = 0
for prime in primes:
    if is_valid_digits(prime):
        count += 1

print(count)

---

九、根据数字的位数进行判断

例题一：判断奇偶

输入一个数，判断这个数的奇数位数字是否是奇数（各位、百位、万位...），偶数位数字是否是偶数（十位、千位...）

def check_digits(num):
    num_str = str(num)
    for i, digit in enumerate(num_str):
        digit = int(digit)
        # 判断当前是奇数位还是偶数位
        if (i + 1) % 2 == 1:
            # 奇数位
            if digit % 2 == 0:
                return False
        else:
            # 偶数位
            if digit % 2 == 1:
                return False
    return True


input_num = int(input("请输入一个数: "))
if check_digits(input_num):
    print(f"{input_num} 的奇数位数字是奇数，偶数位数字是偶数。")
else:
    print(f"{input_num} 不满足奇数位数字是奇数，偶数位数字是偶数的条件。")

例题二：判断奇偶2

一个整数如果按从低位到高位的顺序，奇数位 (个位、百位、万位 ⋯ ) 上的数字是奇数，偶数位 (十位、千 位、十万位 ⋯) 上的数字是偶数，我们就称之为 “好数”。给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。

例子：输入 24，输出 7

num = int(input())


def is_odd(n):
    if n % 2 == 0:
        return False
    elif n % 2 != 0:
        return True

def is_even(n):
    if n % 2 == 0:
        return True
    elif n % 2 != 0:
        return False

count = 0
for i in range(1,num+1):
    result = [int(x) for x in str(i)][::-1]
    bools = True
    for idx,val in enumerate(result,start=1):
        if idx % 2 != 0:
            if not is_odd(val):
                bools = False
                break
  
        elif idx % 2 == 0:
            if not is_even(val):
                bools = False
                break
    if bools:
        count += 1
   
print(count)

---

十、递推问题

例题一：弹珠推放

def lei(n):
    if n == 1:
        return 1
    else:
        return n + lei(n-1)

count = 0
ball = 20230610
high = 0

while count < ball:
    # 计算下一个高度所需的弹珠数
    next_count = count + lei(high + 1)
    if next_count > ball:
        break
    high = high + 1
    count = next_count

print(high)