[leetcode] 6. ZigZag Conversion

[leetcode] 6. ZigZag Conversion

Description

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

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 NA L S I GY A H RP I

分析

题目的意思是：把字符串转换成之字形的然后输出。

比如有一个字符串 “0123456789ABCDEF”，转为zigzag 当 n = 2 时：

0 2 4 6 8 A C E1 3 5 7 9 B D F

当 n = 3 时：

0 4 8 C1 3 5 7 9 B D F2 6 A E

当 n = 4 时：

0 6 C1 5 7 B D2 4 8 A E3 9 F

除了第一行和最后一行没有中间形成之字型的数字外，其他都有，而首位两行中相邻两个元素的index之差跟行数是相关的，为 2*nRows - 2,

根据这个特点，我们可以按顺序找到所有的黑色元素（例如n=4中的第一列）在元字符串的位置，将他们按顺序加到新字符串里面对于红色元素出现的位置也是有规律的，每个红色元素（例如n=4中的第二列）的位置为 j + 2nRows-2 - 2i, 其中，j为前一个黑色元素的列数，i为当前行数。比如当n = 4中的那个红色5，它的位置为 1 + 24-2 - 21 = 5，为原字符串的正确位置。当我们知道所有黑色元素和红色元素位置的正确算法，我们就可以一次性的把它们按顺序都加到新的字符串里面。

代码

class Solution {public: string convert(string s, int numRows) { if(numRows<=1){ return s; } string res=""; int len=2*numRows-2; for(int i=0;i

参考文献

​​[编程题]zigzag-conversion​​​​[LeetCode] ZigZag Converesion 之字型转换字符串​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。