# 每日一题（6）：Z字形变换
# 开始
来了来了，最近是比较忙，有断更的时候，大家请见谅~
另外，有部分粉丝看了还给了打赏，在此本人表示非常感谢~
但是希望大家看看就好，真心不用花钱啦，因为也不是特别干的干货，没有帮助到什么的
正文来也
今天这道题呢，和前面一样，都是中等难度的题
在经过前几次刷题之后，我开始倾向于找规律并直接暴力出解
在尝试各种取余操作未果。。终于还是老老实实用编程思维来做了
其实还是那句老话，计算机领域没什么问题不能用抽象一层来解决的
P A H N
A P L S I I G
Y I R
1
2
3
2
3
看到这样的结构，我们可以把它转化成一个List<StringBuilder>
List<StringBuilder> sbs = new ArrayList<>(numRows);
sbs.get(0); // "PAHN"
sbs.get(1); // "APLSIIG"
sbs.get(2); // "YIR"
1
2
3
4
2
3
4
其中，我们需要解决的是，在遍历原串"PAYPALISHIRING"的时候
谁会被分在0组，谁会被分在1组...
可以在脑中模拟一个动画
0 0 0 0
1 1 1 1 1 1 1
2 2 2
1
2
3
2
3
上面的序列其实就是我们需要抽象出来的内容了
也非常适合用队列Queue来存储它们
那么在拿到这个01210121012101序列后
我们就可以完成对字符的分组，最后重组了
下面来看看实现
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
char[] cs = s.toCharArray();
// 获取01210121012101序列
Queue<Integer> zQueue = genZQueue(cs.length, numRows);
// 初始化每个分组的StringBuilder对象
List<StringBuilder> sbs = new ArrayList<>(numRows);
for (int i = 0; i < numRows; i++) {
sbs.add(new StringBuilder());
}
// 核心步骤，在遍历每个字符的时候，得到它应该归属的分组号，并存入该分组
for (char c : cs) {
sbs.get(zQueue.poll()).append(c);
}
// 组装成结果字符串
StringBuilder sb = new StringBuilder();
for (int i = 0; i < numRows; i++) {
sb.append(sbs.get(i));
}
return sb.toString();
}
// 获取01210121012101序列
private Queue<Integer> genZQueue(int l, int numRows) {
Queue<Integer> queue = new LinkedList<>();
// flag表示Z走向此时是向下还是向上
boolean flag = true;
int j = 0;
for (int i = 0; i < l; i++) {
queue.add(j);
if (flag) {
j++;
} else {
j--;
}
// 当碰到边界的时候，调头转向
if (j == 0 || j == numRows - 1) {
flag = !flag;
}
}
return queue;
}
}
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
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
下面看看执行效率
说实话，效率并不是我唯一看重的
其实，官方题解里可能20行左右代码就完成了，并且时间复杂度还是非常优秀的O(n)
但是，看上去会非常生涩难懂
在我们日常解决工程问题的场景下，还是需要让代码的可读性更甚于效率的
合理的抽象也能让代码可维护性更佳，经得起时间的考验
所以哈哈，一通解释为什么效率低了...（其实就是菜...
还是工程思维对我影响比较深远吧
以上就是今天的内容了~感谢阅读
明天继续