顿搜
飞过闲红千叶，夕岸在哪
类目归类
字符串操作——算法设计 · 篇一
08/10
一、字符串的基本操作
GitHub地址：字符串长度.cpp
- ①、求整个子符串的长度：可用递归
- ②、未知子符串的总长度，求最后一个单词的长度
1、以空格分界，计数置零
2、遍历字符串，计数自增
3、遇到空格，计数置零；遇到'\0'，遍历结束，当前计数即为最后单词的长度。
- ③、无覆盖拷贝
1、如果dst和src区域没有重叠，那么从开始处逐一拷贝 (dst <= src || dst >= (src+count))
2、如果dst和src区域有交叉，那么从尾部开始向起始位置拷贝
## 二、字符串中的查找 > GitHub地址：字符串查找与反转.cpp + ①、 查找各字符出现的次数 > 1、定义一个hash数组，键为字符， 值为个数 > 2、依次遍历字符串，并记录到hash数组中即可 + ②、整个句子以单词为单位进行反转 > 1、首先完成整个句子的反转 > 2、然后完成内部单词的二次反转 + ③、字符串内部单词的反转 > 1、从头部开始，以空格为分界点，对每一个单词进行反转
## 三、字符串中的排序 > GitHub地址：字符串排序（可引申为快排）.cpp + ①、排序字符串，使大写字符在前，小写字符在后 > 1、使用双指针，一个记录上次交换的位置，即后指针，初始化为-1，交换之前自增。 > 2、另一个记录当前遍历到的字符，即前指针，初始化为0。 > 3、每每遇到小写字母，前指针右移，遇到大写字母，与后指针交换当前值，然后自增。 > 4、该方案能保证大写字符的相对顺序不变 + ②、同上，但是使得小写字符的相对顺序不改变 > 1、与上面的方法相同，但此时应该从后往前遍历，交换的是小写字符
## 四、字符串去重 > GitHub地址：字符串去重.cpp + ①、排序好的字符串，重复的字符串只保留一个 > 1、使用双指针，一个记录不重复字符串的位置，即后指针，初始化为0。 > 2、另一个记录当前遍历到的字符，即前指针，初始化为1。 > 3、比较前指针和后指针的值是否相等，若不相等，则后指针自增，并把前指针的值赋给后指针。 > 4、若相等，则前指针自增。 > 5、遍历结束后，在前指针的下一个位置，赋值'\0' > 6、若想保留两个重复的字符，则第四条需要增加一个标志，记录重复的个数 + ②、重复的字符全部删除 > 1、使用双指针，一个记录不重复字符串的位置，即后指针，初始化为0。 > 2、另一个记录当前遍历到的字符，即前指针，初始化为1。 > 3、遍历时比较当前字符和下一个字符是否相同，若相同，则置标志位为1，前指针自增 > 4、若不相同，则检查标志位是否为1，若为1，则置零，后指针自增（相当于跳过重复字符） > 5、若标志位为0，则后指针自增，并把前指针的值赋给后指针。 > 6、显然遍历到n-2，此时n-2与n-1比较，但当他们相同时，前置指针则增，已到n-1，下一轮跳出循环 > 7、所以对最后n-1需要单独处理，若n-2与n-1不等，则需要把n-1赋给后指针。 ## 五、将字符串转化为整数（atoi） > GitHub地址：atoi.cpp 需要注意的地方 > 1、数值越界 > 2、正负数 > 3、字符串结束标志
