自顶向下逐步求精解决LeetCode第3307题找出第K个字符II题

3307.找出第K个字符II

难度：困难

问题描述：

Alice和Bob正在玩一个游戏。最初，Alice有一个字符串word="a"。

给定一个正整数k和一个整数数组operations，其中operations[i]表示第i次操作的类型。

现在Bob将要求Alice按顺序执行所有操作：

如果operations[i]==0，将word的一份副本追加到它自身。

如果operations[i]==1，将word中的每个字符更改为英文字母表中的下一个字符来生成一个新字符串，并将其追加到原始的word。例如，对"c"进行操作生成"cd"，对"zb"进行操作生成"zbac"。

在执行所有操作后，返回word中第k个字符的值。

注意，在第二种类型的操作中，字符'z'可以变成'a'。

示例1:

输入：k=5,operations=[0,0,0]

输出："a"

解释：

最初，word=="a"。Alice按以下方式执行三次操作：

将"a"附加到"a"，word变为"aa"。

将"aa"附加到"aa"，word变为"aaaa"。

将"aaaa"附加到"aaaa"，word变为"aaaaaaaa"。

示例2:

输入：k=10,operations=[0,1,0,1]

输出："b"

解释：

最初，word=="a"。Alice按以下方式执行四次操作：

将"a"附加到"a"，word变为"aa"。

将"bb"附加到"aa"，word变为"aabb"。

将"aabb"附加到"aabb"，word变为"aabbaabb"。

将"bbccbbcc"附加到"aabbaabb"，word变为"aabbaabbbbccbbcc"。

提示：

1<=k<=1014

1<=operations.length<=100

operations[i]可以是0或1。

输入保证在执行所有操作后，word至少有k个字符。

问题分析及解答思路：

根据题目的描述，要找到经过数组operations的多次操作之后，所形成字符串中的第K个字符，那么就要知道每一次的操作如何进行，然后利用数组operations中的操作指令，循环操作处理即可得到最后形成的字符串，进而找到问题求解。每一次的操作又根据数组operations中的指令是0还是1有不同的处理，其中指令为0的处理较为简单，而指令为1的操作复杂，是对一个字符串中的每个字符取下一个字符进行替换，所以这就转换为对一个字符，如何转换为下一个字符的问题，可以看到出来，这是一个自顶向下，逐步求精的过程。

解决方案：

函数changeC(c)，功能为将一个小写英文字符c转换为英文字母表中的下一个字母
函数change(s)，功能为将一个英文字符串s中每一个字母转换为下一个字母
函数solution(s,flag)，功能为将一个英文字符串s根据flag指令是0还是1，决定生成一个新的字符串并附加到原字符串尾部
函数endSolution(s,k,operations)，功能为将字符串s按operations中的指令循环进行字符串处理，并返回最后生成的字符串和其中的第k个字符

程序如下：

#对一个字符按规则进行变化，并返回变化后的字符
def changeC(c):
    c=(ord(c)-96+1)%26+96
    return chr(c)

#根据原字符串s按规则变化成新的字符串并返回
def change(s):
    a=[]
    for i in s:
        a.append(changeC(i))
    return(''.join(a))

#对于给定的字符串，根据flag是0还是1生成新的字符串并返回
def solution(s,flag):
    if flag==0:
        return s+s
    else:
        return s+change(s)

#对于给定的s，经过operations中的处理之后，返回第k个字符
def endSolution(s,k,operations):
    for flag in operations:
        s=solution(s,flag)
    return s,s[k-1]

k=int(input('pls input k='))
operations=eval(input('pls input operations='))
print('最后生成字符串：',endSolution('a',k,operations)[0])
print(f'第{k}个字符为：',endSolution('a',k,operations)[1])

运行实例一

pls input k=3

pls input operations=[1,0,1]

最后生成字符串： ababbcbc

第3个字符为： a

运行实例二

pls input k=10

pls input operations=[0,1,0,1]

最后生成字符串： aabbaabbbbccbbcc

第10个字符为： b

感悟：

自顶向下，逐步求精是一种重要的算法思想。能帮助理清思路，化繁为简，有利于问题的解决。

秒客网