LeetCode 6. Zigzag Conversion

6. Zigzag Conversion Medium

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)

完整介绍 https://leetcode.com/problems/zigzag-conversion/

题目是要把文字依 Z 的形状排列後，再重新组起来
其实把文字在纸上写一下，就会找出规则，并不太难，列为 Medium，其实有点偏 Easy
重点大概就是找出规则，如图，

1 -> 7 需要经历 6 步，同样 7 -> 13 也是 6 步，最後一列也是一样的规则
第二列 2 -> 6 需要 4 步，6 -> 8 需要 2 步，然後又是 4 步，2 步，4 步，2 步的变化
第三列 3 -> 5 需要 2 步，5 -> 9 需要 4 步，然後又是 2 步，4 步，2 步，4 步的变化

找到这个规则後就可以写出程序了。

public class A0006_ZigzagConversion {
    
	public String convert(String input, int numRows) {
		if (numRows <= 1)
			return input;
		
		StringBuilder output = new StringBuilder();
		
		int step = (numRows - 1) * 2;
		
		for (int row=0; row<numRows; row++) {
		
			int step1 = step - row * 2; // if step is 8, row is 1, step1 6 step2 2
			int step2 = step - step1;
			int[] steps = new int[] {step1, step2};
			
			if (row == 0 || row == numRows-1)
				steps = new int[] {step, step};

			int idx = row;
			int stepIdx = 0;
			while (idx < input.length()) {
				output.append(input.charAt(idx));
				idx += steps[stepIdx%2];
				stepIdx++;
			}
		}
    	
    	return output.toString();
    }
}

这版先用 StringBuilder 较好懂，用 char[] 来存的话会更快一些，但其实也没快到哪