您现在的位置是:首页 > 正文

删除字符串中重复字符。

2024-02-01 01:35:46阅读 1

题目:删除字符串中重复字符。如果可以,优先删除重复字符中排在比他小字符前面的字符。 比如,输入:bbcacdww;输出:bacdw

分析:如果根本不允许开设数组,则只能就地进行字符串去重,那么可以依次访问字符串中的字符,并删除从该字符串开始到结尾的所有相同字符。时间复杂度为O(n^2 )。

void removeDuplicate(char s[])
{
    int i = 0;
    while (s[i] != '\0')
    {
        int j = i + 1;
        int k = i + 1;
        while (s[k] != '\0')
        {
            if (s[k] != s[i])
            {
                s[j] = s[k];
                ++j;
                ++k;
            }
            else
              ++k;
        }
        s[j] = '\0';
        ++i;
    }   
}

思路2:如果可以开设固定大小,与问题规模无关的固定数组,假如字符串中字符全为ASCII字符,则可以开设一个长度为256的数组来表征某一个字符是否以前出现过。此时,时间复杂度为O(n);

void removeDuplicate1(char s[])
{
    int len = strlen(s);
    bool a[256];
    memset(a, 0, sizeof(a));
    int j = 0;
    int i = 0;
    for (i = 0; i < len; ++i)
    {
        if (!a[s[i]])
        {
            a[s[i]] = true;
            s[j] = s[i];
            ++j;
        }

    }
    s[j] = '\0';
}

思路3:如果字符串中只包含a-z的26个字符,还可以用位示图法来解决,此时只需要一个int(4字节32位),就可以实现第二种思想,此时空间复杂度为O(1),时间复杂度为O(n);

void removeDuplicate2(char s[])
{
    unsigned int check = 0;
    int len = strlen(s);
    int j = 0;
    int v = 0;
    for (int i = 0; i < len; i++)
    {
        v = s[i] - 'a';
        if (!(check & (1 << v)))
        {
            s[j] = s[i];
            j++;
            check |= (1 << v);
        }
    }
    s[j] = '\0';
}

网站文章

  • VM下的Centos7安装ftp服务

    VM下的Centos7安装ftp服务

    Linux安装ftp组件1  安装vsftpd组件 [root@bogon~]# yum -y install vsftpd 2  配置vsftpd组件l  打开vsftpd配置文件/etc/vsftpd/vftpd.confl  配置文件的内容如下anonymous_enable=NO //设定不允许匿名访问local_enable=YES //设定本地用

    2024-02-01 01:35:39
  • matlab练习程序(广度优先搜索BFS、深度优先搜索DFS)

    matlab练习程序(广度优先搜索BFS、深度优先搜索DFS)

    如此经典的算法竟一直没有单独的实现过,真是遗憾啊。广度优先搜索在过去实现的二值图像连通区域标记和prim最小生成树算法时已经无意识的用到了,深度优先搜索倒是没用过。这次单独的将两个算法实现出来,因为算法本身和图像没什么关系,所以更纯粹些。广度优先搜索是从某一节点开始,搜索与其线连接的所有节点,按照广度方向像外扩展,直到不重复遍历所有节点。深度优先搜索是从某一节点开始,沿着其搜索到的...

    2024-02-01 01:34:59
  • win10 安装配置Git

    win10 安装配置Git

    3.继续,执行ssh-keygen-trsa,(注意ssh-keygen无空格),生成SSH(你的电脑与Gitee通信的安全连接)百度地址链接https//pan.baidu.com/s/1Y_P_e...

    2024-02-01 01:34:43
  • 机器学习概述

    简介什么是机器学习?机器学习就是从【数据】中自动分析,获得【规律(模型)】,并利用规律对未知数进行【预测】。样本数据(数据集)的载体- 通常情况下历史数据都不会存储在数据库中,而是存储在文件中(.cs...

    2024-02-01 01:34:37
  • Mysql 基于GTID的主从复制及切换

    参考http://imysql.com/tag/gtidhttp://mysqllover.com/?p=594Mysql 基于GTID的主从复制及切换一、主从复制配置两个mysql服务的my.cnf 中相关内容配置[mysqld]#从复制数据库表设置replicate-wild-ignore-table = mysql.%,information_schema.%,inno...

    2024-02-01 01:34:02
  • linux上传文件put,详解Linux ftp 命令行中下载文件get与上传文件put的操作方法

    尽管现在有许多好的FTP应用程序,但服务器命令行ftp命令的应用程序仍然很多,下面就让电脑乐园小编带你一起来学习详解Linux ftp 命令行中下载文件get与上传文件put的操作方法。介绍:从本地以...

    2024-02-01 01:33:55
  • 切面条问题

    切面条问题

    切面条问题 python

    2024-02-01 01:33:27
  • Java架构师面试题——JVM性能调优

    JVM内存调优 对JVM内存的系统级的调优主要的目的是减少GC的频率和Full GC的次数。 1.Full GC 会对整个堆进行整理,包括Young、Tenured和Perm。Full GC因为需要对...

    2024-02-01 01:33:20
  • python中reversed函数怎么用_Python3 reversed 函数

    Python3reversed 函数描述Python3 reversed 函数返回一个反转的迭代器。语法以下是 reversed 的语法:reversed(seq)参数seq -- 要转换的序列,可以...

    2024-02-01 01:33:12
  • OpenGL之Shader编程入门

    OpenGL之Shader编程入门

    shader编程基本概念。

    2024-02-01 01:33:06