[LeetCode] 6. ZigZag Conversion zig-type conversion string
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"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:P I N
A L S I G
Y A H R
P I
After reading this question for a long time, I didn't understand how it changed. After searching for some information online, I finally understood it. I wanted to put the string into a zigzag, for example, there is a string "0123456789ABCDEF", which is converted to zigzag as shown below:
When n = 2:
0 2 4 6 8 A C E
1 3 5 7 9 B D F
When n = 3:
0 4 8 C
1 3 5 7 9 B D F
2 6 A E
When n = 4:
0 6 C
1 5 7 B D
2 4 8 A E
3 9 F
It can be found that except for the number in which the first line and the last line do not have zigzags formed in the middle, there are all others, and the difference between the index of the two adjacent elements in the first two lines is related to the number of lines, which is 2*nRows - 2. According to this feature, the positions of all black elements in the metastring can be found in order and added to the new string in order. For where the red element appears (the color may not be displayed properly on Github, seePosts on the Blog Garden) is also regular, the position of each red element is j + 2 x numRows-2 - 2 x i, where j is the index of the previous black element and i is the current number of rows. For example, when the red 5 in n = 4 has a position of 1 + 2 x 4-2 - 2 x 1 = 5, which is the correct position of the original string. Knowing the correct algorithm for the positions of all black elements and red elements, you can add them to the new string in order at once. The code is as follows:
Solution 1:
class Solution {
public:
string convert(string s, int numRows) {
if (numRows <= 1) return s;
string res;
int size = 2 * numRows - 2, n = ();
for (int i = 0; i < numRows; ++i) {
for (int j = i; j < n; j += size) {
res += s[j];
int pos = j + size - 2 * i;
if (i != 0 && i != numRows - 1 && pos < n) res += s[pos];
}
}
return res;
}
};
If the rules in the above solution are not easy to imagine, we can also use the following more direct method to create a string array of size numRows, in order to store the entire zigzag array and then splice the characters of each line together, which is the desired result. The order is to traverse by column. First, the first numRows characters exist in the first position of each line in order, and then the connection position of the '' glyph. You can find that they are actually in the line number interval [1, numRows-2]. Just take the characters in order. Finally, splicing each line together is the request. See the code as follows:
Solution 2:
class Solution {
public:
string convert(string s, int numRows) {
if (numRows <= 1) return s;
string res;
int i = 0, n = ();
vector<string> vec(numRows);
while (i < n) {
for (int pos = 0; pos < numRows && i < n; ++pos) {
vec[pos] += s[i++];
}
for (int pos = numRows - 2; pos >= 1 && i < n; --pos) {
vec[pos] += s[i++];
}
}
for (auto &a : vec) res += a;
return res;
}
};
This is the end of this article about C++ implementing LeetCode (6. Font-Converting Strings). For more related contents of C++ implementing Font-Converting Strings, please search for my previous articles or continue browsing the following related articles. I hope everyone will support me in the future!