LeetCode-6 Z字形变换

  • 题目:6. Z字形变换
  • 难度:中等
  • 分类:字符串
  • 解决方案:字符串遍历

今天我们学习第6题Z字形变换,这是一个字符串的中等题,像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们看看这道题的题目描述。

题目描述

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为"LEETCODEISHIRING"行数为3时,排列如下:

L   C   I   R
E T O E S I I G
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

分析

这个题目的难度不太大,主要是对题目的理解,只有理解题目中的Z字形是如何生成后才能做出来。注意,这里的Z字形其实是将Z逆时针旋转90°后形成的,如图1所示。

图1.Z字形旋转过程

题目中的示例字符串不容易看出规律,我们假设一个字符串为"ABCDEFGHIJKLMN",然后看看是如何形成Z字形的,具体过程如图2所示。

图2.解题思路

由图2可知黑色字符表示Z字形垂直部分,红色字符表示Z字形斜右方向部分。不难看出垂直部分字符的个数为numRows,斜右方向部分子数的个数为numRows-2(除首行和最后一行以外,其余的行数个数)。理解这个形成过程后,我们只需要把这个形成过用代码实现即可。

具体java代码如下所示:

class Solution {
    public String convert(String s, int numRows) {
        // 将字符串转换为字符数组
        char[] arr = s.toCharArray();
        // 构建二维数组(这里使用的StringBuilder是Java面试时的一个考点,可以查看String、StringBuffer和StringBuilder的区别)
        StringBuilder[] sb = new StringBuilder[numRows];
        for(int i=0; i<numRows; i++){
            sb[i] = new StringBuilder();
        }
        int index = 0, len = arr.length;
        // 遍历原始数组,构建Z字形二维数组
        while(index < len){
            // 垂直添加元素
            for(int i=0; i<numRows && index < len; i++){
                sb[i].append(arr[index++]);
            }
            
            // 斜右向添加元素
            for(int i=numRows-2; i>=1 && index < len; i--){
                sb[i].append(arr[index++]);
            }
        }
        
        // 将除第0行以外的行有序拼接到第0行后面
        for(int i=1; i<numRows; i++){
            sb[0].append(sb[i]);
        }
        
        return sb[0].toString();
    }
}

提交结果

Github地址

LeetCode-6 Z字形变换

参考链接

6.Z字形变换

更多文章,请扫描二维码关注『算法半岛』
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目描述: 将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "LEETC...
    LeeYunFeng阅读 967评论 0 50
  • 题目 将字符串 "PAYPALISHIRING"以Z字形排列成给定的行数: 之后从左往右,逐行读取字符:"PAHN...
    sxqiong阅读 1,299评论 0 1
  • 6. Z 字形变换 题目 将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。比如输入字符串为...
    索毅阅读 228评论 0 0
  • 正午。 警笛呜呜,警灯闪闪,消防车飞驰而来,漫天的烟雾尘埃……阿凯闻而不见,呼吸急促困难,面部灼痛...
    彬界阅读 132评论 0 1
  • 2018.10.17-10.18日记接龙 中西合璧 珠联璧合,中西合璧。中华五千年传统古文化,扬我中华之威严雄狮之...
    铃兰花开_d7c0阅读 161评论 0 0