首页 > 其他分享 >力扣题目解析--Z字形变换

力扣题目解析--Z字形变换

时间：2024-11-01 14:44:52浏览次数：3  
标签：numRows rows 字符 -- pos ret 力扣 解析 row

题目

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

代码展示 

class Solution {
public:
    string convert(string s, int numRows) {
         if (numRows == 1 || numRows >= s.size()) return s;

        vector<string> rows(min(numRows, int(s.size())));
        int n = s.size();
        int cycleLen = 2 * numRows - 2; // 一个完整的Z字形周期长度

        for (int i = 0; i < n; i++) {
            int pos = i % cycleLen;
            int row = numRows - abs(numRows - 1 - pos);
            rows[row - 1].push_back(s[i]);
        }

        string ret;
        for (const auto& row : rows) {
            ret += row;
        }
        return ret;
    }
};

代码的逐行详细解释 

 

在Z字形排列中，当字符串按Z字形排列时，每个字符都会遵循一定的规律。假设我们有numRows行，那么从第一行到最后一行再回到第二行的路径形成了一个周期。

举例说明

假设我们有numRows = 3，那么Z字形排列如下：

P   A   H   N
A P L S I I G
Y   I   R

可以看到，字符的排列顺序是：

  1. 第一行的字符每隔2 * numRows - 2个字符出现一次；
  2. 第二行的字符每隔numRows - 2个字符出现一次；
  3. 最后一行的字符同样每隔2 * numRows - 2个字符出现一次。

对于第一行和最后一行，它们的周期是一样的，即每隔2 * numRows - 2个字符出现一次。这是因为：

  • 字符从第一行跳转到最后一个字符需要经过numRows - 1个空格；
  • 再从最后一个字符跳转回第一行需要再经过numRows - 1个空格；
  • 因此总长度是numRows - 1 + (numRows - 1) = 2 * numRows - 2。

对于中间行，周期则是不同的。中间行的字符会交替出现在两行之间，其间隔会短一些。

数学解释

对于任意的numRows，我们可以这样理解：

  • 每次从第一行跳到最后一行，再到第一行，构成了一个完整的周期；
  • 跳跃的总长度是numRows - 1（从第一行跳到最后一行）加上numRows - 1（从最后一行跳回第一行）；
  • 所以，一个完整的周期长度为2 * (numRows - 1)，即2 * numRows - 2。

cycleLen = 2 * numRows - 2 确定了字符在Z字形排列中的周期性规律，使得我们可以简单地通过模运算和除法来确定每个字符应该放置的位置。 

解释 pos = i % cycleLen

i 是当前字符在原始字符串中的索引，cycleLen 是一个完整的Z字形周期的长度。i % cycleLen 计算的是当前字符在当前周期内的相对位置。

为什么使用模运算？

模运算 (%) 可以确保索引不会超出周期长度的范围。例如，在一个周期长度为 cycleLen 的情况下，如果 i 超过了 cycleLen，模运算就会给出 i 在 cycleLen 范围内的对应位置。这样可以保证我们在计算行数时不会出错。

如何确定行号？

接下来，我们需要根据 pos 来确定当前字符应该放在哪一行。由于Z字形排列的特性，我们可以根据 pos 来计算出当前字符应该位于哪一行。

对于 numRows 行的情况，周期长度为 2 * numRows - 2，因此：

  • 当 pos 在 [0, numRows - 1) 范围内时，字符位于从上往下数的第 pos 行；
  • 当 pos 在 [numRows, 2 * numRows - 2) 范围内时，字符位于从下往上数的第 2 * numRows - 2 - pos 行。

为了简化计算，我们可以统一使用一个公式来确定行号：

int row = numRows - abs(numRows - 1 - pos);

这个公式可以理解为：

  • 如果 pos 在 [0, numRows - 1) 范围内，那么 numRows - 1 - pos 是正数，abs 不影响结果，row 就是 pos；
  • 如果 pos 在 [numRows, 2 * numRows - 2) 范围内，那么 numRows - 1 - pos 是负数，abs 会取绝对值，row 就是 2 * numRows - 2 - pos。

