将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:

L   C   I   R
E T O E S I I G
E   D   H   N

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

https://leetcode-cn.com/problems/zigzag-conversion/

解法1

这道题本身没什么难度,但是考察逻辑思维的缜密性。我采用朴素的方法,首先计算出按Zigzag排列所需要数组的纬度,然后按照Zigzag的顺序填充这个矩阵,然后将矩阵以字符串的形式输出。题目固定了行数numRows,我们需要计算出numCols。

*   *   *
* * * * * numRows = 3
* * *

* * *
* * * * *
* * * * * numRows = 4
* * *

* * *
* * * * *
* * * * * numRows = 5
* * * * *
* * *

通过上面3个例子观察,我们填满一整列需要numRows个字符,还需要numRows – 2个字符填充每列只有一个字符的列。我们将一整列与每列只有一个字符的列称为一个unit,那么通过观察发现构成一个unit需要numRows + numRows – 2个字符,unit的宽度为 1 + numRows – 2(1是一整列,numRows – 2是一个字符的列)。当然,可能有余下的字符无法构成一个unit,我们首先判断余下字符是否能够成一整列,然后判断余下字符能够构成多少个“只包含一个字符的列”。

我们通过上面的分析,可以计算出numCols,然后我们依照ZigZag的方式填充字符数组。最后依照行主序的方式遍历字符数组,向StringBuilder中追加即可。这道题我提交了6次才通过,分别是由于

  1. 未对空字符串特殊处理
  2. 字符串长度小于一个unit没特殊处理
  3. numRows为1导致unit为0,没做特殊处理
  4. 填充arr中只包含一个字符串的列,需要从倒数第二行开始。

所以计算numCols需要特别的小心,多尝试几个case自测下。

class Solution {
    public String convert(String s, int numRows) {
        if (s == null || s.length() == 0)
            return "";
        if (numRows <= 1)
            return s;

        int numCols;
        int unit = numRows + numRows - 2;

        // 少于一个unit,至少有一列。
        if (s.length() < unit)
            numCols = 1;
        else
            numCols = (s.length() / unit) * (1 + numRows - 2);

        // 下面通过remaining计算余下的字符能够构成几列
        int remaining = s.length() % unit;

        if (remaining != 0) {
            // 不够一个unit,先占一列
            remaining -= numRows;
            numCols++;
            // 一列装不下,剩下的字符每个各占一列
            if (remaining > 0)
                numCols += remaining;
        }

        char[][] arr = new char[numRows][numCols];
        int pos = 0;
        int unitWidth = 1 + numRows - 2;
        int rid = 0;

        for (int cid = 0; cid < numCols && pos < s.length(); cid++) {
            // 从上到下填充一整列
            if (cid % unitWidth == 0) {
                // Top down
                for (rid = 0; rid < numRows && pos < s.length(); rid++) {
                    arr[rid][cid] = s.charAt(pos++);
                }
                rid = numRows - 1;
            } else {
                // Bottom up
                arr[--rid][cid] = s.charAt(pos++);
            }
        }

        StringBuilder sb = new StringBuilder(s.length());
        for (int r = 0; r < numRows; r++) {
            for (int c = 0; c < numCols; c++) {
                if (arr[r] != 0)
                    sb.append(arr[r]);
            }
        }
        return sb.toString();
    }
}
pwrliang Algorithms, Trick

Leave a Reply

Your email address will not be published. Required fields are marked *