你的位置:首页 > Java教程

[Java教程]No.006:ZigZag Conversion


题目:

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P  A  H  NA P L S I I GY  I  R

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

官方难度:

Easy

翻译:

字符串"PAYPALISHIRING",被拆成几列写成如下ZigZag模式,写出转译的代码。

例子:

以上的例子如果表达的不够清楚,再给一个清晰的例子:

a     g     m    s     y
b   f h   l n   r t   x z
c e   i k   o q  u w
d     j     p     v
返回"agmsybfhlnrtxzceikoquwdjpv"

思路:

1.用两次遍历,把新字符串加进数组。

2.头尾两行需要特殊处理,间隔是个定值=2*(nRows-1)。

3.根据走势是从下往上还是从下往上,间隔是不同的,使用一个int型的标志位,每次改变之后乘以-1来控制。

解题中可能遇到的困难:

1.内循环的index是i+j,退出条件是i+j<array.length。

解题代码:

 1 private static String method(String text, int nRows) { 2     char[] array = text.toCharArray(); 3     StringBuffer sb = new StringBuffer(); 4     // 从上至下/从下至上的标志位 5     int flag = 1; 6     // 按行遍历 7     for (int i = 0; i < nRows; i++) { 8       // 每一行的数据 9       for (int j = 0; i + j < array.length;) {10         sb.append(array[i + j]);11         // 极点有特殊的处理方式12         if (i == 0 || i == nRows - 1) {13           j += 2 * (nRows - 1);14         } else {15           if (flag == 1) {16             // 从上至下处理17             j += 2 * (nRows - i - 1);18           } else {19             // 从下至上处理20             j += 2 * i;21           }22           // 下次改变方向23           flag *= -1;24         }25       }26       // 结束一行遍历,方向标志位还原27       flag = 1;28     }29     return sb.toString();30   }

View Code

 测试代码地址:

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/easy/Q006.java

LeetCode题目地址:

https://leetcode.com/problems/zigzag-conversion/

PS:如有不正确或提高效率的方法,欢迎留言,谢谢!