首页 > 其他分享 >代码随想录Day8

代码随想录Day8

时间:2024-08-07 11:54:02浏览次数:17  
标签:字符 Day8 示例 int 反转 代码 随想录 字符串 输入

344.反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 \(O(1)\) 的额外空间解决这一问题。

示例 1:

输入:s = ["h","e","l","l","o"]
输出:["o","l","l","e","h"]

示例 2:

输入:s = ["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

提示:

1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符


正解(双指针)

思路

上代码(●'◡'●)
class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
        }
    }
};

541. 反转字符串II

给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个,则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。

示例 1:

输入:s = "abcdefg", k = 2
输出:"bacdfeg"

示例 2:

输入:s = "abcd", k = 2
输出:"bacd"

提示:

1 <= s.length <= 104
s 仅由小写英文组成
1 <= k <= 104


正解(模拟+STL)

这道题目其实也是模拟,实现题目中规定的反转规则就可以了。
其实在遍历字符串的过程中,只要让 i += (2 * k),i 每次移动 2 * k 就可以了,然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点,这样写,程序会高效很多。
所以当需要固定规律一段一段去处理字符串的时候,要想想在在for循环的表达式上做做文章。

上代码(●'◡'●)
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个,则将剩余字符全部反转。
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

卡码网:54.替换数字

题目描述
给定一个字符串 s,它包含小写字母和数字字符,请编写一个函数,将字符串中的字母字符保持不变,而将每个数字字符替换为number。 例如,对于输入字符串 "a1b2c3",函数应该将其转换为 "anumberbnumbercnumber"。
输入描述
输入一个字符串 s,s 仅包含小写字母和数字字符。
输出描述
打印一个新的字符串,其中每个数字字符都被替换为了number
输入示例

a1b2c3

输出示例

anumberbnumbercnumber

提示信息
数据范围:
1 <= s.length < 104


正解(双指针)

首先扩充数组到每个数字字符替换成 "number" 之后的大小。
例如:字符串 "a5b" 的长度为3,那么将数字字符变成字符串 "number" 之后的字符串为 "anumberb" 长度为 8。
然后从后向前替换数字字符,也就是双指针法,过程如下:i指向新长度的末尾,j指向旧长度的末尾。
思路
其实很多数组填充类的问题,其做法都是先预先给数组扩容带填充后的大小,然后在从后向前进行操作。
这么做有两个好处:

  1. 不用申请新数组。
  2. 从后向前填充元素,避免了从前向后填充元素时,每次添加元素都要将添加元素之后的所有元素向后移动的问题。
上代码(●'◡'●)
#include <iostream>
using namespace std;
int main() {
    string s;
    while (cin >> s) {
        int sOldIndex = s.size() - 1;
        int count = 0; // 统计数字的个数
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                count++;
            }
        }
        // 扩充字符串s的大小,也就是将每个数字替换成"number"之后的大小
        s.resize(s.size() + count * 5);
        int sNewIndex = s.size() - 1;
        // 从后往前将数字替换为"number"
        while (sOldIndex >= 0) {
            if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {
                s[sNewIndex--] = 'r';
                s[sNewIndex--] = 'e';
                s[sNewIndex--] = 'b';
                s[sNewIndex--] = 'm';
                s[sNewIndex--] = 'u';
                s[sNewIndex--] = 'n';
            } else {
                s[sNewIndex--] = s[sOldIndex];
            }
            sOldIndex--;
        }
        cout << s << endl;       
    }
}

这种做法时间复杂度为\(O(n)\);
相比之下,从前向后填充的方法时间复杂度为\(O(n^2)\);
双指针大法好( ̄︶ ̄)↗ 

写博不易,请大佬点赞支持一下8~

标签:字符,Day8,示例,int,反转,代码,随想录,字符串,输入
From: https://www.cnblogs.com/Murder-sans/p/18346760/dmsxl_Day8

