面试经典150题——Z 字形变换

题目来源

力扣每日一题；题序：6

我的题解

方法一 使用StringBuilder数组模拟矩阵

如果numRows是1，则直接返回s。
否则，创建numRows长度的StringBuilder数组，模拟生成Z字形变换后的矩阵。最后将StringBuilder数组使用String.join联合起来

时间复杂度：O(n)
空间复杂度：O(n)

public String convert(String s, int numRows) {
    if(numRows==1)
        return s;
    int n=s.length();
    StringBuilder[] sbs=new StringBuilder[numRows];
    for(int i=0;i<numRows;i++)
        sbs[i]=new StringBuilder();
    int i=0;
    int start=0;
    while(n>0){
        //往下走
        while(n>0){
            sbs[i++].append(s.charAt(start++));
            n--;
            if(i==numRows){
                i=numRows-2;
                break;
            }
        }
        //往上走
        while(n>0){
            sbs[i--].append(s.charAt(start++));
            n--;
            if(i==-1){
                i=1;
                break;
            }
        }
    }
    return String.join("", sbs); 
}

//也可以使用List存储
public String convert(String s, int numRows) {
    if(numRows==1)
        return s;
   int n=s.length();
    List[] list=new ArrayList[numRows];
    for(int i=0;i<numRows;i++){
        list[i]=new ArrayList<>();
    }
    boolean flag=false;
    int index=0;
    for(int i=0;i<n;i++){
        list[index].add(s.charAt(i));
        if(!flag){

            if(index+1==numRows){
                index=index-1;
                flag=true;
            }else{
                index++;
            }
        }else{
            if(index-1<0){
                index=1;
                flag=false;
            }else{
                index--;
            }
        }
    }
    StringBuilder sb=new StringBuilder();
    for(int i=0;i<numRows;i++){
        list[i].forEach(sb::append);
    }
    return sb.toString();

}

方法二 找规律+直接构造

研究矩阵的每个非空字符会对应到 s 的哪个下标（记作 idx），从而直接构造出答案。
由于 Z 字形变换的周期为 t=2r−2，因此对于矩阵第一行的非空字符，其对应的 idx均为 t 的倍数，即 idx≡ 0(mod t)；同理，对于矩阵最后一行的非空字符，应满足 idx≡ r−1(mod t)。
对于矩阵的其余行（行号设为 i），每个周期内有两个字符，第一个字符满足 idx ≡ i (mod t)，第二个字符满足 idx ≡ t−i(mod t)。
下图是numRows为4时的规律

时间复杂度：O(n)
空间复杂度：O(1)

public String convert(String s, int numRows) {
    int n = s.length();
    int r = numRows;
    if (r == 1 || r >= n) {
        return s;
    }
    int t = r * 2 - 2;
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < r; i++) { // 枚举矩阵的行
        for (int j = 0; j < n - i; j += t) { // 枚举每个周期的起始下标
            ans.append(s.charAt(j + i)); // 当前周期的第一个字符
            if (i > 0 && i < r - 1 && j + t - i < n) {
                ans.append(s.charAt(j + t - i)); // 当前周期的第二个字符
            }
        }
    }
    return ans.toString();
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~