在这个例子中，s 是 "PAYPALISHIRING"，numRows 是 3。

  1. 计算周期长度：cycleLen = 2 * numRows - 2 = 4。
  2. 遍历字符串：
    • 对于 i = 0，pos = 0 % 4 = 0，row = 3 - abs(3 - 1 - 0) = 3 - 2 = 1，字符 'P' 放在第一行。
    • 对于 i = 1，pos = 1 % 4 = 1，row = 3 - abs(3 - 1 - 1) = 3 - 1 = 2，字符 'A' 放在第二行。
    • 对于 i = 2，pos = 2 % 4 = 2，row = 3 - abs(3 - 1 - 2) = 3 - 0 = 3，字符 'Y' 放在第三行。
    • 对于 i = 3，pos = 3 % 4 = 3，row = 3 - abs(3 - 1 - 3) = 3 - 1 = 2，字符 'P' 放在第二行。
    • 以此类推，直到字符串遍历结束。

最终，rows 中存储了每一行的字符，将这些字符拼接起来就得到了Z字形排列后的字符串。

 

目标

我们的目标是确定当前字符应该放置在哪一行。我们需要一个公式来根据当前字符在周期内的位置（即pos）来计算出它所在的行数。

分析

对于一个Z字形排列，我们可以观察到以下规律：

  1. 当字符处于周期的前半段时（即pos小于numRows - 1），它们从上到下依次放置；
  2. 当字符处于周期的后半段时（即pos大于等于numRows - 1），它们从下往上依次放置。

公式推导

前半段（pos < numRows - 1）

对于前半段，pos表示的是从第一行开始的行数，因此：

  • 当pos为0时，字符应该放置在第一行；
  • 当pos为1时，字符应该放置在第二行；
  • ……
  • 当pos为numRows - 1时，字符应该放置在最后一行。

因此，对于前半段，行号row就是pos。

后半段（pos ≥ numRows - 1）

对于后半段，我们需要从最后一行开始往回计数，因此：

  • 当pos为numRows时，字符应该放置在倒数第二行；
  • 当pos为numRows + 1时，字符应该放置在倒数第三行；
  • ……
  • 当pos为2 * numRows - 2时，字符应该放置在第一行。

因此，对于后半段，行号row应该是2 * numRows - 2 - pos。

统一公式

为了简化代码，我们可以通过一个统一的公式来计算行号row，无论pos是在前半段还是后半段。

int row = numRows - abs(numRows - 1 - pos);
公式解析

  • numRows - 1 - pos：这个表达式给出了一个数值，这个数值的正负取决于pos是处于前半段还是后半段。

    • 当pos在前半段时，numRows - 1 - pos为正数；
    • 当pos在后半段时，numRows - 1 - pos为负数。

  • abs(numRows - 1 - pos)：取上述表达式的绝对值，无论pos处于哪个阶段，这个表达式总是非负的。

  • numRows - abs(numRows - 1 - pos)：这个表达式确保了row总是有效的行号。

    • 当pos在前半段时，row就是pos；
    • 当pos在后半段时，row就是2 * numRows - 2 - pos。

示例

假设numRows = 3，周期长度cycleLen = 2 * numRows - 2 = 4，那么对于pos的不同值，row的计算如下：

  • pos = 0：row = 3 - abs(3 - 1 - 0) = 3 - 2 = 1 （第一行）
  • pos = 1：row = 3 - abs(3 - 1 - 1) = 3 - 1 = 2 （第二行）
  • pos = 2：row = 3 - abs(3 - 1 - 2) = 3 - 0 = 3 （第三行）
  • pos = 3：row = 3 - abs(3 - 1 - 3) = 3 - 1 = 2 （第二行）

通过这个公式，我们可以统一处理前半段和后半段的情况，从而正确地计算出行号row。



string ret;
for (const auto& row : rows) {
    ret += row;
}
return ret;


代码作用


