本文主要是介绍阿亮的算法之路——6. Z 字形变换,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
看到题目就觉得有戏,看起来复杂了一点,但是凭我的感觉,这题用暴力是比较容易做的,只是可能比较繁琐。
z型变换,实际上是n型,不过都无所谓,我用一个二维数组往里一套,后面再遍历拼接成字符串,就OK了。只是在往二维数组里放值的时候,条件不容易控制,需要慢慢找规律。
自己尝试
思路
因为需要慢慢找规律,所以我在草稿纸上画了一下图:
就是字符串的每个字符索引,与这个字符被放入二维数组中的位置关系。仔细观察,我们可以将这些分组,例如:当numRows=3时,这个变量代表着这个字符串需要被分成一个多少行的z型,我们可以将0-3、4-7、8-11……等分成一个组,当numRows=4时,可以将0-5、6-11、12-17……等分成一个组。为什么要这样分呢?因为这些组0、4、8和0、6、12这数都被放到了第一行,也就是说,他们会被放入二维数组的第一个数组里面。这些数好像也都有着某种规律,好像是可以被某个整数整除。我们就可以根据这个规律来确定每个被放在第一行的数,然后可以通过numRows确定,被放在第一列的数,然后确定被放在斜线上的数,最后在根据递增找出递增与所处二维数组中的位置
这是主要的处理逻辑,然后再对一些特殊和临界情况进行处理就OK了
首次通过
public static String convert(String s, int numRows){int length = s.length();StringBuilder stringBuilder = new StringBuilder();if (numRows == 1){ return s; }if (numRows == 2){char[][] chars = new char[2][length / 2 + 1];for (int i = 0; i < length; i++){if (i % 2 == 0){ chars[0][i / 2] = s.charAt(i); }else{ chars[1][(i-1)/2] = s.charAt(i); }}for (int n = 0; n < chars.length; n++){for (int m = 0; m < chars[n].length; m++){char c = chars[n][m];if (c != '\u0000'){ stringBuilder.append(c); }}}return stringBuilder.toString();}else{char[][] chars = new char[numRows][length];int lineCount = 0;for (int i = 0; i < length; i++){if (i / (numRows - 1) % 2 == 0 && i % (numRows - 1) == 0){for (int j = 0; j < numRows; j++){if (i + j >= length){ break; }chars[j][lineCount * (numRows - 1)] = s.charAt(i + j);}i += numRows;for (int j = 0; j < numRows - 2; j++){if (i + j >= length){ break; }chars[numRows - 2 - j][(lineCount) * (numRows - 1) + j + 1] = s.charAt(i + j);}i += numRows - 3;lineCount++;}}for (int n = 0; n < chars.length; n++){for (int m = 0; m < chars[n].length; m++){char c = chars[n][m];if (c != '\u0000'){ stringBuilder.append(c); }}}return stringBuilder.toString();}}
代码冗余较多,提交结果
还好,能完成功能,至于优化,咱们慢慢来,如果功能都无法完成,那就有点打击自信心了。
初次优化
public static String convert(String s, int numRows){int length = s.length();StringBuilder stringBuilder = new StringBuilder();if (numRows == 1){ return s; }char[][] chars = new char[numRows][length / 2 + 1];if (numRows == 2){for (int i = 0; i < length; i++){if (i % 2 == 0){ chars[0][i / 2] = s.charAt(i); }else{ chars[1][(i-1)/2] = s.charAt(i); }}}else{int lineCount = 0;for (int i = 0; i < length; i++){if (i / (numRows - 1) % 2 == 0 && i % (numRows - 1) == 0){for (int j = 0; j < numRows; j++){if (i + j >= length){ break; }chars[j][lineCount * (numRows - 1)] = s.charAt(i + j);}i += numRows;for (int j = 0; j < numRows - 2; j++){if (i + j >= length){ break; }chars[numRows - 2 - j][(lineCount) * (numRows - 1) + j + 1] = s.charAt(i + j);}i += numRows - 3;lineCount++;}}}for (int n = 0; n < chars.length; n++){for (int m = 0; m < chars[n].length; m++){char c = chars[n][m];if (c != '\u0000'){ stringBuilder.append(c); }}}return stringBuilder.toString();}
思路没有变,对一些冗余的代码进行抽取,提交结果
嘿嘿!还不错。代码还可以再简化一点,但是代码简化了,效率方面却没有提升,可能是因为逻辑没有变,只是改进了写法。所以代码也就不贴了。
大佬思路
官方给出的题解,也是类似于找规律,但是他找的规律巧妙得多,他利用的是:也是将每个字符放入一个类似二维数组的容器,安装这个n性移动的时候,每次这个行都是朝着一个方向变的,只是到了顶部或者底部,才会转向,他就利用了这个特点,巧妙的控制行的变动,最后将这个类似二维数组的容器再拼接成一个字符串。
代码
public String convert(String s, int numRows) {if (numRows == 1) return s;List<StringBuilder> rows = new ArrayList<>();for (int i = 0; i < Math.min(numRows, s.length()); i++)rows.add(new StringBuilder());int curRow = 0;boolean goingDown = false;for (char c : s.toCharArray()) {rows.get(curRow).append(c);if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;curRow += goingDown ? 1 : -1;}StringBuilder ret = new StringBuilder();for (StringBuilder row : rows) ret.append(row);return ret.toString();}
提交结果
每次官方给出的答案都是如此巧妙,总是简洁又能完成功能,而且效率还不错,真好奇这些人脑子里面装的是什么。
在官方的题解下面看到了一个评论,把我笑喷了
哈哈,估计这哥们和我一样,花了老大工夫,写了几十上百行代码,还没人家写的十几行代码效率高。
今日拿下两题,噢力给!!!!
这篇关于阿亮的算法之路——6. Z 字形变换的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!