LeetCode 06 模拟 Z 字型字符串转换

我会带着你远行 2022-03-06 14:28 90阅读 0赞

**6. ZigZag Conversion        难度：Medium**

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

想了会没实现出来，没想到关键点上。看了答案的其中一种解法，感觉思路很巧妙，重点就是 Z 字形，在第一行 和 最后一行的时候 它会 类似 翻转的样子 继续走下去，所以要先设置一个 boolean 变量判断 是否 在第一行或者最后一行。

大概思路：

1. 首先判断 s 字符串是否长度为1（空串就没意义了，暂不讨论）

等于1 ， 直接返回该串；否则进行下一步；

2. 创建一个 包含 StringBuilder 的 List 集合，为啥不创建 String 或者 StringBuffer 的 List 集合呢？ 首先，StringBuffer 和          StringBuilder 可以 调用 append 方法来扩展字符串，不像 String ,开销太大； 其次，在不考虑线程安全的情况下，StringBuilder速度更快，就选它了。  这个 List 集合到底要装几个 StringBuilder 呢？ 个数等于 传参 numRows 和 s.length() 的最小值，稍微想一下就明白了；

3. 设置 初始行变量 0 ； 布尔值 false ;

4. 调用 toCharArray() 方法，遍历每一个字符，挨个拼接到对应的 StringBuilder 中；首先肯定是从第一行（下标为0）开始，加到第一个 StringBuilder 中，然后观察 当前行是否 是第一行或者最后一行，如果不是，就把当前行加1 ， 即将遍历的字符加到下面一个 StringBuilder 中； 如果是，就反转 布尔值 ，当前行 减 1，即将遍历的字符加到前面一个 StringBuilder 中；这样就达到了 Z 字形的效果；

5. 最后，所有字符遍历完，依次遍历 StringBuilder ，拼接完成，得到最终结果。

package pers.leetcode;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * LeetCode 06 模拟Z 字型字符串转换
     * 难度: Medium
     *
     * @author admin
     * @date 2019/3/19 9:13
     */
    public class ZigZagConversion {
    
        public static void main(String[] args) {
           String output = convert("PAYPALISHIRING",3);
           System.out.println(output);
        }
    
        /**
         * Z 字型字符转换
         * @param s 字符串
         * @param numRows 指定划分几行
         * @return
         */
        public static String convert(String s, int numRows){
            if (numRows == 1) return s;
    
            List<StringBuilder> rows = new ArrayList<>();
            for (int i = 0; i < Math.min(numRows, s.length()); i++)
                rows.add(new StringBuilder());
    
            int curRow = 0;
            boolean goingDown = false;
    
            for (char c : s.toCharArray()) {
                rows.get(curRow).append(c);
                if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
                curRow += goingDown ? 1 : -1;
            }
    
            StringBuilder ret = new StringBuilder();
            for (StringBuilder row : rows) ret.append(row);
            return ret.toString();
        }
    }