这段代码的目的是将之前按照Z字形排列分配到各个行的字符重新组合成一个新的字符串。具体来说：


  1.  
    初始化结果字符串：
     
    string ret;
     
    创建一个空字符串ret，用于存放最终的结果字符串。
     
  2.  
    遍历所有行：
     
    for (const auto& row : rows) {
    ret += row;
}
     
    这里使用了范围基础的for循环来遍历rows向量中的每个字符串。rows是一个包含每一行字符的vector<string>。
     
  3.  
    拼接字符串：
     
    ret += row;
     
    对于rows中的每一个字符串row，将其追加到结果字符串ret的末尾。这样，每一行的字符都会依次被加入到ret中。
     
  4.  
    返回结果字符串：
     
    return ret;
     
    返回最终的结果字符串ret，它包含了按照Z字形排列规则重新组织后的字符序列。
     


const auto& row : rows 解释


这段代码是一个范围基础的for循环（range-based for loop），它是C++11引入的一种更加简洁和易读的方式来遍历容器中的元素。


语法解释


  1.  
    const：
    

    • const关键字表明在此循环中，row是一个常量引用，意味着你不能通过row来修改原始容器中的元素。这样做可以提高效率，因为不需要复制元素。
  2.  
    auto：
    

    • auto关键字用来自动推断row的类型。编译器会根据rows容器中的元素类型来自动确定row的类型。这样可以避免手动指定类型，使代码更简洁。
  3.  
    &：
    

    • &表示row是一个引用（reference）。这意味着row直接引用容器中的元素，而不是复制它们。这样做可以避免在每次循环时复制元素，提高性能。
  4.  
    row：
    

    • row是循环体中使用的变量名，代表每次迭代时当前元素的引用。
  5.  
    rows：
    

    • rows是我们要遍历的容器（在这里是一个std::vector<std::string>）。


 


逐步解释


  1.  
    初始化：
    

    • 在每次循环开始之前，row会被初始化为rows容器中的下一个元素的引用。
  2.  
    循环条件：
    

    • 循环会一直执行，直到所有的元素都被处理完毕。
  3.  
    循环体：
    

    • 每次迭代时，row代表当前元素的引用。在这个例子中，row是rows中的一个字符串。
  4.  
    更新结果字符串：
    

    • ret += row; 这一行代码将当前的字符串row追加到结果字符串ret的末尾。


示例


假设rows是一个包含三个字符串的向量：{"PAHN", "YP", "ALSIGYIR"}。


  1.  
    第一次迭代：
    

    • row引用rows[0]，即"PAHN"。
    • ret += row; => ret = "PAHN"。
  2.  
    第二次迭代：
    

    • row引用rows[1]，即"YP"。
    • ret += row; => ret = "PAHNY"。
  3.  
    第三次迭代：
    

    • row引用rows[2]，即"ALSIGYIR"。
    • ret += row; => ret = "PAHNYALSIGYIR"。


为什么使用const auto&


  1.  
    避免复制：
    

    • 使用引用而不是复制元素可以提高性能，特别是在处理较大的对象时。
  2.  
    类型推断：
    

    • auto关键字让编译器自动推断类型，减少了代码编写时的工作量，并提高了可读性和维护性。
  3.  
    不可变性：
    

    • const关键字确保在循环过程中不会修改容器中的元素，这对于只读操作非常有用。


 


 


 


 


 




标签：numRows,rows,字符,--,pos,ret,力扣,解析,row	

