题目链接

LeetCode

题目描述

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

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

P A H N
A P L S I I G
Y I R

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

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

string convert(string s, int numRows);

示例 1：

输入： s = “PAYPALISHIRING”, numRows = 3
输出： “PAHNAPLSIIGYIR”

示例 2：

输入： s = “PAYPALISHIRING”, numRows = 4
输出： “PINALSIGYAHRPI”
解释：
P I N
A L S I G
Y A H R
P I

示例 3：

输入： s = “A”, numRows = 1
输出： “A”

提示：

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、',' 和 '.' 组成
  • 1 <= numRows <= 1000

    解题思路

    方法一：找规律

    都与 numRows 相关
  1. 如果 numRows == 1， 则字符串不变
  2. 第一行和最后一行两个元素之间的间隔为 2*(numRows-1)
  3. 中间的行，奇数个间隔和偶数个间隔之和为 2*(numRows-1) ，并且每向下一行，奇数间隔数 -2，偶数间隔数 +2
  1. class Solution {
  2.     public String convert(String s, int numRows) {
  3.         if(numRows == 1){
  4.             return s;
  5.         }
  6.         StringBuilder res = new StringBuilder();
  7.         // 第一行和最后一行的间隔
  8.         int grid = 2*(numRows-1);
  9.         // 中间行的 奇数间隔和偶数间隔
  10.         int odd = grid, even = grid;
  11.         // 遍历每一行的结果
  12.         for(int i = 0; i < numRows; ++i){
  13.             boolean flag = true;
  14.             for(int j = i; j < s.length();){
  15.                 res.append(s.charAt(j));
  16.                 // 每次有两个相邻的间隔，并且间隔之和为2*(numRows-1) 交换出现
  17.                 if(flag){
  18.                     j = j + odd;
  19.                 }else{
  20.                     j = j + even;
  21.                 }
  22.                 flag = !flag;
  23.             }
  24.             // odd == 2 说明下一行是最后一行，最后一行的所有间隔都是2*(numRows-1)
  25.             odd = odd == 2? grid : odd - 2;
  26.             // 奇数间隔每次是上一行奇数间隔减2
  27.             // 偶数间隔等于 2*(numRows-1) - odd
  28.             even = odd == grid ? grid : grid - odd;
  29.         }
  30.         return res.toString();
  31.     }
  32. }
  • 时间复杂度 O(n)
  • 空间复杂度 O(n)