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

相关文章

来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

6868
来自专栏跟着阿笨一起玩NET

c#实现打印功能

2792
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.2K7
来自专栏大内老A

The .NET of Tomorrow

Ed Charbeneau(http://developer.telerik.com/featured/the-net-of-tomorrow/) Exciti...

31810
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

2717
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3145
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5486
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2645
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2587
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5327

扫码关注云+社区