从零学算法6

6. Z 字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

	P   A   H   N
	A P L S I I G
	Y   I   R
1
2
3

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“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
1
2
3
4

示例 3：
输入：s = “A”, numRows = 1
输出：“A”
提示：
1 <= s.length <= 1000
s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成
1 <= numRows <= 1000

• 我的原始人解法（可略）：模拟，找到变换规律。首先 row 为 1 返回 s 即可；然后用字符二维数组 res 记录变换后的形状，比如例子 2，可以分为 3 列一组，每一列的长度为 numRows,1,1，numRows 为其他时同理，可分为 numRows - 1 列一组，每一组长度为 numRows,1,1。根据这个规律，我们可以得到所需的列有多少列。
• 分组示意图

•  P        	I    			N
   A   L    	S  I G
   Y A      	H R
   P        	I
  1
  2
  3
  4

• 然后就是遍历 s 根据规律将字符加入 res，先在当前列从上到下加 numRows 个字符，然后将字符加入下一列的倒数第二行，下一列倒数第三行…直到下一列的第二行，就完成一组，之后同理

•   public String convert(String s, int numRows) {
        if(numRows == 1)return s;
        int len = s.length();
        int numCols = getNumCols(len, numRows);
        char[][] res = new char[numRows][numCols];
        int col = 0;
        int i = 0;
        StringBuilder sb = new StringBuilder();
        while(col < numCols){
            int row = 0;
            // 先加 x 列一组中的第一列
            while(i < len && row < numRows){
                res[row++][col] = s.charAt(i++);
            }
            col++;
            // 剩下的行数从倒数第二行开始
            row = numRows - 1 - 1;
            // 再加 x 列一组的剩下列，每一列有一个字符
            while(i < len && row > 0){
                res[row--][col++] = s.charAt(i++);
            }
        }
        for(char[] cs : res){
            for(char c : cs){
                if(c != '\u0000')sb.append(c);
            }
        }
        return sb.toString();
    }
    // 计算有几列
    public int getNumCols(int len, int numRows){
        int[] nums = new int[numRows - 1];
        Arrays.fill(nums, 1);
        nums[0] = numRows;
        int numCols = 0;
        while(len > 0){
            for(int i = 0; i < nums.length; i++){
                len -= Math.min(len, nums[i]);
                numCols++;
                if(len == 0)break;
            }
        }
        return numCols;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44

• 他人解法：其实观察过后会发现，字符所放的行数就是从 0 ~ numRows-1 -> numRows-1 ~ 0 -> 0 ~ numRows-1... 循环变动，我们定义一个 stringBuilder 数组 rows，跟随行变化规律拼接字符即可。
• 比如 “abcde”，numRows = 3，就是把 a 加入第一行, 得到 rows[0] = a，然后把 b 加入第二行 rows[1] = b -> rows[2] = c -> rows[1] = bd -> rows[0] = ae，最终把每一行的结果拼接到一起：ae + bd + c = aebdc

•   public String convert(String s, int numRows) {
        if(numRows == 1)return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        // flag: 行变化规律标志，控制 rowIndex 递增还是递减
        int rowIndex = 0, flag = -1;
        for(char c : s.toCharArray()) {
            rows.get(rowIndex).append(c);
            // 行到顶部就该往下递增，到底部就该往上递减，所以改变 flag
            if(rowIndex == 0 || rowIndex == numRows - 1)flag = -flag;
            rowIndex += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) res.append(row);
        return res.toString();
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16