1.长度最小的子数组

. - 力扣(LeetCode)

(1)题目描述 

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度如果不存在符合条件的子数组,返回 0 。

(2)原理

如何把暴力解法优化为滑动窗口 

解法一:暴力枚举出所有的子数组的和

解法二:滑动窗口-时间复杂度O(n)【暴力解法遇到单调性时】

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left=0,right=0;
        int n=nums.length;
        int count=0;
        int len=Integer.MAX_VALUE;
        int sumsum=0;
        
        for(left=0,right=0;right<n;right++){
            //进窗口
            sumsum=sumsum+nums[right];
            while(sumsum>=target){
                len=Math.min(len,right-left+1);
                //出窗口
                sumsum=sumsum-nums[left];
                left++;
            }
            
        }
        return len==Integer.MAX_VALUE?0:len;
    }
}

2. 无重复字符的最长子串

LCR 016. 无重复字符的最长子串 - 力扣(LeetCode)

(1)题目描述

子串的子数组都是连续的一串

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

子串

 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke"是一个子序列,不是子串。

(2)原理

解法一:暴力枚举 + 哈希表(判断字符是否重复出现) 

解法二:利用规律,使用滑动窗口

class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int left=0,right=0,n=s.length();
        int len=0;
        if(n<=1){
            return n;
        }
        HashSet<Character> hashSet=new HashSet<>();
        for(left=0,right=0;right<n;right++){
            char exsitss=s.charAt(right);
            while(hashSet.contains(exsitss)){
                //出窗口
                hashSet.remove(s.charAt(left));
                left++;
            }
            //进窗口
            hashSet.add(exsitss);
            len=Math.max(len,right-left+1);
        }
        return len;
    }
}

 同时我们可以用数组模拟哈希表

3.最大连续1的个数3

1004. 最大连续1的个数 III - 力扣(LeetCode)

给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。

示例 1:

输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释:[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。

示例 2:

输入:nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:10
解释:[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。

(1)题目描述

(2)原理

解法一:暴力枚举+zero计数器

解法二:滑动窗口

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left=0,right=0,n=nums.length;
        int count=0;
        int lenlen=0;
        for(left=0,right=0;right<n;right++){
            //进窗口
            if(nums[right]==0){
                count++;
            }
            //出窗口
            while(count>k){
                if(nums[left]==0){
                    count--;
                }
                left++;
            }
            lenlen=Math.max(lenlen,right-left+1);
        }
        return lenlen;
    }
}

 4.将x减到0的最小操作数

(1)题目描述

. - 力扣(LeetCode)

给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ,返回 最小操作数 ;否则,返回 -1 。

示例 1:

输入:nums = [1,1,4,2,3], x = 5
输出:2
解释:最佳解决方案是移除后两个元素,将 x 减到 0 。

示例 2:

输入:nums = [5,6,7,8,9], x = 4
输出:-1

示例 3:

输入:nums = [3,2,20,1,1,3], x = 10
输出:5
解释:最佳解决方案是移除后三个元素和前两个元素(总共 5 次操作),将 x 减到 0 。

(2)原理

正难则反

 

class Solution {
    public int minOperations(int[] nums, int x) {
        //正难则反
        int left=0,right=0,n=nums.length;
        int sum=0;
        int sumsum=0;
        int len=Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            sum=sum+nums[i];
        }
        int target=sum-x;
        if(target==0){
            return n;
        }
        //滑动窗口
        for(left=0,right=0;right<n;right++){
            sumsum=sumsum+nums[right];
            while(sumsum>=target&&left<=right){
                if(sumsum==target){
                    len=Math.max(len,right-left+1);
                }
                //出窗口
                sumsum=sumsum-nums[left];
                left++;
            }
        }
        return len==Integer.MIN_VALUE?-1:(n-len);
    }
}

 5.水果成篮

904. 水果成篮 - 力扣(LeetCode)

(1)题目描述

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:

  • 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
  • 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。

给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

(2)原理

转化:找出一个最长的子数组的长度,子数组中不超过两种类型的水果

解法一:暴力枚举+哈希表

解法二:滑动窗口

class Solution {
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();

