算法之字符串锯齿转换

如下所示，字符串“ PAYPALISHIRING”以Z字形写在给定数量的行上。
n=3时：

P   A   H   N
A P L S I I G
Y   I   R

对应转换结果为：P A H N A P L S I I G Y I R

n=4：

P     I     N
A   L S   I G
Y A   H R
P     I

对应转换结果为：P I N A L S I G Y A H R P I

n=5：

P       H
A     S I
Y   I   R
P L     I G
A       N

对应转换结果为：P H A S I Y I R P L I G A N

问题1，如何确定转换后的行数？

如图所示不难发现，n为几，行数即为几个。

问题2，使用何种数据结构来存储转换结果？

由如上转换结果可以看出，结果的输出顺序是按照行的顺序从左往右，从上到下顺序显示出来的。
所以对应的存储结构即为List集合，即可按顺序将转换之后的结果按照从左到右，从上到下顺序存储起来。

List<List<String>> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
    result.add(new ArrayList<String>());
}

问题3，如何存储每行转换结果？

开始分析规律了。由上面几个示例可以看出，字符串变换是每隔一个周期便进行一次变换，故接下来便要分析几个字母来作为1个period周期。

问题3.1，确定转换周期

由上面几个示例可以归纳得出，period = (n + (n-2))。

问题3.2，确定单周期内每行对应的存储定位

通过观察得出，在单周期内，当索引<n时，当前索引即对应第几行字母，但是当n <= 索引<= period时，索引需要重定向。如n=3，索引为3时，实际上对应的行号为2；n=4，索引为4时，实际上对应的行号为2等等。由此可得出：索引 = (n-1) - (索引-n+1)

最终实现

public class JavaTest {
    public static void main(String[] args) {
        zigZagConversion("PAYPALISHIRING", 4);
    }

    private static void zigZagConversion(String src, int n) {
        List<List<String>> result = new ArrayList<>();
        zigZagConversion(result, src, n);
        for (int i=0; i<result.size(); i++) {
            for(String s:result.get(i)) {
                System.out.print(s+" ");
            }
        }
    }

    private static void zigZagConversion(List<List<String>> result, String src, int n) {
        for (int i=0; i<n; i++) {
            result.add(new ArrayList<String>());
        }
        boolean down;
        for(int i=0; i<src.length(); i++) {
            int index = i%(2*n - 2);
            down = index < n;
            String alphaBate = src.substring(i, i+1);
            if (down) {
                result.get(index).add(alphaBate);
            } else {
                index = (n - 1) - (index - n + 1);
                result.get(index).add(alphaBate);
            }
        }
    }
}

总结

一般见到这种题目，基本上都是考的中学的数学归纳。一旦找到规律，一般都可以写出正确的算法来。所以问题就定位在如何找到其中的规律。

最后编辑于：2020.06.06 11:59:49