0006._ZigZag_Conversion.md

5. ZigZag Conversion

难度: Medium

刷题内容

原题连接

• https://leetcode-cn.com/problems/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 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);
    }
}