LeetCode-Java: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"

① 找规律

2ms,超过98.63%

43.69MB,超过86.85%

这道题还是有点难度在,一开始想要设置一个二维数组,遍历整个字符串,按照变换的规则将字符串存入到二维数组当中,最后将二维数组按照从左向右顺序读取转换成字符串。

写了一半,感觉这个思路写起来太麻烦了,想走个捷径,就按照下图的方式把原‘s’、排列情况、输出情况都列出来,想要得到一个‘函数’,可以使得输入转变为输出。

题目已经给定了numRows,按照规律排列能够找到第一行元素彼此之间间隔多少,后几行输出则根据第一行的输出±i (i=1,2,3…)即可

但在这种情况下,仍旧存在一些特殊情况需要考虑,比如如果numRows<2,那无论如何排列都是原本的‘s’,按照代码的情况的话,容易造成数组越界,所以numRows<2,直接返回s。

在这里插入图片描述

问题:为什么要设置use[]数组?

**答:**use[]数组主要用于记录字符串当中哪些元素已经被使用过,防止元素重复使用。具体在例子当中可以看为‘P A Y R A’,假设第一行是"P A",第二行是“A R”,第三行应该是‘Y’,如果按照代码的逻辑,在‘p’下标基础上+2输出一次,在‘A’下标基础上-2输出一次,那么‘Y’会被输出两次,有了use[]数组就可以保证只输出一次。当然也有其他的方法,不设置use[]数组也可以防止多输出情况,能够节省一些空间,但实现更复杂,更不易懂,感觉没必要。

问题:为什么第二个for循环当中的for循环设置j<len+numRows?

**答:**主要是因为用例“ABCD”,numRows=3无法通过。第一个for循环是用来确定第一行的情况的,第二个for循环是根据第一行情况找到第一行元素左右两侧±i的位置进行保存。用例“ABCD”,第一行只有‘A’,第二行应当为‘B D’,假设j<len的话,则第二行只有‘B’,因为‘D’是根据s[4](该元素不存在)的左右两侧进行确定的,所以理论上j一定得比len多出一个(2*numRows-2)/2,里面的判断只需要看j±i是否会超过数组范围就可保证不会越界。

那为什么是j<len+numRows,而不是j<len+numRows-1?主要原因是加上-1也可以,就是运行速度略微慢了一点,所以呐,这里去掉了,影响不大~

