算法
1 无重复字符的最长子串
3. 无重复字符的最长子串 - 力扣（LeetCode）
首先理解题目，这个里面说的最重要的就是不包含重复字符这个关键词。这个的意思就是我们找到的子串中不能包含一样的字符，也就是最长就是所有英文字母都出现一次，即26。然后，我们用两个指针进行判断，左指针用于表示起始位置，右指针来记录在当前起始位置下最长不重复子串的位置。然后，我们判断右指针是否重复。如果不重复，说明该元素是子串的一部分，把该字符加进来；如果重复，则说明右指针到位置了，我们移动左指针。这里，一定要注意我们移除对应的元素。考虑我们要记录不重复的字符，所以我们使用Set这个数据结构。最后，我们记录结果，由于Set是随时改变的，因此我们使用具体的int值result来记录Set中的最大值。result必须设置为0，我们必须考虑到空字符串的情况。
在具体的书写的时候需要注意一些类和方法的书写，如HashSet中后面的S是大写，字符串获取长度的是length方法，而不是length属性，一定一定要写括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> set = new HashSet<Character>();
int left = 0, right = 0;
int result = 0;
while (left < s.length() && right < s.length()) {
Character chr = s.charAt(right);
if (!set.contains(chr)) {
set.add(s.charAt(right));
right++;
}else{
if (left != 0){
set.remove(s.charAt(left-1));
}
left++;
}
result = Math.max(result, set.size());
}
return result;
}
}
|
2.判断字符是否唯一
面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
要么使用循环，逐次判断对应的元素是否已经重复。也可以使用Java提供的Set直接进行判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean isUnique(String astr) {
HashSet<Character> set = new HashSet<Character>();
for (int i = 0; i < astr.length(); i++) {
char chr = astr.charAt(i);
if (set.contains(chr)) {
return false;
}else{
set.add(chr);
}
}
return true;
}
}
|
3.判定是否互为字符重拍
面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）
这个题目的重点就是知道每个对应的字符都有多少个，只要字符个数相同就能够保证满足要求。如果只考虑小写字母的话，我们可以只使用数组进行记录。我一开始想到的就是所有字符，所以才用了HashMap的方式，并且调用了对应的equals方法来进行判断。使用数组记录的时候，它使用了小技巧，不需要记录两个数组，只需要先记录第一个字符串中的所有元素，然后再减去第二个字符串中的元素。如果每个元素数量都相同的话，那么每个元素的数目就是0。数组元素中一旦有一个数目不为0，就说明元素数目没有对应上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public boolean CheckPermutation(String s1, String s2) {
HashMap<Character, Integer> hm1 = new HashMap<Character, Integer>();
HashMap<Character, Integer> hm2 = new HashMap<Character, Integer>();
for (int i = 0; i < s1.length(); i++) {
if (!hm1.containsKey(s1.charAt(i))){
hm1.put(s1.charAt(i), 0);
}else {
char c = s1.charAt(i);
hm1.replace(c, hm1.get(c)+1);
}
}
for (int i = 0; i < s2.length(); i++) {
if (!hm2.containsKey(s2.charAt(i))){
hm2.put(s2.charAt(i), 0);
}else {
char c = s2.charAt(i);
hm2.replace(c, hm2.get(c)+1);
}
}
return hm1.equals(hm2);
}
}
class Solution {
public boolean CheckPermutation(String s1, String s2) {
int len = s1.length();
if (len != s2.length())
return false;
int[] counts = new int[26];
for (int i = 0; i < len; i++)
counts[s1.charAt(i) - 'a'] ++;
for (int i = 0; i < len; i++)
counts[s2.charAt(i) - 'a'] --;
for (int cnt : counts){
if (cnt != 0)
return false;
}
return true;
}
}
|