专栏首页灵魂画师牧码画解算法:6. Z 字形变换

画解算法:6. Z 字形变换

题目链接

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

题目描述

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 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

解题方案

思路

  • 标签:字符串
  • 整体的思路是遍历字符串,遍历过程中将每行都看成新的字符串构成字符串数组,最后再将该数组拼接起来即可
  • 如果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;
};

画解

本文分享自微信公众号 - 牧码啦(mumalo),作者:灵魂画师牧码

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 画解算法 242-有效的字母异位词

    https://leetcode-cn.com/problems/valid-anagram/

    灵魂画师牧码
  • 开源想赚钱?快使用开源软件打赏平台IssueHunt

    对于普通开发者而言,在使用开源软件的过程中,有新特性的需求和遇到bug是非常常见的事情。但新特性并不一定在软件维护者的计划之中,而bug也不一定能够及时解决。

    灵魂画师牧码
  • 画解算法:67. 二进制求和

    https://leetcode-cn.com/problems/add-binary/

    灵魂画师牧码
  • 如何使用Tahoe-LAFS将您的数据保存在云中

    虽然Tahoe-LAFS可能类似于其他分散或分布式文件系统,如Gluster,Ceph或其他,但它解决的问题却不同。在最权威文件存储(LAFS)设计了以下事项:

    沈唁
  • 关于Java里面的字符串常量池的介绍和优化

    上一篇文章提到我们在java里面不是通过new创建的string字符串会被放到一个叫字符串常量池的地方,那么本篇文章我们就来详细的了解下常量池的相关知识。

    我是攻城师
  • 快乐游戏,解放双手

    上回说到这个PyUserInput这个库能够模拟鼠标和键盘点击(没看过的朋友底部有传送门),今天老肥再来实战一波游戏脚本制作。

    老肥码码码
  • JavaScript 是如何工作的:JavaScript 的内存模型

    作为程序员,声明变量、初始化变量(或不初始化变量)以及稍后为它们分配新值是我们每天都要做的事情。

    Fundebug
  • 对比python字符串函数,轻松学习pandas的 str 矢量化字符串函数

    python字符串应该是python里面最重要的数据类型了,因此学会怎么处理各种各样的字符串,显得尤为重要。

    朱小五
  • Anaconda+VSCode配置tensorflow开发环境的教程详解

    Anaconda是一个开源的python发行版本,是现在比较流行的python数据科学平台,可以对python的科学包做到有效管理。在配置python开发环境时...

    砸漏
  • 数据挖掘算法-Matlab实现:Logistic 回归

    什么叫做回归呢?举个例子,我们现在有一些数据点,然后我们打算用一条直线来对这些点进行拟合(该曲线称为最佳拟合曲线),这个拟合过程就被称为回归。 利用Logis...

    机器学习AI算法工程

扫码关注云+社区

领取腾讯云代金券