阿亮的算法之路——6. Z 字形变换

2024-01-07 02:59
文章标签 算法 变换 字形 阿亮

本文主要是介绍阿亮的算法之路——6. Z 字形变换,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

题目描述
看到题目就觉得有戏,看起来复杂了一点,但是凭我的感觉,这题用暴力是比较容易做的,只是可能比较繁琐。

z型变换,实际上是n型,不过都无所谓,我用一个二维数组往里一套,后面再遍历拼接成字符串,就OK了。只是在往二维数组里放值的时候,条件不容易控制,需要慢慢找规律。

自己尝试

思路

因为需要慢慢找规律,所以我在草稿纸上画了一下图:
草稿图就是字符串的每个字符索引,与这个字符被放入二维数组中的位置关系。仔细观察,我们可以将这些分组,例如:当numRows=3时,这个变量代表着这个字符串需要被分成一个多少行的z型,我们可以将0-3、4-7、8-11……等分成一个组,当numRows=4时,可以将0-5、6-11、12-17……等分成一个组。为什么要这样分呢?因为这些组0、4、8和0、6、12这数都被放到了第一行,也就是说,他们会被放入二维数组的第一个数组里面。这些数好像也都有着某种规律,好像是可以被某个整数整除。我们就可以根据这个规律来确定每个被放在第一行的数,然后可以通过numRows确定,被放在第一列的数,然后确定被放在斜线上的数,最后在根据递增找出递增与所处二维数组中的位置

这是主要的处理逻辑,然后再对一些特殊和临界情况进行处理就OK了

首次通过
    public static String convert(String s, int numRows){int length = s.length();StringBuilder stringBuilder = new StringBuilder();if (numRows == 1){ return s; }if (numRows == 2){char[][] chars = new char[2][length / 2 + 1];for (int i = 0; i < length; i++){if (i % 2 == 0){ chars[0][i / 2] = s.charAt(i); }else{ chars[1][(i-1)/2] = s.charAt(i); }}for (int n = 0; n < chars.length; n++){for (int m = 0; m < chars[n].length; m++){char c = chars[n][m];if (c != '\u0000'){ stringBuilder.append(c); }}}return stringBuilder.toString();}else{char[][] chars = new char[numRows][length];int lineCount = 0;for (int i = 0; i < length; i++){if (i / (numRows - 1) % 2 == 0 && i % (numRows - 1) == 0){for (int j = 0; j < numRows; j++){if (i + j >= length){ break; }chars[j][lineCount * (numRows - 1)] = s.charAt(i + j);}i += numRows;for (int j = 0; j < numRows - 2; j++){if (i + j >= length){ break; }chars[numRows - 2 - j][(lineCount) * (numRows - 1) + j + 1] = s.charAt(i + j);}i += numRows - 3;lineCount++;}}for (int n = 0; n < chars.length; n++){for (int m = 0; m < chars[n].length; m++){char c = chars[n][m];if (c != '\u0000'){ stringBuilder.append(c); }}}return stringBuilder.toString();}}

代码冗余较多,提交结果
第一次提交还好,能完成功能,至于优化,咱们慢慢来,如果功能都无法完成,那就有点打击自信心了。

初次优化
    public static String convert(String s, int numRows){int length = s.length();StringBuilder stringBuilder = new StringBuilder();if (numRows == 1){ return s; }char[][] chars = new char[numRows][length / 2 + 1];if (numRows == 2){for (int i = 0; i < length; i++){if (i % 2 == 0){ chars[0][i / 2] = s.charAt(i); }else{ chars[1][(i-1)/2] = s.charAt(i); }}}else{int lineCount = 0;for (int i = 0; i < length; i++){if (i / (numRows - 1) % 2 == 0 && i % (numRows - 1) == 0){for (int j = 0; j < numRows; j++){if (i + j >= length){ break; }chars[j][lineCount * (numRows - 1)] = s.charAt(i + j);}i += numRows;for (int j = 0; j < numRows - 2; j++){if (i + j >= length){ break; }chars[numRows - 2 - j][(lineCount) * (numRows - 1) + j + 1] = s.charAt(i + j);}i += numRows - 3;lineCount++;}}}for (int n = 0; n < chars.length; n++){for (int m = 0; m < chars[n].length; m++){char c = chars[n][m];if (c != '\u0000'){ stringBuilder.append(c); }}}return stringBuilder.toString();}

思路没有变,对一些冗余的代码进行抽取,提交结果

提交结果2
嘿嘿!还不错。代码还可以再简化一点,但是代码简化了,效率方面却没有提升,可能是因为逻辑没有变,只是改进了写法。所以代码也就不贴了。

大佬思路

官方给出的题解,也是类似于找规律,但是他找的规律巧妙得多,他利用的是:也是将每个字符放入一个类似二维数组的容器,安装这个n性移动的时候,每次这个行都是朝着一个方向变的,只是到了顶部或者底部,才会转向,他就利用了这个特点,巧妙的控制行的变动,最后将这个类似二维数组的容器再拼接成一个字符串。

代码
public String convert(String s, int numRows) {if (numRows == 1) return s;List<StringBuilder> rows = new ArrayList<>();for (int i = 0; i < Math.min(numRows, s.length()); i++)rows.add(new StringBuilder());int curRow = 0;boolean goingDown = false;for (char c : s.toCharArray()) {rows.get(curRow).append(c);if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;curRow += goingDown ? 1 : -1;}StringBuilder ret = new StringBuilder();for (StringBuilder row : rows) ret.append(row);return ret.toString();}

提交结果
官方答案提交结果
每次官方给出的答案都是如此巧妙,总是简洁又能完成功能,而且效率还不错,真好奇这些人脑子里面装的是什么。

在官方的题解下面看到了一个评论,把我笑喷了
题外话

哈哈,估计这哥们和我一样,花了老大工夫,写了几十上百行代码,还没人家写的十几行代码效率高。

今日拿下两题,噢力给!!!!

这篇关于阿亮的算法之路——6. Z 字形变换的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/ql_7256/article/details/107884557
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/578506

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

C++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析:transform_iterator1. transform_iterat

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为