848. Shifting Letters

https://leetcode.com/problems/shifting-letters/

题目解释

你有一个字串都是小写的字串s ，还有一组偏移(shift)次数的阵列shifts

一次的shift 会将字母往下一个顺序偏移，如 shift('a') = 'b', shift('t') = 'u', shift('z') = 'a'

而阵列shifts[i] = x 代表我们要将字串s 的前i+1 个字母偏移x 次

example

解法:

1. 首先，这题要把字母做变化的话，用ASCII的代码做计算应该是最方便的

2. 再来，我们要计算各个字母需要偏移几次，如example1 的a 是17次、b 是14次、c 是9次

3. 最後，我们计算字串s的每个字母，记录他已经从字母a 偏移几次了，如a 偏移0次、b偏移1次、c偏移2次，这样比较方便计算

4. 最後的最後，我们就得到Time Limit Exceeded 的程序码

程序码

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        
        s_int = [ord(i) - 97 for i in s] #记录从字母*a* 偏移几次了
        
        shifts_sum = [sum(shifts[i:]) for i in range(len(shifts))] # 计算各个字母需要偏移几次
        
        res = ''
        for i in range(len(s)):
            res += chr(97 + (s_int[i] + shifts_sum[i]) % 26) #别忘了modulo 26
            
        return res

可以过得解法:

LeetCode的很多题目若送出O(n^2)的解答通常就不会过

而上段程序码的shifts_sum = [sum(shifts[i:]) for i in range(len(shifts))] 就是太花时间的原因，所以我们稍微改一下第二步的想法

example1 的a 要偏移17次，也就是3 + 5 + 9次
example1 的b 要偏移 8次，也就是 5 + 9次
example1 的c 要偏移 9次，也就是 9次

依照上面的规律，我们只需要先把shifts 做加总，再一项一项扣除掉不需要的次数就好

程序码

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        
        s_int = [ord(i) - 97 for i in s]
        
        shifts_sum = sum(shifts)

        res = ''
        for i in range(len(s)):
            res += chr(97 + (s_int[i] + shifts_sum) % 26)
            shifts_sum -= shifts[i]
            
        return res

闲聊

今天的题目是难度Medium 的题目，写起来不会很难

就只要多想一下怎麽避免回圈包住回圈的解法而已

今天是第8天，恭喜我自己完成一周的进度罗!