6. Z 字形变换

二维数组模拟

就是找出放单词位置的规律出来

var convert = function(s, numRows) {
    //如果要求的行数都超过了字符串的长度或者本身行数要求就为1
    const n=s.length,r=numRows;
    if(r === 1 || r>=n){
        return s;
    }
    //设每隔一定的周期字符串都会排成对应的 ‘V’ 字符
    //可以发现当向下排R个时，到新的第一行的中间有R-2个字母
    //因此可以让行变为  r+ r -2= 2*r-2
    const ar=r*2-2;
    //可以让每个周期 T 的列变为 1 + r-2
    //那么行是固定的，列一共为 (r-1) * T 
    //根据观察T 为 [s.length-1]/(2*r-2) + 1
    //因为认为最后一个周期为完整周期 像个'l'也不是没可能
    const c=Math.floor((n+ ar -1)/ar)*(r-1);
    //构建一个仅为值引用的二维数组
    const mat=new Array(r).fill(0).map(()=>new Array(c).fill(0));
    let x=0,y=0;
    //先遍历字符串
    for(let i=0;i<n;i++){
        mat[x][y]=s[i];
        // 如果满足 i mod ar < r-1的条件，则就要向下画
        if(i% ar <r-1){
            ++x;
        //而不满足的话，就是要向右上开始画了。
        }else{
            --x;
            ++y;
        }
    }
    //之后就要按照题目规则重新弄成新的字符串
    const res=[];
    //获取每行的单词组
    for(const row of mat){
        //再根据每列获取单个单词
        for (const ch of row){
            if(ch !==0){
                res.push(ch);
            }
        }
    }
    return res.join('');
};

复杂度分析

时间复杂度：\(O(r\cdot n)\)，其中 \(r=\textit{numRows}\)，\(n\) 为字符串 \(s\) 的长度。

空间复杂度：\(O(r\cdot n)\)。