中通建设计院网站,wordpress 空间商,北京免费建网站,邯郸网站制作官网关键字#xff1a;数学归纳法 一、题目 将一个给定字符串 s 根据给定的行数 numRows #xff0c;以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 PAYPALISHIRING 行数为 3 时#xff0c;排列如下#xff1a; P A H N
A P L S I I G
Y I R … 关键字数学归纳法 一、题目 将一个给定字符串 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个13n - 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)-n0?(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((i1) / (2n-2)))*(n-1) ((i1) % (2n-2)-n0?(n-2)1:((i1) % (2n-2) 0?0:1) 所在行row (i1)%(2n-2) n?((i1)%(2n-2)0?2:(i1)%(2n-2)):2n-(i1)%(2n-2) 3、 遍历字符串把每个字符放在对应的位置上
4、再按行从左到右取字符
五、完整代码
let convert function(s,numRows 3){let n numRows;let len s.length;let m 0let 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 (i1)%(2*n-2)let col (Math.floor((i1)/(2*n-2)))*(n-1) (remainder1-n0?(n-2)1:(remainder1 0?0:1))col col -1 // 从0列开始let row remainder1 n?remainder1:2*n-remainder1if(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
