Python刷题练习

---

1.寻找相同字串

题目描述:
给你两个字符串t和p，要求从t中找到一个和p相同的连续子串，并输出该子串第一个字符的下标。

输入描述:
输入文件包括两行 分别表示字符串t和p
保证t的长度不小于p
且t的长度不超过1000000
p的长度不超过10000

输出描述:
如果能从t中找到一个和p相等的连续子串，则输出该子串第一个字符在t中的下标，下标从左到右依次为1,2,3,…；
如果不能，则输出 “No”
如果含有多个这样的子串，则输出第一个字符下标最小的

用例：
输入：AVERDXIVYERDIAN
RDXI
输出：4

"""寻找相同字串"""def search_same_string(t: str, p: str):""""""t_len = len(t)p_len = len(p)for i in range(t_len):if t[i] == p[0]:for j in range(p_len):if t[i+j] != p[j]:breakelse:return i + 1return "No"t = "AVERDXIVYERDIAN"
p = "RDXI"
result = search_same_string(t, p)
print(result)

2.密钥格式化

题目描述:
给定一个非空字符串 S，其被 N 个’-‘分隔成 N+1 的子串，给定正整数 K，要求除第一个子串外，其余的串每 K 个用’-‘分隔，并将小写字母转换为大写。

输入描述:
正整数 K 和‘-’分割的字符串，如：
2
25G3C-abc-d

输出描述:
转换后的字符串

用例1：
输入：4
5F3Z-2e-9-w
输出：5F3Z-2E9W

用例2：
输入：2
2-5g-3-J
输出：2-5G-3J

"""密钥格式化"""def key_format(k: int, s: str):""""""s_split = s.split("-")post_s = "".join(s_split[1:]).upper()post_s_split = [post_s[i:i+k] for i in range(0, len(post_s), k)]post_s = "-".join(post_s_split)result = f"{s_split[0]}-{post_s}"return resultk = 4
s = "5F3Z-2e-9-w"
result = key_format(k, s)
print(result)

3.五键键盘的输出

题目描述：
有一个特殊的5键键盘，上面有a，ctrl-c，ctrl-x，ctrl-v，ctrl-a五个键。
a键在屏幕上输出一个字母a；
ctrl-c将当前选择的字母复制到剪贴板；
ctrl-x将当前选择的字母复制到剪贴板，并清空选择的字母；
ctrl-v将当前剪贴板里的字母输出到屏幕；
ctrl-a选择当前屏幕上的所有字母。

注意：
剪贴板初始为空，新的内容被复制到剪贴板时会覆盖原来的内容
当屏幕上没有字母时，ctrl-a无效
当没有选择字母时，ctrl-c和ctrl-x无效
当有字母被选择时，a和ctrl-v这两个有输出功能的键会先清空选择的字母，再进行输出
给定一系列键盘输入，输出最终屏幕上字母的数量。

输入描述:
输入为一行，为简化解析，用数字1 2 3 4 5代表a，ctrl-c，ctrl-x，ctrl-v，ctrl-a五个键的输入，数字用空格分隔。

输出描述:
输出一个数字，为最终屏幕上字母的数量。

用例1：
输入：[1, 1, 1]
输出：3

用例2：
输入：[1, 1, 5, 1, 5, 2, 4, 4]
输出：2

"""5键键盘的输出"""def five_key_board(opts: list):""""""output = ""select = ""backup = ""for n in opts:if n == 1:if select:output = ""select = ""output += "a"if n == 2:if not select:continuebackup = selectif n == 3:if not select:continuebackup = selectoutput = ""if n == 4:if select:output = ""select = ""output += backupif n == 5:if not output:continueselect = outputreturn len(output)opts = [1, 1, 5, 1, 5, 2, 4, 4]
result = five_key_board(opts)
print(result)

4.单词重量

题目描述：
每个句子由多个单词组成，句子中的每个单词的长度都可能不一样，我们假设每个单词的长度Ni为该单词的重量，你需要做的就是给出整个句子的平均重量V。

