算法刷题-字符串-替换空格

题目：剑指Offer 05.替换空格

力扣题目链接

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：
输入：s = “We are happy.”
输出：“We%20are%20happy.”

思路

如果想把这道题目做到极致，就不要只用额外的辅助空间了！

首先扩充数组到每个空格替换成"%20"之后的大小。

然后从后向前替换空格，也就是双指针法，过程如下：

i指向新长度的末尾，j指向旧长度的末尾。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UOQ3D3Dc-1687011835976)(https://code-thinking.cdn.bcebos.com/gifs/%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.gif)]

有同学问了，为什么要从后向前填充，从前向后填充不行么？

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

  1. 不用申请新数组。
  2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

时间复杂度，空间复杂度均超过100%的用户。

C++代码如下：

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;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

此时算上本题，我们已经做了七道双指针相关的题目了分别是：

  • 27.移除元素
  • 15.三数之和
  • 18.四数之和
  • 206.翻转链表
  • 142.环形链表II
  • 344.反转字符串

拓展

这里也给大家拓展一下字符串和数组有什么差别，

字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定，接下来我来说一说C/C++中的字符串。

在C语言中，把一个字符串存入一个数组时，也把结束符 '\0’存入数组，并以此作为该字符串是否结束的标志。

例如这段代码：

char a[5] = "asd";
for (int i = 0; a[i] != '\0'; i++) {
}

在C++中，提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用’\0’来判断是否结束。

例如这段代码:

string a = "asd";
for (int i = 0; i < a.size(); i++) {
}

那么vector< char > 和 string 又有什么区别呢？

其实在基本操作上没有区别，但是 string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有。

所以想处理字符串，我们还是会定义一个string类型。

其他语言版本

C：

char* replaceSpace(char* s){
    //统计空格数量
    int count = 0;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        if (s[i] == ' ') {
            count++;
        }
    }

    //为新数组分配空间
    int newLen = len + count * 2;
    char* result = malloc(sizeof(char) * newLen + 1);
    //填充新数组并替换空格
    for (int i = len - 1, j = newLen - 1; i >= 0; i--, j--) {
        if (s[i] != ' ') {
            result[j] = s[i];
        } else {
            result[j--] = '0';
            result[j--] = '2';
            result[j] = '%';
        }
    }
    result[newLen] = '\0';

    return result;
}

Java：

