0%

[0006] Z 字形变换

发表于 更新于 分类于 ， 本文字数： 2.1k 阅读时长 ≈ 2 分钟
...

[0006] 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
Related Topics
  • 字符串

    • 题目解析

    • 本题是一道模拟题

    不确定性

    方法一：直接模拟法

    分析

    • 按照题中要求，将字符按顺序放入容器内
    • 遍历容器，按行读出字符

    思路

    • 建立一个行数为numRows，列数为s.size()，类型为string的二维容器，并初始化所有值为””
    • 设定初始方向为向下，另一种可能的方向向右上
    • 按照字符串s中的字符顺序，依次放入容器中
    • 当满足条件时，更改方向
    • 放入完成后，按行进行读取

    注意

    知识点

    • 数组的下标操作

    复杂度

    • 时间复杂度 O(n)，其中n为给定字符串的长度
    • 空间复杂度 O(n)，其中n为给定字符串的长度

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    //提交时会超时
    string convert(string s, int numRows){
    	if (numRows== 1){
    		return s;
    	}
    	vector<vector<string>> vec(numRows, vector<string>(s.size(), ""));
    	int dir = 0;//dir表示字符方向，0代表向下，1代表向右上
    	int row = 0, col = 0;
    	vec[row][col] = s[0];
    	for (int i = 1; i < s.size(); i++){
    		if (dir == 0){
    			vec[++row][col] = s[i];
    		}
    		if (dir == 1){
    			vec[--row][++col] = s[i];
    		}
    		if (i % (numRows - 1) == 0){
    			dir = 1 - dir;
    		}
    	}
    	string res;
    	for (int j = 0; j < numRows; j++){
    		for (int k = 0; k < col + 1; k++){
    			if (vec[j][k] != ""){
    				res += vec[j][k];
    			}
    		}
    	}
    	return res;
    }

    方法二：按行插入法

    分析

    • 若将每一行看作一个“容器”，则本题实际上就是将字符分别放入对应的容器中
    • 方向是自上向下，再自下向上，循环往复
    • 最后按行将”容器“拼接到一起

    思路

    • 建立一个字符串容器vec，大小为numRows
    • 定义i作为行下标，dir作为顺序插入的方向
    • 将每个字符添加到对应的（行）字符串中
    • 当i == 0或者i == numRows - 1时，则将dir反向
    • 按行将容器vec内的字符串拼接到一起

    注意

    • 在本题中，如果numRows为1时，则返回原字符串
    • 若s.size()为0或者s.size()为1时，也可以考虑边界情况，但是在提交时会报错

    知识点

    • vector容器的使用

    复杂度

    • 时间复杂度 O(n)，其中n为给定字符串的长度
    • 空间复杂度 O(m)，其中m=numRows

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    string convert(string s, int numRows){
    	if (numRows== 1){
    		return s;
    	}
    	
    	vector<string> vec(numRows);
    	int i = 0;
    	int dir = -1;
    	for (char c: s){
    		vec[i] += c;
    		if (i == 0 || i == numRows - 1){
    			dir = -1 * dir;
    		}
    		i += dir;
    	}
    	string res;
    	for (string s : vec){
    		res += s;
    	}
    	return res;
    }

    相关题目

    相关文章