Z 字形变换

其实这道题就是移到数学题

分析

以 LEETCODEISHIRING 为示例，分别对row = 3, row = 4, row = 5, 进行分析, 括号表示index

row = 3

row/column c = 0 c = 1 c = 2 c = 3 c = 4 c = 5 c = 6 c = 7
r = 0 L(0) C(4) I(8) R(12)
r = 1 E(1) T(3) O(5) E(7) S(9) I(11) I(13) G(15)
r = 2 E(2) D(6) H(10) N(14)

row = 4

row/column c = 0 c = 1 c = 2 c = 3 c = 4 c = 5 c = 6
r = 0 L(0) D(6) R(12)
r = 1 E(1) O(5) E(7) I(11) I(13)
r = 2 E(2) C(4) I(8) H(10) N(14)
r = 3 T(3) S(9) G(15)

row = 5

row/column c = 0 c = 1 c = 2 c = 3 c = 4 c = 5 c = 6 c = 7
r = 0 L(0) I(8)
r = 1 E(1) E(7) S(9) G(15)
r = 2 E(2) D(6) H(10) N(14)
r = 3 T(3) O(5) I(11) I(13)
r = 4 C(4) R(12)
  • 我们看这三个 r = 0时，第一个数跟第二数的偏移， 我们称这个为总偏移量
    • row = 3时, 偏移为 4 - 0 = 4
    • row = 4时，偏移为 6 - 0 = 6
    • row = 5时，偏移为 8 - 0 = 8
    • 总结： 偏移 = 2 * row - 2
  • 再看 r = 1时，就是第二行数据， 第一个数跟第二个数以及第三个数的偏移
    • row = 3 时，偏移为 3 - 1 = 2， 5 - 3 = 2， 上面总偏移量为4，所以第3个数跟第2个数的偏移量为 4-2 =2
    • row = 4 时，偏移为 5 - 1 = 4， 7 - 5 = 2， 上面总偏移量为6，所以第3个数跟第2个数的偏移量为 6-4 =2。 这一行往后的偏移是 4, 2, 4, 2, 4, 2 这样走
    • row = 5 时，偏移为 7 - 1 = 6， 9 - 7 = 2， 上面总偏移量为8，所以第3个数跟第2个数的偏移量为 6-4 =2。 这一行往后的偏移是 6, 2, 6, 2, 6, 2 这样
    • 直到前一个数 + 偏移量 >= s.length换下一行。
    • 总结：第一个数与第二个数偏移量为 2 * (row - (r + 1)), 而第二个数跟第三个数的偏移量为 （总偏移量 - 第一个数跟第二个数的偏移量）
  • 往后如此类推，但最后一行跟第一行的偏移量应该一样

源码

var convert = function(s, numRows) {
    let result = [];
    let length = s.length;
    if(numRows == 1) {
        return s;
    }
    let totalOffset = 2 * numRows - 2; // 总偏移量
    let flag = true;  // 标志位
    let i = 0;      // 表示数组中有几个数
    let row = 1;    // 表示 第几行
    let start = 0;  // 表示 当前index
    let offset = 2 * (numRows - row);
    while(i < length) {
        result.push(s[start]);
        // 第一行的偏移量跟最后一行的偏移量一样
        if(row == 1 || row == numRows) {
            start = start + totalOffset;
        } else {
            if(flag) {
                start = start + offset;
                flag = false;
            } else {
                start = start + (totalOffset - offset);
                flag = true;
            }
        }

        i++;
        // 换下一行，同时计算他的偏移值，把flag 重置
        if(start >= length) {
            row++;
            start = row - 1;
            flag = true
            offset = 2 * (numRows - row);
        }
    }
    return result.join("")
};