class Solution {
    public String convert(String s, int numRows) {
        if (numRows<2) return s;//如果numRows=1,则s不需要变换直接返回
        StringBuilder str=new StringBuilder();//StringBuilder比String运算速度要快
        int len=s.length();
        int[] use=new int[len];//记录s的元素是否使用过
        //变换后的第一行
        for(int i=0;i<len;i=i+2*numRows-2){
            use[i]=1;
            str.append(s.charAt(i));
        }
        //变换后的2~numRows行
        for(int i=1;i<numRows;i++){
            for(int j=0;j<len+numRows;j=j+2*numRows-2){
                //为什么设置j<len+numRows看上面
                //先j-1,后j+1,符合s的从左到右顺序
                if(j-i>=0 && j-i<len && use[j-i]!=1){
                    //保证数组不越界,并且没使用过就加入到str
                    use[j-i]=1;
                    str.append(s.charAt(j-i));
                }
                if(j+i<len && use[j+i]!=1){
                    //保证数组不越界,并且没使用过就加入到str
                    use[j+i]=1;
                    str.append(s.charAt(j+i));
                }
            }
        }
        return str.toString();//转换成字符串返回
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/537127.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024Mathorcup(妈妈杯)数学建模C题python代码+数据教学

2024Mathorcup数学建模挑战赛&#xff08;妈妈杯&#xff09;C题保姆级分析完整思路代码数据教学 C题题目&#xff1a;物流网络分拣中心货量预测及人员排班 因为一些不可抗力&#xff0c;下面仅展示部分代码&#xff08;很少部分部分&#xff09;和部分分析过程&#xff0c;其…

[python] Numpy库用法(持续更新)

先导入一下 import numpy as np 一、np.random用法 生成随机整数&#xff1a;np.random.randint(low, high, size) low: 最小值high: 最大值size: 生成的数组大小&#xff08;可以是多维&#xff0c;下面同理&#xff09; 生成随机浮点数&#xff1a;np.random.uniform(low, …

下线圈和包扎

电机槽内放好 所有槽纸 槽内再放入引槽纸 作用是放线圈的时候避免划伤线 开始放线圈 绑了白色扎带的朝外面 线圈的一边放进去后&#xff0c;另一边还悬在外面 &#xff0c;这里俗称 吊边。 为了保护吊边 &#xff0c;在吊边处放一张大的绝缘纸 &#xff08;如下图&#xff0…

32.WEB渗透测试-数据传输与加解密(6)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;31.WEB渗透测试-数据传输与加解密&#xff08;5&#xff09; 关于discuz3.5的源码内容和…

C++STL--谓词

谓词 ① 可调用的表达式称为谓词,包括仿函数,自定义函数,lambda表达式。 ② 接受一个参数的谓词&#xff0c;称为一元谓词。 ③ 接受两个参数的谓词&#xff0c;称为二元谓词。 可调用的表达式:对于一个对象或者表达式,如果可以使用调用运算符(),就称它为可以调用的。 一元谓…

java混淆的重要性分析

Java代码混淆是一种常用的安全技术&#xff0c;它通过对Java代码进行变换和重命名&#xff0c;使得源代码变得难以理解和逆向工程&#xff0c;从而增强代码的安全性。以下是对Java混淆重要性的分析&#xff1a; 保护知识产权&#xff1a;Java混淆可以防止恶意用户或竞争对手轻易…

macos 查看 远程服务器是否开放某个端口

想要使用mac查看远程服务器某个端口是否开发&#xff0c;可通过 nc 命令&#xff0c;如下&#xff1a; nc -zv <服务器IP> <端口号>如果该端口开发&#xff0c;结果为&#xff1a;succeeded! Connection to <服务器IP> port <端口号> [类型] succeed…

密码学 | 椭圆曲线 ECC 密码学入门(二)

目录 4 椭圆曲线&#xff1a;更好的陷门函数 5 奇异的对称性 6 让我们变得奇特 ⚠️ 原文地址&#xff1a;A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography ⚠️ 写在前面&#xff1a;本文属搬运博客&#xff0c;自己留着学习。如果你和我一样…

leetcode 1702

leetcode 1702 题目 例子 代码思路 class Solution { public:string maximumBinaryString(string binary) {int n binary.size();int i binary.find(0);if(i string::npos){return binary;}int zeros count(binary.begin(), binary.end(), 0);string s(n, 1);s[izeros-1]…

Python爬虫怎么挣钱?6个Python爬虫赚钱方式,搞搞副业不是问题

1.最典型的就是找爬虫外包活儿 网络爬虫最通常的的挣钱方式通过外包网站&#xff0c;做中小规模的爬虫项目&#xff0c;向甲方提供数据抓取&#xff0c;数据结构化&#xff0c;数据清洗等服务。新入行的程序员大多都会先尝试这个方向&#xff0c;直接靠技术手段挣钱&#xff0…

数据结构复习指导之绪论(算法的概念以及效率的度量)

文章目录 绪论&#xff1a; 2.算法和算法评价 知识总览 2.1算法的基本概念 知识点回顾与重要考点 2.2算法效率的度量 知识总览 1.时间复杂度 2.空间复杂度 知识点回顾与重要考点 归纳总结 绪论&#xff1a; 2.算法和算法评价 知识总览 2.1算法的基本概念 算法( Al…

一辆汽车的节拍时间是怎样的?

节拍时间&#xff0c;又称 takt time&#xff0c;是德语中“节奏”的意思。在汽车制造业中&#xff0c;它指的是按照客户需求和生产计划&#xff0c;生产一辆汽车所需的时间。这个时间是固定的&#xff0c;它决定了生产线上每个工序的操作速度和节奏&#xff0c;是生产线上所有…

一题多解之数塔问题

递归实现:记忆化深度遍历 #include <iostream> #include <algorithm> #include <string> using namespace std; int num[1000][1000],n;//递归实现:记忆化深度遍历 int dfs(int x,int y){int sum0;//记录最大情况if(x>n||y>x) return sum;//实现每次都…

功能测试_验证标题长度合法性_边界值法

验证标题长度合法性&#xff08;标题长度大于0&#xff0c;小于等于30个字符&#xff09; 开内闭外&#xff0c;保留1和31

水电智能远程抄表系统

水电智能远程抄表系统是一种应用先进技术实现水电抄表的智能化管理系统&#xff0c;通过远程抄表、数据传输和智能分析&#xff0c;实现了对水电使用情况的实时监测和管理。本文将从系统特点、构成以及带来的效益三个方面展开介绍。 系统特点 1.远程抄表&#xff1a;系统能够…

cas学习4:自定义登出页面

接上一章学习 cas学习3&#xff1a;自定义登录页面_cas 个性化页面-CSDN博客 后我们要自定义登出页面&#xff0c;因为在配置完cas后各个子系统退出后的都是cas登出页面。不符合实际需要&#xff0c;所以我们要配置自己的登出页面 1.修改application.properties 增加&#…

有效确认手机号机主姓名,避免信息错误

在如今信息爆炸的时代&#xff0c;手机已经成为我们生活中必不可少的一部分。手机号码的重要性已经不仅仅是联系工具&#xff0c;更是诸多场景下的实名认证必备条件&#xff0c;如电商、游戏、直播、金融等。为了保证用户信息的准确性和安全性&#xff0c;挖数据平台上的手机号…

软件测试学习之MySQL学习笔记(完结)

目录 1. 数据库**** 1.1. 概念**** 1.2. 分类**** 1.2.1. 关系型数据库**** 1.2.1.1. SQL**** 1.2.2. 安装**** 1.2.2.1. Navicat**** 2. SQL语句**** 2.1. 常用数据类型**** 2.2. 数据库**** 2.3. 表**** 2.3.1. 字段约束**** 2.4. 数据**** 2.4.1. 增 insert**…

AI革新病历系统-能“读懂”病历,或将能“思考”

Artificial Intelligence&#xff08;人工智能&#xff09;&#xff0c;简称AI。它其实是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 电子病历系统拖慢了医疗工作流程&#xff0c;人工智能或许能改善这一困境。 一位名叫罗杰的…

典型神经网络模型—自编码器

文章目录 编码器的介绍基本原理编码器的分类 应用案例网络构建训练步骤&#xff1a;调优&#xff1a; 编码器的介绍 基本原理 在神经网络中&#xff0c;编码器&#xff08;Encoder&#xff09;是一种用于将输入数据转换为另一种形式的网络组件或模型部分。编码器的核心任务是…