早上参加了leetcode的周赛,好久没有比过赛,很多细节没有第一时间考虑到,AC了前两道题目,第三道题目超时,第四道没时间做了。在这里给大家展示一下题目和我的解法。
有一个由小写字母组成的字符串 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 <= 20000
0 <= 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 删除。