Joyce' Blog
0%

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)

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
/*
思路：找出每一行的字母位置的规律，具体做法是将所有的字母分组，每一组是一个'v'字形，
每一组中，除了最上面一行和最下面一行，都会有两个间隔规律的字母处于同一行中
*/
string zigzag(string s, int numRows)
{
	if (numRows == 1)
		return s;
	string* r=new string[numRows];
	for (int i = 0; i < numRows; ++i)
	{
		r[i] = "";
	}
	int groupSize = 2 * numRows - 2;//组的大小
	int size = s.length();
	for (int i = 0; i < numRows; ++i)
	{
		int j = i;
		while (j < size)
		{
			//若没有在最开始讨论“只有一行”的情况，这里会进入死循环
			r[i] += s[j];
			int k = 2 * (numRows - i - 1) ;//每一组中处于同一行的字母的间隔
			if (k > 0 &&(i)&& ((j + k) < size))
				//不是最上面一行和最下面一行，并且小于总字符串长度
				r[i] += s[j + k];
			j += groupSize;//查找每个组
		}
	}
	string res = "";
	for (int i = 0; i < numRows; ++i)
	{
		res += r[i];
	}
	return res;
}
int main()
{
	string s1 = "PAYPALISHIRING";
	int num1 = 3;
	cout << zigzag("AB", 2) << "\n";
	system("pause");
	return 0;
}

学习一个更精简的解决方法：

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

        if (numRows == 1) return s;

        vector<string> rows(min(numRows, int(s.size())));
        int curRow = 0;
        bool goingDown = false;

        for (char c : s) {
            rows[curRow] += c;
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }

        string ret;
        for (string row : rows) ret += row;
        return ret;
    }
};

复杂度比最上面的做法低，依次遍历总的字符串，比较巧的地方是改变子字符串的行号，用goingDown表示此时向上（+1）还是向下（-1）走，若是此时curRow是最上面一行或最下面一行，则变换方向，即goingDown取反。