[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. 1 <= S.length = shifts.length <= 20000
  2. 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)的时间复杂度内解决问题,双重循环还是会慢很多的。

最后祝大家享受生活, 享受代码。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端开发

javascript逻辑运算符“||”和“&&”

1814
来自专栏C/C++基础

统计无符号整数二进制中1的个数(Hamming weight)

之所以来记录这个问题的解法,是因为在在线编程中经常遇到,比如编程之美和京东的校招笔试以及很多其他公司都累此不疲的出这个考题。看似简单的问题,背后却隐藏着很多精妙...

1322
来自专栏take time, save time

你所能用到的BMP格式介绍(二)

一、可能你忽视的基础         在正式开始之前,我不得不从最基本的地方开始,因为这些地方大多数人会忽视的一干二净,如果不在开始进行说明,那么在后面一定会有...

2857
来自专栏chenjx85的技术专栏

leetcode-137-Single Number II-第二种解法

2.8K12
来自专栏阿凯的Excel

让你眼花缭乱的匹配函数反查技巧

小编已经连续写了三期关于匹配函数的用法,匹配函数的扛把子(老大)肯定是Vlookup函数莫属,但是Vlookup函数有一个问题,就是要查找的内容,必须在查找内容...

2896
来自专栏带你撸出一手好代码

从PHP代码的细节说起

因为一个BUG, 我在一个摇摇欲坠,几乎碰一下就会散架的项目中某一个角落中发现下面这样一段代码 ? 这段程序与那个BUG有密切的关系。 我来回反复的捉摸这段代码...

3907
来自专栏Python中文社区

Python如何传递运算表达式

正小歪,Python 工程师,主要负责 Web 开发和日志数据处理。博客文章《真正的 Tornado 异步非阻塞》、《使用 JWT 让你的 RESTful AP...

1001
来自专栏IMWeb前端团队

简洁的javascript编码(一)--变量、函数

本文作者:IMWeb jaychen 原文出处:IMWeb社区 未经同意,禁止转载 ? 一、变量 使用语义化的变量名称 Bad cons...

2349
来自专栏数说工作室

【SAS Says】基础篇:3. 描述数据

本节介绍如何利用SAS写一份数据报告,给出数据的基本信息。 从3.11开始的内容,是留给处女座的,主要说如何用proc tabulate和proc report...

31410
来自专栏九彩拼盘的叨叨叨

如何给函数取个合适的名字

Quora 和 Ubuntu Forums thread 上的 4500 个程序员对上面的问题进行投票。49%的程序员认为给函数,变量等命名是最难的任务。

622

扫码关注云+社区