LeetCode6—ZigZag Conversion

我会带着你远行 2022-06-09 14:22 144阅读 0赞

本类型博客中的各算法的时间复杂度分析均为博主自己推算，本类型博客也是博主自己刷LeetCode的自己的一些总结，因此个中错误可能较多，非常欢迎各位大神在博客下方评论，请不吝赐教

#     #

# 一、问题 #

*  输入：输入一个字符串和整数
 *  输出：输出该字符串转换成zigzag形式之后的

# 二、输入输出示例 #

示例一：

*  输入： 字符串为"PAYPALISHIRING"，行数为3
 *  输出："PAHNAPLSIIGYIR"
 *  输入的ZigZag字符串如下图所示：
 *  ![Center][]

# 三、解法 #

输出是Zigzag字符串每行的字符按照从左到右，从上到下的顺序依次拼接所得，因此如何每行的字符是解题的关键。观察发现对于要展示成n行的字符串，可以将其前2n-1个字符当作一组，然后该组中不同位置索引对应的行数是一定的，这是一种比较笨重的做法，另一种方法类似于找规律，观察可以发现每行字符在原字符串中的索引是有规律的，可以利用该规律直接获得每行对应的字符串。

## 解法一：找规律获得每行的字符串 ##

**解题思路**：通过观察可以发现第一行和最后一行每个字符可以作为一组，前后两个字符的索引之差为numRows\*2-2。而中间的每行可以将两个字符看作一组，两组字符的索引之差为numRows\*2-2，而组内前后两个字符之间的索引差为 numRows\*2-2-2\*(当前行数-1)，利用如上规律，即可直接获得每行的所有字符。

package com.happy.leetcode.p6;
    
    
    public class ZigZagConversionV1 {
    
    
        public static void main(String[] args) {
            String s = "A";
            String an = "PAHNAPLSIIGYIR";
            String re = new ZigZagConversionV1().convert(s, 3);
            System.out.println(re.equals(an));
            System.out.println(an);
            System.out.println(re);
        }
    
    
        /**
         * zigzag对话转换方式
         * @param s 字符串
         * @param numRows 行数
         * @return
         */
        public String convert(String s, int numRows) {
            if(s.length()<=numRows || numRows==1) {
                return s;
            }
            StringBuilder sb = new StringBuilder();
            int d = numRows*2-2;
            // 第一行
            for(int i=0; i<s.length(); i+=d) {
                sb.append(s.charAt(i));
            }
            // 第二行到第numRows-1行
            for(int j=1; j<numRows-1; j++) {
                for(int i=j; i<s.length(); i+=d) {
                    sb.append(s.charAt(i));
                    if(i+d-j*2<s.length()) {
                        // 组内两个字符之间相差i+d-j*2
                        sb.append(s.charAt(i+d-j*2));
                    }
                }
            }
            // 最后一行
            for(int i=numRows-1; i<s.length(); i+=d) {
                sb.append(s.charAt(i));
            }
            return sb.toString();
        }
    
    
    }

**时间复杂度分析**：遍历numRows行，每行遍历的时间复杂度为O(n)，因此总的时间复杂度为 **O(numRows\*n)**，其中n表示字符串长度

[Center]: /images/20220609/133dd5255bdb474fbed08c3ed30794c6.png