LeetCode第六题：N 字形变换

admin
学习
2023-09-13
52热度
0评论

题目来源：Leetcode第六题

1.题目描述

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

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：P A H N A P L S I I G Y I R

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

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3

输出："PAHNAPLSIIGYIR"

提示：

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

2.解题思路

解法一：按行排序

描述：初始化一个数组来存储N字形的每一行，遍历原始字符串的每一个字符，根据Z字形的当前方向（向上或向下）确定要放入哪一行。到达顶部或者底部的时候，反转方向，将所有的行连接为一个字符串，就是我们的结果。
时间复杂度：O(n)。n是字符串的长度。
空间复杂度：O(n)。我们为每一行分配了空间，因此总空间复杂度为原字符串的长度，即O(n)。其他定义的变量是常数空间，可以忽略。
参考代码：

java版：

class Solution {
    public String convert(String s, int numRows) {
        // 如果给定行数为1，或者这个字符串长度为给定的行数
        // 就直接返回字符串
        if (numRows == 1 || s.length() <= numRows) {
            return s;
        }

        // 新建一个StringBuilder数组来保存每一行的字符
        // 那样我们直接输出这个数组就是想要的结果
        StringBuilder[] rows = new StringBuilder[numRows];

        // 遍历给定的长度，给定多长我们就新建多大的StringBuilder()
        // 一个StringBuilder()存一行字符
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }

        // 定义当前遍历的行数
        int curRow = 0;
        // 定义goingDown来判断增加行数还是减少行数
        // 初始化为false
        boolean goingDown = false;

        // 遍历字符串
        for (char c : s.toCharArray()) {
            // 在当前行的StringBuilder中添加这个字符
            rows[curRow].append(c);
            // 如果遍历到两端，说明需要回头
            // 比如第0行，需要回头去第1行，到最后一行后，需要在返回
            // 怎么返回呢，通过goingDown，初始化为false说明是往上走的
            // 到0行，变为true，开始往下面走，到最后一行变为false，回头，如此循环
            if (curRow == 0 || curRow == numRows - 1) {
                goingDown = !goingDown;
            }
            // 当goingDown为true的时候，行数加1，为false，行数-1
            curRow += goingDown ? 1 : -1;
        }

        // 在新建一个StringBuilder来存结果
        StringBuilder ret = new StringBuilder();
        // 遍历存着每一行字符的StringBuilder数组
        // 将每一行的值存进结果
        for (StringBuilder row : rows) {
            ret.append(row);
        }
        // 返回结果以字符串的形式
        return ret.toString();
    }
}

C++版：

class Solution {
public:
	string convert(string s, int numRows) {
		// 如果给定行数为1，或者这个字符串长度为给定的行数
		// 就直接返回字符串
		if (numRows == 1 || s.size() == numRows)
		{
			return s;
		}
		//新建一个数组来保存每一行的字符，数组长度为字符串长度和给定长度的较小值
		//因为可能字符串长度比给定的长度小，那样会浪费内存
		vector<string> rows(min(int(s.size()), numRows));

		//定义当前遍历的行数
		int curRow = 0;
		// 定义goingDown来判断增加行数还是减少行数
		// 初始化为false
		bool goingDown = false;
		// 遍历字符串
		for (char c : s)
		{
			// 在当前行中添加这个字符
			rows[curRow] += c;
			// 如果遍历到两端，说明需要回头
		   // 比如第0行，需要回头去第1行，到最后一行后，需要在返回
		   // 怎么返回呢，通过goingDown，初始化为false说明是往上走的
		   // 到0行，变为true，开始往下面走，到最后一行变为false，回头，如此循环
			if (curRow == 0 || curRow == numRows - 1)
			{
				goingDown = !goingDown;
			}
			// 当goingDown为true的时候，行数加1，为false，行数-1
			curRow += goingDown ? 1 : -1;
		}

		//定义一个字符串来存储结果
		string ret;

		//把我们的数组中存的每一行的字符结果合并就是最后的结果
		for (string row : rows)
		{
			ret += row;
		}
		//返回字符串
		return ret;
	}
};

