文档章节

算法实战(六)Z 字形变换

o
 osc_isezqdgg
发布于 2019/09/18 20:15
字数 1174
阅读 12
收藏 0
cos

精选30+云产品,助力企业轻松上云!>>>

一.前言

  之前因为第五题最长回文字符串需要使用到dp解法,所以我花了很长的时间来研究dp(因为每天又要上班,加上这段时间事情比较多,所以花了三个星期才搞定),好不容易算入了个门,有兴趣的同学可以看看我写的dp的文章,话不多说,今天开始继续刷题。

二.题目

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

     比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:

                 

 

 

       之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"

             请你实现这个将字符串进行指定行数变换的函数:string convert(string s, int numRows);

  示例1:输入: s = "LEETCODEISHIRING", numRows = 3 

       输出: "LCIRETOESIIGEDHN"

  示例2:输入: s = "LEETCODEISHIRING", numRows = 4

       输出: "LDREOEIIECIHNTSG"

       解释:                       

三.解题思路

   解法1:二维数组

      对于这种字符串变换的问题,我向来都是很头疼,一开始认为变化太多了很复杂,实际分析了一下这个题目后,发现并没有我想象的那么难。给定了一个行数后,对于字符串的走法,只有两种一种是沿着当前这一列往下走,一种是斜着往上走。我们只要判断一下,什么时候需要往下,什么时候需要斜着往上走就行了。定义一个二维数组,将字符串存在对应的位置,遍历完字符串之后,再将数组中的字符拼接起来,就能得到我们要的结果。

      代码如下:

 1 class Solution {
 2     public String convert(String s, int numRows) {
 3         //首先,我们对额外情况进行一下过滤
 4         if (s == null || s.length() == 0 || numRows <= 1 || s.length() < numRows){
 5             return s;
 6         }
 7         ///创建一个stringBuilder,用来保存最后的结果
 8         StringBuilder stringBuilder = new StringBuilder();
 9         //创建一个二维数组,用来保存字符串到对应的位置
10         Character[][] arr = new Character[numRows][s.length()];
11         int num1 = 0;//行号
12         int num2 = 0;//列号
13         //遍历字符串
14         for (Character c : s.toCharArray()){
15             //当我们处于第一行时,或者上一行的字符不为null时,继续往下读
16             if (num1 == 0 || arr[num1 - 1][num2] != null){
17                 arr[num1++][num2] = c;
18                 //当到了最后一行时,往斜上方移动一个
19                 if (num1 == numRows){
20                     num1 = numRows - 2;
21                     num2++;
22                 }
23             }else {
24                 //一直向斜上方移动
25                 arr[num1--][num2++] = c;
26             }
27         }
28         //此时二维数组中记录了所有的字符了,按照顺序,取出不为空的字符
29         for (int i = 0; i < numRows; i++){
30             for (int j = 0; j < arr[0].length; j++){
31                 if (arr[i][j] != null){
32                     stringBuilder.append(arr[i][j]);
33                 }
34             }
35         }
36         return stringBuilder.toString();
37     }
38 }

      说明:这种解法的好处是思路简单,题目在构建Z字形变化时和我们平时使用的二维数组刚好吻合,所以能让人直观的理解,缺点就是时间复杂度太高了,我们进行Z字形变化所用的时间复杂度是O(n),但是我们把二维数组中的字符重新取出却要耗费O(n^2),得不偿失,所以我就在想有没有什么更好的数据结构能够利用一下,可惜没想出来。

  解法二:创建一个StringBuilder的list

    这个是leetcode提供的官方解法,思路真的是相当之巧妙,创建一个StringBuilder的List,用来保存每一行的字符串,其他的思路和上面的类似,就是两种走法,往下走和往上走。只不过最后我们获得结果的时候,只需要把list中的StringBuilder凭借到一起就可以了。

    代码如下:

 1 class Solution {
 2     public String convert(String s, int numRows) {
 3         //首先,我们对额外情况进行一下过滤
 4         if (s == null || s.length() == 0 || numRows <= 1 || s.length() < numRows){
 5             return s;
 6         }
 7         List<StringBuilder> list = new ArrayList<>();
 8         for (int i = 0; i < numRows; i++){
 9             list.add(new StringBuilder());
10         }
11         boolean bool = true;
12         int cos = 0;//行号
13         //只有两个地方需要进行变化,一个是在第一行,一个时在最后一行
14         for (Character c : s.toCharArray()){
15             if (cos == numRows){
16                 cos -= 2;
17                 bool = false;
18             }
19             if (cos == 0){
20                 bool = true;
21             }
22             if (bool){
23                 list.get(cos++).append(c);
24             }else {
25                 list.get(cos--).append(c);
26             }
27         }
28 
29         StringBuilder result = new StringBuilder();
30         for (StringBuilder  stringBuilder : list){
31             result.append(stringBuilder);
32         }
33         return result.toString();
34     }
35 }

    这样的时间复杂度就变成了O(n)了。这就是今天Z字形变化的两种解法,大家有什么不懂的或者有更加高深的看法,欢迎一起探讨。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
