算法day06

第一题

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

如题上述：

本题原来的意思给定一个数字x，从数组的左边或者右边使用x减去数组中的数字，直到减去最后一个数字为0时，返回最小的操作次数；如果最终减去的数组中的数字之后不能得到0，则返回-1；

我们由正难则反原理将题意转化为如下所示：

如上图所示，我们使用滑动窗口模型，让窗口内的子数组之和为sum-x，左边区域和右边区域的数组之和为x，为了保证左右区间的数组长度最小，则中间区域的数组长度需要最长；

故此解题步骤如下所示：

步骤一：

定义左右双指针；

步骤二：

进窗口：

右指针移动一位，并记录sum在案；

步骤三：

判断出窗口操作：

如果tar>sum-x，则开始出窗口操作，直到不满足刚刚上述条件；

所谓出窗口操作则是，sum减去当前左指针所指的数值，并且左指针右移一位；

注意每一次出完窗口操作之后要更新中间数组区域的长度；

最后返回的结果是-1or整个数组长度-之前记录的数组长度；

综上所述，代码如下：

class Solution {
    public int minOperations(int[] nums, int x) {
        int sum =  0;
        for(int a : nums){
            sum += a;
        }
        int tar = sum - x;
        if(tar < 0){
            return -1;
        }
        int temp = 0,res = -1;
        for(int left = 0,right = 0;right < nums.length;right++){
            temp += nums[right];
            while(temp > tar){
                temp -= nums[left++];
            }
            if(temp == tar){
                res = Math.max(res,right-left+1);
            }
        }
        if(res == -1){
            return res;
        }else{
            return nums.length-res;
        }
    }
}

第二题

904. 水果成篮

由上题可知：

本题的意思可以转化为在一个最长的数组，且里面的元素种类不能超过2；

本题采用滑动模块的思想，解题步骤如下所示：

步骤一：

定义左右双指针；

步骤二：

进窗口操作：

右指针移动一位，将其所指的元素放在hash表里面

步骤三：

判断操作：

当hash表的长度大于2时，hash表中左指针的元素先-1，判断左指针所值的元素是否是否为0，如果为零，将该元素移除hash表，反之不然，同时将左指针向前移动一位；即完成出窗口操作，最后更新当前窗口的长度并记录在案；

返回最长的窗口的长度；

代码如下所示：
class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
        int res = 0;
        for(int left = 0,right = 0;right < fruits.length;right ++){
            int in = fruits[right];
            hash.put(in,hash.getOrDefault(in,0)+1);
            while(hash.size() > 2){
                int out = fruits[left]; 
                hash.put(out,hash.get(out)-1);
                if(hash.get(out)== 0){
                    hash.remove(out);
                }
                left ++;
            }
            res = Math.max(res,right-left+1);
        }
        return res;
    }
}

下面用数组代表hash表，如下所示：

class Solution {
    public int totalFruit(int[] fruits) {   
        int res = 0,n = fruits.length;
        int[] hash = new int[n+1];
        for(int left = 0,right = 0,kinds = 0;right < n;right ++){
            int in = fruits[right];
            if(hash[in] == 0){
                kinds++;
            }
            hash[in]++;
            while(kinds > 2){
                int out = fruits[left]; 
                hash[out] --;
                if(hash[out]== 0){
                    kinds --;
                }
                left ++;
            }
            res = Math.max(res,right-left+1);
        }
        return res;
    }
}

第三题

438. 找到字符串中所有字母异位词

题目如上所示：

首先如何能够快速的判断出相同的异位词，只有采用hash表；

其次本次采用滑动窗口和hash表的方法来解决；

解题步骤如下：

步骤一：

定义所有双指针；

步骤二：进窗口

当前右指针所指的字符映射到hash表中的位置中，该位置上记录的是该元素当前在窗口中的数目；每当有字符进入到窗口，其对应的hash表中的相应位置会记录该字符的存在数量；

步骤三：

当前左右指针所指的窗口的长度是否和固定数组的长度m比较：

窗口长度大于m：

在hash表中减去当前左指针所映射位置的数量，即该元素所记录的数量减一，同时左指针向右移动一位；

此时得到一个新的窗口，这时候要更新我们的结果，即检查两个hash表是否一致；

步骤四：关于两个hash表进行比较的简单方法：

如图所示，定义一个count变量，来记录有效hash2表中字符的总数量，如当前hash1中需求有效字符数量为3，所以我们需要确定更新结果的前提就是hash2中所统计的count=3时，就要返回该子数组的第一个元素下标，详细加分析如下所示：

进窗口后：如果当前该字符对应hash表中的记录数目小于该元素的有效数目，则count变量加一；

出窗口前：如果当前该字符对应hash表中的记录数目小于该元素的有效数目，则count变量减一；

当所记录的count==需要的值m时，我们要更新结果：

其中代码如下所示：
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<Integer> ();
        char[] s1 = s.toCharArray();
        char[] p1 = p.toCharArray();

        int[] hash1 = new int[26];
        for(char ch: p1){
            hash1[ch-'a']++;
        }

        int[] hash2 = new int[26];
        int m = p1.length;
        for(int left = 0,right = 0,count =0;right < s1.length;right++){
            char in = s1[right];
            hash2[in -'a']++;
            if(hash2[in-'a']<=hash1[in-'a']){
                count++;
            }
            if(right - left + 1 > m){
                char out = s1[left++];
                if(hash2[out-'a'] <= hash1[out-'a']){
                    count--;
                }
                hash2[out-'a']--;

            }
            if(count == m){
                ret.add(left);
            }
        }
        return ret;
    


    }
}