题目
Z 字形变换
https://leetcode-cn.com/problems/zigzag-conversion/java
公众号 《java编程手记》记录JAVA学习平常,分享学习路上点点滴滴,从入门到放弃,欢迎关注编程
描述
难度:中等数组
将一个给定字符串 s
根据给定的行数 numRows
,以从上往下、从左到右进行 Z
字形排列。函数
好比输入字符串为 "PAYPALISHIRING
" 行数为 3
时,排列以下:学习
P A H N A P L S I I G Y I Rurl
以后,你的输出须要从左往右逐行读取,产生出一个新的字符串,好比:"PAHNAPLSIIGYIR
"。.net
请你实现这个将字符串进行指定行数变换的函数:code
string convert(string s, int numRows);内存
示例 1:leetcode
输入:s = "PAYPALISHIRING", numRows = 3 输出:"PAHNAPLSIIGYIR"
示例 2:
输入:s = "PAYPALISHIRING", numRows = 4 输出:"PINALSIGYAHRPI"
P I N A L S I G Y A H R P I
示例 3:
输入:s = "A", numRows = 1 输出:"A"
提示:
1 <= s.length <= 1000 s 由英文字母(小写和大写)、',' 和 '.' 组成 1 <= numRows <= 1000
Solution
解法
解题思路
如何输出最后的字符串
- 总体的思路是遍历字符串,在遍历过程当中将每行都当作新的字符串构成字符串数组,最后再将该数组拼接起来便可
- 若是
numRows=1
则说明当前字符串即为结果,可直接返回,不然整个字符串须要经历,向下向右
,向下向右
,这样的反复循环过程 - 设定
down
变量true
表示是否向下
,false
表示向右,loc
变量表示当前字符串数组的下标
- 若是
down
为true
,则loc=loc+1
,字符串数组下标向后
移动,将当前字符加入当前字符串中 - 若是
down
为false
,则表示向右,则loc=loc-1
,字符串数组下标向前
移动,将当前字符加入当前字符串中
CODE
class Solution { public String convert(String s, int numRows) { if(numRows==1){ return s ; } //当前坐标 int loc = 0 ; //当前是否往下 boolean down = true; String[] cs = new String[numRows]; //结果数组,对应有numRows个数组,每一个数组用来记录对应行的数据,好比'PAYPALISHIRING' // P A H N cs[0] // A P L S I I G cs[1] // Y I R cs[2] for(int ii =0 ;ii<numRows;ii++) cs[ii]=""; for(int i =0;i<s.length();i++){ //当前这行相加 cs[loc] +=s.charAt(i); if(loc==0){ down = true; } if(loc ==numRows-1){ down = false; } loc += (down?1:-1); } String res =""; for(String c : cs){ res+=c; } return res; } }
复杂度
-
时间复杂度
O(N)
-
空间复杂度
O(N)
结果
-
执行用时:
18
ms, 在全部 Java 提交中击败了20.89
%的用户内存消耗:
39.1
MB, 在全部 Java 提交中击败了44.72
%的用户
艾欧尼亚昂扬不灭!