首页 > itarticle > LeetCode-Zigzag Conversion

LeetCode-Zigzag Conversion

admin 11月 12, 2020 0

题目

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)

1
2
3
 
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:

1
 
string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return PAHNAPLSIIGYIR.

解题思路

0123456789 nRows = 2

1
2
 
0 2 4 6 8
1 3 5 7 9

Output:
0 2 4 6 8 1 3 5 7 9

0123456789 nRows = 3

1
2
3
 
0   4   8
1 3 5 7 9
2   6

Output:
0 4 8 1 3 5 7 9 2 6

0123456789 nRows = 4

1
2
3
4
 
0     6
1   5 7
2 4   8
3     9

Output:
0 6 1 5 7 2 4 8 3 9

每个Zigzag包含的字符为 size = nRows + nRows - 2
每次跨度一个之，第一行和最后一行只需要添加一个字符，中间每一行需要添加两个字符
第二个字符和前面添加这个字符在s的index相差size - 2 * index

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
public String convert(String s, int numRows) {

	if (s == null || s.length() == 0 || numRows <= 0)
		return "";

	if (numRows == 1)
		return s;

	StringBuilder res = new StringBuilder();
	int size = 2 * numRows - 2;

	for (int i = 0; i < numRows; i++) {
		for (int j = i; j < s.length(); j += size) {
			res.append(s.charAt(j));
			if (i != 0 && i != numRows - 1) {
				int temp = j + size - 2 * i;
				if (temp < s.length())
					res.append(s.charAt(temp));
			}
		}
	}
	return res.toString();
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能