中等：
观光景点组合得分问题
小R正在研究一组观光景点，每个景点都有一个评分，保存在数组 values 中，其中 values[i] 表示第 i 个观光景点的评分。同时，景点之间的距离由它们的下标差 j - i 表示。
一对景点 (i < j) 的观光组合得分为 values[i] + values[j] + i - j，也就是两者评分之和减去它们之间的距离。
小R想知道，在哪种情况下能够获得观光景点组合的最高得分。
测试样例：
样例1：
输入：
values = [8, 3, 5, 5, 6]
输出：11
样例2：
输入：
values = [10, 4, 8, 7]
输出：16
样例3：
输入：
values = [1, 2, 3, 4, 5]
输出：8
def solution(values: list) -> int:
n = len(values)
if n < 2:
return 0 # 如果数组长度小于2，无法形成组合，返回0或其他适当值
# 初始化
max_i_plus_values = values[0] + 0 # 初始时i=0
max_score = values[0] + values[1] + 0 - 1 # 初始组合 (0,1)
# 从第二个元素开始遍历
for j in range(1, n):
# 计算当前j的values[j] - j
current = values[j] - j
# 更新最大组合得分
max_score = max(max_score, max_i_plus_values + current)
# 更新max_i_plus_values
max_i_plus_values = max(max_i_plus_values, values[j] + j)
return max_score
if __name__ == '__main__':
# 测试样例1
print(solution(values=[8, 3, 5, 5, 6]) == 11) # 输出: True
# 测试样例2
print(solution(values=[10, 4, 8, 7]) == 16) # 输出: True
# 测试样例3
print(solution(values=[1, 2, 3, 4, 5]) == 8) # 输出: True
最少前缀操作问题
小U和小R有两个字符串，分别是SS和TT，现在小U需要通过对SS进行若干次操作，使其变成TT的一个前缀。操作可以是修改SS的某一个字符，或者删除SS末尾的字符。现在你需要帮助小U计算出，最少需要多少次操作才能让SS变成TT的前缀。
测试样例：
样例1：
输入：
S = "aba", T = "abb"
输出：1
样例2：
输入：
S = "abcd", T = "efg"
输出：4
样例3：
输入：
S = "xyz", T = "xy"
输出：1
def solution(S: str, T: str) -> int:
len_S = len(S)
len_T = len(T)
# 计算需要删除的字符数量
deletions = max(0, len_S - len_T)
# 截断 S，使其长度不超过 T
S_new = S[:len_T] if len_S > len_T else S
# 计算需要修改的字符数量
modifications = 0
for i in range(len(S_new)):
if S_new[i] != T[i]:
modifications += 1
# 总操作次数
total_operations = deletions + modifications
return total_operations
if __name__ == '__main__':
print(solution("aba", "abb") == 1) # 输出: True
print(solution("abcd", "efg") == 4) # 输出: True
print(solution("xyz", "xy") == 1) # 输出: True
print(solution("hello", "helloworld") == 0) # 输出: True
print(solution("same", "same") == 0) # 输出: True
小C的好数
小C对“好数”非常感兴趣，她定义一个不含前导零的正整数为“好数”，如果它的所有数位最多包含两种不同的数字。例如，数字 23，2323，9，111，和 101 都是好数。现在小C想知道，从1到nn之间有多少个好数。
例如：当n=110n=110时，所有的1位数、2位数，以及一些3位数（如 100, 101）都是好数，一共有102个。
测试样例：
样例1：
输入：
n = 110
输出：102
样例2：
输入：
n = 1000
输出：352
def solution(n: int) -> int:
count = 0 # 初始化好数的计数器
for num in range(1, n + 1):
num_str = str(num) # 将数字转换为字符串
unique_digits = set(num_str) # 获取数字中不同的字符
if len(unique_digits) <= 2: # 如果不同字符数量 <= 2
count += 1 # 计数器加1
return count
if __name__ == '__main__':
print(solution(110) == 102) # 输出: True
print(solution(1000) == 352) # 输出: True
print(solution(1) == 1) # 输出: True
困难：
二进制之和
小U和小R喜欢探索二进制数字的奥秘。他们想找到一个方法，将两个二进制字符串相加并以十进制的形式呈现。这个过程需要注意的是，他们的二进制串可能非常长，所以常规的方法可能无法处理大数。小U和小R希望你帮助他们设计一个算法，该算法能在保证时间复杂度不超过O(n^2)的前提下，返回两个二进制字符串的十进制求和结果。
测试样例：
样例1：
输入：
binary1 = "101" ,binary2 = "110"
输出：'11'
省略样例，直接贴代码
def solution(binary1: str, binary2: str) -> str:
# Function to add two binary strings
def add_binary(b1, b2):
i = len(b1) - 1
j = len(b2) - 1
carry = 0
res = []
while i >= 0 or j >= 0 or carry:
bit1 = int(b1[i]) if i >= 0 else 0
bit2 = int(b2[j]) if j >= 0 else 0
total = bit1 + bit2 + carry
carry = total // 2
res.append(str(total % 2))
i -= 1
j -= 1
return ''.join(res[::-1])
# Function to convert binary string to decimal string
def binary_to_decimal(bin_str):
decimal = [0] # List to store each digit, least significant digit at the end
for bit in bin_str:
# Multiply current decimal by 2
carry = 0
for idx in range(len(decimal)-1, -1, -1):
temp = decimal[idx] * 2 + carry
decimal[idx] = temp % 10
carry = temp // 10
if carry:
decimal = [carry] + decimal
# Add the current bit
if bit == '1':
carry = 1
for idx in range(len(decimal)-1, -1, -1):
temp = decimal[idx] + carry
decimal[idx] = temp % 10
carry = temp // 10
if carry == 0:
break
if carry:
decimal = [carry] + decimal
return ''.join(map(str, decimal))
# Step 1: Add the binary strings
binary_sum = add_binary(binary1, binary2)
# Step 2: Convert the binary sum to decimal string
decimal_sum = binary_to_decimal(binary_sum)
return decimal_sum
if __name__ == "__main__":
# 测试样例1
print(solution("101", "110") == "11") # 输出: True
# 测试样例2
print(solution("111111", "10100") == "83") # 输出: True
# 测试样例3
print(solution("111010101001001011", "100010101001") == "242420") # 输出: True
# 测试样例4
print(solution("111010101001011", "10010101001") == "31220") # 输出: True
# 测试样例5
print(solution("11", "1") == "4") # 输出: True
小C的连续自然数乘积问题
小S在学习素数因子的分解，她希望在[1,n]的范围内，找到一些连续的自然数，这些数的乘积最多包含k个不同的素因子。你的任务是帮助小S找到可以取的连续自然数的最大长度。
连续的自然数指的是不能重复且相邻数的差为1的一组正整数，例如 [2, 3, 4, 5] 和 [5, 6, 7] 都是连续的取数。
测试样例
样例1：
输入：
n = 10,k = 3
输出：6
直接贴代码:)
def solution(n: int, k: int) -> int:
# 生成素数列表，使用埃拉托斯特尼筛法
sieve = [True] * (n + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(n**0.5) + 1):
if sieve[i]:
for j in range(i*i, n+1, i):
sieve[j] = False
primes = [i for i, is_prime in enumerate(sieve) if is_prime]
# 生成每个数的素因子列表
factors = [[] for _ in range(n + 1)]
for prime in primes:
for multiple in range(prime, n + 1, prime):
factors[multiple].append(prime)
left = 1
max_length = 0
prime_counts = {}
distinct_primes = 0
for right in range(1, n + 1):
# 添加右边的数的素因子
for p in factors[right]:
if p in prime_counts:
prime_counts[p] += 1
else:
prime_counts[p] = 1
distinct_primes +=1
# 如果超过k个不同的素因子，移动左指针
while distinct_primes > k and left <= right:
for p in factors[left]:
prime_counts[p] -=1
if prime_counts[p] ==0:
del prime_counts[p]
distinct_primes -=1
left +=1
# 更新最大长度
current_length = right - left +1
if current_length > max_length:
max_length = current_length
return max_length
if __name__ == "__main__":
print(solution(10, 3) == 6)
print(solution(20, 5) == 12)
print(solution(100, 4) == 10)