输入描述:
无

输出描述:
无

用例1：
输入：“Who Love Solo”
输出：3.67

"""单词重量"""def word_weight(s: str):""""""words = s.split()words_len = len(words)all_w = 0for word in words:all_w += len(word)result = round(all_w / words_len, 2)return results = "Who Love Solo"
result = word_weight(s)
print(result)

5.输出指定字母在字符串的中的索引

题目描述：
给定一个字符串，把字符串按照大写在前小写在后排序，输出排好后的第 K 个字母在原来字符串的索引。
相同字母输出第一个出现的位置。

输入描述:
无

输出描述:
无

用例1：
输入：hAkDAjByBq
4
输出：6

"""输出指定字母在字符串的中的索引"""def output_index(s: str, k: int):""""""new_s = sorted(s)s_len = len(s)for i in range(s_len):if s[i] == new_s[k-1]:return is = "hAkDAjByBq"
k = 4
result = output_index(s, k)
print(result)

6.污染水域

题目描述：
输入一行字符串，字符串可转换为N*N的数组，数组可认为是一个水域，判断多少天后，水域被全部污染。
数组中只有0和1，0表示纯净，1表示污染，每天只可污染上下左右的水域，如果开始全部被污染，或永远无法污染，则返回-1。

输入描述:
无

输出描述:
无

用例1：
输入：[[1,0,1], [0,0,0], [1,0,1]]
输出：2

用例2：
输入：[[0,0], [0,0]]
输出：-1

"""污染水域"""def pollute_water(nums: list):""""""polluted = []nums_len = len(nums)for x in range(nums_len):for y in range(nums_len):if nums[x][y] == 0:continuepolluted.append((x, y))if not polluted or len(polluted) == nums_len * nums_len:return -1def operate():polluted_len = len(polluted)for i in range(polluted_len):x = polluted[i][0]y = polluted[i][1]if x - 1 >= 0 and (x - 1, y) not in polluted:polluted.append((x - 1, y))if x + 1 < nums_len and (x + 1, y) not in polluted:polluted.append((x + 1, y))if y - 1 >= 0 and (x, y - 1) not in polluted:polluted.append((x, y - 1))if y + 1 < nums_len and (x, y + 1) not in polluted:polluted.append((x, y + 1))day = 1while True:operate()if len(polluted) == nums_len * nums_len:return dayday += 1nums = [[1, 0, 1],[0, 0, 0],[1, 0, 1],
]
result = pollute_water(nums)
print(result)

7.九宫格按键输入

题目描述：
九宫格按键输入，输出显示内容，有英文和数字两个模式，默认是数字模式，数字模式直接输出数字，英文模式连续按同一个按键会依次出现这个按键上的字母，如果输入”/”或者其他字符，则循环中断。
字符对应关系如图：
1: ,.
2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz
#:
0: 空格
/:
要求输入一串按键，输出屏幕显示。

输入描述:
输入范围为数字 0~9 和字符’#’、’/’，输出屏幕显示，例如，
在数字模式下，输入 1234，显示 1234
在英文模式下，输入 1234，显示 ,adg

输出描述:
#用于切换模式，默认是数字模式，执行#后切换为英文模式；
/表示延迟，例如在英文模式下，输入 22/222，显示为 bc；
英文模式下，多次按同一键，例如输入 22222，显示为 b；

用例1：
输入：“123#222235/56”
输出：“123adjjm”

