算法实战(六)Z 字形变换
一.前言
之前因为第五题最长回文字符串需要使用到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:二维数组
对于这种字符串变换的问题,我向来都是很头疼,一开始认为变化太多了很复杂,实际分析了一下这个题目后,发现并没有我想象的那么难。给定了一个行数后,对于字符串的走法,只有两种一种是沿着当前这一列往下走,一种是斜着往上走。我们只要判断一下,什么时候需要往下,什么时候需要斜着往上走就行了。定义一个二维数组,将字符串存在对应的位置,遍历完字符串之后,再将数组中的字符拼接起来,就能得到我们要的结果。
代码如下:
class Solution {
public String convert(String s, int numRows) {
//首先,我们对额外情况进行一下过滤
if (s == null || s.length() == 0 || numRows <= 1 || s.length() < numRows){
return s;
}
///创建一个stringBuilder,用来保存最后的结果
StringBuilder stringBuilder = new StringBuilder();
//创建一个二维数组,用来保存字符串到对应的位置
Character[][] arr = new Character[numRows][s.length()];
int num1 = 0;//行号
int num2 = 0;//列号
//遍历字符串
for (Character c : s.toCharArray()){
//当我们处于第一行时,或者上一行的字符不为null时,继续往下读
if (num1 == 0 || arr[num1 - 1][num2] != null){
arr[num1++][num2] = c;
//当到了最后一行时,往斜上方移动一个
if (num1 == numRows){
num1 = numRows - 2;
num2++;
}
}else {
//一直向斜上方移动
arr[num1--][num2++] = c;
}
}
//此时二维数组中记录了所有的字符了,按照顺序,取出不为空的字符
for (int i = 0; i < numRows; i++){
for (int j = 0; j < arr[0].length; j++){
if (arr[i][j] != null){
stringBuilder.append(arr[i][j]);
}
}
}
return stringBuilder.toString();
}
}
说明:这种解法的好处是思路简单,题目在构建Z字形变化时和我们平时使用的二维数组刚好吻合,所以能让人直观的理解,缺点就是时间复杂度太高了,我们进行Z字形变化所用的时间复杂度是O(n),但是我们把二维数组中的字符重新取出却要耗费O(n^2),得不偿失,所以我就在想有没有什么更好的数据结构能够利用一下,可惜没想出来。
解法二:创建一个StringBuilder的list
这个是leetcode提供的官方解法,思路真的是相当之巧妙,创建一个StringBuilder的List,用来保存每一行的字符串,其他的思路和上面的类似,就是两种走法,往下走和往上走。只不过最后我们获得结果的时候,只需要把list中的StringBuilder凭借到一起就可以了。
代码如下:
class Solution {
public String convert(String s, int numRows) {
//首先,我们对额外情况进行一下过滤
if (s == null || s.length() == 0 || numRows <= 1 || s.length() < numRows){
return s;
}
List<StringBuilder> list = new ArrayList<>();
for (int i = 0; i < numRows; i++){
list.add(new StringBuilder());
}
boolean bool = true;
int cos = 0;//行号
//只有两个地方需要进行变化,一个是在第一行,一个时在最后一行
for (Character c : s.toCharArray()){
if (cos == numRows){
cos -= 2;
bool = false;
}
if (cos == 0){
bool = true;
}
if (bool){
list.get(cos++).append(c);
}else {
list.get(cos--).append(c);
}
} StringBuilder result = new StringBuilder();
for (StringBuilder stringBuilder : list){
result.append(stringBuilder);
}
return result.toString();
}
}
这样的时间复杂度就变成了O(n)了。这就是今天Z字形变化的两种解法,大家有什么不懂的或者有更加高深的看法,欢迎一起探讨。
最新文章
- MIT 6.828 JOS学习笔记13 Exercise 1.10
- MySQL 5.7 学习:功能性能的提升
- oc swizzling 真的好用
- iOS自动化编译
- 新手Oracle安装及使用入门
- 2.4---把链表划分为两部分(CC150)
- phpstorm相关设置
- elixir 高可用系列(二) GenServer
- atitit.泛型编程总结最佳实践 vO99 java c++ c#.net php
- 把所有特权给root &#39;%&#39;所有IP
- 单点登录系统构建之一——基础知识(Kerberous/SAML)
- docker 连接容器
- ios开发常见问题及解决办法
- 我的第一个MyBatis
- eclipse中tomcat的add and Remove找不到项目
- gcc 与 glibc 的关系 glibc版本查看
- 在php中怎么利用js把参数传递给弹窗
- js 获取后缀参数
- Sqlite 常用函数推荐
- [LeetCode] Search in Rotated Array II
热门文章
- js 动画提示数据有变化
- 利用Python进行多项式拟合
- 清除浮动(overflow、clear、:after等方法)
- 700k把web端程序包装为桌面程序
- 时间转换(scanf的指定格式读入)
- Codeforces 1296E2. String Coloring (hard version)
- 「AT2292」Division into Two
- 学习SpringBoot零碎记录——配置应用URL名称
- 吴裕雄--天生自然JAVA面向对象高级编程学习笔记:匿名内部类
- 关于 vue.config.js 文件的配置