首页 > 代码库 > 【Leet Code】ZigZag Conversion
【Leet Code】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 RAnd 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"
.题目的意思就是把一个string从头到尾按下面的方式排放(以四行为例):
然后再以{‘1’‘7’‘13’} {‘2’‘6’‘8‘’12‘} {’3‘’5‘’9‘’11‘} {’4‘’10‘},给定的行数已经在传递参数的时候确定了,我们要分开处理每一行;
注意看两个纵列{1,2,3,4}和{7,8,9,10},相差刚好为 2 * nRows - 2;
(而除了第一行和最后一行,其他行中间还隔着一个字符,而这个与字符的位置刚好相差 (nRows - i - 1) * 2 , i 是当前行<0开始>)
再加入越界的判断,我们可以得到下面算法:
class Solution { public: string convert(string s, int nRows) { if( nRows <= 1 ) { return s; } string ret{}; int len = s.length(); int add = 2 * nRows - 2; for( int i = 0; i < nRows; i++ ) { for(int j = i; j < len; j+=add) { ret += s[j]; if (i != 0 && i != nRows - 1 && j + (nRows-i-1) * 2 < s.length()) { ret += s[j + (nRows-i-1) * 2]; } } } return ret; } };
【Leet Code】ZigZag Conversion
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。