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

算法leetcode|68. 文本左右对齐(rust重拳出击)


文章目录

  • 68. 文本左右对齐:
    • 样例 1:
    • 样例 2:
    • 样例 3:
    • 提示:
  • 分析:
  • 题解:
    • rust:
    • go:
    • c++:
    • python:
    • java:


68. 文本左右对齐:

给定一个单词数组 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

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。
  • 首先要仔细理解题目的意思。
  • 每行有最大宽度,在宽度范围内尽可能多的放置单词,单词间的空格尽可能平均,也就是最大差一个空格,而且多的空格要都在左面的单词之间。
  • 不难理解,但是实现起来有很多细节,比较繁琐,容易出错,应该尽量复用方法或者函数。
  • 我们需要一个在单词之间填充指定个数空格的方法或者函数,可以拆分为拼装指定个数个空格为字符串的方法或者函数,以及在单词之间插入指定字符串的方法或者函数,这样很多地方可以复用。

题解:

rust:

impl Solution {pub fn full_justify(words: Vec<String>, max_width: i32) -> Vec<String> {// blank 返回长度为 n 的由空格组成的字符串fn blank(n: usize) -> String {(0..n).map(|_| {' '}).collect()}// join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串fn join(words: &Vec<String>, left: usize, right: usize, sep: &str) -> String {let mut str = String::from(words[left].as_str());(left + 1..right).for_each(|i| {str.push_str(sep);str.push_str(words[i].as_str());});return str;}let max_width = max_width as usize;let mut ans = Vec::new();let (mut right, n) = (0, words.len());loop {let left = right; // 当前行的第一个单词在 words 的位置let mut sum_len = 0; // 统计这一行单词长度之和// 循环确定当前行可以放多少单词,注意单词之间应至少有一个空格while right < n && sum_len + words[right].len() + right - left <= max_width {sum_len += words[right].len();right += 1;}// 当前行是最后一行:单词左对齐,且单词之间应只有一个空格,在行末填充剩余空格if right == n {let mut row = join(&words, left, n, " ");row.push_str(blank(max_width - row.len()).as_str());ans.push(row);return ans;}let num_words = right - left;let num_spaces = max_width - sum_len;// 当前行只有一个单词:该单词左对齐,在行末填充剩余空格if num_words == 1 {let mut row = String::from(words[left].as_str());row.push_str(blank(num_spaces).as_str());ans.push(row);continue;}// 当前行不只一个单词let avg_spaces = num_spaces / (num_words - 1);let extra_spaces = num_spaces % (num_words - 1);let mut row = String::new();row.push_str(join(&words, left, left + extra_spaces + 1, blank(avg_spaces + 1).as_str()).as_str()); // 拼接额外加一个空格的单词row.push_str(blank(avg_spaces).as_str());row.push_str(join(&words, left + extra_spaces + 1, right, blank(avg_spaces).as_str()).as_str()); // 拼接其余单词ans.push(row);}}
}

go:

func fullJustify(words []string, maxWidth int) (ans []string) {blank := func(n int) string {return strings.Repeat(" ", n)}right, n := 0, len(words)for {left := right // 当前行的第一个单词在 words 的位置sumLen := 0   // 统计这一行单词长度之和// 循环确定当前行可以放多少单词,注意单词之间应至少有一个空格for right < n && sumLen+len(words[right])+right-left <= maxWidth {sumLen += len(words[right])right++}// 当前行是最后一行:单词左对齐,且单词之间应只有一个空格,在行末填充剩余空格if right == n {s := strings.Join(words[left:], " ")ans = append(ans, s+blank(maxWidth-len(s)))return}numWords := right - leftnumSpaces := maxWidth - sumLen// 当前行只有一个单词:该单词左对齐,在行末填充剩余空格if numWords == 1 {ans = append(ans, words[left]+blank(numSpaces))continue}// 当前行不只一个单词avgSpaces := numSpaces / (numWords - 1)extraSpaces := numSpaces % (numWords - 1)s1 := strings.Join(words[left:left+extraSpaces+1], blank(avgSpaces+1)) // 拼接额外加一个空格的单词s2 := strings.Join(words[left+extraSpaces+1:right], blank(avgSpaces))  // 拼接其余单词ans = append(ans, s1+blank(avgSpaces)+s2)}
}

c++:

class Solution {
private:// blank 返回长度为 n 的由空格组成的字符串string blank(int n) {return string(n, ' ');}// join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串string join(vector<string> &words, int left, int right, string sep) {string s = words[left];for (int i = left + 1; i < right; ++i) {s += sep + words[i];}return s;}
public:vector<string> fullJustify(vector<string>& words, int maxWidth) {vector<string> ans;int right = 0, n = words.size();while (true) {int left = right; // 当前行的第一个单词在 words 的位置int sumLen = 0; // 统计这一行单词长度之和// 循环确定当前行可以放多少单词,注意单词之间应至少有一个空格while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {sumLen += words[right++].length();}// 当前行是最后一行:单词左对齐,且单词之间应只有一个空格,在行末填充剩余空格if (right == n) {string s = join(words, left, n, " ");ans.emplace_back(s + blank(maxWidth - s.length()));return ans;}int numWords = right - left;int numSpaces = maxWidth - sumLen;// 当前行只有一个单词:该单词左对齐,在行末填充剩余空格if (numWords == 1) {ans.emplace_back(words[left] + blank(numSpaces));continue;}// 当前行不只一个单词int avgSpaces = numSpaces / (numWords - 1);int extraSpaces = numSpaces % (numWords - 1);string s1 = join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1)); // 拼接额外加一个空格的单词string s2 = join(words, left + extraSpaces + 1, right, blank(avgSpaces)); // 拼接其余单词ans.emplace_back(s1 + blank(avgSpaces) + s2);}}
};

python:

class Solution:def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:def blank(n: int) -> str:return ' ' * nans = []right, n = 0, len(words)while True:left = right  # 当前行的第一个单词在 words 的位置sum_len = 0  # 统计这一行单词长度之和# 循环确定当前行可以放多少单词,注意单词之间应至少有一个空格while right < n and sum_len + len(words[right]) + right - left <= maxWidth:sum_len += len(words[right])right += 1# 当前行是最后一行:单词左对齐,且单词之间应只有一个空格,在行末填充剩余空格if right == n:s = " ".join(words[left:])ans.append(s + blank(maxWidth - len(s)))breaknum_words = right - leftnum_spaces = maxWidth - sum_len# 当前行只有一个单词:该单词左对齐,在行末填充空格if num_words == 1:ans.append(words[left] + blank(num_spaces))continue# 当前行不只一个单词avg_spaces = num_spaces // (num_words - 1)extra_spaces = num_spaces % (num_words - 1)s1 = blank(avg_spaces + 1).join(words[left:left + extra_spaces + 1])  # 拼接额外加一个空格的单词s2 = blank(avg_spaces).join(words[left + extra_spaces + 1:right])  # 拼接其余单词ans.append(s1 + blank(avg_spaces) + s2)return ans

java:

class Solution {public List<String> fullJustify(String[] words, int maxWidth) {List<String> ans   = new ArrayList<String>();int          right = 0, n = words.length;while (true) {int left   = right; // 当前行的第一个单词在 words 的位置int sumLen = 0; // 统计这一行单词长度之和// 循环确定当前行可以放多少单词,注意单词之间应至少有一个空格while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {sumLen += words[right++].length();}// 当前行是最后一行:单词左对齐,且单词之间应只有一个空格,在行末填充剩余空格if (right == n) {StringBuilder sb = join(words, left, n, " ");sb.append(blank(maxWidth - sb.length()));ans.add(sb.toString());return ans;}int numWords  = right - left;int numSpaces = maxWidth - sumLen;// 当前行只有一个单词:该单词左对齐,在行末填充剩余空格if (numWords == 1) {StringBuilder sb = new StringBuilder(words[left]);sb.append(blank(numSpaces));ans.add(sb.toString());continue;}// 当前行不只一个单词int           avgSpaces   = numSpaces / (numWords - 1);int           extraSpaces = numSpaces % (numWords - 1);StringBuilder sb          = new StringBuilder();sb.append(join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1))); // 拼接额外加一个空格的单词sb.append(blank(avgSpaces));sb.append(join(words, left + extraSpaces + 1, right, blank(avgSpaces))); // 拼接其余单词ans.add(sb.toString());}}// blank 返回长度为 n 的由空格组成的字符串private StringBuilder blank(int n) {StringBuilder sb = new StringBuilder();for (int i = 0; i < n; ++i) {sb.append(' ');}return sb;}// join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串private StringBuilder join(String[] words, int left, int right, CharSequence sep) {StringBuilder sb = new StringBuilder(words[left]);for (int i = left + 1; i < right; ++i) {sb.append(sep);sb.append(words[i]);}return sb;}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~


相关文章:

算法leetcode|68. 文本左右对齐(rust重拳出击)

文章目录 68. 文本左右对齐&#xff1a;样例 1&#xff1a;样例 2&#xff1a;样例 3&#xff1a;提示&#xff1a; 分析&#xff1a;题解&#xff1a;rust&#xff1a;go&#xff1a;c&#xff1a;python&#xff1a;java&#xff1a; 68. 文本左右对齐&#xff1a; 给定一个…...

基于MATLAB实现小波算法仿真(附上多个完整源码+数据集)

小波变换是一种常用的信号处理技术&#xff0c;广泛应用于图像处理、音频处理、压缩等领域。本文将介绍MATLAB中小波变换的基本原理和实现方法&#xff0c;并给出一个示例来说明如何使用MATLAB进行小波变换和逆变换。 文章目录 1. 引言2. 小波变换的基本原理3. MATLAB中的小波变…...

【深度学习注意力机制系列】—— CBAM注意力机制(附pytorch实现)

CBAM&#xff08;Convolutional Block Attention Module&#xff09;是一种用于增强卷积神经网络&#xff08;CNN&#xff09;性能的注意力机制模块。它由Sanghyun Woo等人在2018年的论文[1807.06521] CBAM: Convolutional Block Attention Module (arxiv.org)中提出。CBAM的主…...

【资料分享】全志科技T507-H工业核心板规格书

1 核心板简介 创龙科技SOM-TLT507是一款基于全志科技T507-H处理器设计的4核ARM Cortex-A53全国产工业核心板&#xff0c;主频高达1.416GHz。核心板CPU、ROM、RAM、电源、晶振等所有元器件均采用国产工业级方案&#xff0c;国产化率100%。 核心板通过邮票孔连接方式引出MIPI C…...

Profibus-DP转modbus RTU网关modbus rtu和tcp的区别

捷米JM-DPM-RTU网关在Profibus总线侧实现主站功能&#xff0c;在Modbus串口侧实现从站功能。可将ProfibusDP协议的设备&#xff08;如&#xff1a;EH流量计、倍福编码器等&#xff09;接入到Modbus网络中&#xff1b;通过增加DP/PA耦合器&#xff0c;也可将Profibus PA从站接入…...

AlmaLinux 9 安装 Edge 和 Chrome

AlmaLinux 9 安装 Edge 和 Chrome 1. 安装 Edge2. 安装 Chrome 1. 安装 Edge 更新源&#xff0c; sudo dnf update -y # sudo dnf install dnf-utils -y添加 Edge 源&#xff0c; sudo dnf config-manager --add-repo https://packages.microsoft.com/yumrepos/edge再次更新…...

NGINX——负载均衡

负载均衡————>通过反向代理来实现 nginx反向代理的七层代理和四层代理 七层代理&#xff1a; 七层代理时最常用的反向代理方式&#xff0c;其只能配置在nginx的配置文件的http模块中&#xff0c;而且方法名称必须要定义成“upstream”模块&#xff0c;注意不能写在se…...

C#实现端口扫描和执行cmd命令、调用摄像头

C#端口扫描 using System; using System.Collections.Generic; using System.Linq; using System.Net; using System.Net.Sockets; using System.Threading;namespace PortScanner {class Program{static void Main(string[] args){// 设置扫描参数string host "localho…...

【图像恢复】基于交替乘子方法(ADMM)图像恢复算法研究[固定点收敛和应用](Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Qt 使用QLabel的派生类实现QLabel的双击响应

1 介绍 在QLabel中没有双击等事件响应&#xff0c;需要构建其派生类&#xff0c;自定义信号(signals)、重载事件函数(event)&#xff0c;最后在Qwidget中使用connect链接即可&#xff0c;进而实现响应功能。 对于其余没有需求事件响应的QObject同样适用。 此外&#xff0c;该功…...

关于@JSONField的使用

1.此注解来自jar包com.alibaba.fastjson 今天分享一个有意思的事情。这个注解作用与类的属性上&#xff0c;如下&#xff1a; ApiModelProperty(value"开始时间,格式:yyyy-MM-dd",required true) JSONField(name"start_date",ordinal 1) private String…...

Centos7单机部署ElasticSearch

Centos7单机部署ElasticSearch 引言 Elasticsearch是一种广泛使用的开源搜索引擎&#xff0c;专门为分布式环境设计&#xff0c;但也可以在单机上运行。它使存储、搜索和分析大量数据变得更加容易和高效。此教程将引导你通过在Centos7上单机部署Elasticsearch&#xff0c;涵盖…...

js玩儿爬虫

前言 提到爬虫可能大多都会想到python&#xff0c;其实爬虫的实现并不限制任何语言。 下面我们就使用js来实现&#xff0c;后端为express&#xff0c;前端为vue3。 实现功能 话不多说&#xff0c;先看结果&#xff1a; 这是项目链接&#xff1a;https://gitee.com/xi1213/w…...

新利好带动 POSE 持续上扬,月内几近翻倍

PoseiSwap 是 Nautilus Chain 上的首个 DEX&#xff0c;得益于 Nautilus Chain 的模块化 Layer3 构架&#xff0c;PoseiSwap 正在基于 zk-Rollup 方案构建全新的应用层&#xff0c;并基于此构建隐私、合规等全新的特性&#xff0c;为未来其布局 RWA 领域推动 Web2、Web3 世界的…...

Windows terminal 添加 git bash 解决git中文乱码显示问题

Windows terminal 添加 git bash 解决git中文乱码显示问题 在 windows terminal 中配置git 说明&#xff1a; 点击箭头选择设置 说明&#xff1a; 点击"添加新配置文件"配置名称命令行&#xff0c;可执行文件的具体语句 C:\Program Files\Git\bin\bash.exe启动目录…...

C语言实现选择排序

什么是选择排序&#xff1f; 选择排序是一种简单直观的排序算法&#xff0c;它的核心思想是每次从未排序的元素中选择最小&#xff08;或最大&#xff09;的元素&#xff0c;然后将其放到已排序序列的末尾。通过重复这个过程&#xff0c;直到所有元素都排好序为止。 选择排序…...

unable to write symref for HEAD: Permission denied

今天从gitee上面克隆项目到本地时报错如下 warning: unable to unlink ‘D:/IDEAcode/ruiji1.0/.git/HEAD.lock’: Invalid argument error: unable to write symref for HEAD: Permission denied 解决方法&#xff1a;将要存放项目的文件夹权限修改为完全控制 原先权限&…...

长时间序列遥感数据处理及在全球变化、物候提取、植被变绿与固碳分析、生物量估算与趋势分析等领域中的实践技术应用

植被是陆地生态系统中最重要的组分之一&#xff0c;也是对气候变化最敏感的组分&#xff0c;其在全球变化过程中起着重要作用&#xff0c;能够指示自然环境中的大气、水、土壤等成分的变化&#xff0c;其年际和季节性变化可以作为地球气候变化的重要指标。此外&#xff0c;由于…...

【行为型设计模式】C#设计模式之策略模式

题目&#xff1a;假设你正在开发一个手机应用程序&#xff0c;该应用程序包含一个计算器功能。用户可以根据自己的需求选择不同的计算策略进行计算&#xff0c;例如加法、减法、乘法或除法。请使用策略模式设计该计算器功能&#xff0c;使得用户可以根据自己的选择进行相应的计…...

Linux Shell 编程入门

从程序员的角度来看&#xff0c; Shell本身是一种用C语言编写的程序&#xff0c;从用户的角度来看&#xff0c;Shell是用户与Linux操作系统沟通的桥梁。用户既可以输入命令执行&#xff0c;又可以利用 Shell脚本编程&#xff0c;完成更加复杂的操作。在Linux GUI日益完善的今天…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...