【刷题记录】6. Z 字形变换

作者：WangNing

2022 年 7 月 10 日
本文字数：991 字
阅读完需：约 3 分钟

一、题目描述

来源：力扣（LeetCode）

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"解释：

解释：P     I    NA   L S  I GY A   H RP     I

复制代码

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

二、思路分析

0.0 Z 形变换应该叫 И 形变换
从题目来看原字符串是 Z 形的排列顺序
输出结果其实就是从第一行(S1)到第 n 行(Sn)的 n 个子串拼接.
我们只要按定义 N 个子串按顺序遍历 Z 形字符串把每个字符放入到对应行的子串记录中即可
行是从 1-numRows 然后 numRows-1，即是该字符属于第几行子串的规律

如上面的例子 2

解释：P     I    N  ---s1 = pinA   L S  I G  ---s2 = alsinY A   H R     ---s3 = yanrP     I       ---s4 = pi

复制代码

三、代码实现

class Solution {    public String convert(String s, int numRows) {        if(numRows < 2) return s;        List<StringBuilder> rows = new ArrayList<StringBuilder>(); //子串集合
        StringBuilder res = new StringBuilder();        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());        int i = 0;   //正向的时候的该字符所在行数        int m = -1;  //用于行数变化 正向+1 反向-1        for(char c : s.toCharArray()) {            rows.get(i).append(c);            if(i == 0 || i == numRows -1){                m = - m;            }            i += m;        }        for(StringBuilder row : rows) res.append(row);        return res.toString();    }}

复制代码

复杂度分析：

时间复杂度： $O (N)$ 遍历一遍字符串 s；
空间复杂度： $O (N)$ N 为字符串长度

运行结果

总结

这种模拟题最主要的还是要多找出来规律，找出相应的规律，然后转化为数学问题，就比较容易解决了。

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/cba37a43b88b662e4e6450b27】。

WangNing

关注

还未添加个人签名 2020.10.13 加入

一个只想提(快)升(乐)自(摸)我(鱼)的混子选手～

发布

暂无评论

创作场景

【刷题记录】6. Z 字形变换

一、题目描述

二、思路分析

三、代码实现

复杂度分析：

运行结果

总结

WangNing

评论