LeetCode:Z 字形变换

https://www.cnblogs.com/pgjett/p/12463641.html LeetCode:Z 字形变换 字符串 Z 字形变换的巧妙解法:设立标志位控制迭代方向 No.6 Z 字形变换 题目: 将一个给定字符串根据给定的行数,以...

osc_xmvqghwh
03/19
3
0
LeetCode:Z 字形变换

LeetCode:Z 字形变换 字符串 Z 字形变换的巧妙解法:设立标志位控制迭代方向 No.6 Z 字形变换 题目: 将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。 示例 1: 比如...

pgjett
03/11
0
0
LeetCode:Z 字形变换

https://www.cnblogs.com/pgjett/p/12463641.html LeetCode:Z 字形变换 字符串 Z 字形变换的巧妙解法:设立标志位控制迭代方向 No.6 Z 字形变换 题目: 将一个给定字符串根据给定的行数,以...

osc_0hs26yvj
03/19
7
0
[ccf/csp题]201412-2 Z字形扫描

试题编号: 201412-2 试题名称: Z字形扫描 时间限制: 2.0s 内存限制: 256.0MB 问题描述: 问题描述   在图像编码的算法中,需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一...

fengxinlinux
2017/10/31
0
0
算法题--Z字形变换

题目描述 将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下: 之后,你的输出需要从左往右逐行读取,产...

独孤求媛
2019/10/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

什么是token及怎样生成token

什么是token   Token是服务端生成的一串字符串,以作客户端进行请求的一个令牌,当第一次登录后,服务器生成一个Token便将此Token返回给客户端,以后客户端只需带上这个Token前来请求数据即...

osc_zzg7fpke
53分钟前
10
0
往事不堪回首

开局一张图,内容全靠编 从12年大学毕业到如今,兜兜转转,依然在码工,码农,码代码的路上徘徊着,从最初的用asp.net写站点,写内部的CRM,内部管理系统,内部的XXX,很难想象内部的系统居然...

osc_9os5791s
54分钟前
23
0
java 事件监听器

package com.qimh.springbootfiledemo.listener;/** * 事件监听器 * 监听person 事件源的eat 和 sleep 的方法 * @author */public interface PersonListener { void doEa...

qimh
55分钟前
21
0
[原创.数据可视化系列之四]跨平台,多格式的等值线和等值面的生成

这些年做项目的时候,碰到等值面基本都是arcgis server来支撑的,通过构建GP服务,一般的都能满足做等值线和等值面的需求。可是突然有一天,我发现如果没有arcgis server 的话,我既然没法生...

osc_bvincwvq
55分钟前
16
0
个人作业——软件工程实践总结&个人技术博客

这个作业属于哪个课程 2020春|S班(福州大学) 这个作业要求在哪里 个人作业——软件工程实践总结&个人技术博客 这个作业的目标 总结软件工程课程以及实践中的收获 作业正文 其他参考文献 一...

osc_9piujk2x
55分钟前
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部