相关文章

  • 毕业设计:基于微信小程序的校篮球联赛系统【代码+论文+PPT】
    全文内容包括:1、采用技术;2、系统功能;3、系统截图;4、配套内容。索取方式见文末微信号,欢迎关注收藏!一、采用技术语言:Java1.8框架:SpringBoot数据库:MySQL5.7、8.0开发工具:IntelliJIDEA旗舰版、微信开发工具其他:Maven3.8以上二、系统功能球队管理:负责添加、编辑、删除和查询......
  • 不写代码,这样使用Python seaborn、matplotlib
    今天分享一个PyQt5GUI工具,动动鼠标拖拽就使用Python的Matplotlib、Seaborn进行绘图,并导出高清PDF。sviewgui安装pip install sviewguisviewgui使用使用很简单,因为,他只有一个方法啊:buildGUI();下面以tips.csv数据和boxplot为例介绍sviewgui的使用。以下三种方法均可......
  • Windows远程桌面(RDP)错误代码:0x516
    错误代码0x516和错误信息“你已断开连接,因为已与远程电脑建立了另一个连接”通常表示在尝试建立远程桌面连接时,目标计算机上已经有一个远程桌面会话活跃。检查隐藏的远程会话如果你有管理员权限,你可以通过命令行工具query和logoff来结束会话。即使看起来没有活......
  • 「代码随想录算法训练营」第三十一天 | 动态规划 part4
    1049.最后一块石头的重量II题目链接:https://leetcode.cn/problems/last-stone-weight-ii/题目难度:中等文章讲解:https://programmercarl.com/1049.最后一块石头的重量II.html视频讲解:https://www.bilibili.com/video/BV14M411C7oV/题目状态:看题解过思路:本题本质上就是将......
  • 代码随想录算法训练营第62天 | 最短路径:dijkstra(堆优化版)+ Bellman_ford算法
    47.参加科学大会https://kamacoder.com/problempage.php?pid=1047dijkstra(堆优化版)精讲https://www.programmercarl.com/kamacoder/0047.参会dijkstra堆.html#思路94.城市间货物运输Ihttps://kamacoder.com/problempage.php?pid=1152Bellman_ford算法精讲https://www.pr......
  • pytorch深度学习分类代码简单示例
    train.py代码如下importtorchimporttorch.nnasnnimporttorch.optimasoptimmodel_save_path="my_model.pth"#定义简单的线性神经网络模型classMyModel(nn.Module):def__init__(self):super(MyModel,self).__init__()self.output=n......
  • 代码随想录算法训练营第61天 | 图论part08:拓扑排序+迪杰斯特拉朴素法
    117.软件构建https://kamacoder.com/problempage.php?pid=1191拓扑排序精讲https://www.programmercarl.com/kamacoder/0117.软件构建.html#拓扑排序的背景47.参加科学大会https://kamacoder.com/problempage.php?pid=1047dijkstra(朴素版)精讲https://www.programmercarl.c......
  • 企业为什么需要对源代码进行加密,12款源代码加密软件推荐
    在信息技术快速发展的今天,源代码是企业最为核心的知识产权之一。对源代码进行加密是保护企业竞争优势和知识产权的关键措施。1.保护知识产权:源代码是软件和技术的核心组成部分,未经授权的访问和泄露可能导致知识产权的损失。2.防止逆向工程:加密可以有效防止黑客通过逆向工......
  • 图片增加文本水印(右下角)--Java代码实现
    一.效果展示水印前                                               水印后        二.代码实现 /***在给定的图片上添加文本水印。**@paramsourceImgPath源图片路径*......
  • 深入解析:23种软件设计模式详解及其分类(创建型、结构型、行为型)附代码示例DEMO
    目录引言一、创建型模式1.简单工厂模式(SimpleFactoryPattern)2.抽象工厂模式(AbstractFactoryPattern)3.单例模式(SingletonPattern)4.建造者模式(BuilderPattern)5.原型模式(PrototypePattern)二、结构型模式1.适配器模式(AdapterPattern)2.桥接模式(BridgePatt......