代码随想录--字符串--替换空格题型
①这道题可以直接申请一个临时数组,然后遍历字符串,是空格则加入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;
}
};
相关文章:
代码随想录--字符串--替换空格题型
①这道题可以直接申请一个临时数组,然后遍历字符串,是空格则加入20%,最后再把临时数组转化为字符串。 怎么把一个数组转化为字符串? 如数组arry[], string newstr new string(arry,0,arry.size()-1); return newstr; 而且临时数…...
Spring JDBC和事务控制
目录 Spring JDBC 和 事务控制主要内容Spring 整合 JDBC 环境构建项目添加依赖坐标添加 jdbc 配置文件编写 spring 配置文件配置数据源C3P0 数据源配置DBCP 数据源配置 模板类配置Spring JDBC 测试 (入门)创建指定数据库创建数据表使用 JUnit 测试JUnit …...
【音视频第16天】详解STUN协议
一个webRTC传输协议搞得自己云里雾里的。现在主动攻克一下。先看看STUN协议。好,我们开始吧 目录 1.讲讲什么是NAT?2.NAT有啥问题?3.四种NAT类型4.STUN Server5.TURN ServerSTUN和TURN的实现:什么是STUN?为什么需要ST…...
C++算法初级11——01背包问题(动态规划2)
C算法初级11——01背包问题(动态规划2) 文章目录 C算法初级11——01背包问题(动态规划2)问题引入0-1背包问题分析0-1背包问题的形式化分析优化 问题引入 辰辰采药 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大…...
Python 库大全(下)
格式化输出 模块 reprlib 提供了一份定制的 repr(),用于简洁 地展示各种大的或者多层嵌套的容器变量: >>> 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缓存介绍 缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有…...
【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匿名类如何在运行时动态生成?
以下是一些使用匿名类的场景: 2. 简单的工厂模式:当需要在运行时动态创建一些简单的对象时,可以使用匿名类替代创建不必要的类定义和文件。 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语言】函数的数据传递原理 | 数组传入函数方法
创作不易,本篇文章如果帮助到了你,还请点赞支持一下♡>𖥦<)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ…...
vue3源码(3)——computed
Vue3中的computed底层源码主要是通过使用Proxy对象来实现的。下面是对Vue3中computed底层源码的详细解读: 在Vue3中,computed的实现是通过使用createComputed函数来创建的。createComputed函数接收两个参数:getter和setter。 在createComput…...
数学建模第七天:数学建模算法篇之插值及MATLAB实现
目录 一、前言 1、引例 2、拟合定义 3、拟合与插值的关系 二、拟合 1、线性最小二乘法求解 ①思路 ②解法 2、MATLAB对线性最小二乘拟合的实现 ①函数说明 ②求解例题 3、MATLAB实现非线性曲线拟合 ①lsqcurvefit函数 ②代码求解 4、MATLAB实现非线性最小二乘拟…...
RUST 每日一省:生命周期作用域
生命周期 一个变量的生命周期就是它从创建到销毁的整个过程。 作用域 我们声明的每个变量都有作用域。作用域其实是变量和值存在的环境。作用域是由一对花括号表示的。例如,使用块表达式会创建一个作用域,即任何以花括号开头和结尾的表达式。此…...
【过程8】——能量守恒视角总结感受
一、背景 另一个角度的看到,观望着过程中自己曾经类似的经历(小舅子的工作)。 时间久了,经历多了,感悟会更加的充实;最近自己对于人在维持能量的过程中也有很多的感悟,一并做一下总结 二、过程 1.人为什么天性不愿意…...
kong(4):限流配置
Kong 提供了 Rate Limiting 插件,实现对请求的限流功能,避免过大的请求量过大,将后端服务打挂。 Rate Limiting 支持秒/分/小时/日/月/年多种时间维度的限流,并且可以组合使用。例如说:限制每秒最 多 100 次请求&…...
人脸识别 Face Recognition 入门
人脸识别 Face Recognition 入门概述 总述传统特征方法深度学习方法损失函数改进基于欧几里德和距离的损失基于角度/余弦边距的损失SoftMax 损失及其变体 一级标题二级标题二级标题二级标题 找论文搭配 Sci-Hub 食用更佳 💪 Sci-Hub 实时更新 : https://tool.yovisu…...
【AI绘画】Midjourney的使用及程序示例
Midjourney 1.背景2.Midjourney的原理3.Midjourney的使用方法4.Midjourney的示例代码 1.背景 Midjourney 是一款基于深度学习的图像转换工具,其可以将一张图像转换成具有不同风格的图像,例如将一张照片转换成卡通风格的图像。Midjourney 基于 TensorFlow…...
无公网IP?教你在外远程访问本地wamp服务器「内网穿透」
目录 前言 1.Wamp服务器搭建 1.1 Wamp下载和安装 1.2 Wamp网页测试 2. Cpolar内网穿透的安装和注册 2.1 本地网页发布 2.2 Cpolar云端设置 2.3 Cpolar本地设置 3. 公网访问测试 4. 结语 前言 软件技术的发展日新月异,各种能方便我们生活、工作和娱乐的新…...
leetcode 628. 三个数的最大乘积
题目描述解题思路执行结果 leetcode 628. 三个数的最大乘积 题目描述 三个数的最大乘积 给你一个整型数组 nums ,在数组中找出由三个数组成的最大乘积,并输出这个乘积。 示例 1: 输入:nums [1,2,3] 输出:6 示例 2&…...
fork函数如何创建进程,exit/_exit函数如何使进程终止的详细分析与代码实现
🎊【进程通信与并发】专题正在持续更新中,进程,线程,IPC,线程池等的创建原理与运用✨,欢迎大家前往订阅本专题,获取更多详细信息哦🎏🎏🎏 🪔本系列…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
