LeetCode——Z字形变换（java）

Z字形变换

一、题目及要求

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

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：
L C I R
E T O E S I IG
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数： string convert(string s, int numRows); 示例 1:
输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN” 示例 2:
输入: s = “LEETCODEISHIRING”, numRows = 4 输出: “LDREOEIIECIHNTSG” 解释: L
D R E O E I I E C I H N T S G

二、题目分析

• 这里思路直接引用大佬的了，后续代码我来具体分析 （请一定要看，不然后面代码大概率会看不懂，思路很重要）
  

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

作者：guanpengchn
链接：https://leetcode-cn.com/problems/zigzag-conversion/solution/hua-jie-suan-fa-6-z-zi-xing-bian-huan-by-guanpengc/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

三、代码解析

（1）初始化

• 这里分为两个操作，第一是判断行数，如果行数为1，则直接返回字符串，不需要进行z字变形；其次是创建变量及存储空间，本方法使用数组。

 //判断要输出的行数，如果为一行则直接返回本字符串
        if(numRows == 1)
            return s;
        //如果字符串长度过短，则输出的行数有可能达不到预期的行数，所以这里采取字符串长度和预期行数的最小值来创建数组空间
        int len = Math.min(s.length(), numRows);
        //创建字符型的数组
        String []rows = new String[len];

（2）编写算法

• 先将数组都初始化 赋值为空字符串，接着定义loc和down变量，分别表示数组下标和是否向下行走的标志。

 //通过循环将，数组初始化
        for(int i = 0; i< len; i++) rows[i] = "";
        //loc代表数组的下标
        int loc = 0;
        //down表示是否向下走
        boolean down = false;

• 接着通过遍历字符串的方式将元素添加进创建好的数组，这里需要注意一点，就是使用 substring() 方法时，注意两个参数必须为和i+1才能每次添加一个元素，不然会出现一次添加多个字符的情况。（详情参考API文档）
  

//遍历字符串，并将元素添加进指定的位置
        for(int i=0;i<s.length();i++) {
            rows[loc] += s.substring(i,i+1);
            //判断loc==0判断是否在第一行，loc==numRows-1判断是否在最后一行
            if(loc == 0 || loc == numRows - 1)
                //反转方向
                down = !down;
                //通过down的值来改变loc
            loc += down ? 1 : -1;
        }

• 将数组的字符串拼接并将其作为返回值返回。

 //字符串拼接
        String ans = "";
        for(String row : rows) {
            ans += row;
        }
        return ans;

四、完整代码

public class Test07 {
    public static void main(String[] args) {
        String s = "LEETCODEISHIRING";
        int num = 4;
        String convert = convert(s, num);
        System.out.println(convert);
    }
    public static String convert(String s, int numRows) {
        //判断要输出的行数，如果为一行则直接返回本字符串
        if(numRows == 1)
            return s;
        //如果字符串长度过短，则输出的行数有可能达不到预期的行数，所以这里采取字符串长度和预期行数的最小值来创建数组空间
        int len = Math.min(s.length(), numRows);
        //创建字符型的数组
        String []rows = new String[len];
        //通过循环将，数组初始化
        for(int i = 0; i< len; i++) rows[i] = "";
        //loc代表数组的下标
        int loc = 0;
        //down表示是否向下走
        boolean down = false;
        //遍历字符串，并将元素添加进指定的位置
        for(int i=0;i<s.length();i++) {
            rows[loc] += s.substring(i,i+1);
            //判断loc==0判断是否在第一行，loc==numRows-1判断是否在最后一行
            if(loc == 0 || loc == numRows - 1)
                //反转方向
                down = !down;
                //通过down的值来改变loc
            loc += down ? 1 : -1;
        }
        //字符串拼接
        String ans = "";
        for(String row : rows) {
            ans += row;
        }
        return ans;
    }
}

五、总结

• 此题不难，主要是思路难想，一开始我走了歪路用找规律去解题，虽然成功了，但是会觉得很无趣，所以我又去学习了这种方法，简单太多了，希望能帮到大家。