文章目录

• 前言
• 一、每日一题63：得到 K 个黑块的最少涂色次数（力扣2379）
• 二、每日一题64：使数组和能被 P 整除（力扣1590）【前缀和+哈希表】
• 三、和可被 K 整除的子数组（力扣974）【前缀和+哈希表】
• 四、每日一题65：字母与数字（面试题 17.05）【前缀和+哈希表】
• 五、连续数组（力扣525）【前缀和+哈希表】

前言

1、得到 K 个黑块的最少涂色次数
2、使数组和能被 P 整除
3、和可被 K 整除的子数组
4、字母与数字
5、连续数组

一、每日一题63：得到 K 个黑块的最少涂色次数（力扣2379）

较为简单的滑动窗口问题，直接AC

class Solution {public int minimumRecolors(String blocks, int k) {int left = 0;int right = k-1;int length = blocks.length();int reFlash=Integer.MAX_VALUE;int count = 0;while(right<=length-1){ //最小滑动窗口 找到满足条件的窗口 然后压缩左边界//更新操作数for(int i = left;i<=right;i++){if(blocks.charAt(i)=='W'){count++;}}reFlash = Math.min(reFlash,count);//更新值right++;left++;count=0;}return reFlash;}
}

二、每日一题64：使数组和能被 P 整除（力扣1590）【前缀和+哈希表】

前缀和+哈希表
类似于之前的 力扣560 和为 K 的子数组
加了一些同余知识

大佬题解

class Solution {public int minSubarray(int[] nums, int p) {int sum = 0;for(int num:nums){sum= (sum+num)%p;}int res = nums.length;if(sum==0) return 0;HashMap map = new HashMap<>();map.put(0,-1);int pre = 0;for(int i=0;ipre = (pre+nums[i])%p;map.put(pre,i);int compare = (pre-sum+p)%p;if(map.containsKey(compare)){int j = map.get(compare);res = Math.min(res,i-j);}    }return res==nums.length? -1:res;}
}

三、和可被 K 整除的子数组（力扣974）【前缀和+哈希表】

分析：
在做完每日一题 1590 后，这道题直接可以AC

class Solution {public int subarraysDivByK(int[] nums, int k) {HashMap map = new HashMap<>();int pre =0;map.put(0,1);int res = 0;for(int i=0;ipre =( (pre+nums[i])%k+k)%k;if(map.containsKey(pre)){res += map.get(pre);}map.put(pre,map.getOrDefault(pre,0)+1);}return res;}
}

四、每日一题65：字母与数字（面试题 17.05）【前缀和+哈希表】

分析：
连续---->前缀和+哈希表
怎么去联系到一起？

map.putIfAbsent(pre,i); 这个函数非常好用！！！！

class Solution {public String[] findLongestSubarray(String[] array) {HashMapmap = new HashMap<>();int pre = 0;int len=0;int max = 0;int end = 0;map.put(0,-1);for(int i =0;ipre += Character.isLetter(array[i].charAt(0))?1:-1;// 字母1 数字-1len = i - map.getOrDefault(pre,i);if(len>max){max = len;end = i;}map.putIfAbsent(pre,i);}return Arrays.copyOfRange(array, end-max+1, end+1);}
}

五、连续数组（力扣525）【前缀和+哈希表】

分析：
跟上一题几乎一模一样的套路
0记为-1，1几位1；

class Solution {public int findMaxLength(int[] nums) {HashMap map = new HashMap<>();map.put(0,-1);int max =0;int pre = 0;for(int i=0;ipre += nums[i]==0?-1:1;//0表示-1  1表示1int len = i-map.getOrDefault(pre,i);if(len>max){max = len;}map.putIfAbsent(pre,i);}return max;}
}