2024.2.12 算法

算法

1 无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

首先理解题目，这个里面说的最重要的就是不包含重复字符这个关键词。这个的意思就是我们找到的子串中不能包含一样的字符，也就是最长就是所有英文字母都出现一次，即26。然后，我们用两个指针进行判断，左指针用于表示起始位置，右指针来记录在当前起始位置下最长不重复子串的位置。然后，我们判断右指针是否重复。如果不重复，说明该元素是子串的一部分，把该字符加进来；如果重复，则说明右指针到位置了，我们移动左指针。这里，一定要注意我们移除对应的元素。考虑我们要记录不重复的字符，所以我们使用Set这个数据结构。最后，我们记录结果，由于Set是随时改变的，因此我们使用具体的int值result来记录Set中的最大值。result必须设置为0，我们必须考虑到空字符串的情况。

在具体的书写的时候需要注意一些类和方法的书写，如HashSet中后面的S是大写，字符串获取长度的是length方法，而不是length属性，一定一定要写括号。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 统计包含不重复字符（最长26）的子串长度
        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直接进行判断。

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，就说明元素数目没有对应上。

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;
    }
}