526互联

算法刷题记录-长度最小的子数组

发布时间 2023-11-02 16:11:59作者: 工带菜鸡

算法刷题记录-长度最小的子数组

长度最小的子数组

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

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

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

思路：这题挺难的，看了解析才懂，暴力解法肯定超时间了，用两个指针表示当前判断数组的索引。初始都是0，high向后遍历，sum加上对应的值，当大于目标值，表示此时以low作为头的最优解已经找到，但这并非一定是以high作为尾的最优解，将low增加，sum减去对应的值并做判断。每次记录下当前找到的最优解的长度并于前的作比较。

public int minSubArrayLen(int target, int[] nums) {
    int low=0,high=0,res=Integer.MAX_VALUE;
     int sum=0;
     while (low<=high & high< nums.length){
         sum+=nums[high++];
         while (sum>=target){
             res=(high-low)<res?(high-low):res;
             sum-=nums[low++];
         }
     }
    return res==Integer.MAX_VALUE?0:res;
}

水果成篮

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

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

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

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

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

思路：这题的本质就是在数组里找一个尽可能长的子数组，让这个子数组只有两个数字。用了两种做法，第一种就是暴力解法，用一个nums存储两个值，对数组遍历，即判定以每一个值开始时的解，并比较每种解取最优解，思路简单，但是超内存了。代码图下：

public int totalFruit1(int[] fruits) {
    int res=1;
    int[] nums=new int[2];
    nums[0]=-1;nums[1]=-1;
    for (int i = 0; i < fruits.length; i++) {
        nums[0]=fruits[i];nums[1]=-1;
        int restemp=1;
        for (int j = i+1; j < fruits.length; j++) {
            if(fruits[j]==nums[0]){
                restemp+=1;
            }
            else if(nums[1]==-1){
                nums[1]=fruits[j];
                restemp+=1;
            }
            else if(fruits[j]==nums[1]){
                restemp+=1;
            }
            else {
                res=res>restemp?res:restemp;
                break;
            }
        }
        res=res>restemp?res:restemp;

    }

    return res;
}

第二种做法就是针对第一种做法做优化，其实暴力解法做了很多不必要的操作，下面详细说明：

fruits=[1,1,6,5,6,6,1,1,1,1]

可以看到对第一个1求解后是3，[1,1,6]。但其实第二个1是不必要计算的，因为他一定比第一个1小，这样可以得到这种优化：

if(fruits[j]==nums[0]){
    if(nums[1]==-1){
        i++;
    }
    restemp+=1;
}

在对第一个6求解，得到结果4，[6,5,6,6]。此时可以直接到第二个6求解，简单来说从后往前找第一个不重复的数字，因为之前的结果肯定不会此时好，比如6，5，5，6，6，5，5。在对第一个6求解后，直接在倒数第2个5开始即可。由此可得：

    else {
        res=res>restemp?res:restemp;
        j--;
        i=j;
        while (fruits[j]==fruits[j-1]){
            i=j-1;
            j--;
        }
        i--;
        break;
    }

对于第五个元素6求解，可以看到结果是6，[6,6,1,1,1,1]。此时应该会对1求解(6自加)，这一步也是不必要的，因为此时已经得到6了，不可能在得到任何一种比6还长得结果。因此：

if(fruits.length-i< res){
    return res;
}

综上，最终代码：

public int totalFruit(int[] fruits) {
        int res=1;
        int[] nums=new int[2];
        nums[0]=-1;nums[1]=-1;
        for (int i = 0; i < fruits.length; i++) {
            nums[0]=fruits[i];nums[1]=-1;
            int restemp=1;
            for (int j = i+1; j < fruits.length; j++) {
                if(fruits[j]==nums[0]){
                    if(nums[1]==-1){
                        i++;
                    }
                    restemp+=1;
                }
                else if(nums[1]==-1){
                    nums[1]=fruits[j];
                    restemp+=1;
                }
                else if(fruits[j]==nums[1]){
                    restemp+=1;
                }
                else {
                    res=res>restemp?res:restemp;
                    j--;
                    i=j;
                    while (fruits[j]==fruits[j-1]){
                        i=j-1;
                        j--;
                    }
                    i--;
                    break;
                }
            }
            res=res>restemp?res:restemp;
            if(fruits.length-i< res){
                return res;
            }

        }

        return res;
    }

