526互联

力扣刷题笔记-06 N字形变换

发布时间 2023-09-27 17:14:05作者: 张三01011010

06 N字形变换

不要混日子，小心日子把你混了

对于题目的理解

比如说，我给一个字符串，LEETCODE，行数为3，然后按照N字形排列，就是下面这个排列方式。排列完之后正常读取，结果就是LCETOEED。这叫做N字形变换。

image-20230926下午52718303

这个例子里给的行数就是3，往下排三行，然后往右往上走。

chatGPT

思路

  1. 边界情况/特殊情况：就给一行，或者给的行数和字符串的长度是一样的，那么就直接返回原来的字符串
  2. 创建一个长度为numRows的字符数组rows，用于存储每行的字符

。。。没抄完，但是我已经理解了。

我的理解：

  1. 准备一个数组，类型是StringBuilder，StringBuilder[] rows = new StringBuilder[numRows];容量为给定的行数 numRows，每一个数组元素代表一行。为什么每个数组元素代表一行呢？这里困扰了很久，其实很简单，玄机就在于声明的是StringBuilder类型的。我们在排列的时候是从上往下排列的，所以这里也是从上往下填充数组，每个元素代表一行。当这一列填充结束的时候，就去下一列，仍旧是对row[index]这个元素，也就是对应行的元素，但是这里是append，自然就把这一行元素拼接上来了
  2. 定义一个index ，初始值为0，用来标志是哪一行；
  3. 定义一个step，初始值是1，用来标记是向上走还是向下走，1表示向下，-1表示向上
  4. 考虑边界情况：
    1. index==0；此时在第一行，应该往下走。step设置为1，index = index+step，这样的话就会是一直在向下走
    2. 向下走到index = numRows-1，表示走到最下面一行了，该向上走了，这个时候把step设置为-1，index= index+step，这样就相当于在向上走。
  5. 遍历字符串s
  6. 遍历结束以后，再去遍历数组，拼接，就是N字形变换之后的结果了。

上代码：

/**
 * 首先要理解怎么算是N字变换
 * 一个正常的字符串，按照给定的行数，从上到下，斜着向上，再向下，就像N字一样
 *
 * 解决这个问题的思路是假如给了4行，那就申请一个StringBuilder数组，大小容量也是4
 * 遍历给定的字符S，从上往下，向数组元素添加，但是这里的添加是append，下次走到这一行，仍旧append，这样就拼进去了
 * 虽然我知道这样讲可能没讲明白，那我在换个说法
 *
 * 1. 每个数组元素代表一行的字符串，注意这里的一行指的是N字形排列之后的一行
 * 2. 题目给了多少行，数组里就有多少个元素，用了StringBuilder这个类型，就可以直接拼接，拼接一整行。
 * 3. N字形边界情况：一开始是向下，然后到了最底下，应该向上走了。所以我们需要两个变量，一个用来指示从上往下到第几行，一个用来指示
 * 要不要转换方向。这里不用考虑向右走，因为向右走就是在数组元素后面append一个字符。当index是0的时候，应该向下走，可以让index+1，
 * 当index是给定的行数numRows-1的时候，应该向上走，就是index-1。
 * @param s
 * @param numRows
 * @return
 */
class Solution {

    public String convert(String s, int numRows) {

        // 如果行数是1或者是字符串的长度，直接返回字符串
        if (numRows == 1 || s.length() <= numRows) {
            return s;
        }

        // 准备数组用来存放字符
        StringBuilder[] rows = new StringBuilder[numRows];
        // 初始化数组
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }

        // 标记在哪一行
        int index = 0;
        // 标记往下走还是往上走
        int step = 1;

        // 遍历字符串
        for (char c : s.toCharArray()) {
            rows[index].append(c);
            if (index == 0){
                
                
                // 此时表示最上面一行，应该是往下走，就+1；直到走到else里，说明到底了
                step = 1;
        } else if (index == numRows - 1) {
            // 这里说明到底了，就-1，往上走，直到index == 0；
            step = -1;
        }
    
            index += step;
        }
        
        // 拼接字符串
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }
        return result.toString();
    }
}

划重点：

我一开始想，可能是用二维数组来记录，因为有横竖的类似于表格的排列，所以很长一段时间内无法理解为什么是一个一维数组就能解决 StringBuilder[] rows = new StringBuilder[numRows];巧妙的地方在于 StringBuilder,数组容量是行数，列数不用考虑，因为StringBuilder可以append，往后无限增加列，这就相当于是二维数组了。但是这里有一点不得不注意，你要对数组初始化。