前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode刷题实战6:Z字形变换

LeetCode刷题实战6:Z字形变换

作者头像
程序员小猿
发布2021-01-19 12:26:25
2500
发布2021-01-19 12:26:25
举报
文章被收录于专栏:程序IT圈程序IT圈

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 Z字形变换 ,这道题很有意思,我们先来看题面:

题意

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) https://leetcode.com/problems/zigzag-conversion/

翻译

给定一个字符串,将它变成蛇形输出。这个蛇形的概念比较抽象,我们需要结合样例才能理解。

样例

P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);
Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

分析

这题的题意有点鬼畜,意思是说将给定的字符串先按照蛇形排列好,然后再按行依次读入,最后输出新的字符串。

虽然LeetCode上给这题的难度是Medium,但实际上它还是比较简单的。和上一题的曼切斯特算法比起来,算得上是很简单的了。LeetCode 5 迅速判断回文串的曼切斯特算法

这题会告诉我们字符串以及蛇形扭曲的行数,将字符串排成蛇形。这种没有任何算法或者数据结构,仅仅是实现题意的问题称为模拟题。显然今天的这一题就是一道模拟题。模拟题唯一的难度就是编码,实现一些比较复杂的功能,考验的其实是工程能力。

这个蛇形的排列也很简单,因为我们只要输出最后的按行连接的结果。所以我们完全可以忽略列的位置信息,只用关注摆放的行就好了。因为行数是有限的,对于每一行,我们可以用一个字符串记录当前行目前为止摆放的字符串,最后按照行的顺序将所有行的结果连接到一起就好了。通过观察,我们很容易发现,摆放的行是有周期规律的。一个周期是2 * rowJum - 2,从0先递增到rowNum - 1,再递减到1。

发现规律之后,再写出code就不难了。

def convert(text, numRows):
    # 记录每一行结果的dict
    lines = {}
    if numRows == 0:
        return text

    for i in range(len(text)):
        # 计算应该放在哪一行
        idx = i % (2 * numRows - 2)
        # 判断是在递增区间还是递减区间
        if idx >= numRows:
            idx = 2 * numRows - 2 - idx

        line = lines.get(idx, "")
        lines[numRows] = line + text[i]

    result = ""
    # 拼接答案
    for i in range(numRows):
        result += lines[i]
    return result

上面的代码很简单,但是藏着一个可以优化的地方。

在于dict的使用,dict的查询需要开销。其实我们可以替换成数组,因为我们已经确定行数了,所以数组的长度是固定的。如此优化之后,时间效率会更高一点。但是差别不会很大,代码就不放了,我想大家应该都能想明白。

今天的文章就到这里,如果觉得有所收获,请点个在看或者转发吧。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-08-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员小猿 微信公众号,前往查看

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

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档