最小覆盖字串

给你一个字符串 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。

思路：这题试了很多，一直超时间，感觉还是判断的过于过于冗余了，简单来说就是每次以某一个字符为起点判断，下次从当前判断的第一个存在目标字符串的开始判断。

public String minWindow(String s, String t) {
    String res="";
    char[] arrs=s.toCharArray();
    char[] arrt=t.toCharArray();
    boolean tag=true;
    for (int i = 0; i < arrs.length; i++) {
        boolean[] flag=new boolean[arrt.length];
        int sum=0;
        String restemp="";int index=0;
        if(arrs.length-i<arrt.length){
            break;
        }
        for (int j = i; j < arrs.length; j++) {
            if(index==arrt.length){
                break;
            }
            if(!tag){
                if(restemp.length()>res.length()){
                    break;
                }
            }
            restemp+=arrs[j];
            for (int k = 0; k < arrt.length; k++) {
                if(arrs[j]==arrt[k]){
                    if(i!=j) {
                        sum += 1;
                    }
                    if(sum==1){
                        i=j-1;
                    }
                }
                if(!flag[k]) {
                    if (arrs[j] == arrt[k]) {
                        flag[k] = true;
                        index += 1;
                        break;
                    }
                }
            }
        }

        if(tag) {
            if(index<arrt.length){
                break;
            }
            res = restemp;
            tag=false;
        }
        else {
            if(index==arrt.length){
                res = res.length() < restemp.length() ? res : restemp;
            }
        }

    }
    return res;
}

解法二：用一个字典，第一存目标字符串所有字符的出现次数。第二个存当前比较字符串所有字符的次数。比较当前字符串和目标字符串，用low和high分别代表两个指针，不满足则high++.满足low++

public boolean judge(HashMap<Character, Integer> dictionary,HashMap<Character, Integer> dictionary1){
    boolean allElementsContained = true;
    for (Character key:dictionary.keySet()){
        if(dictionary.get(key)>dictionary1.get(key)){
            allElementsContained=false;
            break;
        }
    }
    if (allElementsContained) {
        return true;
    } else {
        return false;
    }
}

public String minWindow(String s, String t) {
    String res = "";
    int low = 0, high = 0;
    char[] arrs=s.toCharArray();
    char[] arrt=t.toCharArray();
    HashMap<Character, Integer> dictionary = new HashMap<>();
    HashMap<Character, Integer> dictionary1 = new HashMap<>();
    if(arrs.length<arrt.length){
        return "";
    }
    for (int i = 0; i < arrt.length; i++) {
        if(dictionary.containsKey(arrt[i])){
            dictionary.put(arrt[i],dictionary.get(arrt[i])+1);
        }
        else {
            dictionary.put(arrt[i],1);
        }
    }

    for (int i = 0; i < arrs.length; i++) {
        dictionary1.put(arrs[i],0);
    }

    for (Character key:dictionary.keySet()){
        if(!dictionary1.containsKey(key)){
            return "";
        }
    }

    while (high<=s.length()){
        if(high-low<arrt.length){
            dictionary1.put(arrs[high],dictionary1.get(arrs[high])+1);
            high++;
        }
        else {
            String temp=s.substring(low,high);
            while (judge(dictionary,dictionary1)){
                if(res==""){
                    res=temp;
                }
                else {
                    res=res.length()<temp.length()?res:temp;
                }
                dictionary1.put(arrs[low],dictionary1.get(arrs[low])-1);
                low++;
                temp=s.substring(low,high);
            }
            if(high-low<arrt.length-1){
                break;
            }
            if(high<arrs.length) {
                dictionary1.put(arrs[high], dictionary1.get(arrs[high]) + 1);
            }
            high++;
        }
    }

    return res;
}