LeeCode [N字形变换]算法解析

关键字：数学归纳法

一、题目

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

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

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，

比如："PAHNAPLSIIGYIR"。

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

convert(s, numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

二、思路：使用数学归纳法对Z字形排列进行规律总结

// 3阶Z变形 7个1

// 1    1

// 1 1 1

// 1    1

// 4阶Z变形 10个1

// 1         1

// 1     1  1

// 1  1     1

// 1         1

// 5阶Z变形 13个1

// 1            1

// 1        1  1 

// 1     1     1 

// 1  1        1 

// 1            1

// ........

// n阶Z变形

// 得到公式，n阶:3n-2个1，3n - 2 = n + (n-2) + n

经过以上归纳，我们知道了对于Z字变形的一个数学上的规律，这里的n就是题目中的numRows变量。同时从图形上看，我们可以把一个V形看成一个周期（如下图，表示3个周期），确定这个思想有利于理解后面的逻辑。

1            1             1

1        1  1         1  1        1

1     1     1      1     1     1

1  1        1   1        1   1

1            1             1

三、现在我们知道了这样一个规律，那么我们很容易想到把字符串按照这样的规律放进到一个二维数组里面，所以，我们需要基于我们发现的规律来分析出两个关键点：

• 二维数组的行列数
• 每一个字符在二维数组中的位置

四、实现步骤

1、定义一个二维数组,二维数组为arr[n-1][m-1],n为行数,m为列数，s为字符串

m = (Math.floor(s.length / (2n-2)))*(n-1) + (s.length % (2n-2)-n>0?(n-2)+1:(s.length % (2n-2) === 0?0:1)；这里把(n + (n-2))看成一个周期

// 粗略一点的话，m也可以直接等于 Math.ceil(s.length/(2n - 2))*(n-1）

2、每个字符在二维数组中的位置（同样用到了数学归纳法）

 假设字符的索引为i：

所在列：col = (Math.floor((i+1) / (2n-2)))*(n-1) + ((i+1) % (2n-2)-n>0?(n-2)+1:((i+1) % (2n-2) === 0?0:1)

所在行：row = (i+1)%(2n-2) <=n?((i+1)%(2n-2)===0?2:(i+1)%(2n-2)):2n-(i+1)%(2n-2) 

3、 遍历字符串，把每个字符放在对应的位置上

4、再按行，从左到右取字符

五、完整代码

let convert = function(s,numRows = 3){
    let n = numRows;
    let len = s.length;
    let m = 0
    let arr = new Array(n);
    if(len < (3 * numRows - 2)){
        return s
    }
    m = (Math.floor(len/(2*n-2)))*(n-1)
    let remainder = len%(2*n-2)
    if(remainder !== 0){
        m += (remainder - n > 0?(n-2)+1:1)
    }
    for(let i = 0;i < n;i++){
        arr[i] = new Array(m);
    }
    // 遍历字符串
    for(let i = 0;i < len;i++){
        let remainder1 = (i+1)%(2*n-2)
        let col = (Math.floor((i+1)/(2*n-2)))*(n-1) + (remainder1-n>0?(n-2)+1:(remainder1 === 0?0:1))
        col = col -1 // 从0列开始
        let row = remainder1 <= n?remainder1:2*n-remainder1
        if(remainder1 === 0){
            row = 2
        }
        row = row - 1 // 从0行开始
        arr[row][col] = s[i]
    }
 
    // 按行从左向右取字符串
    let result = '';
    for(let i = 0;i < n;i++){
        for(let j = 0;j < m;j++){
            if(arr[i][j]){
                result += arr[i][j]
            }
        }
    }
 
    console.log(arr)
    console.log(result)
}
convert("PAYPALISHIRING",3) //输出：PAHNAPLSIIGYIR
convert("PAYPALISHIRING",4) //输出：PINALSIGYAHRPI