前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【打卡贴】(No.006)从零开始刷LeetCode

【打卡贴】(No.006)从零开始刷LeetCode

作者头像
PM小王
发布2019-07-01 14:52:11
3330
发布2019-07-01 14:52:11
举报
文章被收录于专栏:程序员小王

NO.6 Z字形变换

原题:

将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数:

代码语言:javascript
复制
P   A   H   N
A P L S I I G
Y   I   R

之后从左往右,逐行读取字符:"PAHNAPLSIIGYIR"

实现一个将字符串进行指定行数变换的函数:

代码语言:javascript
复制
string convert(string s, int numRows);

示例 1:

代码语言:javascript
复制
输入: s = "PAYPALISHIRING", numRows = 3输出: "PAHNAPLSIIGYIR"

示例 2:

代码语言:javascript
复制
输入: s = "PAYPALISHIRING", numRows = 4输出: "PINALSIGYAHRPI"解释:P     I    N
A   L S  I G
Y A   H R
P     I

除了第一行和最后一行没有中间形成之字型的数字外,其他都有,而首位两行中相邻两个元素的index之差跟行数是相关的,为 2*nRows - 2, 根据这个特点,我们可以按顺序找到所有的黑色元素在元字符串的位置,将他们按顺序加到新字符串里面。对于红色元素出现的位置也是有规律的,每个红色元素的位置为 j + 2*nRows-2 - 2*i, 其中,j为前一个黑色元素的列数,i为当前行数。 比如当n = 4中的那个红色5,它的位置为 1 + 2*4-2 - 2*1 = 5,为原字符串的正确位置。当我们知道所有黑色元素和红色元素位置的正确算法,我们就可以一次性的把它们按顺序都加到新的字符串里面。

代码语言:javascript
复制
def convert(self, s, numRows):
    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): 
        for j in range(i, str_length, node_length):
            # 第一行和最后一行
            还有普通行的整列数字
            result += s[j]  
            if i != 0 and i != numRows - 1 and \
              j - 2 * i + node_length < str_length:
                # 单列行的数字
                result += s[j - 2 * i + node_length]  
    return result
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-10-02,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

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