//使用一个新的对象，复制 str，复制的过程对其判断，是空格则替换，否则直接复制，类似于数组复制
public static String replaceSpace(String s) {
        if (s == null) {
            return null;
        }
        //选用 StringBuilder 单线程使用，比较快，选不选都行
        StringBuilder sb = new StringBuilder();
        //使用 sb 逐个复制 s ，碰到空格则替换，否则直接复制
        for (int i = 0; i < s.length(); i++) {
            //s.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
            //if (" ".equals(String.valueOf(s.charAt(i)))){}
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

//方式二：双指针法
public String replaceSpace(String s) {
    if(s == null || s.length() == 0){
        return s;
    }
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
    s += str.toString();
    int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
    char[] chars = s.toCharArray();
    while(left>=0){
        if(chars[left] == ' '){
            chars[right--] = '0';
            chars[right--] = '2';
            chars[right] = '%';
        }else{
            chars[right] = chars[left];
        }
        left--;
        right--;
    }
    return new String(chars);
}

Go：

// 遍历添加
func replaceSpace(s string) string {
    b := []byte(s)
    result := make([]byte, 0)
    for i := 0; i < len(b); i++ {
        if b[i] == ' ' {
            result = append(result, []byte("%20")...)
        } else {
            result = append(result, b[i])
        }
    }
    return string(result)
}

// 原地修改
func replaceSpace(s string) string {
    b := []byte(s)
    length := len(b)
    spaceCount := 0
    // 计算空格数量
    for _, v := range b {
        if v == ' ' {
            spaceCount++
        }
    }
    // 扩展原有切片
    resizeCount := spaceCount * 2
    tmp := make([]byte, resizeCount)
    b = append(b, tmp...)
    i := length - 1
    j := len(b) - 1
    for i >= 0 {
        if b[i] != ' ' {
            b[j] = b[i]
            i--
            j--
        } else {
            b[j] = '0'
            b[j-1] = '2'
            b[j-2] = '%'
            i--
            j = j - 3
        }
    }
    return string(b)
}

python：

class Solution:
    def replaceSpace(self, s: str) -> str:
        counter = s.count(' ')
        
        res = list(s)
        # 每碰到一个空格就多拓展两个格子，1 + 2 = 3个位置存’%20‘
        res.extend([' '] * counter * 2)
        
        # 原始字符串的末尾，拓展后的末尾
        left, right = len(s) - 1, len(res) - 1
        
        while left >= 0:
            if res[left] != ' ':
                res[right] = res[left]
                right -= 1
            else:
                # [right - 2, right), 左闭右开
                res[right - 2: right + 1] = '%20'
                right -= 3
            left -= 1
        return ''.join(res)
            

class Solution:
    def replaceSpace(self, s: str) -> str:
        # method 1 - Very rude
        return "%20".join(s.split(" "))

        # method 2 - Reverse the s when counting in for loop, then update from the end.
        n = len(s)
        for e, i in enumerate(s[::-1]):
            print(i, e)
            if i == " ":
                s = s[: n - (e + 1)] + "%20" + s[n - e:]
            print("")
        return s

javaScript:

/**
 * @param {string} s
 * @return {string}
 */
 var replaceSpace = function(s) {
   // 字符串转为数组
  const strArr = Array.from(s);
  let count = 0;

  // 计算空格数量
  for(let i = 0; i < strArr.length; i++) {
    if (strArr[i] === ' ') {
      count++;
    }
  }

  let left = strArr.length - 1;
  let right = strArr.length + count * 2 - 1;

  while(left >= 0) {
    if (strArr[left] === ' ') {
      strArr[right--] = '0';
      strArr[right--] = '2';
      strArr[right--] = '%';
      left--;
    } else {
      strArr[right--] = strArr[left--];
    }
  }

  // 数组转字符串
  return strArr.join('');
};

TypeScript：

function replaceSpace(s: string): string {
    let arr: string[] = s.split('');
    let spaceNum: number = 0;
    let oldLength: number = arr.length;
    for (let i = 0; i < oldLength; i++) {
        if (arr[i] === ' ') {
            spaceNum++;
        }
    }
    arr.length = oldLength + 2 * spaceNum;
    let cur: number = oldLength - 1;
    for (let i = arr.length - 1; i >= 0; i--, cur--) {
        if (arr[cur] !== ' ') {
            arr[i] = arr[cur]
        } else {
            arr[i] = '0';
            arr[--i] = '2';
            arr[--i] = '%';
        }
    }
    return arr.join('');
};

Swift:

func replaceSpace(_ s: String) -> String {
    var strArr = Array(s)
    var count = 0

    // 统计空格的个数
    for i in strArr {
        if i == " " {
            count += 1
        }
    }
    // left 指向旧数组的最后一个元素
    var left = strArr.count - 1
    // right 指向扩容后数组的最后一个元素（这里还没对数组进行实际上的扩容）
    var right = strArr.count + count * 2 - 1

    // 实际对数组扩容
    for _ in 0..<(count * 2) {
        strArr.append(" ")
    }

    while left < right {
        if strArr[left] == " " {
            strArr[right] = "0"
            strArr[right - 1] = "2"
            strArr[right - 2] = "%"
            left -= 1
            right -= 3
        } else {
            strArr[right] = strArr[left]
            left -= 1
            right -= 1
        }
    }

    return String(strArr)
}

Scala:

方式一: 双指针

object Solution {
  def replaceSpace(s: String): String = {
    var count = 0
    s.foreach(c => if (c == ' ') count += 1) // 统计空格的数量
    val sOldSize = s.length // 旧数组字符串长度
    val sNewSize = s.length + count * 2 // 新数组字符串长度
    val res = new Array[Char](sNewSize) // 新数组
    var index = sNewSize - 1 // 新数组索引
    // 逆序遍历
    for (i <- (0 until sOldSize).reverse) {
      if (s(i) == ' ') {
        res(index) = '0'
        index -= 1
        res(index) = '2'
        index -= 1
        res(index) = '%'
      } else {
        res(index) = s(i)
      }
      index -= 1
    }
    res.mkString
  }
}

方式二: 使用一个集合，遇到空格就添加%20

object Solution {
  import scala.collection.mutable.ListBuffer
  def replaceSpace(s: String): String = {
    val res: ListBuffer[Char] = ListBuffer[Char]()
    for (i <- s.indices) {
      if (s(i) == ' ') {
        res += '%'
        res += '2'
        res += '0'
      }else{
        res += s(i)
      }
    }
    res.mkString
  }
}

方式三: 使用map

object Solution {
  def replaceSpace(s: String): String = {
    s.map(c => if(c == ' ') "%20" else c).mkString
  }
  }

PHP：

function replaceSpace($s){
    $sLen = strlen($s);
    $moreLen = $this->spaceLen($s) * 2;

    $head = $sLen - 1;
    $tail = $sLen + $moreLen - 1;

    $s = $s . str_repeat(' ', $moreLen);
    while ($head != $tail) {
        if ($s[$head] == ' ') {
            $s[$tail--] = '0';
            $s[$tail--] = '2';
            $s[$tail] = '%';
        } else {
            $s[$tail] = $s[$head];
        }
        $head--;
        $tail--;
    }
    return $s;
}
// 统计空格个数
function spaceLen($s){
    $count = 0;
    for ($i = 0; $i < strlen($s); $i++) {
        if ($s[$i] == ' ') {
            $count++;
        }
    }
    return $count;
}

Rust

impl Solution {
    pub fn replace_space(s: String) -> String {
        let mut len: usize = s.len();
        let mut s = s.chars().collect::<Vec<char>>();
        let mut count = 0;
        for i in &s {
            if i.is_ascii_whitespace() {
                count += 1;
            }
        }
        let mut new_len = len + count * 2;
        s.resize(new_len, ' ');
        while len < new_len {
            len -= 1;
            new_len -= 1;
            if s[len].is_ascii_whitespace() {
                s[new_len] = '0';
                s[new_len - 1] = '2';
                s[new_len - 2] = '%';
                new_len -= 2;
            }
            else { s[new_len] = s[len] }
        }
        s.iter().collect::<String>()
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/29648.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

webpack提升开发体验SourceMap

webpack提升开发体验SourceMap

一、开发场景介绍 开发中我们不可避免的会写一些bug出来&#xff0c;这时候要调试&#xff0c;快速定位到bug到底出现在哪尤为关键。 例如我故意在sum函数中写一个错误代码如下&#xff1a; 这时我们用前面章节已经写好的开发模式的webpack.dev.js运行&#xff0c;控制台会出…
阅读更多...
【总结笔记】Spring

【总结笔记】Spring

1 Spring容器加载配置文件进行初始化。 Spring容器加载配置文件进行初始化主要有两种形式&#xff1a; 加载配置文件进行初始化&#xff1a; ClassPathXmlApplicationContext ctx new ClassPathXmlApplicationContext(“ApplicationContext.xml”); 加载配置类进行初始化&…
阅读更多...
业务流程自动化：ThinkAutomation Professional Crack

业务流程自动化：ThinkAutomation Professional Crack

ThinkAutomation 助力您的业务流程自动化。自动执行本地和基于云的业务流程&#xff0c;以降低成本并节省时间。 自动化传入的通信渠道&#xff0c;监控数据库&#xff0c;对传入的Webhook&#xff0c;Web表单和聊天机器人做出反应。处理文档、附件、本地文件和其他邮件源。 …
阅读更多...
基于Spark的气象数据分析

基于Spark的气象数据分析

研究背景与方案 1.1.研究背景 在大数据时代背景下&#xff0c;各行业数据的规模大幅度增加&#xff0c;数据类别日益复杂&#xff0c;给数据分析工作带来极大挑战。气象行业和人们的生活息息相关&#xff0c;随着信息时代的发展&#xff0c;大数据技术的出现为气象数据的发展…
阅读更多...
模板匹配笔记

模板匹配笔记

模板匹配是一种最基本、最原始的模式识别的方法。通过对比某一特定物体的图案位于图像的什么地方&#xff0c;进而识别出物体。它是图像处理中最基本、最常用的匹配方法。它的局限性主要是它只能进行平行移动&#xff0c;若原图像中的匹配目标发生旋转或大小变化&#xff0c;该…
阅读更多...
前端vue入门(纯代码)09

前端vue入门(纯代码)09

【09.vue中组件的自定义事件】 自定义组件链接 在vue中用的click【点击】、keyup【按键】……等事件&#xff0c;这些属于内置事件&#xff0c;也就是js自带的事件。 问题一&#xff1a;什么是组件自定义事件呢&#xff1f; 【内置事件】:是给html元素用的&#xff0c;比如s…
阅读更多...
014、数据库管理之配置管理

014、数据库管理之配置管理

配置管理 TiDB配置系统配置集群配置配置的存储位置区分TiDB的系统参数和集群参数 系统参数系统参数的作用域系统参数的修改 集群参数集群参数的修改配置参数的查看 实验一&#xff1a; 在不同作用域下对数据库的系统参数进行修改session级别global级别 实验二&#xff1a; 修改…
阅读更多...
【TCP/IP】多进程服务器的实现(进阶) - 信号处理及signal、sigaction函数

【TCP/IP】多进程服务器的实现(进阶) - 信号处理及signal、sigaction函数

目录 信号 signal函数 sigaction函数 用信号来处理僵尸进程 在之前我们学习了如何处理“僵尸进程”&#xff0c;不过可能也会有疑问&#xff1a;调用wait和waitpid函数时我们关注的始终是在子进程上&#xff0c;那么在父进程上如何实现对子进程的管控呢&#xff1f;为此&am…
阅读更多...
零基础速成simulink代码生成——简单滤波器实现2

零基础速成simulink代码生成——简单滤波器实现2

simulink setting 找到model settings solver求解器配置 Code Generation 代码生成配置 生成代码报告 添加stateflow注释 可以将变量保存在定义的文件（选） 实践 简单一阶滤波器
阅读更多...
使用一键安装工具快速搭建 ESP-IDF 开发环境 (Windows)

使用一键安装工具快速搭建 ESP-IDF 开发环境 (Windows)

我们收到用户对 ESP-IDF SDK 软件开发环境感到搭建难、门槛高的反馈。为解决用户在此方面的问题。为此&#xff0c;我们推出本期教程介绍在 Windows 操作系统下使用一键安装工具快速搭建 ESP-IDF 开发环境。 您可以观看下面的教程视频&#xff0c;也可以阅读接下来本篇的图文教…
阅读更多...
CVPR 2023 | 图像超分，结合扩散模型/GAN/部署优化，low-level任务，视觉AIGC系列

CVPR 2023 | 图像超分，结合扩散模型/GAN/部署优化，low-level任务，视觉AIGC系列

1、Activating More Pixels in Image Super-Resolution Transformer 基于Transformer的方法在低级别视觉任务中&#xff0c;如图像超分辨率&#xff0c;表现出了令人印象深刻的性能。Transformer的潜力在现有网络中仍未得到充分发挥。为了激活更多的输入像素以实现更好的重建&a…
阅读更多...
有哪些工具软件一旦用了就离不开？

有哪些工具软件一旦用了就离不开？

&#x1f496;前言 目前&#xff0c;随着科技的快速发展&#xff0c;电脑已经进入了许许多多人的生活 &#xff0c;在平日的学习、工作和生活里&#xff0c;我们会用的各种各样的强大软件。市面上除了某些大公司开发在强大软件&#xff0c;还有各路大神开发具有某些功能的强大…
阅读更多...
Java阶段四Day01

Java阶段四Day01

Java阶段四Day01 文章目录 Java阶段四Day01Security框架通配符Vue脚手架 Vue-cli关于VUE关于VUE Cli创建Vue Cli工程解决端口被占用 Vue工程的工程结构[.idea]【重要】[node_modules]【重要】[public]favicon.icoindex.html [src][assets][compnents]【重要】[router][store]【…
阅读更多...
Spring基础知识（二）

Spring基础知识（二）

目录 1.Spring Bean是什么 2.Spring提供的配置方式 3.Spring bean中的scope 4.Spring bean容器的生命周期 5.Spring的内部bean 6.Spring装配是什么 7.自动装配模式 8.自动装配的局限性 9.基于注解配置容器 10.如何启动注解装配 1.Spring Bean是什么 Spring官方文档对…
阅读更多...
客户端负载均衡工具Ribbon

客户端负载均衡工具Ribbon

一 什么是Ribbon Ribbon介绍 目前主流的负载方案分为以下两种&#xff1a; 集中式负载均衡&#xff0c;在消费者和服务提供方中间使用独立的代理方式进行负载&#xff0c;有硬件的&#xff08;比如 F5&#xff09;&#xff0c;也有软件的&#xff08;比如 Nginx&#xff09;…
阅读更多...
10大白帽黑客专用的 Linux 操作系统

10大白帽黑客专用的 Linux 操作系统

平时在影视里见到的黑客都是一顿操作猛如虎&#xff0c;到底他们用的都是啥系统呢&#xff1f; 今天给大家分享十个白帽黑客专用的Linux操作系统。 ▍1. Kali Linux Kali Linux是最著名的Linux发行版&#xff0c;用于道德黑客和渗透测试。Kali Linux由Offensive Security开发&…
阅读更多...
哨兵架构redisCluster-Redis（五）

哨兵架构redisCluster-Redis（五）

上篇文章介绍了主从架构以及lua脚本。 主从架构&lua脚本-Redis&#xff08;四&#xff09;https://blog.csdn.net/ke1ying/article/details/131159229 Sentinel集群 主从的搭建我们已经完成&#xff0c;但如果主节点宕机&#xff0c;这时候导致整个redis服务不可用怎么办…
阅读更多...
打造智能生活方式

打造智能生活方式

2个互联网工具与你分享 分享一&#xff1a; 随记单词是一款功能强大的单词记忆和管理应用程序。它为用户提供了便捷的学习工具和智能化的记忆方式&#xff0c;帮助用户轻松有效地记忆和掌握单词。 随记单词的特点之一是个性化记忆计划。用户可以根据自己的学习进度和需求&am…
阅读更多...
【LeetCode热题100】打卡第21天：最小路径和爬楼梯

【LeetCode热题100】打卡第21天：最小路径和爬楼梯

文章目录 【LeetCode热题100】打卡第21天&#xff1a;最小路径和&爬楼梯⛅前言 最小路径和&#x1f512;题目 爬楼梯&#x1f512;题目&#x1f511;题解 【LeetCode热题100】打卡第21天&#xff1a;最小路径和&爬楼梯 ⛅前言 大家好&#xff0c;我是知识汲取者&#…
阅读更多...
牛客网基础语法41~50题

牛客网基础语法41~50题

牛客网基础语法41~50题&#x1f618;&#x1f618;&#x1f618; &#x1f4ab;前言&#xff1a;今天是咱们第五期刷牛客网上的题目。 &#x1f4ab;目标&#xff1a;熟练用数学知识来解决编程问题&#xff0c;会利用每种循环。 &#x1f4ab;鸡汤&#xff1a;压抑了&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023