【剑指offer】删除字符也出现在一个字符串

【剑指offer】删除字符也出现在一个字符串

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

转载请注明出处:http://blog.csdn.net/ns_code/article/details/27110873


    剑指offer上的字符串相关题目。 

    题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。比如。输入”They are students.””aeiou”,则删除之后的第一个字符串变成”Thy r stdnts.”

    这里主要要分析两个方面:

    1、怎样推断那些字符是须要删除的字符。

同非常多字符串问题一样。能够开辟一个哈希数组。所有初始化为false,将第二个字符串中字符相应的映射位置置为ture,表示这些位置相应的字符在第一个字符串中须要删除。

    2、关于删除字符的操作,每次删除一个。而后把后面的元素均左移一位,因为要删除的字符可能有多个,这样的方法的时间复杂度为O(n*n)。我们这里有O(n)的删除方法。我们能够设想,当一个字符须要被删除的时候,我们把它所占的位置让它后面的字符来填补,也就相当于这个字符被删除了。在详细实现中,我们能够定义两个指针(pFastpSlow),初始的时候都指向第一字符的起始位置。当pFast指向的字符是须要删除的字符,则pFast直接跳过。指向下一个字符。假设pFast指向的字符是不须要删除的字符,那么把pFast指向的字符赋值给pSlow指向的字符,而且pFastpStart同一时候向后移动指向下一个字符。这样。前面被pFast跳过的字符相当于被删除了。用这样的方法,整个删除在O(n)时间内就能够完毕。

    前面也有篇删除反复字符的博文用到了该删除方法。见这里:http://blog.csdn.net/ns_code/article/details/21328151

    另外,有一点须要注意。char的范围在-128-127,unsigned char的范围才是在0-255。因此ASCII值在128-255之间的字符,假设保存为了char型。其转化为int值的范围是在-128–1之间,这点在以下的代码中有体现。

    依据以上思路写出的代码例如以下:

#include<stdio.h>
#include<string.h>
#define MAX 256

