68. 文本左右对齐【 力扣(LeetCode) 】
一、题目描述
给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词;也就是说,尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充,使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配,则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐,且单词之间不插入额外的空格。
注意:
单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0,小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
二、测试用例
示例 1:
输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
["This is an","example of text","justification. "
]
示例 2:
输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
["What must be","acknowledgment ","shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",因为最后一行应为左对齐,而不是左右两端对齐。 第二行同样为左对齐,这是因为这行只包含一个单词。
示例 3:
输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"],maxWidth = 20
输出:
["Science is what we","understand well","enough to explain to","a computer. Art is","everything else we","do "
]
提示:
1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] 由小写英文字母和符号组成
1 <= maxWidth <= 100
words[i].length <= maxWidth
三、解题思路
- 基本思路:
贪心算法,按顺序累加单词长度,如果一旦大于一行最大长度,则除去该单词生成一行,记得特殊处理一个单词一行和最后一行单词,这两种情况都是左对齐。 - 具体思路:
- 预处理:定义函数
add_space(int n),其作用是生成n个空格的字符串。定义函数add_str(int start, int end, int len, int maxWidth, vector<string>& words),其作用是生成一行字符串,参数start表示该行的首个单词下标,end表示下一行的首个单词下标,len表示该行单词长度,不包括空格,maxWidth表示该行长度,words表示所有单词。 - 生成每行字符串:按序遍历单词,累加单词长度,判断累加单词长度+应需空格长度是否小于每行最大长度,是,表示可以容纳该单词,则累加单词长度;否则,表示超过,则生成该行,并且重置累加单词长度,记录该单词下标作为下一行的首个单词下标。
- 后处理:最后一定会剩下一行单词没有处理,特殊处理最后一行单词,拼接单词和必要的空格,最后补充空格使其填满一行。
- 预处理:定义函数
四、参考代码
时间复杂度: O ( n ) \Omicron(n) O(n)
空间复杂度: O ( n ) \Omicron(n) O(n)
class Solution {
public:string add_space(int n) {return string(n,' ');}string add_str(int start, int end, int len, int maxWidth,vector<string>& words) {string str = "", space = "";if (end - start == 1) {str = words[start] + add_space(maxWidth - len);} else {int count = (maxWidth - len) / (end - start - 1);int r = (maxWidth - len) - count * (end - start - 1);str = words[start];for (int j = start + 1; j < end; j++) {if (r > 0) {str += " ";r--;}str += add_space(count) + words[j];}}return str;}vector<string> fullJustify(vector<string>& words, int maxWidth) {int n = words.size();int len = 0, start = 0;vector<string> strs;for (int i = 0; i < n; i++) {if (len + words[i].length() + i - start <= maxWidth) {len += words[i].length();} else {strs.push_back(add_str(start, i, len, maxWidth, words));len = 0;start = i--;}}// 拼接最后一行string last=words[start];for(int i=start+1;i<n;i++){last+=" "+words[i];}strs.push_back(last+add_space(maxWidth-last.length()));return strs;}
};
相关文章:
68. 文本左右对齐【 力扣(LeetCode) 】
一、题目描述 给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词;也就是说,尽可能多地往每行中放置单…...
【中等】 猿人学web第一届 第6题 js混淆-回溯
文章目录 请求流程请求参数 加密参数定位r() 方法z() 方法 加密参数还原JJENCOde js代码加密环境检测_n("jsencrypt")12345 计算全部中奖的总金额请求代码注意 请求流程 请求参数 打开 调试工具,查看数据接口 https://match.yuanrenxue.cn/api/match/6 请…...
低、中、高频率段具体在不同应用中的范围是多少
1、低频率段(Low Frequency Range) ①建筑声学和噪声控制:通常将20 Hz 到 200 Hz 的频率范围视为低频段。在这一范围内,声音的波长较长,通常与低音(如重低音音乐)和建筑结构中的振动有关。 ②…...
Oxford Model600 Model400低温氦压缩机cryogenic helium compressor手侧
Oxford Model600 Model400低温氦压缩机cryogenic helium compressor手侧...
Golang面试题四(并发编程)
目录 1.Go常见的并发模型 2.哪些方法安全读写共享变量 3.如何排查数据竞争问题 4.Go有哪些同步原语 1. Mutex (互斥锁) 2. RWMutex (读写互斥锁) 3. Atomic 3.1.使用场景 3.2.整型操作 3.3.指针操作 3.4.使用示例 4. Channel 使用场景 使用示例 5. sync.WaitGr…...
计算机学生高效记录并整理编程学习笔记的方法
哪些知识点需要做笔记? 以下是我认为计算机学生大学四年可以积累的笔记。 ① 编程语言类(C语言CJava):保留课堂笔记中可运行的代码部分,课后debug跑一跑。学习语言初期应该多写代码(从仿写到自己写&#…...
【书生大模型实战】L2-LMDeploy 量化部署实践闯关任务
一、关卡任务 基础任务(完成此任务即完成闯关) 使用结合W4A16量化与kv cache量化的internlm2_5-7b-chat模型封装本地API并与大模型进行一次对话,作业截图需包括显存占用情况与大模型回复,参考4.1 API开发(优秀学员必做)使用Func…...
《编程学习笔记之道:构建知识宝库的秘诀》
在编程的浩瀚世界里,我们如同勇敢的探险家,不断追寻着知识的宝藏。而高效的笔记记录和整理方法,就像是我们手中的指南针,指引着我们在这片知识海洋中前行,不至于迷失方向。在这篇文章中,我们将深入探讨如何…...
DETR论文,基于transformer的目标检测网络 DETR:End-to-End Object Detection with Transformers
transformer的基本结构: encoder-decoder的基本流程为: 1)对于输入,首先进行embedding操作,即将输入映射为向量的形式,包含两部分操作,第一部分是input embedding:例如,在NLP领域&…...
untiy有渲染线程和逻辑线程嘛
之前我也这么认为,其实unity引擎是单线程的,当然后续的jobs不在考虑范围内 如果你在一个awake 或者 start方法中 延时,是会卡住主线程的 比如 其实游戏引擎有一个基础简单理解,那就是不断的进行一个循环,在这个周期循…...
什么是数据仓库ODS层?为什么需要ODS层?
在大数据时代,数据仓库的重要性不言而喻。它不仅是企业数据存储与管理的核心,更是数据分析与决策支持的重要基础。而在数据仓库的各个层次中,ODS层(Operational Data Store,操作型数据存储)作为关键一环&am…...
permutation sequence(
60. Permutation Sequence class Solution:def getPermutation(self, n: int, k: int) -> str:def rec(k, l, ans, n):if(n0): return# 保留第一个位置,剩下数字的组合leftCom math.factorial(n - 1) #用于计算 (n-1) 的阶乘值ele k // leftCommod k % leftCo…...
PCL 三线性插值
文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 三线性插值是一种在三维空间中使用已知数据点进行插值的方法。它是在立方体内的插值方法,通过利用立方体的八个顶点的已知值来估算立方体内任意一点的值。三线性插值扩展了一维的线性插值和二维的双线性插值。其基…...
JVM虚拟机(一)介绍、JVM内存模型、JAVA内存模型,堆区、虚拟机栈、本地方法栈、方法区、常量池
目录 学习JVM有什么用、为什么要学JVM? JVM是什么呢? 优点一:一次编写,到处运行。(Write Once, Run Anywhere,WORA) 优点二:自动内存管理,垃圾回收机制。 优点三&am…...
Python利用xlrd复制一个Excel中的sheet保留原格式创建一个副本(注:xlrd只能读取xls)
目录 专栏导读库的介绍库的安装完整代码总结 专栏导读 🌸 欢迎来到Python办公自动化专栏—Python处理办公问题,解放您的双手 🏳️🌈 博客主页:请点击——> 一晌小贪欢的博客主页求关注 👍 该系列文…...
40、Python之面向对象:扩展的对象属性解析顺序(描述符 + MRO)
引言 在上一篇文章中,我们简单回顾了Python中在继承语境下的属性解析顺序,同时补充了能够控制、影响属性解析的3个函数/方法(2个魔术方法 1个内置函数),相信对Python中属性的解析,相较于MRO,有…...
stm32—时钟、定时器和看门狗
1. 时钟 什么是时钟呢? 一个可以产生周期性信号的设备 什么是周期性信号? 1 ----- ----- ----- 0 ----- ----- ----- 所以时钟信号就是周期性变化的信号 关于时钟我们有两个比较重要…...
Windows平台RTSP|RTMP播放器如何实时调节音量
我们在做Windows平台RTSP、RTMP播放器的时候,有这样的技术需求,特别是多路监控的时候,并不是每一路audio都需要播放出来的,所以,这时候,需要有针对音量调节的设计: /** smart_player_sdk.cs* C…...
Leetcode JAVA刷刷站(10)正则表达式匹配
一、题目概述 二、思路方向 在Java中,实现一个支持.和*的正则表达式匹配器,可以通过递归或动态规划(DP)的方法来完成。这里,我将使用动态规划的方法来解决这个问题,因为它更容易理解和实现。 动态规划的思…...
合并图片为pdf
1.先使用IDM在网页下载: 2.按文件类型分组,在按名称大小排序,之后使用Acrobat合并文件成一个pdf即可...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving
地址:LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂,正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...
