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

代码随想录--字符串--替换空格题型


①这道题可以直接申请一个临时数组,然后遍历字符串,是空格则加入20%,最后再把临时数组转化为字符串。
怎么把一个数组转化为字符串?
如数组arry[],
string newstr = new string(arry,0,arry.size()-1);
return newstr;
而且临时数组的空间要申请大一些。
public String replaceSpace(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int index = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[index++] = '%';
                array[index++] = '2';
                array[index++] = '0';
            } else {
                array[index++] = c;
            }
        }
        String newStr = new String(array, 0, index);
        return newStr;
    }

②或者用栈,只是出栈后结果是需要来个翻转吗?有点不大会。


③不过上面的这些方法都需要时间复杂度O(n),并且空间复杂度O(n)。
接下来有个时间复杂度O(n),但是空间复杂度O(1)的做法,要是学会了也不难,接下来说说这种解法。
这个解法就不需要申请新的空间。
第一步,首先扩充数组到每个空格替换成"%20"之后的大小。
比如这道题,每个空格要变成20%,即一个空格变成了3个空格,所以每个空格处要添加2个空格,即先统计字符串中有多少个空格,然后+多少个空格*2。怎么添加字符串长度?
//s.resize(n); resize将string类中有效字符改变到n个。
第二步,从后向前替换空格,也就是双指针法,过程如下:
i指向新长度的末尾,j指向旧长度的末尾。
然后i,j往前,如果s[j]不是空格则把s[j]赋给s[i]; 如果s[j]是空格,则s[i]赋为0, s[i-1]赋为2, s[i-2]赋为%,并且i往前移三格。然后继续i,j一起往前移继续如此轮下去。


④有同学问了,为什么要从后向前填充,从前向后填充不行么?
从前向后填充就是O(n^2)的算法了,因为每次添加元素都要将添加元素之后的所有元素向后移动。

⑤其实很多数组填充类的问题,都可以先预先给数组扩容带填充后的大小,然后在从后向前进行操作。
这么做有两个好处:
不用申请新数组。
从后向前填充元素,避免了从前向后填充元素时,每次添加元素都要将添加元素之后的所有元素向后移动的问题。


当i=j时,即说明扩充的空格都用完了,说明前面已经没有空格要变成20%了,所以就可以结束了,所以循环结束条件就是j<i,而不是j<=i。
 

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; // 统计空格的个数
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 扩充字符串s的大小,也就是每个空格替换成"%20"之后的大小
        s.resize(s.size() + count * 2);
        int sNewSize = s.size();
        // 从后先前将空格替换为"%20"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};
 


 

相关文章:

代码随想录--字符串--替换空格题型

①这道题可以直接申请一个临时数组&#xff0c;然后遍历字符串&#xff0c;是空格则加入20%&#xff0c;最后再把临时数组转化为字符串。 怎么把一个数组转化为字符串? 如数组arry[]&#xff0c; string newstr new string(arry,0,arry.size()-1); return newstr; 而且临时数…...

Spring JDBC和事务控制

目录 Spring JDBC 和 事务控制主要内容Spring 整合 JDBC 环境构建项目添加依赖坐标添加 jdbc 配置文件编写 spring 配置文件配置数据源C3P0 数据源配置DBCP 数据源配置 模板类配置Spring JDBC 测试 &#xff08;入门&#xff09;创建指定数据库创建数据表使用 JUnit 测试JUnit …...

【音视频第16天】详解STUN协议

一个webRTC传输协议搞得自己云里雾里的。现在主动攻克一下。先看看STUN协议。好&#xff0c;我们开始吧 目录 1.讲讲什么是NAT&#xff1f;2.NAT有啥问题&#xff1f;3.四种NAT类型4.STUN Server5.TURN ServerSTUN和TURN的实现&#xff1a;什么是STUN&#xff1f;为什么需要ST…...

C++算法初级11——01背包问题(动态规划2)

C算法初级11——01背包问题&#xff08;动态规划2&#xff09; 文章目录 C算法初级11——01背包问题&#xff08;动态规划2&#xff09;问题引入0-1背包问题分析0-1背包问题的形式化分析优化 问题引入 辰辰采药 辰辰是个天资聪颖的孩子&#xff0c;他的梦想是成为世界上最伟大…...

Python 库大全(下)

格式化输出 模块 reprlib 提供了一份定制的 repr()&#xff0c;用于简洁 地展示各种大的或者多层嵌套的容器变量&#xff1a; >>> import reprlib >>> reprlib.repr(set(\supercalifragilisticexpialidocious\)) "{\a\, \c\, \d\, \e\, \f\, \g\, ...…...

如何用链表实现LRU缓存淘汰算法

链表学习 一、 缓存1.1缓存介绍1.2 缓存策略 二、链表结构2.1 单链表2.2 循环链表2.3 双向链表2.4 双向循环链表2.5 链表与数组性能对比 三、如何基于链表实现LRU缓存淘汰算法 一、 缓存 1.1缓存介绍 缓存是一种提高数据读取性能的技术&#xff0c;在硬件设计、软件开发中都有…...

【01】数据结构与算法基础-数据、数据元素、数据项和数据对象 | 数据类型和抽象数据类型 | 抽象数据类型的表示和C++实现

