拿什么拯救你,我的offer!(从零打卡刷Leetcode——No.006)

写在前边:

小詹此记录贴的读者越来越少了,也许是小詹总结的不够好欢迎留言区提出宝贵的意见!也欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!


No.6 Z字型变换

原题:(有中文网站,就不去读英语啦哈哈)

将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数,之后从左往右,逐行读取字符:"PAHNAPLSIIGYIR"实现一个将字符串进行指定行数变换的函数:

例如:

输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"
解释:
P     I    N
A   L S  I G
Y A   H R
P     I

题目大意:首先"Z字型"要能够看出来其具体走向,为了便于小伙伴理解题意,将字符串改为顺序的字符,方便理解。如下排列后要按照逐行输出(如下则为AGBFHLCEIKDJ)


题目分析:看到这种题目,必须先找规律,就像本科c语言学习过程一样。小詹首先找到两列的规律,在纸上一顿乱画……然后发现:第一行比较具有代表性,其他行可以通过第一行加减得到,而第一行相邻两列之间相隔为2*numRows-2,下面就以numRows分别为3和4为例,画出来方便小伙伴理解(字丑人帅噢)

得到了这就可以往下继续思考了~我们可以依次打印出每一行,第一行简单,字符串的索引符合2*numRows-2的整数倍即可。之后只用依次加上行数或者减去行数即可,例如i表示第几行(为方便,从0开始,第0行、1行…i行…)。这里提供一种取模的方法(可以理解成余数)。这里得观察到首末两行比较简单,字符在字符串中对应索引除以2*numRows-2模为0或者numRows-1;中间若干行,要多出一种情况,取模为i(从上往下箭头方向)或者2*numRows-2-i(从下往上箭头方向)。

于是我们可以逐行输出,第一层循环为遍历所有行,第二层循环遍历所有符合对应行的字符。代码和注释如下:

class Solution:
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        n = numRows
        #开始小詹是利用列表保存,然后得到结果
        #再将其转换为字符串的,这里定义空的列表
        res_list = []
        l = len(s)
        #考虑到极端情况,其实这里小詹还是没有考虑全
        #除了一行,还应该考虑到单字符串或者空字符串
        if n == 1:
            return s
        #遍历0到n-1行
        for i  in range(n):
            #遍历所有字符,j表示索引
            for j in range(l):
                #这是就是小詹介绍的取模判断是否在第i行输出
                if j%(2*n-2) == i or j%(2*n-2) == 2*n-2-i:
                    res_list.append(s[j])
        #这里就是利用join将列表转换为字符串
        res = "".join(res_list)
        return res

是不是觉得很简单?不,超时了你敢信,虽然执行出得到了正确结果,但是提交显示超时!分析下,做了哪些无用的计算呢?这里注意到for j in range(l):遍历了所有的索引,但是事实上是有规律可循的,并不需要暴力遍历所有。代码

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        str_length = len(s)
        node_length = 2*numRows - 2  # 两列之间的差
        #其实并不需要第一种方法那样列表字符串来回折腾。。。
        result = ""
        #极端特殊情况,直接返回原字符串
        if str_length == 0 or numRows == 0 or numRows == 1:
            return s
        # 从第一行遍历到最后一行
        for i in range(numRows): 
            #大的改进在这里!!!不再逐一遍历,而相当于j += node_length
            for j in range(i, str_length, node_length):
                # 第一行和最后一行  还有普通行的整列数字
                result += s[j]  
                #不是第一行和最后一行,且不说普通垂直的时,j-*i+node_length得到第i行斜着的那部分需输出的字符
                if i != 0 and i != numRows-1 and j - 2*i + node_length < str_length:
                    result += s[j-2*i+node_length]  # 单列行的数字
        return result

到这就得到了可以通过的正确解答了,写文章比做题还耗时……感兴趣的小伙伴可以提交try一下噢!

往期推荐

【记录帖】(No.001)从零打卡刷Leetcode

【记录帖】(No.002)从零打卡刷Leetcode

【记录帖】(No.003)从零打卡刷Leetcode

【记录帖】(No.004)从零打卡刷Leetcode

【记录帖】(No.005)从零打卡刷Leetcode

原文发布于微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文发表时间:2018-06-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术沉淀

Pandas雅虎金融数据获取与分析

利用Pandas模块直接获取雅虎财经数据,方便之极。注意把官方提示把from pandas.io import data, wb替换为from pandas_d...

51230
来自专栏量化投资与机器学习

【精心解读】用pandas处理大数据——节省90%内存消耗的小贴士

本文我们讨论 pandas 的内存使用,展示怎样简单地为数据列选择合适的数据类型,就能够减少 dataframe 近 90% 的内存占用。

1.8K50
来自专栏小樱的经验随笔

UESTC 1599 wtmsb【优先队列+排序】

题目链接:UESTC 1599 wtmsb 题意:给你一组数,每一次取出两个最小的数,将这两个数的和放入这组数中,直到这组数只剩下一个,求最后剩下那个数的大小!...

28260
来自专栏阿凯的Excel

文本数字拆分技巧(第二弹!)

上期刚刚分享了简单的通过智能填充和Len与LenB函数实现的文本数字拆分! 感兴趣可以点我先看上一期的! 本期难度较上期略有提高,和您分享新的技巧。 ? 没...

30970
来自专栏数说工作室

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

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

389100
来自专栏牛客网

头条实习面经

【每日一语】真实人生中,我们往往在大势底定无可更改时才迟迟进场,却又在胜败未分的浑沌中提早离席。——翁贝托·埃科《开头与结尾》

13920
来自专栏desperate633

[编程题] 猜数游戏分析代码

首先我们分析,dp[i]表示前i个数的合法个数 当第i个数是素数的时候,前面除了1都没有能除尽的,所以这个位置可以随便选Y或N,所以dp[i] = dp[i-...

12630
来自专栏猿人谷

oc 中随机数的用法(arc4random() 、random()、CCRANDOM_0_1()

1)、arc4random() 比较精确不需要生成随即种子        使用方法 :                  通过arc4random() 获取0到...

26180
来自专栏潇涧技术专栏

Python Algorithms - C6 Divide and Combine and Conquer

Python算法设计篇(6) Chapter 6: Divide and Combine and Conquer

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

PTA 7-2 列车调度(25 分)

7-2 列车调度(25 分) 火车站的列车调度铁轨的结构如下图所示。 ? 两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平...

36590

扫码关注云+社区

领取腾讯云代金券