当前位置: 首页 > news >正文

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

三、解题思路

  1. 基本思路:
      贪心算法,按顺序累加单词长度,如果一旦大于一行最大长度,则除去该单词生成一行,记得特殊处理一个单词一行和最后一行单词,这两种情况都是左对齐。
  2. 具体思路:
    • 预处理:定义函数 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 &#xff0c;重新排版单词&#xff0c;使其成为每行恰好有 maxWidth 个字符&#xff0c;且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词&#xff1b;也就是说&#xff0c;尽可能多地往每行中放置单…...

【中等】 猿人学web第一届 第6题 js混淆-回溯

文章目录 请求流程请求参数 加密参数定位r() 方法z() 方法 加密参数还原JJENCOde js代码加密环境检测_n("jsencrypt")12345 计算全部中奖的总金额请求代码注意 请求流程 请求参数 打开 调试工具&#xff0c;查看数据接口 https://match.yuanrenxue.cn/api/match/6 请…...

低、中、高频率段具体在不同应用中的范围是多少

1、低频率段&#xff08;Low Frequency Range&#xff09; ①建筑声学和噪声控制&#xff1a;通常将20 Hz 到 200 Hz 的频率范围视为低频段。在这一范围内&#xff0c;声音的波长较长&#xff0c;通常与低音&#xff08;如重低音音乐&#xff09;和建筑结构中的振动有关。 ②…...

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…...

计算机学生高效记录并整理编程学习笔记的方法

哪些知识点需要做笔记&#xff1f; 以下是我认为计算机学生大学四年可以积累的笔记。 ① 编程语言类&#xff08;C语言CJava&#xff09;&#xff1a;保留课堂笔记中可运行的代码部分&#xff0c;课后debug跑一跑。学习语言初期应该多写代码&#xff08;从仿写到自己写&#…...

【书生大模型实战】L2-LMDeploy 量化部署实践闯关任务

一、关卡任务 基础任务&#xff08;完成此任务即完成闯关&#xff09; 使用结合W4A16量化与kv cache量化的internlm2_5-7b-chat模型封装本地API并与大模型进行一次对话&#xff0c;作业截图需包括显存占用情况与大模型回复&#xff0c;参考4.1 API开发(优秀学员必做)使用Func…...

《编程学习笔记之道:构建知识宝库的秘诀》

在编程的浩瀚世界里&#xff0c;我们如同勇敢的探险家&#xff0c;不断追寻着知识的宝藏。而高效的笔记记录和整理方法&#xff0c;就像是我们手中的指南针&#xff0c;指引着我们在这片知识海洋中前行&#xff0c;不至于迷失方向。在这篇文章中&#xff0c;我们将深入探讨如何…...

DETR论文,基于transformer的目标检测网络 DETR:End-to-End Object Detection with Transformers

transformer的基本结构: encoder-decoder的基本流程为&#xff1a; 1&#xff09;对于输入&#xff0c;首先进行embedding操作&#xff0c;即将输入映射为向量的形式&#xff0c;包含两部分操作&#xff0c;第一部分是input embedding&#xff1a;例如&#xff0c;在NLP领域&…...

untiy有渲染线程和逻辑线程嘛

之前我也这么认为&#xff0c;其实unity引擎是单线程的&#xff0c;当然后续的jobs不在考虑范围内 如果你在一个awake 或者 start方法中 延时&#xff0c;是会卡住主线程的 比如 其实游戏引擎有一个基础简单理解&#xff0c;那就是不断的进行一个循环&#xff0c;在这个周期循…...

什么是数据仓库ODS层?为什么需要ODS层?

在大数据时代&#xff0c;数据仓库的重要性不言而喻。它不仅是企业数据存储与管理的核心&#xff0c;更是数据分析与决策支持的重要基础。而在数据仓库的各个层次中&#xff0c;ODS层&#xff08;Operational Data Store&#xff0c;操作型数据存储&#xff09;作为关键一环&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# 保留第一个位置&#xff0c;剩下数字的组合leftCom math.factorial(n - 1) #用于计算 (n-1) 的阶乘值ele k // leftCommod k % leftCo…...

PCL 三线性插值

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 三线性插值是一种在三维空间中使用已知数据点进行插值的方法。它是在立方体内的插值方法,通过利用立方体的八个顶点的已知值来估算立方体内任意一点的值。三线性插值扩展了一维的线性插值和二维的双线性插值。其基…...

JVM虚拟机(一)介绍、JVM内存模型、JAVA内存模型,堆区、虚拟机栈、本地方法栈、方法区、常量池

目录 学习JVM有什么用、为什么要学JVM&#xff1f; JVM是什么呢&#xff1f; 优点一&#xff1a;一次编写&#xff0c;到处运行。&#xff08;Write Once, Run Anywhere&#xff0c;WORA&#xff09; 优点二&#xff1a;自动内存管理&#xff0c;垃圾回收机制。 优点三&am…...

Python利用xlrd复制一个Excel中的sheet保留原格式创建一个副本(注:xlrd只能读取xls)

目录 专栏导读库的介绍库的安装完整代码总结 专栏导读 &#x1f338; 欢迎来到Python办公自动化专栏—Python处理办公问题&#xff0c;解放您的双手 &#x1f3f3;️‍&#x1f308; 博客主页&#xff1a;请点击——> 一晌小贪欢的博客主页求关注 &#x1f44d; 该系列文…...

40、Python之面向对象:扩展的对象属性解析顺序(描述符 + MRO)

引言 在上一篇文章中&#xff0c;我们简单回顾了Python中在继承语境下的属性解析顺序&#xff0c;同时补充了能够控制、影响属性解析的3个函数/方法&#xff08;2个魔术方法 1个内置函数&#xff09;&#xff0c;相信对Python中属性的解析&#xff0c;相较于MRO&#xff0c;有…...

stm32—时钟、定时器和看门狗

1. 时钟 什么是时钟呢&#xff1f; 一个可以产生周期性信号的设备 什么是周期性信号&#xff1f; 1 ----- ----- ----- 0 ----- ----- ----- 所以时钟信号就是周期性变化的信号 关于时钟我们有两个比较重要…...

Windows平台RTSP|RTMP播放器如何实时调节音量

我们在做Windows平台RTSP、RTMP播放器的时候&#xff0c;有这样的技术需求&#xff0c;特别是多路监控的时候&#xff0c;并不是每一路audio都需要播放出来的&#xff0c;所以&#xff0c;这时候&#xff0c;需要有针对音量调节的设计&#xff1a; /** smart_player_sdk.cs* C…...

Leetcode JAVA刷刷站(10)正则表达式匹配

一、题目概述 二、思路方向 在Java中&#xff0c;实现一个支持.和*的正则表达式匹配器&#xff0c;可以通过递归或动态规划&#xff08;DP&#xff09;的方法来完成。这里&#xff0c;我将使用动态规划的方法来解决这个问题&#xff0c;因为它更容易理解和实现。 动态规划的思…...

合并图片为pdf

1.先使用IDM在网页下载&#xff1a; 2.按文件类型分组&#xff0c;在按名称大小排序&#xff0c;之后使用Acrobat合并文件成一个pdf即可...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验

2024年初&#xff0c;人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目&#xff08;一款融合大型语言模型能力的云端AI编程IDE&#xff09;时&#xff0c;技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力&#xff0c;TRAE在WayToAGI等…...