目录) 0.数据结构的研究内容1.数据、数据元素、数据项和数据对象1.1数据1.2数据元素(Data element)和数据项1.3数据项1.4数据对象1.5数据结构(Data Structure)1.6逻辑结构的种类1.7存储结构的种类2.数据类型和抽象数据类型2.1数据类型(Data Type)2.2抽象数据类型(Abstract …...

PHP匿名类的使用场景有哪些?PHP匿名类怎么用?有什么好处?PHP匿名类如何在运行时动态生成?

以下是一些使用匿名类的场景&#xff1a; 2. 简单的工厂模式&#xff1a;当需要在运行时动态创建一些简单的对象时&#xff0c;可以使用匿名类替代创建不必要的类定义和文件。 function createGreeter($name) {return new class($name) {private $name;public function __cons…...

【并发基础】一篇文章带你彻底搞懂Java线程中断的底层原理——interrupt()、interrupted()、isInterrupted()

目录 〇、Java线程中断与阻塞的区别 0.1 线程中断 0.2 线程阻塞 一、线程的中断 二、中断方法 2.1 void interrupt() 2.1.1 可中断的阻塞 2.1.2 不可中断的阻塞 2.1.3 实践案例 2.2 boolean isInterrupted() 2.3 boolean interrupted() 2.4 代码案例 三、源码分析…...

【c语言】函数的数据传递原理 | 数组传入函数方法

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; 给大家跳段街舞感谢支持&#xff01;ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ…...

vue3源码(3)——computed

Vue3中的computed底层源码主要是通过使用Proxy对象来实现的。下面是对Vue3中computed底层源码的详细解读&#xff1a; 在Vue3中&#xff0c;computed的实现是通过使用createComputed函数来创建的。createComputed函数接收两个参数&#xff1a;getter和setter。 在createComput…...

数学建模第七天:数学建模算法篇之插值及MATLAB实现

目录 一、前言 1、引例 2、拟合定义 3、拟合与插值的关系 二、拟合 1、线性最小二乘法求解 ①思路 ②解法 2、MATLAB对线性最小二乘拟合的实现 ①函数说明 ②求解例题 3、MATLAB实现非线性曲线拟合 ①lsqcurvefit函数 ②代码求解 4、MATLAB实现非线性最小二乘拟…...

RUST 每日一省:生命周期作用域

生命周期 一个变量的生命周期就是它从创建到销毁的整个过程。 作用域 我们声明的每个变量都有作用域。作用域其实是变量和值存在的环境。作用域是由一对花括号表示的。例如&#xff0c;使用块表达式会创建一个作用域&#xff0c;即任何以花括号开头和结尾的表达式。此…...

【过程8】——能量守恒视角总结感受

一、背景 另一个角度的看到&#xff0c;观望着过程中自己曾经类似的经历(小舅子的工作)。 时间久了&#xff0c;经历多了&#xff0c;感悟会更加的充实&#xff1b;最近自己对于人在维持能量的过程中也有很多的感悟&#xff0c;一并做一下总结 二、过程 1.人为什么天性不愿意…...

kong(4):限流配置

Kong 提供了 Rate Limiting 插件&#xff0c;实现对请求的限流功能&#xff0c;避免过大的请求量过大&#xff0c;将后端服务打挂。 Rate Limiting 支持秒/分/小时/日/月/年多种时间维度的限流&#xff0c;并且可以组合使用。例如说&#xff1a;限制每秒最 多 100 次请求&…...

人脸识别 Face Recognition 入门

人脸识别 Face Recognition 入门概述 总述传统特征方法深度学习方法损失函数改进基于欧几里德和距离的损失基于角度/余弦边距的损失SoftMax 损失及其变体 一级标题二级标题二级标题二级标题 找论文搭配 Sci-Hub 食用更佳 &#x1f4aa; Sci-Hub 实时更新 : https://tool.yovisu…...

【AI绘画】Midjourney的使用及程序示例

Midjourney 1.背景2.Midjourney的原理3.Midjourney的使用方法4.Midjourney的示例代码 1.背景 Midjourney 是一款基于深度学习的图像转换工具&#xff0c;其可以将一张图像转换成具有不同风格的图像&#xff0c;例如将一张照片转换成卡通风格的图像。Midjourney 基于 TensorFlow…...

无公网IP?教你在外远程访问本地wamp服务器「内网穿透」

目录 前言 1.Wamp服务器搭建 1.1 Wamp下载和安装 1.2 Wamp网页测试 2. Cpolar内网穿透的安装和注册 2.1 本地网页发布 2.2 Cpolar云端设置 2.3 Cpolar本地设置 3. 公网访问测试 4. 结语 前言 软件技术的发展日新月异&#xff0c;各种能方便我们生活、工作和娱乐的新…...

leetcode 628. 三个数的最大乘积

题目描述解题思路执行结果 leetcode 628. 三个数的最大乘积 题目描述 三个数的最大乘积 给你一个整型数组 nums &#xff0c;在数组中找出由三个数组成的最大乘积&#xff0c;并输出这个乘积。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&#xff1a;6 示例 2&…...

fork函数如何创建进程,exit/_exit函数如何使进程终止的详细分析与代码实现

&#x1f38a;【进程通信与并发】专题正在持续更新中&#xff0c;进程&#xff0c;线程&#xff0c;IPC&#xff0c;线程池等的创建原理与运用✨&#xff0c;欢迎大家前往订阅本专题&#xff0c;获取更多详细信息哦&#x1f38f;&#x1f38f;&#x1f38f; &#x1fa94;本系列…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...