From： https://blog.csdn.net/wxtg1921/article/details/143315285
      

      




      

      

        
相关文章

        

          
    
 
  • WebSocket详解：从前端到后端的全栈理解
    文章目录前言一、WebSocket简介1.1WebSocket的特点二、WebSocket的工作原理2.1握手过程2.2数据传输三、WebSocket在前端的应用四、WebSocket在后端的应用五、WebSocket的局限与解决方案结语前言随着互联网技术的发展，传统的HTTP协议在某些场景下的局限性逐渐显......
     
  • Golang 开源库分享：faker - 随机生成有趣的假数据！
    GitHub仓库链接：https://github.com/bxcodec/faker简介在开发和测试过程中，我们经常需要各种各样的测试数据。如果手动去生成这些数据，不仅耗时，还容易出错。faker是一个Go语言的假数据生成库，可以快速生成各种字段的随机数据。这个库可以帮我们轻松生成各种属性的假数据，比如姓名......
     
  • ShellScript
    StorageSrvShelScript编写添加用户的脚本，存储在/shells/userAdd.sh目录。当有新员工入职时，管理员运行脚本为其创建公司账号。自动分配客户端账号、公司邮箱、samba目录及权限、网站账号等。以userAddlifei的方式运行脚本，lifei为举例的员工姓名前提条件完成了LDAP服务......
     
  • 专有云是什么
    专有云，或称私有云，是一种仅供特定组织或企业使用的云计算环境。本文将介绍以下几个方面：1、专有云的定义与特性；2、专有云与公有云的对比；3、专有云的应用场景；4、如何构建和管理专有云。在定义与特性部分，我们将详细探讨专有云如何通过提供独享的资源和高度定制的服务，满足特定组织的需......
     
  • ”回溯算法“框架及练习题
    @目录一、回溯算法是什么？二、框架如下：本人其他文章链接一、回溯算法是什么？结论：回溯=穷举解决一个回溯问题，实际上就是一个决策树的遍历过程路径：就是已经做出的选择选择列表：就是你当前可以做出的选择结束条件：就是basecase条件，也就是临界条件二、框架如下：框架如下：resu......
     
  • 视频播放组件中，样式全屏和全屏的区别是什么？
    在视频播放组件中，"样式全屏"和"全屏"是两种不同的显示模式，它们的主要区别在于显示范围和用户体验。以下是详细的解释：样式全屏（PseudoFullscreen）显示范围：样式全屏通常是指在当前网页中最大化视频播放器的显示区域，但不会覆盖整个浏览器窗口。视频播放器会扩展到其父容器的最......
     
  • 详细介绍磁珠的工作原理
    磁珠在电路中也是用得非常多的，下面是一些经常会看到的知识点，或者说是经验吧。①电感的单位是亨H，磁珠的单位是欧姆Ω②电感是储存能量的，磁珠是通过发热来消耗能量的③磁珠是用来吸收超高频信号，多用于信号回路及EMC对策不知道同志们想过没有，这些结论是怎么来的呢？要理解......
     
  • 如何实现一个通知系统？
    在实际工作中，我们经常会用到通知系统，比如，用户完成在线购买后，需要发送订单确认邮件、支付处理成功的短信以及包裹发货的推送通知。那么，什么是通知系统？如何设计一个通知系统？需求收集在设计之前，我们先来详细了解下通知系统的需求，本文从功能需求和非功能需求两个方面来介绍。功能需......
     
  • PostgreSQL技术大讲堂 - 第70讲：PG数据库数据加载调优案例
     PostgreSQL技术大讲堂-第70讲，主题：postgresq数据库数据加载调优案例讲课内容：  1、数据库参数调整  2、后台进程cpu绑定调整  3、数据库并行操作调整  数据加载是每个DBA经常需要完成的工作，如何让数据加载变得更快，本期视频跟大家一起分享调优带来的乐趣......
     
  • Spring Boot 和 Spring Cloud 的区别和联系_1
    ###SpringBoot和SpringCloud的区别和联系在现代软件开发领域，SpringBoot和SpringCloud是两个极其重要的框架，它们在微服务架构中扮演着关键角色。直接回答这个问题，SpringBoot和SpringCloud的主要区别在于：SpringBoot旨在简化Spring应用的创建和开发过程、SpringClou......
     
    •            
          

        

      

    

    

      
赞助商

      




      

      
阅读排行

      

        
      

    

  





  
 
    
网站主页关于我们联系我们网站地图 

    
本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。 

    
Copyright © 2020-2023  IPS99  版权所有 IPS99