"""九宫格按键输入"""def nine_key_input(s: str):""""""nums_dict = {"1": ",.","2": "abc","3": "def","4": "ghi","5": "jkl","6": "mno","7": "pqrs","8": "tuv","9": "wxyz","#": "","0": "空格","/": "",}num_mode = Truenum_index = ["-1", 0]output = []s_len = len(s)for i in range(s_len):if s[i] == "/":num_index = ["-1", 0]continueif s[i] == "#":num_mode = Falsecontinueif num_mode:output.append(s[i])num_index = ["-1", 0]continueif s[i] == "0":output.append(" ")continueif s[i] == num_index[0]:s_i_len = len(nums_dict[s[i]])if num_index[1] + 1 == s_i_len:num_index[1] = 0else:num_index[1] += 1output[-1] = nums_dict[s[i]][num_index[1]]continueoutput.append(nums_dict[s[i]][0])num_index = [s[i], 0]result = "".join(output)return results = "123#222235/56"
result = nine_key_input(s)
print(result)

8.任务最优调度

题目描述：
给定一个正整数数组表示待系统执行的任务列表，数组的每一个元素代表一个任务，元素的值表示该任务的类型。
请计算执行完所有任务所需的最短时间。
任务执行规则如下:
1.任务可以按任意顺序执行，且每个任务执行耗时间均为1个时间单位。
2.两个同类型的任务之间必须有长度为N个单位的冷却时间，比如N为2时，在时间K执行了类型3的任务，那么K+1和K+2两个时间不能执行类型3任务。
3.系统在任何一个单位时间内都可以执行一个任务，或者等待状态。
说明：数组最大长度为1000，数组最大值1000。

输入描述:
1.第一行记录一个用半角逗号分隔的数组，数组长度不超过1000，数组元素的值不超过1000，
2.第二行记录任务冷却时间，N为正整数，N<=100。

输出描述:
输出为执行完所有任务所需的最短时间。

用例1：
输入：[2, 2, 2, 3]
2
输出：7

"""任务最优调度"""def task_optimal_solution(nums: list, n: int):""""""nums_len = len(nums)min_time = 0task = 1task_seq = []while task <= nums_len:add_time_min = -1task_index = 0for i in range(nums_len):if i in task_seq:continuetask_seq_len = len(task_seq)for j in range(-1, -n-1, -1):if -j > task_seq_len:continueif nums[i] == nums[task_seq[j]]:add_time = 1 + n + j + 1breakelse:add_time = 1if add_time_min == -1 or add_time < add_time_min:add_time_min = add_timetask_index = imin_time += add_time_mintask_seq.append(task_index)task += 1return min_timenums = [2, 2, 2, 3]
n = 2
result = task_optimal_solution(nums, n)
print(result)

9.高效的任务规划

题目描述：
你有 n 台机器，编号为 1~n，每台都需要完成一项工作，机器经过配置后都能独立完成一项工作。
假设第 i 台机器你需要花 Bi 分钟进行设置，然后开始运行，Ji 分钟后完成任务。
现在，你需要选择布置工作的顺序，使得用最短的时间完成所有工作。
注意，不能同时对两台进行配置，但配置完成的机器们可以同时执行他们各自的工作。

输入描述:
第一行输入代表总共有 M 组任务数据（1<M<=10）。
每组数第一行为一个整数指定机器的数量 N（0<N<=1000）。随后的 N 行每行两个整数，第一个表示 B（0<=B<=10000），第二个表示 J（0<=J<=10000）。
每组数据连续输入，不会用空行分隔。各组任务单独计时。

输出描述:
对于每组任务，输出最短完成时间。

用例1：
输入：1
1
2 2
输出：4

用例2：
输入：1
3
1 1
2 2
3 3
输出：7

"""高效的任务规划"""def optimal_task_plan(n: list):""""""n_len = len(n)machine = 1machine_seq = []all_config_time = 0min_time = 0while machine <= 2:config_time = -1machine_ind = 0max_run_time = -1for i in range(n_len):if i in machine_seq:continuerun_time = n[i][1]if max_run_time == -1 or run_time > max_run_time:max_run_time = run_timeconfig_time = n[i][0]machine_ind = imachine_seq.append(machine_ind)all_config_time += config_timemin_time = max(min_time, all_config_time + max_run_time)machine += 1return min_timen = [(1, 1), (2, 2), (3, 3)]
result = optimal_task_plan(n)
print(result)