LeetCode每日一题，Z字形变换

题目

Z 字形变换

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

公众号 《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注

描述

难度：中等

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

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

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

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"

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

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

Solution

解法

解题思路

如何输出最后的字符串

• 整体的思路是遍历字符串，在遍历过程中将每行都看成新的字符串构成字符串数组，最后再将该数组拼接起来即可
• 如果 numRows=1则说明当前字符串即为结果，可直接返回，否则整个字符串需要经历，向下向右，向下向右，这样的反复循环过程
• 设定 down 变量true表示是否向下，false表示向右，loc 变量表示当前字符串数组的下标
• 如果 down 为 true，则 loc=loc+1，字符串数组下标向后移动，将当前字符加入当前字符串中
• 如果 down 为 false，则表示向右，则 loc=loc-1，字符串数组下标向前移动，将当前字符加入当前字符串中

image-20210418171756824

CODE

class Solution {
    public String convert(String s, int numRows) {
         if(numRows==1){
             return s ;
         }
         //当前坐标
         int loc = 0 ;
         //当前是否往下
         boolean down = true;
        String[] cs = new String[numRows];
         //结果数组，对应有numRows个数组，每个数组用来记录对应行的数据,比如'PAYPALISHIRING'
         //     P   A   H   N           cs[0]
         //     A P L S I I G           cs[1]
         //     Y   I   R               cs[2]

         for(int ii =0 ;ii<numRows;ii++) cs[ii]="";
         for(int i =0;i<s.length();i++){
             //当前这行相加
            cs[loc] +=s.charAt(i);
            if(loc==0){
                down = true;
            }
            if(loc ==numRows-1){
                down = false;
            }
            loc += (down?1:-1);
         }
         String res ="";
         for(String c : cs){
            res+=c;
         }
         return res;
    }
}

复杂度

• 时间复杂度 O(N)

• 空间复杂度 O(N)

结果

• 执行用时：18 ms, 在所有 Java 提交中击败了20.89%的用户

  内存消耗：39.1 MB, 在所有 Java 提交中击败了44.72%的用户

艾欧尼亚昂扬不灭！