LeetCodeHot100-第六题-Z字形变换-找规律

6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：

示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
</pre>

示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
</pre>

示例 3：
输入：s = "A", numRows = 1
输出："A"</pre>

理解题意：

就是一个字符串我们要给他顺序排列为Z字形，然后顺时针旋转90度（实际上就是N，题目应该变成N形变换）

思路：

其实N形是有规律的，左边是4行（numRows = 4），右边是3行（numRows = 3），每个元素在第几行可以用取余来对其判断。
对几取余：
可以将元素分组，每组为v字形，如:012345就是一组。那么取余就很简单了，i对6取余（6 = 2numRows - 2），不难看出中间斜着的部分比numRows少了两个位置。
取余取出来了，那么怎样判断他在哪行呢：
余数小于numRows的肯定就在余数行，大于等于的另外判断。比如4，它在第二行，numRows - 1 - ( i - (numRows - 1)) ==> 2numRows - 2 - i。
2*4 - 2 - 4 = 2，4就在第二行。

最后，每遍历一次我们就取出一行数据，遍历numRows次字符串就可以，时间复杂度O(n * numRows)

image.png

代码实现

    class Solution {
        public String convert(String s, int numRows) {
            if(numRows < 2) return s;

            int n = 2 * numRows - 2;
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < numRows; i++) {
                for (int j = 0; j < s.length(); j++) {
                    //得到余数，通过余数能得到在第几行
                    int k = j % n;
                    if (k > numRows - 1) {
                        k = numRows - 1  - (k - (numRows - 1));
                    }
                    if (k == i) {
                        stringBuilder.append(s.charAt(j));
                    }
                }
            }

            return String.valueOf(stringBuilder);
        }
    }

缺点：时间复杂度很高

image.png