描述
一个字符串只包含大写字母，求其连续相同字母子串中，长度第K长的子串长度，相同字母只取
最长那个子串。
例:AAAAHHHBBCDHHHH
K=3
输出:2
代码(python)
def test_007(k, target_str):
print(f"输入的字符串是:{target_str}",end="")
# 以字符串中的字母创建一个字典
print("")
dict_1 = {}
for i in target_str:
if i not in dict_1.keys():
dict_1[i] = 0
index = 0
count = 0
max_index = len(target_str) - 1
# 临时变量a 初始值为字符串的第一个字母
a = target_str[0]
# 遍历字符串
while index <= max_index:
# 若字母相等，长度加1
if a == target_str[index]:
count += 1
# 若不同，表示是下一个字串，
# 记录当前字串的长度
# 更新临时变量a，记录下一个
else:
if dict_1[a] < count:
dict_1[a] = count
count = 1
a = target_str[index]
index += 1
# 上述代码只在else保存的时前一个字串的长度，
# 在index=max_index时会出现计数未保存的情况
# 1. 若n-1和n位置的字母相同，不会将更新的count加到字典
# 2. 若n-1和n位置的字母不相同，不会将新字串的长度加到字典
# 所以在最后加一次处理操作
if dict_1[a] < count:
dict_1[a] = count
# for i, j in dict_1.items():
# print(i, j)
# 利用set去重（不同字母构成的字串长度相同）然后转成list升序排序,题目答案是步不去重的结果
# 最后输出k-1位置的值
# out_list = sorted(list(set(dict_1.values())))
out_list = sorted(dict_1.values())
if k > len(out_list):
print(f"k={k}大于字符串的子串长度大小构成的list的长度{len(out_list)}",end="")
else:
print(f"输入k={k},第{k}长的子串的长度是{out_list[k-1]}")
运行结果
描述
上台阶，一个阶梯有N阶台阶，每次只能上1步或者3步，求一共有多少种不同的方式上台阶？
例：N=50
输出：122106097
思路
动态规划：
假设上N阶台阶的方式有F(n)种，我们从后往前思考，最后一次上台阶的方式只能为1步或者3步，
那么倒数第二次的处于的台阶就是n-1阶或者n-3阶，所以完成n阶台阶的总组合数就可以转换成
F(n)=F(n-1)+F(n-3)，依次往前推，可以等到F(6)=F(5)-F(3),F(5)=F(4)-F(2),F(4) = F(3) + F(1),
可以观察到规律，当n大于等于6的时候，等式右边的值就可以在之前的等式找到，所以我们只
需先手动计算基础项的值,F(1)= 1，F(2) =1,F(3)=2，就可以由前面的等式得到后面等式需要的值。
代码(python)
# 非递归代码实现，n大于等于4的时候可以用F(n)=F(n-1)+F(n-3)
def test_004(n):
if n <= 2:
return 1
elif n == 3:
return 2
else:
# 用来存放a值,因为a的更替存在跨度问题，所以用一个长度为2的list维护
temp_a_list = [1, 1]
a, b, sum1 = 2, 1, 0
while n > 3:
sum1 = a + b
temp_a_list[0], temp_a_list[1] = temp_a_list[1], a
b = temp_a_list[0]
a = sum1
n -= 1
return sum1
# 递归实现 但是执行时间会很长
def test_0041(n):
if n <= 2:
return 1
elif n == 3:
return 2
else:
return test_0041(n-1)+test_0041(n-3)
运行截图
描述
有一堆石子，一次编号1-100围成圈，给定一个数K，从1开始数K个，将此石子踢出，继续报
数，最后当石子总数小于K时，输出最后剩余石子编号。
例:K为3
输出:58，91
思路和代码(python)
def test_002(n):
list_1 = [x for x in range(1, 101)]
max_index = len(list_1) - 1
index = 0 # 序列index
count = 0 # 记录被踢出人的个数
num_n = 0 # 记录报数
# 循环退出条件，踢出(100 - n - 1)个人
while count < 98:
# 1.循环列表找到值不是-1的，报数值加1（-1的表示已经踢出）
# 2.当报数num_n=n时，表示找到了踢出的人，设置计数count_n=0，退出循环
# 3.将此时的list_1[index]赋值为-1，表示踢出
# 4.重复1-3，直到count == (101-n)退出外层循环
while True:
# 当index 大于maxindex 表示需要从头开始计数了
if index > max_index:
index = 0
# 找到值不是-1的就报数（-1表示以被踢出的），否则报数直接index增加
if list_1[index] != -1:
num_n += 1
if num_n == n:
num_n = 0
break
index += 1
count += 1
# print(f"第{count}次，踢出{list_1[index]}")
list_1[index] = -1
print("处理完毕！")
for item in list_1:
if item != -1:
print(item, end=" ")
运行结果
