阿亮的算法之路——6. Z 字形变换

阿亮的算法之路——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); }}}String();}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); }}}String();}}

代码冗余较多，提交结果
还好，能完成功能，至于优化，咱们慢慢来，如果功能都无法完成，那就有点打击自信心了。

初次优化

    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); }}}String();}

思路没有变，对一些冗余的代码进行抽取，提交结果

嘿嘿！还不错。代码还可以再简化一点，但是代码简化了，效率方面却没有提升，可能是因为逻辑没有变，只是改进了写法。所以代码也就不贴了。

大佬思路

官方给出的题解，也是类似于找规律，但是他找的规律巧妙得多，他利用的是：也是将每个字符放入一个类似二维数组的容器，安装这个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()) {(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);String();}

提交结果

每次官方给出的答案都是如此巧妙，总是简洁又能完成功能，而且效率还不错，真好奇这些人脑子里面装的是什么。

在官方的题解下面看到了一个评论，把我笑喷了

哈哈，估计这哥们和我一样，花了老大工夫，写了几十上百行代码，还没人家写的十几行代码效率高。

今日拿下两题，噢力给！！！！