C版：

char* convert(const char* s, int numRows) {
	int len = strlen(s);

	// 当行数为1或字符串长度不大于行数时，直接返回原字符串
	if (numRows == 1 || len <= numRows) {
		char* result = (char*)malloc(len + 1);
		for (int i = 0; i < len; i++) {
			result[i] = s[i];
		}
		result[len] = '\0';
		return result;
	}

	// 为行动态分配内存空间
	char** rows = (char**)malloc(numRows * sizeof(char*));
	for (int i = 0; i < numRows; i++) {
		rows[i] = (char*)malloc(len + 1);
		rows[i][0] = '\0';  // 初始化为空字符串
	}

	int curRow = 0;
	int goingDown = 0;  // 用于决定Z字形的方向

	// 遍历原始字符串的每一个字符
	for (int i = 0; i < len; i++) {
		int rowLen = strlen(rows[curRow]);
		rows[curRow][rowLen] = s[i];
		rows[curRow][rowLen + 1] = '\0';

		// 当我们到达Z字形的顶部或底部时，改变方向
		if (curRow == 0 || curRow == numRows - 1) {
			goingDown = !goingDown;
		}
		curRow += goingDown ? 1 : -1;
	}

	// 将所有行连接成一个字符串
	char* ret = (char*)malloc(len + 1);
	int retIdx = 0;
	for (int i = 0; i < numRows; i++) {
		int rowLen = strlen(rows[i]);
		for (int j = 0; j < rowLen; j++) {
			ret[retIdx++] = rows[i][j];
		}
		free(rows[i]);
	}
	ret[retIdx] = '\0';
	free(rows);

	return ret;
}

解法二：按行访问

描述：找出转化的规律，利用数学公式计算每个字符在 Z 字形中的位置。首先定义一个周期长度，这个周期代表从 Z 字形的第一行的一个元素到下一个元素所需要遍历的字符数量。接下来，我们按行读取字符。对于每一行，我们定义了两个索引，一个是周期的开始，一个是周期的中间或结束。这两个索引之间的距离变化取决于我们当前处于哪一行。
时间复杂度：O(n)。其中 n 是输入字符串的长度。尽管我们有两层循环，但每个字符只被处理一次。外循环按行遍历，而内循环则跳过一个周期的数量，所以总的迭代次数与 n 相关。
空间复杂度：O(n)。输出字符串的大小与输入字符串的大小相同，所以空间复杂度是 O(n)。这不包括输入字符串的大小，只是考虑了输出的字符串大小。
参考代码：

java版：

class Solution {

    public String convert(String s, int numRows) {
        // 如果给定行数为1，或者这个字符串长度为给定的行数
        // 就直接返回字符串
        if (numRows == 1 || s.length() == numRows) {
            return s;
        }
        // 存放结果
        StringBuilder result = new StringBuilder();

        // 定义这个Z字形的周期字符数
        // 例如 A...E...I
        // .....B.D.F.H.J
        // .....C...G...K
        // ABCD是一个周期，EFGH是一个周期
        // 周期的算法就是给定的行数*2，然后-2，减的数字就是首尾 固定是2
        int cycle = 2 * numRows - 2;

        // 遍历行数，从第0行开始
        for (int i = 0; i < numRows; i++) {
            // 遍历这一行的每一个字符，i就是索引的偏移量，i+j就是元素的真实索引
            // 例如第一行的第一个字符，真实索引就是i+j，也就是1
            // 注意循环结束后是j加上周期值，这样才是下一个周期的这一行元素的索引
            for (int j = 0; j + i < s.length(); j += cycle) {
                // 例如 A...E...I
                // .....B.D.F.H.J
                // .....C...G...K
                // 将元素添加到结果中
                // 注意这里只是添加了竖着的部分，斜线中的元素没有添加，这里斜线不包括竖着的部分
                // 例如上面例子的ABCEFGIJK都是通过这个添加的，而斜线中的DH不是
                result.append(s.charAt(j + i));

                // 添加斜线中的字符，不包括斜线两端，所以i != 0 && i != numRows - 1
                // 斜线中的字符索引就是 j + cycle - i，例如D在第一行的第二个字符
                // 也就是i=1，j=0，他的索引就是3
                // 为什么这么算呢，因为j一直都是这个周期的第0个元素，就是上面的AEI
                // 加上周期也就是下一个周期的第0个元素，-i就是减去行数，-1就是第一行斜线上的值
                // 也就是上一个周期第一行的斜线上的值
                if (i != 0 && i != numRows - 1 && j + cycle - i < s.length()) {
                    result.append(s.charAt(j + cycle - i));
                }
            }
        }

        // 通过上面的循环已经获得了结果，返回结果就行
        return result.toString();
    }
}

