---
# System prepended metadata

title: 0006. ZigZag Conversion
tags: [Leetcode, Medium, Math]

---

#  0006. ZigZag Conversion
###### tags: `Leetcode` `Medium` `Math`
Link: https://leetcode.com/problems/zigzag-conversion/
## 思路
### 思路一
自己想出来哒，画图然后找规律
可以发现 

对于n行的, s中的第i个字符：
对余数进行判断
i%(2n-2) == 0 ----> row0
i%(2n-2) == 1 & 2n-2-1 ----> row1
i%(2n-2) == 2 & 2n-2-2 ----> row2
...
i%(2n-2) == n-1 ----> row(n-1)
==>
对 k = i%(2n-2)进行判断
k<=n-1时候，s[i]就属于第k行
k>n-1时候，s[i]就属于2n-2-k行
最后将rows拼接起来就行了
### 思路二
暴力解法
从左到右迭代 ss，将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。

只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会发生改变。
## Java Code
### 思路一
```java=
class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1){
            return s;
        }
        List<StringBuilder> rows = new ArrayList<>();
        for(int i = 0;i < numRows;i++){
            rows.add(new StringBuilder());
        }
        char[] sArray = s.toCharArray();
        for(int i = 0;i < s.length();i++){
            if(i%(2*numRows-2)>numRows-1){
                rows.get(2*numRows-2-i%(2*numRows-2)).append(sArray[i]);
            }
            else{
                rows.get(i%(2*numRows-2)).append(sArray[i]);
            }
        }
        StringBuilder ret = new StringBuilder();
        for(StringBuilder row:rows){
            ret.append(row);
        }
        return ret.toString();
    }
}
```
###  思路二
```java=
class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        List<StringBuilder> rows = new ArrayList<>();
        for(int i = 0;i < Math.min(numRows,s.length());i++){
            rows.add(new StringBuilder());
        }
        int currRow = 0;
        boolean goDown = false;
        for(char c:s.toCharArray()){
            rows.get(currRow).append(c);
            if(currRow == 0||currRow == numRows-1){
                goDown = !goDown;
            }
            currRow += goDown?1:-1;
        }
        StringBuilder ret = new StringBuilder();
        for(StringBuilder row:rows){
            ret.append(row);
        }
        return ret.toString();
    }
}

```
## Result
### 思路一
Runtime: 6 ms, faster than **54.81%** of Java online submissions for ZigZag Conversion.
Memory Usage: 39.5 MB, less than **71.22%** of Java online submissions for ZigZag Conversion.
### 思路二
Runtime: 6 ms, faster than **54.81%** of Java online submissions for ZigZag Conversion.
Memory Usage: 39.5 MB, less than **71.22%** of Java online submissions for ZigZag Conversion.
## 注意
- StringBuilder的使用，比用String效率更高，因为要不断拼接
- 给StringBuilder对象拼接的函数：append
- StringBuilder转换String：toString
- 为什么写List```<StringBuilder> rows = new ArrayList<>();```而不是new List？因为List是个接口不能实例化，可以实例化的有ArrayList、LinkedList
- ArrayList的size是可以不断改变的，也就是随时可以增删东西
