LeetCode 6：ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

And then read line by line: "PAHNAPLSIIGYIR"

 

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

首先题目看得一脸懵逼，查了下zigzag这个单词的意思，“Z字形的”，脑袋旋转90度，才明白了要表达啥意思，竖着Z字形排列

比如congratulations就变成这幅模样

/**
 *  congratulations
 *  c     t     o
 *  o   a u   i n
 *  n r   l t   s
 *  g     a
 */

最终要求是横着输出的，那么可以定义个字符串数组，所有nRows行每行组成的字符串保存在字符串数组里，最终只要将字符串数组按顺序输出即可

其实这样还是不好看出点啥东西，加一点标注再看看

/**
 *  String:     congratulations
 *  Row  1:     c     t     o
 *  Row  2:     o   a u   i n
 *  Row  3:     n r   l t   s
 *  Row  4:     g     a
 */

在保存到字符串数组的时候，当从第1行开始的时候，index++；当从第nRows行开始的时候，index- -，row初值为1，flag控制向下还是向上同时控制++还是- -；这里大概这样实现流程：

i = 0；第1行，字符s[i] = c append给rowArray[0]，flag = 1表示下一个往下走了，row += flag向下进入第2行

i = 1；第2行，字符s[i] = o append给rowArray[1]，flag = 1，row += flag向下进入第3行

i = 2；第3行，字符s[i] = n append给rowArray[2]，flag = 1，row += flag向下进入第4行

i = 3；第4行，字符s[i] = g append给rowArray[3]，flag = -1表示下一个往上走了，row += flag向上进入了第3行

i = 4；第3行，字符s[i] = r append给rowArray[2]，flag = -1，row += flag向上进入第2行

……

综合起来就是rowArray[row – 1] += s.charAt(i)，如果row == 1到了第一行，flag = 1，如果row == nRows（这里是4），最后row += flag控制行数，准备向下就+1，准备向上就-1

Java源码

package com.maoxiaomeng;

import java.util.Arrays;

/**
 * @author lihui
 * @date 2018/3/25 16:44
 */
public class Solution {

    public String convert(String s, int numRows) {
        /**
         *  String:     congratulations
         *  Row  1:     c     t     o
         *  Row  2:     o   a u   i n
         *  Row  3:     n r   l t   s
         *  Row  4:     g     a
         */

        int len = s.length();
        if (numRows <= 1 || numRows >= len) {
            return s;
        }

        String[] rowArray = new String[numRows];
        Arrays.fill(rowArray, "");
        
        int row = 1;
        int flag = 1;
        for (int i = 0; i < len; ++i) {
            rowArray[row - 1] += s.charAt(i);

            if (row == 1) {
                flag = 1;
            }
            if (row == numRows){
                flag = -1;
            }
            
            row += flag;
        }

        String ss = new String();
        for (String myStr : rowArray) {
            ss += myStr;
        }
        return ss;
    }
}

如果传入的行数比字符串长度还长，或者不大于1直接返回该字符串即可