Day32 LeetCode

1. All anagrams in the string

给定两个字符串 s 和 p,找到 s 中所有 p 的 变位词 的子串,返回这些子串的起始索引.不考虑答案输出的顺序.
变位词 指字母相同,但排列不同的字符串.

分析：

使用滑动窗口,滑动窗口的大小为p的长度.First use an array to recordp中字母出现的次数,Then count the number of occurrences of each letter in the sliding window,If the two arrays are the same, the starting coordinates will be recorded.

class Solution {
    
    public List<Integer> findAnagrams(String s, String p) {
    
        List<Integer> res = new ArrayList<>();
        int n = s.length(), m = p.length();
        if (m > n) return res;
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        for (int i = 0; i < m; i++) {
    
            count1[s.charAt(i)-'a']++;
            count2[p.charAt(i)-'a']++;
        }
        if (Arrays.equals(count1, count2)) res.add(0);
        for (int i = 0; i < n-m; i++) {
    
            --count1[s.charAt(i)-'a'];
            ++count1[s.charAt(i+m)-'a'];
            if (Arrays.equals(count1, count2)) res.add(i+1);
        }
        return res;
    }
}

2. 不含重复字符的最长子字符串

给定一个字符串 s ,请你找出其中不含有重复字符的最长连续子字符串的长度.

分析：

It is implemented using hash table and sliding window.初始化left=right=0,先用right开始遍历字符串,If the current character does not exist in the hash table, it is stored in the table,长度加1;Start if the current character exists in the hash tableleft++直到下标leftis equal to the current character,然后再left++,Store the current character into the table.

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        if (s.isEmpty()) return 0;
        int ans = 1;
        int start = 0;
        Set<Character> set = new HashSet<>();
        set.add(s.charAt(0));
        for (int end = 1; end < s.length(); end++) {
    
            if (set.contains(s.charAt(end))) {
    
                while (s.charAt(start) != s.charAt(end)) {
    
                    set.remove(s.charAt(start));
                    start++;
                }
                set.remove(s.charAt(start));
                start++;
                set.add(s.charAt(end));
            } else {
    
                set.add(s.charAt(end));
                ans = Math.max(ans, end - start + 1);
            }

        }
        return ans;
    }
}

3. The shortest string containing all characters

给定两个字符串 s 和 t .返回 s 中包含 t 的所有字符的最短子字符串.如果 s 中不存在符合条件的子字符串,则返回空字符串 “” .
如果 s 中存在多个符合条件的子字符串,返回任意一个.
注意： 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量.

分析：

1.Both uppercase and lowercase letters,用1个数组ascii128个字符包含,比哈希快,也比2个26Arrays are easy to write.
2.变量allCheck whether the number of valid letters meets the settlement conditions(all==m说明tMatch all letters in).
3.Shrink the left border before settlementlRemove extra letters,Go for the minimum length.
4.Shrink the left border after settlementl去除1个有效字母,Find the next string that matches all

class Solution {
    
    public String minWindow(String s, String t) {
    
        int n=s.length(),m=t.length();
        if(n<m)return "";
        int[] ori=new int[128],cnt=new int[128];
        for(int i=0;i<m;i++){
    
            ori[(int)t.charAt(i)]++;
        }
        int l=0,r=0,c=-1,len=n+1,all=0;
        while(r<n){
    
            int p=(int)s.charAt(r);
            if(cnt[p]<ori[p])all++;
            cnt[p]++;
            if(all==m){
    
                int k=(int)s.charAt(l);
                while(l<=r&&cnt[k]>ori[k]){
    
                    cnt[k]--;
                    l++;
                    k=(int)s.charAt(l);
                }
                if(r-l+1<len){
    
                    c=l;
                    len=r-l+1;
                }
                while(l<=r&&all==m){
    
                    k=(int)s.charAt(l);
                    if(cnt[k]==ori[k]){
    
                        all--;
                    }
                    cnt[k]--;
                    l++;
                }
            }
            r++;
        }
        return len==n+1?"":s.substring(c,c+len);
    }
}

4. 有效的回文

给定一个字符串 s ,验证 s 是否是 回文串 ,只考虑字母和数字字符,可以忽略字母的大小写.

本题中,将空字符串定义为有效的 回文串 .

分析：

双指针+Determines whether it is an alphanumeric character.

class Solution {
    
    public boolean isPalindrome(String s) {
    
        s = s.toLowerCase();
        int l = 0, r = s.length() - 1;
        while (l < r) {
    
            while (l < r && !check(s.charAt(l))) l++;
            while (l < r && !check(s.charAt(r))) r--;
            if (l < r && s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
    public boolean check(char c) {
     //检测字符c是否为数字或字母
        return 'a' <= c && c <= 'z' || '0' <= c && c <= '9';
    }

}

5. 最多删除一个字符得到回文

给定一个非空字符串 s,请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串.

分析：

双指针,设定左右指针,将二者分别指向字符串的两边.依次比较左右指针对应的字符是否相等.
如果相等,继续比较剩下的字符.如果不相等,则分两种情况,只要有一种情况是回文字符串即可：

• 删除左边的 left 指针指向的元素,判断 s[left+1, right] 是否回文.
• 删除右边的 right 指针指向的元素,判断s[left, right-1] 是否回文.

class Solution {
    
    public boolean validPalindrome(String s) {
    
        for(int left = 0, right = s.length() - 1; left < right; left++, right--){
    
            // 如果不相等,则分两种情况：删除左边的元素,或者右边的元素,再判断各自是否回文,满足一种即可.
            if(s.charAt(left) != s.charAt(right)) 
                return isPalindrome(s, left+1, right) || isPalindrome(s, left, right - 1);
        }
        return true;
    }

    // 判断字符串 s 的 [left, right] 是否回文
    private boolean isPalindrome(String s, int left , int right){
    
        while (left < right){
    
            if (s.charAt(left++) != s.charAt(right--))
                return false;
        }
        return true;
    }
}