2014
11-19

# LeetCode-ZigZag Conversion[模拟]

### 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   N
A P L S I I G
Y   I   R


And then read line by line: "PAHNAPLSIIGYIR"

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

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

n=4:
\begin{Code}
P I N
A L S I G
Y A H R
P I
\end{Code}

n=5:
\begin{Code}
P H
A S I
Y I R
P L I G
A N
\end{Code}

// LeetCode, ZigZag Conversion
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
string convert(string s, int nRows) {
if (nRows <= 1 || s.size() <= 1) return s;
string result;
for (int i = 0; i < nRows; i++) {
for (int j = 0, index = i; index < s.size();
j++, index = (2 * nRows - 2) * j + i) {
result.append(1, s[index]);  // 垂直元素
if (i == 0 || i == nRows - 1) continue;   // 斜对角元素
if (index + (nRows - i - 1) * 2 < s.size())
result.append(1, s[index + (nRows - i - 1) * 2]);
}
}
return result;
}
};


Java代码:

public class Solution {
public String convert(String s, int nRows) {
if(s == null || s.length() == 0 || nRows <= 1) return s;
char arr[] = s.toCharArray();
char carr[] = new char[arr.length];

int step = nRows * 2 - 2;
int zcnt = arr.length / step;
int k = 0;

for(int i=0; i<nRows; i++){
for(int j=0; j<=zcnt; j++){
if(i == 0){
if(j*step < arr.length)
carr[k++] = arr[j*step];
}else if(i == nRows-1){
if(j*step+i < arr.length)
carr[k++] = arr[j*step+i];
}else{
if(j*step+i < arr.length)
carr[k++] = arr[j*step+i];
if((j+1)*step-i < arr.length)
carr[k++] = arr[(j+1)*step-i];

}
}

}
return new String(carr);
}
}

1. 根本没几把用，人家根本不管你怎么想，就是要拖你，上次一个六十多大妈来传销基督，我烦了说了一声，说我信佛教，大妈还能对我唠叨几十分钟佛祖不爱你，基督爱你

2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

3. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

4. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？