难度: Medium

内容描述

字符串“PAYPALISHIRING”以之字形模式写入给定数量的行，如下所示：（您可能希望以固定字体显示此模式，以提高可读性）
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 s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

解题方案

思路 1
**- 时间复杂度: O(len(s))**- 空间复杂度: O(len(s))**

需要将字符串s转换为按N排列，总共有numRows行，直接将字符串转换为N字形，然后输出, beats 74.18%

class Solution {
    // 将字符串进行z子排列,行数为numRows
    public String convert(String s, int numRows) {
       // 思路：先转换为z字
        List[] arr = new List[numRows]; // 保存每一行元素
        for(int i = 0; i < numRows; i ++){
            arr[i] = new ArrayList();
        }
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length;){
            // 每次打印两列
            for(int j = 0; j < numRows && i < chars.length; j++,i++){
                List list = arr[j];
                list.add(chars[i]);
            }
            for(int j = numRows - 1; j >= 0 && i < chars.length; j --){
                if(j == numRows - 1 || j == 0){
                    arr[j].add(' ');
                }else{
                    arr[j].add(chars[i]);
                    i++;
                }
            }
        }
        // 输出最终字符串
        char[] result = new char[chars.length];
        int index = 0;
        for(int i = 0; i < numRows; i ++){
            List list = arr[i];
            for(int j = 0; j < list.size(); j ++){
                if(' ' != (char)list.get(j)){
                    result[index++] = (char) list.get(j);
                }
            }
        }
        return new String(result);
    }
}