Z字型变换(Go,LeetCode)

目录

题目描述

解决方案

代码

代码走读

传送门


 

题目描述

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

比如输入字符串为 LEETCODEISHIRING ,行数为3时,排列如下:

L   C   I   R
E T O E S I I G
E   D   H   N

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串:LCIRETOESIIGEDHN

 

解决方案

使用模拟法解决形象生动。

假设行数为n,我们生成n个列表表示成n行,定义一个指针变量模拟Z字形走向:从第1行依次往下,到达最后一行后在往上走,重复该循环,直到所有元素都被遍历完。

指针变量每走到一个元素,就将该元素插入到对应行数的列表中。最终将每一行字符连接输出,得到想要的结果。

复杂度分析:因为只需要遍历一遍字符串,因此时间复杂度为 O(n)。只需要定义常数个变量,因此空间复杂度为 O(1) 。

 

代码

package main

import (
	"fmt"
	"strings"
)

func convert(s string, numRows int) string {
	if numRows == 1 {
		return s
	}

	pool := make([][]string, 0)
	for i := 0; i < numRows; i++ {
		pool = append(pool, make([]string, 0))
	}
	down := false
	currentLine := 0

	for _, c := range s {
		if currentLine == 0 || currentLine == numRows-1 {
			down = !down
		}

		pool[currentLine] = append(pool[currentLine], string(c))
		if down {
			currentLine++
		} else {
			currentLine--
		}
	}

	result := ""
	for i := range pool {
		line := strings.Join(pool[i], "")
		result += line
	}
	return result
}

 

代码走读

package main

import (
   "fmt"
   "strings"
)

func convert(s string, numRows int) string {
   // 如果给定的行数只有一行,那么只需要将原字符串返回
   if numRows == 1 {
      return s
   }

   // 初始化存储每一行字符的二维切片
   pool := make([][]string, 0)
   for i := 0; i < numRows; i++ {
      pool = append(pool, make([]string, 0))
   }

   // down变量用来模拟Z字型游标的走向(flase向上,true向下)
   down := false

   // 游标指针变量,表示当前行数
   currentLine := 0

   for _, c := range s {
      // 如果游标抵达边界,需要改变方向
      if currentLine == 0 || currentLine == numRows-1 {
         down = !down
      }

      // 对应行添加字符
      pool[currentLine] = append(pool[currentLine], string(c))
      if down {
         currentLine++
      } else {
         currentLine--
      }
   }

   // 按照每一行字符依次拼接的方式输出结果
   result := ""
   for i := range pool {
      line := strings.Join(pool[i], "")
      result += line
   }
   return result
}

// 自测用例
func main() {
   fmt.Println(convert("LEETCODEISHIRING", 3))
}

 

传送门

LeetCode试题链接

热门文章

暂无图片
编程学习 ·

OpenCV笔记三--直方图

直方图定义:直方图均衡化-提高对比度-cv::equalizeHistvoid equalizeHist( InputArray src, OutputArray dst ); //输入为八位灰度图像从图片建立直方图-split,calcHistapi:void split(const Mat& src, Mat* mvbegin);//三Mat图像转化为三个图像 void calcHist( const Mat…
暂无图片
编程学习 ·

css实现瀑布流

一行代码实现瀑布流css 的 column-count 属性,将一个盒子分成 x 列,例如 column-count: 2; ,就是将一个div分成 2 列但是排列不是按照数组顺序排序,因为分成2列后是按照顺序从上往下排列,会自动计算,第一列按照数组顺序渲染完才接着渲染第二列,无关紧要 <template>…
暂无图片
编程学习 ·

Python之OpenCV的学习(一)

一.安装 打开Pycharm:File -> Settings -> Project:xxxx下的Project Interpreter,如图所示然后,点击右边的加号进行搜索点击左下角Install Package即可 如果搜索不出来,可以看一下是不是pip源的问题 点击Manage Repositories我使用的是豆瓣pip源:http://pypi.douba…
暂无图片
编程学习 ·

JS 中的展开运算符你了解多少 ?

什么是展开运算符 (...)?展开运算符 :允许一个表达式在某处展开。展开运算符在多个参数(用于函数调用)或多个元素(用于数组字面量)或者多个变量(用于解构赋值)等地方可以使 用,作用就是 展开数组或字符串为一个新数组。注意 : 展开运算符不能用在对象当中,因为目前…
暂无图片
编程学习 ·

Java-eclipse 设置字体字号大小,如何设置居中

文字一般都放在 标签内: 这里以 JLable 与 按钮 为实例: JLabel label; JButton exitBtn; //表题**标签** label = new JLabel("个人停车详情",JLabel.CENTER);//设置字体居中 label.setFont(new Font("微软雅黑", Font.BOLD, 20));//设置字体字号大小 l…
暂无图片
中恒嘉业 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
cgfy ·

8. 源码分析之ConsumeQueue

源码分析之ConsumeQueue 消息发送时数据在ConsumeQueue的落地 ​ 连续发送5条消息&#xff0c;消息是不定长&#xff0c;首先所有信息先放入 Commitlog中&#xff0c;每一条消息放入Commitlog的时候都需要上锁&#xff0c;确保顺序的写入。 ​ 当Commitlog写成功了之后。数据…
暂无图片
coreui ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
未来博客 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
建站日记 ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
mfbz ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
mfbz ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
珊珊日记 ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
珊珊日记 ·

8. 源码分析之ConsumeQueue

源码分析之ConsumeQueue 消息发送时数据在ConsumeQueue的落地 ​ 连续发送5条消息&#xff0c;消息是不定长&#xff0c;首先所有信息先放入 Commitlog中&#xff0c;每一条消息放入Commitlog的时候都需要上锁&#xff0c;确保顺序的写入。 ​ 当Commitlog写成功了之后。数据…