        int left = 0, ans = 0;
        for (int right = 0; right < n; ++right) {
            cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);
            while (cnt.size() > 2) {
                cnt.put(fruits[left], cnt.get(fruits[left]) - 1);
                if (cnt.get(fruits[left]) == 0) {
                    cnt.remove(fruits[left]);
                }
                ++left;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

 Java HashMap getOrDefault() 方法 | 菜鸟教程 (runoob.com)

6.找出字符串所有字母异位词

(1)题目描述

LCR 015. 找到字符串中所有字母异位词 - 力扣(LeetCode)

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

变位词 指字母相同,但排列不同的字符串。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。

(2)原理

滑动窗口是固定的情况

class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret=new ArrayList<>();
        char[] s=ss.toCharArray();
        char[] p=pp.toCharArray();
        int[] hash1=new int[26];//统计字符串p,每一个字符出现的个数
        for(char ch:p){
            hash1[ch-'a']++;
        }
        int[] hash2=new int[26];//统计窗口中,每一个字符出现的个数
        int m=p.length;
        for(int left=0,right=0,count=0;right<s.length;right++){
            char in=s[right];
            if(++hash2[in-'a']<=hash1[in-'a']){//进窗口+维护,count为有效字符
                count++;
            }
            if(right-left+1>m){//出窗口,
                char out=s[left++];
                if(hash2[out-'a']--<=hash1[out-'a']){//出窗口+维护
                    count--;
                }
            }
            //更新结果
            if(count==m){
                ret.add(left);
            }
        }
        return ret;
    }
}

 7.串联所有单词的子串

30. 串联所有单词的子串 - 力扣(LeetCode)

(1)题目描述

给定一个字符串 s 和一个字符串数组 words words 中所有字符串 长度相同

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd""cdabef", "cdefab""efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1:

输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2:

输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3:

输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

(2)原理

 

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret=new ArrayList<>();
        Map<String,Integer> hash1=new HashMap<>();//保存字典中的所有字频
        for(String str:words){
            hash1.put(str,hash1.getOrDefault(str,0)+1);
        }
        int len=words[0].length(),m=words.length;//每个字符串长度是一致的
        for(int i=0;i<len;i++){//执行操作
            //滑动窗口的具体操作
            Map<String,Integer> hash2=new HashMap<>();//保存窗口中的所有字频
            for(int left=i,right=i,count=0;right+len<=s.length();right+=len){
                //进窗口+维护
                String in=s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in)<=hash1.getOrDefault(in,0)){
                    count++;
                }
                //出窗口
                if(right-left+1>len*m){
                    //出窗口+维护
                    String out=s.substring(left,left+len);
                    if(hash2.get(out)<=hash1.getOrDefault(out,0)){
                        count--;
                    }
                    hash2.put(out,hash2.get(out)-1);
                    left+=len;
                }
                //更新结果
                if(count==m){
                    ret.add(left);
                }
            }

        }
        return ret;
    }
}

 8.最小覆盖子串

(1)题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。

注意:

  • 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2:

输入:s = "a", t = "a"
输出:"a"
解释:整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。

提示:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s 和 t 由英文字母组成

(2)原理

合法的时候才出窗口

class Solution {
    public String minWindow(String ss, String tt) {
        char[] s=ss.toCharArray();
        char[] t=tt.toCharArray();

        int[] hash1=new int[128];//统计字符串t中字符的频次
        int kinds=0;//字符串t中,有多少种字符
        for(char ch:t){
            if(hash1[ch]++==0){
                kinds++;
            }
        }
        int[] hash2=new int[128];//统计滑动窗口字符的频次
        int minlen=Integer.MAX_VALUE,begin=-1;
        for(int left=0,right=0,count=0;right<s.length;right++){
            char in=s[right];
            if(++hash2[in]==hash1[in]){
                count++;//进窗口+维护count
            }
            while(kinds==count){//判断
                //更新结果
                if(right-left+1<minlen){
                    begin=left;
                    minlen=right-left+1;
                }
                char out=s[left++];
                if(hash2[out]--==hash1[out]){
                    count--;//出窗口+维护count
                }
            }
        }
        if(begin==-1){
            return new String();
        }else{
            return ss.substring(begin,begin+minlen);
        }

    }
}

 

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部