RBA的技术分享

将一个给定字符串 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

最开始的最笨的办法.就是初始化一个二维数组.然后按说明.把原数组填进去. 填完后再遍历下二维数据.取出非0的就可以了.

具体代码如下:

public  class Solution {

        public String convert(String s, int numRows) {
            if (numRows == 1) {
                return s;
            }
            // S = N + (N-2)
            // 一个周期  : N + N-2 字符
            // 周期内列数: 1 + N - 2
            char[] chs = s.toCharArray();
            int length = s.length();
            int width = numRows - 2 + 1;
            int l1 = length / (2 * numRows - 2) * width;
            int left = length % (2 * numRows - 2);
            int l2 = 0;
            if (left > 0) {
                l2 = left <= numRows ? 1 : (1 + left - numRows);
            }

            char[][] map = new char[numRows][l1 + l2];

            int k = 0;
            for (int j = 0; j < l1 / width; j++) {
                for (int i = 0; i < numRows; i++) {
                    map[i][j * width] = chs[k++];
                }
                for (int i = numRows - 2; i > 0; i--) {
                    map[i][j * width + (numRows - i - 1)] = chs[k++];
                }

            }
            if (l2 > 0) {
                if (left <= numRows) {
                    for (int t = 0; t < left; t++) {
                        map[t][l1] = chs[k++];
                    }
                } else {
                    for (int t = 0; t < numRows; t++) {
                        map[t][l1] = chs[k++];
                    }
                    for (int j = numRows - 2, lastLeft = left - numRows; lastLeft > 0; lastLeft--) {
                        map[j][l1 + (numRows - j - 1)] = chs[k++];
                        j--;
                    }
                }
            }
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < numRows; i++) {
                for (int j = 0; j < l1 + l2; j++) {
                    if (map[i][j] > 0) {
                        sb.append(map[i][j]);
                    }
                }
            }
            return sb.toString();
        }
    }

上面代码很简单,就不说了. 在此计算过程中. 实际上要计算这个二维数组宽度,即列.
然后在填充的时候,我们是按原字符的顺序填进去的. 同时,这个值是可以反推的.也就是说一个格子会填才能数.我们是可以反推过来的.
用它处于哪一个块. 然后再看在哪一行.就可以反算出来. 然后再用这个反算出来的 offset 去原数组里面验证.如果没有越界就加到新数组中.
这样实际在不初始化二维数组的情况下可以按虚拟的二维数组还原出变换后的字符串.

代码

class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1){return s;}

        int len = s.length();
        char[] chs = s.toCharArray();
        
        //int width = 1+numRows-2;
        int blocks = (s.length() + 2*numRows - 2 - 1)  / (2*numRows - 2);
        int blockSize = (2*numRows - 2);

        char[] out = new char[len];
        int k = 0;
        for(int i = 0;i<numRows;i++){
            for(int b = 0; b<blocks;b++){

                int offset = (b*blockSize)+i;
                if(offset < len){
                    out[k++]=chs[offset];
                }

                if(i>0 && i< numRows-1){
                    offset = (b+1)*blockSize - i ;
                    if(offset < len){
                        out[k++]=chs[offset];
                    }
                }
            }
        }    
        return new String(out);
    }
}