企业网站优化方案模板,桂林模板网站建设,wordpress手机文章列表,网站在建设中模板题目描述 将一个给定字符串根据给定的行数#xff0c;以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时#xff0c;排列如下#xff1a;
L C I R
E T O E S I I G
E D H N之后#xff0c;你的输出需要从左往右逐行读…题目描述 将一个给定字符串根据给定的行数以从上往下、从左到右进行 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我的解决方案 使用坐标法建立x轴、y轴计算每个字符所处的位置 二维坐标 y处于多少行 x每行元素的相对位置
public static String convert(String s, int numRows) {if(numRows 2 || snull || s.length()1) {return s;}Character[][] c new Character[numRows][s.length()/2 1];int x0,y0;for(int i0;is.length();i2*(numRows-1)) {y 0;//每个字符必定有其位置for(int j0;jnumRows (i j)s.length();j) {c[y][x] s.charAt(i j);}y numRows-2;if(y0) {for(int knumRows;k2*(numRows-1) (i k)s.length(); k) {c[y--][x] s.charAt(ik);}}x;}StringBuilder result new StringBuilder();for(int i0;inumRows;i) {for(int j0;js.length()/2 1;j) {if(c[i][j] ! null) {result.append(c[i][j]);}}}return result.toString();}改进方案
本以为此算法除了建立二维数组浪费一部分空间之外时间复杂度很难优化了。看了参考答案之后豁然开朗原来不必计算二维坐标值每行元素的位置在从左至右遍历的时候就已经有序了。只需要记录元素在第几行就可以了。 改进后的算法
public static String convert(String s, int numRows) {if(numRows 1) {return s;}ListStringBuilder arrList new ArrayListStringBuilder();for(int i0; iMath.min(s.length(), numRows);i) {arrList.add(new StringBuilder());}int row0;boolean changeDirect true;for(char c:s.toCharArray()) {arrList.get(row).append(c);changeDirect (row 0 || row numRows -1)?!changeDirect:changeDirect;row row (changeDirect?-1:1);}StringBuilder rep new StringBuilder();for(StringBuilder sb : arrList) {rep.append(sb);}return rep.toString();}代码逻辑更加清晰更加便于维护并且减少了部分运算量执行速度提高了近一倍。
持续精进加油
