0x01. 做一道字符串变换的题目

给定一组字符串例按照设定一个行数，以从上到下，从左到右进行Z字形排列。
比如输入的字符串为『ABCEDFGHIJKLMN』，行数设为3的时候，排列如下

[A] [ ] [E] [ ] [I] [ ] [M]
[B] [D] [F] [H] [J] [L] [N]
[C] [ ] [G] [ ] [K] [ ] [ ]

之后，你的输出需要从左往右逐行读取，产生一个新的字符串，比例如『AEIMBDFHJLNCGK』
请设计一个这样的字符串变换函数

0x02. 分析解题思路

拿到这个题目，从最直观的方向入手就是，按照题目示例中的排序方式给逐个字符串扫描，排列到对应规则的位置上。
通俗来说，按照坐标系走（x轴从左到右，y轴从上到下）我们可以分析出下面的坐标点。
A(0,0)
B(0,1)
C(0,2)
D(1,1)
E(2,0)
F(2,1)
G(2,2)
H(3,1)
…
仔细观察排列关系之后，我们不难发现题中说的排列方式按照Z字形其实是一个误导，对程序而言A->G，E->K实际上不是一个可以重复循环处理的方案，我们需要把这种排列切割为A->D，E->H，这样的处理方式可以使程序能够重复循环处理。
可以得到如下伪代码

*p = str[0]
while *p != '\0'{
    if (i<row){
        ... set value
    }else{
        ... set value
    }
    loop++
}

具体代码实现可以拉到文末。

程序解题到这里，其实本题基本上已经解决了，但是如果我们更深层的思考下，这种解题过程是否可以值得更优化下，一定要使用二维数据来填值吗？从题目的立意来看，无非是将字符串重组，既然说到重组无非就是一个权重变化的过程，那么我们可否设计一个方程来计算这种权重呢？ 其实上面的解题里对应的二维数组也是一个权重的表现。二维坐标对应到一维的权重里。

按照x+y*10的思路去做。
A(0,0)->0
B(0,1)->10
C(0,2)->20
D(1,1)->11
E(2,0)->2
F(2,1)->12
G(2,2)->22
H(3,1)->13

按照解题思路一的分块重复的思路，我们惊奇的发现，后面的循环只是对前面的对应位置加2，这就很棒棒哒，只要算出第一块排列的位置，后面的权重就很好计算了。
转换公式x+y*10 中的系数10肯定不是一个好的系数，对于row 大于10的情况就非常容易两个位置出现转换的权重一致的情况，所以在设计公式的时候我们需要把10替换为字符串长度len，这样就可以保证唯一权重。

0x03. 解题代码

php版本，包含2种思路的解题

<?php

$para = getopt("s:n:");

$row = $para["n"] ?? 0;
if ($row < 2) {
    exit("请输入大于2的行数");
}
$str = $para['s'] ?? '';
if (strlen($str) <= 0) {
    exit("请输入要排序的字符串");
}

$output = null;
$len = strlen($str);
$pos = 0;
$i = 0;
$j = 0;
$loop = 1;
while ($pos < $len) {
    for ($i; $i < $row; $i++) {
        if ($pos == $len) {
            break;
        }
//        echo "$i,$j," . $str[$pos] . "\n";

        $output[$i][$j] = $str[$pos];
        $pos++;

    }
//    echo "| \n";
    $i -= 2;
    $j++;
    for ($j; $j < $row * $loop - 1; $j++) {
        if ($pos == $len) {
            break;
        }
//        echo "$i,$j," . $str[$pos] . "\n";
        $output[$i][$j] = $str[$pos];
        $pos++;
        $i--;
        if ($i < 0) {
            $i = 0;
            $pos--;
            break;
        }
    }
    $loop++;
//    echo "- \n";

}

$output2 = '';
for ($n = 0; $n < $row; $n++) {
    for ($m = 0; $m < $j; $m++) {
        echo isset($output[$n][$m]) ? "[" . $output[$n][$m] . "] " : "[ ] ";
        if (isset($output[$n][$m])) {
            $output2 .= $output[$n][$m];
        }
    }
    echo "\n";
}
echo "$output2.\n";

$output3 = [];
$n = 2 * ($row - 1);
$cnt = ceil((float)$len/$n);
$pos = 0;
for ($k = 0; $k < $cnt; $k++) {
    for ($l = 0; $l < $n; $l++) {
        if ($l < $row) {
            $output3[$l * $len + $k * ($row - 1)] = $str[$pos];
            $pos++;
        } else {
            $output3[($n - $l) * $len + $l - $row + 1 + $k * ($row - 1)] = $str[$pos];
            $pos++;
        }
        if ($pos >= $len) {
            break;
        }
    }
}
ksort($output3);

$output3 = array_values($output3);
$len = count($output3);
for ($i = 0; $i < $len; $i++) {
    echo $output3[$i];
}
echo "\n";

C++版本（限于能力问题，C++版本是练手的，写的不好还望大家指出改进）

#include <iostream>
#include <cmath>

int main(int argc, const char *argv[])
{
    int row, len;
    char str[100];
    std::cout << "请输入行数" << std::endl;
    std::cin >> row;
    if (row < 2) {
        std::cout << "请输入大于2的行数";
        exit(1);
    }

    std::cout << "请输入需要排序字符串" << std::endl;
    std::cin >> str;
    len = (int)strlen(str);
    if (len <= 0) {
        std::cout << "请输入需要排序字符串" << std::endl;
    }

    int b = 2 * (row - 1);
    int cnt = ceil((float)len / b);
//    printf("len=%d,b=%d,cnt=%d\n",len,b,cnt);
//    printf("%f\n",ceil(10.0/3));

    int pos = 0;
    char output3[100 * 100] = {};
    for (int k = 0; k < cnt; k++) {
        for (int l = 0; l < b; l++) {
            if (l < row) {
                output3[l * len + k * (row - 1)] = str[pos];
//                printf("竖排:%d,%d,%d,%c\n", k, l, l * len + k * (row - 1), str[pos]);
                pos++;
            } else {
                output3[(b - l) * len + l - row + 1 + k * (row - 1)] = str[pos];
//                printf("斜排:%d,%d,%d,%c\n", k, l, (b - l) * len + l - row + 1 + k * (row - 1), str[pos]);
                pos++;
            }
//            printf("len=%d,pos=%d,k=%d,l=%d\n",len,pos,k,l);
            if (pos >= len) {
                break;
            }
        }
    }
//    len = (int)strlen(output3);
    for (int i = 0; i < 100 * 100; i++) {
        if (output3[i] != '\0') {
            printf("%c", output3[i]);
        }
    }
    printf("\n");
    return 0;
}