锯齿形变换-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

**难度: Medium**

> 内容描述

```
字符串“PAYPALISHIRING”以之字形模式写入给定数量的行，如下所示：（您可能希望以固定字体显示此模式，以提高可读性）

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:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

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

```

## 解题方案

> 思路 1
******- 时间复杂度: O(len(s))******- 空间复杂度: O(len(s))******

需要将字符串s转换为按N排列，总共有numRows行，直接将字符串转换为N字形，然后输出, beats 74.18%

```java
class Solution {
    // 将字符串进行z子排列,行数为numRows
    public String convert(String s, int numRows) {
       // 思路：先转换为z字
        List[] arr = new List[numRows]; // 保存每一行元素
        for(int i = 0; i < numRows; i ++){
            arr[i] = new ArrayList();
        }
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length;){
            // 每次打印两列
            for(int j = 0; j < numRows && i < chars.length; j++,i++){
                List list = arr[j];
                list.add(chars[i]);
            }
            for(int j = numRows - 1; j >= 0 && i < chars.length; j --){
                if(j == numRows - 1 || j == 0){
                    arr[j].add(' ');
                }else{
                    arr[j].add(chars[i]);
                    i++;
                }
            }
        }
        // 输出最终字符串
        char[] result = new char[chars.length];
        int index = 0;
        for(int i = 0; i < numRows; i ++){
            List list = arr[i];
            for(int j = 0; j < list.size(); j ++){
                if(' ' != (char)list.get(j)){
                    result[index++] = (char) list.get(j);
                }
            }
        }
        return new String(result);
    }
}
```

该分类下的相关小册推荐：

数据结构与算法之美

编程之道-算法面试(下)

业务开发实用算法精讲

数据结构与算法(下)

数据结构与算法(上)

编程之道-算法面试(上)

算法面试通关 50 讲