void DeleteChars(char *str1,char *str2)
{
	if(str1==NULL || str2==NULL)
		return;

	bool hashtable[MAX];
	memset(hashtable,0,sizeof(hashtable));

	//将str2中字符相应的hashtable数组中的位置上的值设为ture
	while(*str2 != '
#include<stdio.h>
#include<string.h>
#define MAX 256
void DeleteChars(char *str1,char *str2)
{
if(str1==NULL || str2==NULL)
return;
bool hashtable[MAX];
memset(hashtable,0,sizeof(hashtable));
//将str2中字符相应的hashtable数组中的位置上的值设为ture
while(*str2 != '\0')
{
//ASCII值在128-255之间的的字符。
//用char保存,转化为int型,在-128--1之间
int index;
if(*str2 >= 0)
index = *str2;
else
index = *str2 + 256;
hashtable[index] = true;
++str2;
}
char *pFast = str1;
char *pSlow = str1;
while(*pFast != '\0')
{
int index;
if(*pFast >= 0)
index = *pFast;
else
index = *pFast + 256;
//不管是否碰到要删除的字符,pFast都后移,
//仅仅有没碰到要删除的字符时,pSlow才后移
if(!hashtable[index])
*pSlow++ = *pFast;	
++pFast;
}
*pSlow = '\0';
}
int main()
{
char str1[] = "They are students";
char str2[] = "Tt";
DeleteChars(str1,str2);
puts(str1);
return 0;
}
') { //ASCII值在128-255之间的的字符。 //用char保存,转化为int型,在-128--1之间 int index; if(*str2 >= 0) index = *str2; else index = *str2 + 256; hashtable[index] = true; ++str2; } char *pFast = str1; char *pSlow = str1; while(*pFast != '
#include<stdio.h>
#include<string.h>
#define MAX 256
void DeleteChars(char *str1,char *str2)
{
if(str1==NULL || str2==NULL)
return;
bool hashtable[MAX];
memset(hashtable,0,sizeof(hashtable));
//将str2中字符相应的hashtable数组中的位置上的值设为ture
while(*str2 != '\0')
{
//ASCII值在128-255之间的的字符。
//用char保存,转化为int型,在-128--1之间
int index;
if(*str2 >= 0)
index = *str2;
else
index = *str2 + 256;
hashtable[index] = true;
++str2;
}
char *pFast = str1;
char *pSlow = str1;
while(*pFast != '\0')
{
int index;
if(*pFast >= 0)
index = *pFast;
else
index = *pFast + 256;
//不管是否碰到要删除的字符,pFast都后移,
//仅仅有没碰到要删除的字符时,pSlow才后移
if(!hashtable[index])
*pSlow++ = *pFast;	
++pFast;
}
*pSlow = '\0';
}
int main()
{
char str1[] = "They are students";
char str2[] = "Tt";
DeleteChars(str1,str2);
puts(str1);
return 0;
}
') { int index; if(*pFast >= 0) index = *pFast; else index = *pFast + 256; //不管是否碰到要删除的字符,pFast都后移, //仅仅有没碰到要删除的字符时,pSlow才后移 if(!hashtable[index]) *pSlow++ = *pFast; ++pFast; } *pSlow = '
#include<stdio.h>
#include<string.h>
#define MAX 256
void DeleteChars(char *str1,char *str2)
{
if(str1==NULL || str2==NULL)
return;
bool hashtable[MAX];
memset(hashtable,0,sizeof(hashtable));
//将str2中字符相应的hashtable数组中的位置上的值设为ture
while(*str2 != '\0')
{
//ASCII值在128-255之间的的字符。
//用char保存,转化为int型,在-128--1之间
int index;
if(*str2 >= 0)
index = *str2;
else
index = *str2 + 256;
hashtable[index] = true;
++str2;
}
char *pFast = str1;
char *pSlow = str1;
while(*pFast != '\0')
{
int index;
if(*pFast >= 0)
index = *pFast;
else
index = *pFast + 256;
//不管是否碰到要删除的字符,pFast都后移,
//仅仅有没碰到要删除的字符时,pSlow才后移
if(!hashtable[index])
*pSlow++ = *pFast;	
++pFast;
}
*pSlow = '\0';
}
int main()
{
char str1[] = "They are students";
char str2[] = "Tt";
DeleteChars(str1,str2);
puts(str1);
return 0;
}
'; } int main() { char str1[] = "They are students"; char str2[] = "Tt"; DeleteChars(str1,str2); puts(str1); return 0; }

    測试结果:

【剑指offer】删除字符也出现在一个字符串

版权声明:本文博客原创文章。博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117608.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 不同维度矩阵相乘[通俗易懂]

    不同维度矩阵相乘[通俗易懂]在深度学习中经常会遇到不同维度的矩阵相乘的情况,本文会通过一些例子来展示不同维度矩阵乘法的过程。总体原则:在高维矩阵中取与低维矩阵相同维度的分片来与低维矩阵相乘,结果再按分片时的顺序还原为高维矩阵。相乘结果的维度与原来的高维矩阵一致。二维乘一维三维乘一维三维乘二维…

    2022年10月31日
  • django使用celery_django serializers

    django使用celery_django serializers前言环境celery==5.0.2在安装完celery后,运行celery会报以下错误ModuleNotFoundError:Nomodulenamed'click._bashc

  • 修改apache服务器端口号_apache修改端口号

    修改apache服务器端口号_apache修改端口号一、修改/etc/httpd/conf/httpd.conf文件中的监听端口号Listen80把80修改成需要的号,如8000,即Listen8000二、查看SELinux下http相关端口#semanageport-l|grephttphttp_cache_port_ttcp3128,8080,8118,10001-10010http_cache_po

  • Ubuntu 14.04 Desktop的Raid1安装总结

    Ubuntu 14.04 Desktop的Raid1安装总结安装基于Ubuntu14.04Desktop的Raid1。由于采用UEFI/GPT方式作为系统启动方式,在安装过程中出现了很多异常情况。本文记录安装的过程。

  • android studio 导出的jar中没有主清单属性「建议收藏」

    android studio 导出的jar中没有主清单属性「建议收藏」问题:androidstudio工程的module生成的jar包,在执行中出现“没有主清单属性”错误。解决办法:原因:MANIFEST.MF中的没有Main-Class在对应的module中的gradle文件中加入:jar{manifest{attributes’Main-Class’:’com.MainClass’}}

  • jmespath(1)基础语法

    jmespath(1)基础语法前言JMESPath是JSON的查询语言。您可以从JSON文档中提取和转换元素官方文档:https://jmespath.org/tutorial.html基本表达式JMESPath用的最多的

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号