[leetcode]No.6 Z 字形变换

[liangbus]

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

No.6 Z 字形变换

该题画图很快就可以得知规律

我首先想到的是用一个二维数组来实现
思路大概如此，遍历字符串，同时判断目前的插入方向是往下，还是往上，据此来确定 row, 和 col 的值，最后再重新遍历二维数组来解构输出结果

var convert = function(s, numRows) {
    if(numRows === 1) return s
    const rect = []
    let i = 0
    while(i++ < numRows) {
        rect.push(
            new Array()
        )
    }
    let row = 0, col = 0
    const len = s.length
    let down = true
    i = 0
    while(i < len) {
        rect[row][col] = s[i++]
        if(row === numRows - 1) {
            down = false
        } else if(row === 0) {
            down = true
        }
        row = down ? row + 1 : row - 1
        col = down ? col : col + 1
    }
    let res = rect.map(row => {
        return row.filter(char => char).join('')
    })
    return res.join('')
};

Emm.. 初版，居然还真跑过了，虽然效率不高

再以初版为基础，优化一下
其实没必要弄二维数组，一维数组同样可以实现，只不过每个元素不再存单个字符，因为这里对列也没有要求，只是要求最终的字符，所以不需要关心每个字符的真正位置

var convert = function(s, numRows) {
    if(numRows === 1) return s
    const rect = new Array(numRows).fill("");
    let i = 0, row = 0, down = true
    const len = s.length
    while(i < len) {
        rect[row] += s[i++]
        if(row === numRows - 1) {
            down = false
        } else if(row === 0) {
            down = true
        }
        row = down ? row + 1 : row - 1
    }
    return rect.join('')
};

优化之后的内存使用有了极大的提高，执行效率了翻了几倍，还不错~