题目描述

ZigZag Conversion

PAYPALISHIRING 按照给定行数 3 的Z型（更像是 N型）变换如下：

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

然后按行返回 PAHNAPLSIIGYIR ，即需实现一个转换函数 string convert(string s, int rows);

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

行数改为 4 如下:

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

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

javascript:

/**
 * @param {string} s
 * @param {number} rows
 * @return {string}
 */
var convert = function(s, rows) {

};

From leetcode No.6 Medium (opens new window)

解法

第一版

点击查看

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
const convert = function (s, numRows) {
    const ret = iter(s, numRows)
    // console.log(ret)
    return ret.reduce((acc, curr) => {
        return acc + curr.filter(x => x !== ' ').join('') 
    }, '')

    function iter(s, numRows) {
        const len = s.length

        if (numRows <= 1) {
            return s.split().map(x=>[x])
        }
        if (len <= numRows) {
            let ret = new Array(numRows)
            for (let i = 0; i < numRows; i++) {
                ret[i] = s[i] ? [s[i]] : [' ']
            }
            return ret
        } else if (len > numRows && len <= numRows * 2 - 2) {
            let ret = new Array(numRows)
            let col = len - numRows + 1
            for (let i = 0; i < numRows; i++) {
                ret[i] = [s[i]]
                for (let j = 1; j < col; j++) {
                    ret[i][j] = ' '
                    if (i === numRows - j - 1) {
                        ret[numRows - j - 1][j] = s[numRows + j - 1]
                    }
                }
            }
            return ret
        } else {
            let ret = new Array(numRows)
            let n = Math.ceil(len / (2 * numRows - 2))

            for (let i = 0; i < n; i++) {
                let unit = iter(s.substring((2 * numRows - 2) * i, (2 * numRows - 2) * (i + 1)), numRows)
                for (let i = 0; i < numRows; i++) {
                    ret[i] = ret[i] ? ret[i].concat(unit[i]) : unit[i]
                }
            }
            return ret
        }
    }

};

修改后

点击查看

/**
 * @param {string} s
 * @param {number} rows
 * @return {string}
 */
const convert = function (s, rows) {
    const ret = iter(s, rows)
    // console.log(ret)
    return ret.reduce((acc, curr) => {
        return acc + curr.filter(x => x !== ' ').join('') 
    }, '')

    function iter(s, rows) {
        const len = s.length
        const unit = 2 * rows - 2

        if(rows <= 1){
            return s.split().map(x=>[x])
        }
        if (len <= unit) {
            let ret = new Array(rows)
            let cols = len - rows + 1
            for (let i = 0; i < rows; i++) {
                ret[i] = [s[i]]
                for (let j = 1; j < cols; j++) {
                    ret[i][j] = ' '
                    if (i === rows - j - 1) {
                        ret[rows - j - 1][j] = s[rows + j - 1]
                    }
                }
            }
            return ret
        } else {
            let ret = new Array(rows)
            let n = Math.ceil(len / unit)

            for (let i = 0; i < n; i++) {
                let group = iter(s.substring(unit * i, unit * (i + 1)), rows)
                for (let i = 0; i < rows; i++) {
                    ret[i] = ret[i] ? ret[i].concat(group[i]) : group[i]
                }
            }
            return ret
        }
    }

};

总结

很有意思的一道题，相当于把字符串打印成 N字形输出。 我自己的思路是：

1. 找规律
2. 面向错误编程。。

规律不难找到，因为具备重复性。
根据数学知识，可以分析出字符串长度(len), 输出图形的行数(rows) 和列数(cols) 之间的关系。
这里N 字形的规律是最小单元由 (rows + rows -2) 个字符组成，共 (1 + rows -2)列。

总共分为三种情况：

• 当列数 为 1时是特殊情况
• 当列数不足或刚好为一个最小单元时的情况容易枚举出
• 如果列数超过一个单元，那肯定是 n个单元, n = Math.ceil(len / (rows + rows -2))，然后按顺序拼接

比较关键是超过一个单元的情况等于 n个单元的推理。这里是我纠结比较久的地方，一开始把一个单元拆得太细：

• 只有一列的情况
• 超过一列，不足或刚好一个单元的情况
• n个完整单元 + 一列的情况
• n个完整单元 + 超过一列的情况

后来测试的时候豁然开朗，一个单元的枚举完后，后续只要超过一个单元，它都是当前一个单元的情况的 n次重复！

以我的经验，这里是典型符合递归的逻辑，因此写了一个递归。并且为了配合打印输出的需求，使用了多维数组。

看了下答案，提供的两种实现方法发现完全是另一种思路…… 好吧，完全跑偏了考点，比较认可Visit by Row的思路:

• 第一行的规律为 k*(2*rows -2)
• 最后一行的规律为 k*(2*rows-2) + rows - 1, 即为第一行的固定偏移
• 中间行的规律为 k*(2*rows -2) + i 及 (k+1)(2*rows-2) - i ( 0 < i < rows-1 )

捋下思路，突破口是第一行的规律，要确定下来按行读取的思路。
接着不难发现最后一行间隔的规律：固定间隔一个最小单元。
中间行的规律是：在一个最小单元内，中间行固定只有两个点。
第一个点可以按照首行规律顺延，至此，第二个点的规律也不难找到

重新实现如下：

点击查看

/**
 * @param {string} s
 * @param {number} rows
 * @return {string}
 */
const convert = function (s, rows) {
    const len = s.length
    const unit = 2 * rows - 2
    let ret = ''
    const tmp = []
    if (rows === 1)
        return s
    for (let row = 0; row < rows; row++) {
        for (let i = 0; i + row < len; i += unit) {
            ret += s[row + i]
            if (row != 0 && row != rows - 1 && i + unit - row < len) {
                ret += s[i + unit - row]
            }
        }
    }
    return ret

};