【算法】6. Z 字形变换(多语言实现)

举报
二当家的白帽子 发表于 2023/05/15 18:02:16 2023/05/15
【摘要】 将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

6. Z 字形变换:

将一个给定字符串 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

分析:

  • 面对这道算法题目,二当家的陷入了沉思。
  • 直接找到规律模拟即可。

题解

rust:

impl Solution {
    pub fn convert(s: String, num_rows: i32) -> String {
		// 输入字符串的长度
		let n = s.len();
		let num_rows = num_rows as usize;
		if num_rows == 1 || num_rows >= n { return s; }

		// 结果
		let mut ret = String::with_capacity(s.len());
		// 一次循环串的长度
		let cycle_len = 2 * num_rows - 2;
		// 将字符串转为字符Vec
		let s = s.chars().into_iter().collect::<Vec<char>>();

		// 注意字符串长度小于行数的问题
		for i in 0..num_rows.min(n) {
			(0..n - i).step_by(cycle_len).for_each(|j| {
				ret.push(s[j + i]);
				if i != 0 && i != num_rows - 1 && j + cycle_len - i < n {
					ret.push(s[j + cycle_len - i]);
				}
			});
		}

		ret
    }
}

go:

func convert(s string, numRows int) string {
	n := len(s)
	if numRows == 1 || numRows >= n {
		return s
	}
	// 一次循环串的长度
	cycleLen := 2*numRows - 2
	ans := make([]byte, 0, n)
	for i := 0; i < numRows; i++ {
		for j := 0; j+i < n; j += cycleLen {
			ans = append(ans, s[j+i])
			if 0 < i && i < numRows-1 && j+cycleLen-i < n {
				ans = append(ans, s[j+cycleLen-i])
			}
		}
	}
	return string(ans)
}

c++:

class Solution {
public:
	string convert(string s, int numRows) {
		int n = s.length();
		if (numRows == 1 || numRows >= n) {
			return s;
		}
		string ans;
		const int cycleLen = 2 * numRows - 2;
		for (int i = 0; i < numRows; ++i) {
			for (int j = 0; j + i < n; j += cycleLen) {
				ans += s[j + i];
				if (0 < i && i < numRows - 1 && j + cycleLen - i < n) {
					ans += s[j + cycleLen - i];
				}
			}
		}
		return ans;
   }
};

python:

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        n = len(s)
        if numRows == 1 or numRows >= n:
            return s
        # 一次循环串的长度
        cycle_len = 2 * numRows - 2
        ans = []
        for i in range(numRows):
            for j in range(0, n - i, cycle_len):
                ans.append(s[j + i])
                if 0 < i < numRows - 1 and j + cycle_len - i < n:
                    ans.append(s[j + cycle_len - i])
        return ''.join(ans)


java:

class Solution {
    public String convert(String s, int numRows) {
        final int n = s.length();
        if (numRows == 1 || numRows >= n) return s;

        StringBuilder ret = new StringBuilder();
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                ret.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                    ret.append(s.charAt(j + cycleLen - i));
            }
        }
        return ret.toString();
    }
}


非常感谢你阅读本文~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://bbs.huaweicloud.cn/community/usersnew/id_1628396583336561 博客原创~


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。