C++版：

class Solution {
public:
	string convert(string s, int numRows)
	{
		// 如果给定行数为1，或者这个字符串长度小于等于给定的行数
		// 就直接返回字符串
		if (numRows == 1 || s.size() <= numRows)
		{
			return s;
		}

		string result = "";

		// 定义这个Z字形的周期字符数
		// 例如 A...E...I
		// .....B.D.F.H.J
		// .....C...G...K
		// ABCD是一个周期，EFGH是一个周期
		// 周期的算法就是给定的行数*2，然后-2，减的数字就是首尾 固定是2
		int cycle = 2 * numRows - 2;

		// 遍历行数，从第0行开始
		for (int i = 0; i < numRows; i++)
		{
			// 遍历这一行的每一个字符，i就是索引的偏移量，i+j就是元素的真实索引
			// 例如第一行的第一个字符，真实索引就是i+j，也就是1
			// 注意循环结束后是j加上周期值，这样才是下一个周期的这一行元素的索引
			for (int j = 0; j + i < s.size(); j += cycle)
			{
				// 例如 A...E...I
				// .....B.D.F.H.J
				// .....C...G...K
				// 将元素添加到结果中
				// 注意这里只是添加了竖着的部分，斜线中的元素没有添加，这里斜线不包括竖着的部分
				// 例如上面例子的ABCEFGIJK都是通过这个添加的，而斜线中的DH不是
				result += s[i + j];

				// 添加斜线中的字符，不包括斜线两端，所以i != 0 && i != numRows - 1
				// 斜线中的字符索引就是 j + cycle - i，例如D在第一行的第二个字符
				// 也就是i=1，j=0，他的索引就是3
				// 为什么这么算呢，因为j一直都是这个周期的第0个元素，就是上面的AEI
				// 加上周期也就是下一个周期的第0个元素，-i就是减去行数，-1就是第一行斜线上的值
				// 也就是上一个周期第一行的斜线上的值
				if (i != 0 && i != numRows - 1 && (j + cycle - i) < s.size())
				{
					result += s[j + cycle - i];
				}
			}
		}
		// 通过上面的循环已经获得了结果，返回结果就行
		return result;
	}
};

C版：

char* convert(char* s, int numRows) {
	int len = strlen(s);
	if (numRows == 1 || strlen(s) <= numRows) {
		char* result = (char*)malloc(len + 1);
		for (int i = 0; i < len; i++) {
			result[i] = s[i];
		}
		result[len] = '\0';
		return result;
	}

	char* result = (char*)malloc(len + 1);  // +1 用于空字符
	int cycle = 2 * numRows - 2;
	int pos = 0;

	for (int i = 0; i < numRows; i++) {
		for (int j = 0; j + i < len; j += cycle) {
			result[pos++] = s[i + j];
			if (i != 0 && i != numRows - 1 && j + cycle - i < len) {
				result[pos++] = s[j + cycle - i];
			}
		}
	}
	result[pos] = '\0';  // 添加终止字符

	return result;
}