# ZigZag Conversion

Feb 15, 2019

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 s, int numRows);


Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I


P   A   H   N
A P L S I I G
Y   I   R


• 第一行中的元素在原来的字符串中下标相差4个。
• 第二行中的元素在原来字符串中下标相差2个。

ok，看起来好像找到了一些规律，继续跑一个例子验证一下，这次的输入是s = "PAYPALISHIRING", numRows = 3，把Z字型画出来：

P     I    N
A   L S  I G
Y A   H R
P     I


• AL相差4个，LS却相差2个
• SI相差4个，IG却相差2个

• YA相差2个，AH相差4个
• HR相差4个，如果还有元素的话，下一个元素与R之间显然相差2个。

• i行的skipDown2*(i-1)，而第一行和最后一行的skipDown都应该为2*(numRows)
• skipDownskipUp是逆序的关系。

string convert(string s, int numRows) {
if (numRows < 2) return s;
vector<int> skipDown(numRows);
vector<int> skipUp(numRows);

skipDown[0] = 2*(numRows-1);
skipUp[0] = 0;
for(int i = 1;i < numRows; i++) {
skipDown[i] = skipDown[i-1] - 2;
skipUp[i] = skipUp[i-1] + 2;
}

skipDown[numRows-1] = skipDown[0];
skipUp[0] = skipUp[numRows-1];

string res(s.size(), ' ');

int index = 0;
for(int i = 0;i < numRows; i++) {
bool flag = true;
for(int j = i;j < s.size();index++) {
res[index] = s[j];

if (flag) { j += skipDown[i]; }
else { j += skipUp[i]; }

flag = !flag;
}
}
return res;
}


LeetCodeLeetCode

Simplify Path

String-to-Integer(atoi)

comments powered by Disqus