【每日算法Day 20】字符串基础2
字符串的很多使用场景要求查找特定的字符的位置或者次数，可以结合哈希使用。同时，熟练使用正则表达式和String类的方法也对字符串的处理很有帮助。
# LeetCode 387. 字符串中的第一个唯一字符 (opens new window)
# 题目描述
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。提示：你可以假定该字符串只包含小写字母。
# 示例
s = "leetcode"
返回 0
s = "loveleetcode"
返回 2
2
3
4
5
# 解题思路
暴力法对于每个字符向后扫描，第一次发现扫描完也没有相同字符则返回该字符，时间复杂度为O(n^2)不赘述了。
“不重复”这一特性即唯一，可以和哈希结合起来，扫描数组逐个把字符的索引插入到哈希集合中（可以使用HashMap，对于这一题字符的出现范围较小自己创建哈希数组也可以），如果放入时发现已经加入过一次则把索引置为-1。插入完成后再依次扫描数组，第一个索引值不为默认或-1的字符就是第一个唯一字符。扫描完都没有这样的字符则返回-1。
public int firstUniqChar(String s) {
//题目假定该字符串只包含小写字母，则只需要26个位置
int[] hash = new int[26];
for(int i=0; i<s.length();i++){
int ch = (int)s.charAt(i)-(int)'a';
//这边写hash[ch]+=1即可，不需要用数组来存索引
//因为反正下面还有一次遍历，第一次遇到计数为1的就是目标字符了
if(hash[ch]==0){
hash[ch]=i+1;
}else{
hash[ch]=-1;
}
}
for(int i=0;i<s.length();i++){
int ch = (int)s.charAt(i)-(int)'a';
if(hash[ch]!=0&&hash[ch]!=-1)
return i;
}
return -1;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# LeetCode 383. 赎金信 (opens new window)
# 题目描述
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。你可以假设两个字符串均只含有小写字母。
(题目说明：罪犯索要赎金为了不暴露自己的字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
# 解题思路
同上，使用哈希数组统计杂志中各字符的数量，写赎金信时再从数组中减去用掉的数量，一旦发现某个字符数量-1后小于0则返回false，写完信都没问题则返回true。
public boolean canConstruct(String ransomNote, String magazine) {
int[] hash =new int[26];
for(int i=0;i<magazine.length();i++){
hash[(int)magazine.charAt(i)-'a']++;
}
for(int i=0;i<ransomNote.length();i++){
if(--hash[(int)ransomNote.charAt(i)-'a']<0)
return false;
}
return true;
}
2
3
4
5
6
7
8
9
10
11
# LeetCode 151. 翻转字符串里的单词 (opens new window)
# 题目描述
给定一个字符串，逐个翻转字符串中的每个单词。
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
# 示例
示例 1：
输入: " hello world! "
输出: "world! hello"
示例 2：
输入: "a good example"
输出: "example good a"
2
3
4
5
6
7
# 解题思路
和字符串中单个字符的翻转不同，前者可以使用双指针来避免使用额外的O(n)空间，而这一题由于要调换的单词长度不定且两个单词的长度也不一定相等所以不好直接用双指针，目前的思路只有切割出字符串中的单词一次放入容器（List）中，翻转，再输出。时间复杂度为O(n)，但是这样需要使用额外的O(n)空间。
public String reverseWords(String s) {
List<String> list=Arrays.asList(s.trim().split("\\s+"));
Collections.reverse(list);
return String.join(" ",list);
}
2
3
4
5
为了避免使用额外的空间，可参考LeetCode 189 旋转数组的分块翻转数组的方法，首先翻转整个字符串，使用双指针搜索每一个单词，再旋转之。不过Java语言中String类不可以再修改，对String的操作一定会用到额外的O(n)空间。题目要求选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。