glmapper

每天一道算法题:Z字形转换

字数统计: 490阅读时长: 2 min
2018/11/10 Share

题目

将字符串 “PAYPALISHIRING” 以Z字形排列成给定的行数:(下面这样的形状)

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

之后按逐行顺序依次排列:”PAHNAPLSIIGYIR”

实现一个将字符串进行指定行数的转换的函数:

1
string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 3) 应当返回 “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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public String convert(String s, int numRows) {
//计算字符串长度
int len = s.length();
//两个周期之间的列数,
int slash = numRows - 2;
//计算行的长度
int rowLength = 0;
while(len > 0){
//竖列
len = len - numRows;
rowLength++;

//斜着的一列
for(int i = 0; i < slash && len > 0; i++){
len--;
rowLength++;
}
}

//建立一个多一列的数组用于保存我们的字符串,并且全部初始化为空格了
char result[] = new char[numRows* rowLength];
// 初始化为空格
for (int i = 0; i < result.length; i++) {
result[i] = ' ';
}
// 当前处理的行数
int curColumn = 0;
int index = 0;

// 下面将字符串写入所谓的矩阵中
while(index < s.length()){
//写入列
for(int i = 0; i < numRows && index < s.length(); i++){
result[rowLength * i + curColumn] = s.charAt(index);
index++;
}

curColumn++;

//写入斜线
for(int i = numRows - 2; i > 0 && index < s.length(); i--){
result[rowLength * i + curColumn] = s.charAt(index);
curColumn++;
index++;
}
}



// 去空格,定义两个指针循环进行操作
index = 0;
// 找第一个是空格的字符位置
while (index < s.length() && result[index] != ' ') {
index++;
}
int next = index + 1;
while (index < s.length()) {
// 找不是空格的元素
while (next < result.length && result[next] == ' ') {
next++;
}
result[index] = result[next];
index++;
next++;
}
return new String(result, 0, index);
}

这个题目想了两天,之前的思路是建立一个二维数组,然后填充,最后遍历数组拿到结果,但是对于很多边界问题不太好考虑,放弃。这两种方案的首要核心都是计算列数和对斜列的处理,没有数学功底和抽象思维的程序员真的伤不起。

原文作者:GuoLei Song

原文链接:http://www.glmapper.com/2018/11/10/leetcodetwo/

发表日期:November 10th 2018, 1:32:42 pm

更新日期:November 10th 2018, 1:33:08 pm

版权声明:转载请注明出处

CATALOG
  1. 1. 题目
  2. 2. 方案