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

一、题目描述

来源：力扣（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    N

A   L S  I G

Y A   H R

P     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 = pin

A   L S  I G  ---s2 = alsin

Y A   H R     ---s3 = yanr

P     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();
    }
}

复杂度分析：

• 时间复杂度：
  网络异常，图片无法展示

  |
  遍历一遍字符串 s；
• 空间复杂度：
  网络异常，图片无法展示

  |
  N为字符串长度

运行结果

总结

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