leetcode如何解决Z字形变换问题

发布时间：2022-01-17 11:50:13 阅读：144 作者：小新栏目：大数据

开发者测试专用服务器限时活动，0元免费领，库存有限，领完即止！点击查看>>

小编给大家分享一下leetcode如何解决Z字形变换问题，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！

题目链接

https://leetcode-cn.com/problems/zigzag-conversion/

题目描述

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

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

L   C   I   RE T O E S I I GE   D   H   N

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

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

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4输出: "LDREOEIIECIHNTSG"解释:L     D     RE   O E   I IE C   I H   NT     S     G

解题方案

思路

标签：字符串
整体的思路是遍历字符串，遍历过程中将每行都看成新的字符串构成字符串数组，最后再将该数组拼接起来即可
如果numRows=1则说明当前字符串即为结果，直接返回
否则整个字符串需要经历，向下向右，向下向右，这样的反复循环过程，设定down变量表示是否向下，loc变量表示当前字符串数组的下标
如果down为true，则loc+=1，字符串数组下标向后移动，将当前字符加入当前字符串中
如果down为false，则表示向右，则loc-=1，字符串数组下标向前移动，将当前字符加入当前字符串中
时间复杂度：O(n)，n为字符串s的长度

代码

Java版本

class Solution {    public String convert(String s, int numRows) {        if(numRows == 1)            return s;                int len = Math.min(s.length(), numRows);        String []rows = new String[len];        for(int i = 0; i< len; i++) rows[i] = "";        int loc = 0;        boolean down = false;        for(int i=0;i<s.length();i++) {            rows[loc] += s.substring(i,i+1);            if(loc == 0 || loc == numRows - 1)                down = !down;            loc += down ? 1 : -1;        }                String ans = "";        for(String row : rows) {            ans += row;        }        return ans;    }}

JavaScript版本

/** * @param {string} s * @param {number} numRows * @return {string} */var convert = function(s, numRows) {    if(numRows == 1)        return s;    const len = Math.min(s.length, numRows);    const rows = [];    for(let i = 0; i< len; i++) rows[i] = "";    let loc = 0;    let down = false;    for(const c of s) {        rows[loc] += c;        if(loc == 0 || loc == numRows - 1)            down = !down;        loc += down ? 1 : -1;    }    let ans = "";    for(const row of rows) {        ans += row;    }    return ans;};