第一题-是否全不同
假设字符串是ASCII字符串
因为码表一共128个元素，所以辅助空间开129个，索引是0~128
可以直接遍历每个字符，取对应的码值作为索引，填入辅助空间内
如果不能开辟辅助空间，就只能两层for循环遍历
取到一个元素，就与所有元素作比较，看相不相等
第二题-字符串反转
与这题对应的题有第八题
不调用封装函数
第三题-字符重新排列
法一
转成字符数组进行排序
法二
用每个字符的ASCll码值作为索引进行记录，开辟一个辅助空间，一个数组加，一个数组减，要减的位置如果计数为0，就不用减，直接返回false，因为计数为0就代表上一个字符串没有这个字符。处理完两个数组后，扫描辅助空间，遇到不是0的，返回false
第四题-字符串压缩
第五题-字符集是否相同
验证两个字符串的字符集是否相同
ASCII
假设字符串是ASCII字符串
延用第三题的思路
不管出现几次，只要有就行。所以辅助函数只要记了就行，不用管记几
所以我们保持数组里只有1和0，用来代表有或没有即可
一个字符串用于在辅助数组里加
另一个字符串用来辅助数组里减
最后扫描辅助数组
非ASCII
如果不是ASCII码值，就用HashMap，这个通用所有字符集
第六题-任意移位包含字符串
两个字符串s1和s2，s2能否被 通过s1作任意移位得到的字符串 包含。
假设字符串是ASCII字符串
延用第三题思路
将s1有的字符在辅助函数里记录
再遍历s2，验证s2中字符所在的位置是否被记录过，有记录就减1
只是比第三题少 “最后遍历数组，查看有没有没被减掉的数组” 这一步
注意，当s1 = ABCD , s2 = CDAA时，也是false
第七题-循环移位包含字符串
这个问题还有另一个名字叫：旋转词（s1）
这道题 比第六题多了个限制，就是不能任意移位，只能循环移位
例如题目上的字符串移位
结论： s2是s1+s1的子串
java解法
也可以用 如果返回的不是-1，就说明包含子串
类中的 方法用于返回指定字符或子字符串在此字符串中第一次出现java基础字符串教程处的索引。如果未找到该字符或子字符串，则返回 。也区分大小写
但一般 会比contains慢一点
cpp解法
第八题-按单词反转
与这题对应的题有第二题
先把整个字符串按字符顺序逆转，调用第二题函数，这样就达到了反转字符串的目的，但不是按单词反转
再按空格分割字符串,数组内的每个元素是一个单词
取出每个单词，因为单词内部也是反转的，所以把单词传进函数再逆转回来后，存入结果字符串
第九题-去除连续出现k次的0
字符串是不可变的，所以不可能在原来的字符串上做处理
法一
可以用正则表达式
eg：0{3}代表3个0
法二
用StringBuilder 一点一点拼接
取s中的每一个字符，如果是0就计数，不是0就添加
但在添加不是0的字符之前，要把它前面去掉k个0后剩下的0都填进去，再添加不是0的数
用count % k来确定要添加几个0
当有2个连续的0，k=3时，count % k = 2；添加2个0
当有4个连续的0，k=3时，count % k = 1；添加2个1
最后单独处理一下末尾的0，因为非0数不会进行除计数以外的操作
eg：This0a00
判断一下最后一位，如果是0，就再count % k来确定要添加几个0
第十题-回文串
回文串：从右往左读和从左往右读，结果是一样的
也就说明，回文串进行反转后，与未反转前相同
利用这个思路，直接将回文串反转，与未反转前作比较即可
第十一题-找回文串
造前两位数，后两位就是前两位的倒序
第十二题-最短摘要
核心思路：用两个指针指向子串的起始和终止，不断更新，一直指向较小子串
找子串的时候先挪动头指针，直到头指针指向下一个关键字，验证当前子串是否包含全部关键字，没包含就挪动尾指针，直到包含全部关键字，比较长度，比上一个子串短就用另外两个指针存一下索引。
继续向前找，还是先向前挪头指针，挪一格验证一下是不是关键字……
细节：
1、每次挪动都验证是不是关键字，是就要标记一下已存在
用一个和关键字一样长度的数组存是否存在，是（1）否（0）
写一个方法indexOf找元素在关键字数组（keys）中的位置，存在就返回索引，不存在返回-1
用索引去辅助空间对应位置标1
因为辅助空间每个位置存的是1或0，所以对辅助空间求和，与长度相比，就能确定是否全部包含
2、用一个变量记录每个子串的j，用于下一个子串的j的初始化
因为下一个子串的j需要用上一个的j作为起始点向前走
这里的上一个j不是上一个最短子串的j，而是上一个子串的j
下一个子串的j不能用end初始化，因为end存的是上一个最短子串的j，我们需要的是上一个子串的j
3、每一次找新的子串时，需要置空辅助空间
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/25740.html