首页 > 代码库 > 待字闺中之删除字符分析
待字闺中之删除字符分析
删除字符串中的“b”和“ac”,需要满足如下的条件:
1. 字符串只能遍历一次
2. 不能够使用额外的空间
例如:
1. acbac ==> ""
2. aaac ==> aa
3. ababac ==> aa
4. bbbbd ==> d
进一步思考:如何处理aaccac呢,需要做哪些改变呢?
分析
首先要明白从字符串中删除某些字符该如何实现,显而易见我们可以把保留的字符拷贝新的字符串中来实现删除。但是题目要求不能使用额外的空间。那就是将要删除的字符全部交换到字符串的尾部,然后设置一个‘\0‘表示字符串的结尾。
其次,如果要删除的都是单个字符的字符串,就很直接:我们使用i和j两个变量遍历字符串,i表示不会删除的字符的位置,j从0开始,只要i所在位置 的字符不是要删除的字符,就str[j]=str[i](str表示字符串),然后j++指向下一个位置。一次遍历即可,不需要额外申请空间,只需要两个 变量。
但是,现在删除的字符串中有多个字符的,如:“ac”。那要如何处理呢?这里介绍一个小技巧:状态机。这里,我们有两个状态:ONE和TWO。TWO表示,前一个字符时‘a’的状态,其他的都用ONE表示。还是采用前面所描述的遍历方法:
1. 如果当前状态为ONE,则拷贝:str[j]=str[i];但如果当前字符满足以下两种状态的任一个,则不进行拷贝:
1. 当前字符是‘b’,因为我们要删除b
2. 当前字符是‘a’,我们要考虑下一个字符是c
2. 如果当前状态为TWO:
1. 当前字符不是‘c’,那么我们要先拷贝前一个字符‘a’
2. 然后考虑当前字符,如果不是‘b’或者‘a’,则拷贝字符
状态转换非常简单,就是每次都检查,是前一个字符为‘a’。基本代码如下:
void stringFilter(char* str) { int i,j=0,length = strlen(str),STATE = 1; for (i = 0;i < length;i++) { //状态为ONE的情况 if (STATE == 1 && str[i] != 'a' && str[i] != 'b') { str[j++] = str[i]; } //状态为TWO的情况 else if (STATE == 2 && str[i] != 'c') { str[j++] = 'a'; if (str[i] != 'a' && str[i] != 'b') { str[j++] = str[i]; } } //跟新当前状态 STATE = str[i] == 'a' ? 2 : 1; //如果需要删除不连续的ac,则打开 //if (j > 1 && str[j-2] == 'a' && str[j-1] == 'c') j -= 2; } if(STATE == 2)str[j++] = 'a'; str[j] = '\0'; }
下面进一步考虑: 根据上面的算法,我们考虑aaccac,最终得到ac。ac在题目中要求的也是要删除的。是否要删除这个ac,就需要和面试官进行交流了,无论如何,总是 要考虑这种情况。还是采用上面的算法,怎么解决删除之后还可以删除的情况?只要把循环最后的代码注释去调即可
待字闺中之删除字符分析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。