[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 条评论
登录 后参与评论

相关文章

来自专栏IT派

使用 Pandas 处理亿级数据

在数据分析领域,最热门的莫过于Python和R语言,此前有一篇文章《别老扯什么Hadoop了,你的数据根本不够大》指出:只有在超过5TB数据量的规模下,Hado...

1034
来自专栏HansBug's Lab

3038: 上帝造题的七分钟2

3038: 上帝造题的七分钟2 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 662  Solved: 302...

2644
来自专栏walterlv - 吕毅的博客

.NET 中 GetProcess 相关方法的性能

2018-08-19 07:04

553
来自专栏技术碎碎念

windows API 开发飞机订票系统 图形化界面 (四)

接下来的是录入航班、修改航班信息功能的实现: 1 //录入航班 2 BOOL EntryFlight(HWND hEntryDlg){ 3 4 ...

2715
来自专栏数据科学与人工智能

【Python环境】使用Python Pandas处理亿级数据

在数据分析领域,最热门的莫过于Python和R语言,此前有一篇文章《别老扯什么Hadoop了,你的数据根本不够大》指出:只有在超过5TB数据量的规模下,Hado...

2735
来自专栏HansBug's Lab

3409: [Usaco2009 Oct]Barn Echoes 牛棚回声

3409: [Usaco2009 Oct]Barn Echoes 牛棚回声 Time Limit: 3 Sec  Memory Limit: 128 MB Su...

2397
来自专栏海天一树

Codeforces 977D 题解报告

http://codeforces.com/contest/977/problem/D

652
来自专栏FreeBuf

苹果OS X Yosemite系统曝多个本地提权漏洞

国外安全研究人员近日曝光最新版Mac OSX 10.10.1系统上存在多处本地提权漏洞,由于提交到苹果官方时间太久都过未得到明确答复,导致研究者直接公布漏洞细节...

17010
来自专栏数据结构与算法

Day3上午解题报告

预计分数:100+40+50=190 实际分数:100+40+50=190 T1 https://www.luogu.org/problem/show?pid=...

2645
来自专栏杨建荣的学习笔记

关于奇怪的并行进程分析(二) (r6笔记第46天)

前几天的并行问题自己分析了下,也算有了一些进展,但是目前还没有找到让人信服的理由,有些读者也比较关心这个问题,所以第二篇中会把自己的分析过程写出来,第三篇中应该...

2533

扫码关注云+社区