[LeetCode Weekly Contest 88]848. 字母移位
原创[LeetCode Weekly Contest 88]848. 字母移位
原创
早上参加了leetcode的周赛，好久没有比过赛，很多细节没有第一时间考虑到，AC了前两道题目，第三道题目超时，第四道没时间做了。在这里给大家展示一下题目和我的解法。
题目描述：
848. 字母移位
有一个由小写字母组成的字符串 S，和一个整数数组 shifts。
我们将字母表中的下一个字母称为原字母的 移位（由于字母表是环绕的， 'z' 将会变成 'a'）。
例如·，shift('a') = 'b'， shift('t') = 'u',， 以及 shift('z') = 'a'。
对于每个 shifts[i] = x ， 我们会将 S 中的前 i+1 个字母移位 x 次。
返回将所有这些移位都应用到 S 后最终得到的字符串。
示例：
输入：S = "abc", shifts = [3,5,9]
输出："rpl"
解释：
我们以 "abc" 开始。
将 S 中的第 1 个字母移位 3 次后，我们得到 "dbc"。
再将 S 中的前 2 个字母移位 5 次后，我们得到 "igc"。
最后将 S 中的这 3 个字母移位 9 次后，我们得到答案 "rpl"。提示：
1 <= S.length = shifts.length <= 200000 <= shifts[i] <= 10 ^ 9
分析
一开始用的是二重循环，即对第n个shift项step，前n个字母移位step次，但是会超时。
经分析，第一个字母总共移位sum(shifts)次，第二个字母少移位shifts[0]次，所以先逆序shifts数组，再求一个steps数组，第n项是shifts数组前n项和，再逆序一次，steps数组的每一项就对应着每一个字母的移位次数，再对26取模就可以了。
例如对于shifts数组[3, 5, 9],逆序得到[9, 5, 3],steps数组为[9, 14, 17]，再逆序得到[17, 14, 9]，分别对应着'a', 'b', 'c'的移位次数。
代码
一如既往的用Python实现。
class Solution:
def shiftingLetters(self, S, shifts):
"""
:type S: str
:type shifts: List[int]
:rtype: str
"""
chars = {x:chr(ord('a') + x) for x in range(0, 26)}
steps = [0] * len(shifts)
shifts = list(reversed(shifts))
for index in range(len(steps)):
steps[index] = (shifts[index] + steps[index - 1]) % 26 if index else shifts[index] % 26
steps = list(reversed(steps))
ans = list(S)
for index in range(len(ans)):
ans[index] = chars[(ord(ans[index])
- ord('a') + steps[index]) % 26]
return ''.join(ans)结语
这个题目给我们的教训是优先考虑是否能在O(n)的时间复杂度内解决问题，双重循环还是会慢很多的。
最后祝大家享受生活， 享受代码。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。