题目
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：
L C I RE T O E S I I G E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例
输入: s = “LEETCODEISHIRING”, numRows = 4
输出: “LDREOEIIECIHNTSG”
解释:
L D R E O E I I E C I H N T S G
分析
方法一：
假如 s = “PAYPALISHIRING”, numRows = 4 (括号里的数字代表这个字符在该字符串的位置）
首先可以确定的是中间斜着的行数（也就是每两个竖列之间的间隔）是gap = numRows - 2 =2
观察可以发现：
第一行和最后一行都是每隔6位取一位 通过观察 ，可以通过（numRows-1）+gap+1得到 其实就是竖着的4个（因为下标从0开始计算，所以应该减一） 加上两个斜着的（gap) 再加上另一列上的1（语言表达能力不太好，希望大家可以看的懂。。。。。） 这样可以计算出首行和尾行的间隔，将这个间隔设为k1，k1 = 6
第二行是1，5，7，11，13 间隔是 +4 +2 +4 +2 … 这个可以两个看作一组，4就是 k2 = k1-i*2 = k1-2 (这里的i是指行数，从0开始计算） ，2可以看作 k1 - k2
第三行是2，4，8，10 间隔是 +2 +4 +2 +4 同样，2是k2 = k1 - i*2 = k1 -4 ，4位k1-k2
验证上面的规律：
s= “PAYPALISHIRING” , numRows = 3 (括号里的数字代表这个字符在该字符串的位置）
gap = numRows - 2 =1
第一行和最后一行都是每隔4位取一位 k1 = （numRows-1）+gap+1 = 3-1+1+1 = 4
第二行是1，3，5，7，9 每次位数增加2 i = 1, +2 +2 +2 +2… k2 = k1-i*2 = k1-2 = 4-2 = 2 后面就可以直接用 k1-k2 然后每次更新k2即可
如果不放心 ，可以另取一个numRows较大的字符串进行测试。
找到规律以后就可以直接编写代码，值得注意的是 这里会有一个边界条件，length == 0或length<=numRows或numRows==1都可以直接输出，不需要进行操作。
方法二：
方法三：
自己体会，这个代码效率是最高的！！！
代码
package com.leetcode.code; import java.util.ArrayList; import java.util.List; /** * LeetCode6-Z字形变换 * * 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。 * * 比如输入字符串为 "LEETCODEISHIRING" 行数为 4 时，排列如下： * * 输入: s = "LEETCODEISHIRING", numRows = 4 * 输出: "LDREOEIIECIHNTSG" * 解释: * * L D R * E O E I I * E C I H N * T S G * */ public class LeetCode6 { // 方法一 public static String convert(String s, int numRows) { int length = s.length(); if(length == 0 || length <= numRows || numRows == 1) { return s; } int gap = numRows - 2; String ans = ""; int k1 = numRows -1 + gap + 1; for (int i = 0; i < numRows; i++) { int location = 0; if (i==0 || i == numRows - 1) { ans = ans + s.charAt(i); location = i + k1; while (location < length) { ans = ans + s.charAt(location); location = location + k1; } } else { ans = ans + s.charAt(i); int k2 = k1 - i * 2; location = location + k2 + i; while (location < length) { ans = ans + s.charAt(location); k2 = k1 - k2; location = k2 + location; } } } return ans; } // 方法二 public static String convert2(String s, int numRows) { if (numRows < 2) { return s; } List<StringBuilder> rows = new ArrayList<StringBuilder>(); for (int i = 0; i < numRows; i++) { rows.add(new StringBuilder()); } int i = 0, flag = -1; for (char c : s.toCharArray()) { rows.get(i).append(c); if (i == 0 || i == numRows - 1) { flag = - flag; } i += flag; } StringBuilder result = new StringBuilder(); for (StringBuilder row : rows) { result.append(row); } return result.toString(); } // 方法三 public String convert3(String s, int numRows) { if (numRows == 1) { return s; } int step = (numRows - 1) << 1; int len = s.length(); char[] ans = new char[len]; char[] chars = s.toCharArray(); int index = -1; for (int i = 0; i < numRows; i++) { for (int j = i; j < len; j += step) { ans[++index] = chars[j]; if (i != 0 && i != numRows - 1 && step - (i << 1) + j < len) { ans[++index] = chars[step - (i << 1) + j]; } } } return new String(ans); } public static void main(String[] args) { System.out.println(convert("LEETCODEISHIRING", 4)); System.out.println(convert2("LEETCODEISHIRING", 4)); System.out.println(convert2("LEETCODEISHIRING", 4)); } }
小结
- 方法一是找规律的方法，也是大家普遍啊知道的方法，时间复杂度略高。
- 方法二的妙处是用flag改变存储的方向，也是该方法的精髓所在。
- 方法三是一个大佬写的代码，我就不做评价了哈哈哈。
性能上：方法一<方法二<方法三
