06. Z字形变换

Zad • • 杂文

06. Z字形变换

难度中等610收藏分享切换为英文关注反馈

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

解法一：利用周期特性

根据z字排列的特性，发现字符串成周期排列，周期为2 * numRows -2，
发现第n行的元素，为每个周期的第i个或者第（周期-i）个

    public static String convert1(String s, int numRows) {
        if(numRows == 1) return s;
        int len = s.length();
        int cycle = 2 * numRows -2;
        StringBuilder sBuffer = new StringBuilder(len);
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < len; j++) {
                if (j % cycle == i || j % cycle == (cycle - i)) {
                    sBuffer.append(s.charAt(j));
                }
            }
        }       
        return sBuffer.toString();
    }

时间复杂度：O(n)，其中 n == len（s）* numRows。每个索引被访问 numRows 次。
空间复杂度：O(n)。创建了一个 len（s）大小的StringBuilder。

解法二：第一种解法的升级

去掉了跳过了许多没必要的检测，省去了大量的时间

算法：

每次一行一行访问，对于第k个周期：

  • 首先，先对边界行，做出判断：
    • 第0行字符位于 k * ( 2 * numRows - 2 ) 处
    • 第numRows - 1 行中字符位于索引 k * （ 2 * numRows -2 ）+numRow - 1
  • 其次，处理中间一般行：
    • 第i行中的字符位于索引 k * （ 2 * numRows - 2 ）+ i 以及（ k + 1）*（2 * numRows - 2 ）- i 处
    public static String convert2(String s, int numRows) {
        if(numRows == 1) return s;
        int len = s.length();
        int cycle = 2 * numRows -2;
        StringBuilder sBuilder = new StringBuilder(len);
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < len; j += cycle) {
                sBuilder.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycle - i < len)
                    sBuilder.append(s.charAt(j + cycle - i));
            }
        }
        return sBuilder.toString();
    }

解法三：按行排序

思路：

遍历字符串，判断确定字符属于Z字形的哪一行，然后放在对于的行。

算法：

我们可以遍历一遍字符串，可以使用当前行和当前方向两个变量来对合适的行进行跟踪。

只有当我们向上移动到最上面或者向下移动到最下面时，才会更改方向。

public static String convert3(String s, int numRows) {
    if(numRows == 1) return s;
    
    List rows = new ArrayList<>();
    
    //创建结果行集合（每行元素按照StringBuilder存放）
    for(int i = 0; i

测试类：

package com.company.project.hot100;

import java.util.List;
import java.util.ArrayList;

/*
 * 6. Z 字形变换
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G
 */
public class Question06 {

    /**
     *  解法一：利用周期特性
     * 根据z字排列的特性，发现字符串成周期排列，周期为2 * numRows -2，
     * 发现第n行的元素，为每个周期的第i个或者第（周期-i）个
     * @param s
     * @param numRows
     * @return
     */
    public static String convert1(String s, int numRows) {
        if(numRows == 1) return s;
        int len = s.length();
        int cycle = 2 * numRows -2;
        StringBuilder sBuilder = new StringBuilder(len);
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < len; j++) {
                if (j % cycle == i || j % cycle == (cycle - i)) {
                    sBuilder.append(s.charAt(j));
                }
            }
        }       
        return sBuilder.toString();
    }

    
    /**
     * 解法二：第一种解法的升级
     * 去掉了跳过了许多没必要的检测，省去了大量的时间
     * 
     * 算法：
     * 
     * @param s
     * @param numRows
     * @return
     */
    public static String convert2(String s, int numRows) {
        if(numRows == 1) return s;
        int len = s.length();
        int cycle = 2 * numRows -2;
        StringBuilder sBuilder = new StringBuilder(len);
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < len; j += cycle) {
                sBuilder.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycle - i < len)
                    sBuilder.append(s.charAt(j + cycle - i));
            }
        }
        return sBuilder.toString();
    }
    
    /**
     * 解法三：按行分组
     * 我们可以遍历一遍字符串，可以使用当前行和当前方向两个变量来对合适的行进行跟踪。
     * 只有当我们向上移动到最上面或者向下移动到最下面时，才会更改方向。
     * @param s
     * @param numRows
     * @return
     */
    public static String convert3(String s, int numRows) {
        if(numRows == 1) return s;
        
        List rows = new ArrayList<>();
        
        //创建结果行集合（每行元素按照StringBuilder存放）
        for(int i = 0; i

版权声明：
作者：Zad
链接：https://www.techfm.club/p/43423.html
来源：TechFM
文章版权归作者所有，未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>