LeetCode第六题——字符串的Z字型转化

发表于 | 分类于 | | 阅读次数:
字数统计: 549 | 阅读时长 ≈ 2

再不刷几道算法题脑子一定是锈完了，废话不说，直接上题。

字符串"PAYPALISHIRING"以”zigzag”形式写出，如：

P A H N
A P L S I I G
Y I R

若一行一行读，则字符串变为："PAHNAPLSIIGYIR"。

要求写一个给定字符串和指定行数的转换程序，例如：

convert("PAYPALISHIRING", 3)返回"PAHNAPLSIIGYIR"。

思路

意思比较容易理解，即将一个字符串以“Z”字型排布后，返回按行读取的字符串。

第一想法：建立一个二维数组strArray,用strArray[x][y]保存每一个字符，最后按照数组的路径读取。

草稿纸上写了伪代码就多的不要不要的，各种某个位置得挨个判断是否为空，于是换一种思路。

以输入"PAYPALISHIRING"为例，仔细观察形式，我们可以把每个元素按照下图所示分组：
test

那么，按以下方式即可直接取到需求字符串：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//先去每组的首字母，即第一排
group[0][0]  =>  P
group[1][0]  =>  A
group[2][0]  =>  H
group[3][0]  =>  N
//再依次取每一行的两个元素
group[0][1]  =>  A
group[0][-1] =>  P //-1表示倒数第1个元素
group[1][1]  =>  L
group[1][-1] =>  S
group[2][1]  =>  I
group[2][-1] =>  I
group[3][1]  =>  G
group[3][-1] =>  不存在
//最后一行一个字母
group[0][2]  => Y
group[1][2]  => I
group[2][2]  => R

任意字符串均可按此思路计算。

实现

按照上面的思路，利用两层循环实现算法，代码如下：

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
public class Solution {
    public String convert(String s, int numRows) {
        if (numRows <= 1) {
            return s;
        }
        int group = numRows * 2 - 2;
        int strLen = s.length();
        int groupNum = strLen%group == 0 ? strLen/group : strLen/group+1;
        boolean flag = true;
        int x=0,y=0;
        StringBuilder sb = new StringBuilder();
		for(int i=0;i<numRows;i++){
            for(int j=0;j<groupNum;j++){
                if(i == 0 || i == numRows-1) {
                    //第一组或，只遍历第组里一个元素
                    int pos = i+group*j;
                    if(pos<strLen){
                        sb.append(s.charAt(pos));
                    }
                }else{
                    int pos1 = i+group*j;
                    int pos2 = (group-i)+group*j;
                    if(pos1<strLen){
                        sb.append(s.charAt(pos1));
                    }
                    if(pos2<strLen){
                        sb.append(s.charAt(pos2));
                    }
                }
            }
        }
        return sb.toString();
    }
}

提交，Accepted!

0%