图解LeetCode06:Z字形变换

LeetCode06:Z字形变换

将一个给定字符串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);

示例:

输入:s = "PAYPPALISHIRING", numRows = 3
输出:"PAHNAPLSIIGYIR"

题目分析:

给定一个字符串,按照字符串的从左到右顺序,从上到下,从下到上的Z行排列,流程图如下所示
图解LeetCode06:Z字形变换

上面这种Z型排列为了方便我们理解过程是如何进行的,我们理解了之后不需要让电脑也这样理解,完全可以转换成以下的方式
图解LeetCode06:Z字形变换

这种方式之后我们可以按照行数维持一个二维数组,另维持一个指针来指向二维数组来判断是应该从上往下填入,还是应该从下往上填入了。
图解LeetCode06:Z字形变换

将字符串s全都遍历结束放到二维数组中,就可以遍历二维数组,拿出结果
图解LeetCode06:Z字形变换

关于从上到下或者从下到上的指针维护,可以声明一个Boolean类型,判断指针是否为0或者到达了numRows-1,从而改变Boolean的数值
图解LeetCode06:Z字形变换

public String convert(String s, int numRows){
        // 如果行数为1,直接输出s
        if(numRows == 1) return s;

        // 判断字符串和行数的大小,取小的那一个
        int len = Math.min(s.length(), numRows);

        // 声明一个数组,存放Z型结果
        String[] datas = new String[len];

        // 为数组赋予空值
        for (int i = 0; i < len; i++) datas[i] = "";

        // 维持两个指针,一个指针索引,一个确定方向
        int ptr = 0;
        // 因为后面要判断指针是否到了第一个(0)或最后一个(numRows-1),所以先为false
        boolean toDown = false;

        // 遍历字符串s
        for (int i = 0; i < s.length(); i++) {
            // 将遍历的该值加入到对应的数组中
            datas[ptr] += s.charAt(i);
            // 判断是否到达顶端或低端,将方向调整
            if (ptr == 0 || ptr == numRows - 1) toDown = !toDown;
            // 根据方向,判断ptr是加1还是减1
            ptr += toDown ? 1 : -1;
        }
        // 遍历结束,取出数据
        String res = "";
        for (String data : datas) {
            res += data;
        }
        return res;
    }

测试:

public static void main(String[] args) {
        LeetCode06 lc = new LeetCode06();
        String result = lc.convert("PAYPALISHIRING", 3);
        System.out.println(result);
    }

结果:

PAHNAPLSIIGYIR
上一篇:C++智能指针(2)—— unique_ptr


下一篇:Effective C++读书笔记~7 模板与泛型编程