首页 > 代码库 > LeetCode第六题,ZigZag Conversion
LeetCode第六题,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"
.题意解析:
The key here is to figure out the index pattern, just draw several concrete example could hele:
nRow = 2: 0 2 4 6 8 10 12 1 3 5 7 9 11 13 nRow = 3: 0 4 8 12 1 3 5 7 9 11 2 6 10 nRow = 4: 0 6 12 1 5 7 11 13 2 4 8 10 3 9第0, len-1行各个字符之间的间隔为2×nRows - 2
第1~len-2行之间会有两个固定间隔之间会有其他字符插入规律:index + 2 * nRows - 2 * i - 2, 这里i是指行号
public class Solution { public static String convert(String s, int nRows) { // Start typing your Java solution below // DO NOT write main() function if (s == null || s.length() == 0 || nRows <= 1) { return s; } String result = generate(s, nRows); return result; } private String generate(String s, int nRows) { int len = s.length(); StringBuffer buffer = new StringBuffer(); int diff = 2 * nRows - 2; for (int i = 0; i < nRows && i < len; i++) { if (i == 0 || i == nRows - 1) { buffer.append(s.charAt(i)); int index = i; while (index + diff < len) { buffer.append(s.charAt(index + diff)); index = index + diff; } // int tmp = i; // while (i + diff < len) { // buffer.append(s.charAt(i + diff)); // i = i + diff; // } // i = tmp; } else { buffer.append(s.charAt(i)); // int tmp = i; int index = i; while (2 * nRows - 2 * i - 2 + index < len || index + diff < len) { if(2 * nRows - 2 * i - 2 + index < len){ buffer.append(s.charAt(2 * nRows - 2 * i - 2 + index)); } if (index + diff < len) { buffer.append(s.charAt(index + diff)); } index += diff; } // while (2 * nRows - i - 2 < len || i + diff < len) { // if (2 * nRows - i - 2 < len && 2 * nRows - i - 2 >= 0) { // buffer.append(s.charAt(2 * nRows - i - 2)); // } // if (i + diff < len) { // buffer.append(s.charAt(i + diff)); // } // i = i + diff; // } // i = tmp; } } return buffer.toString(); } }
class Solution { public: string convert(string s, int nRows) { // Start typing your C/C++ solution below // DO NOT write int main() function string result; if (nRows < 2) return s; for (int i = 0;i < nRows;++i) { for (int j = i;j < s.length();j += 2 * (nRows - 1)) { result.push_back(s[j]); if (i > 0 && i < nRows - 1) { if (j + 2 * (nRows - i - 1) < s.length()) result.push_back(s[j + 2 * (nRows - i - 1)]); } } } return result; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。