2024/4/20—4/21
560.和为K的子数组
前缀和+哈希表,做二叉树的时候也有这个套路。注意细节,遍历到当前前缀和的时候是先找结果个数还是先加入哈希?应该先找结果个数,不然的话,当前位置也算上了(因为是前缀和相减,当前位置算的话(当前 - 当前),子数组就不存在了)。注意先放入一个,处理边界,也就是子数组的长度为0(肯定不算)或者当前全长。
那个枚举的方法,也就是遍历嘛,主要是看懂时间复杂度的解释。
2024/9/10
关于为什么先统计count,在把当前前缀加入map;可以从下标意义的角度去考虑;遍历到的当前位置的前缀和pre[i],对应的数组[0, i];map中已经存在的前缀数组下标为[0,j]; 重点是j的范围是0~i-1;如果有符合题目条件的子数组,它的下标范围肯定是[j+1,i];
如果先把当前前缀和放入map,j就可以取到i,结合上面的分析如果此时[0,j] j=i是一个满足条件的pre[i] - k,那么对应的子数组长度为0;不存在,这种情况对应的k=0;
同理可以明白为什么要先put(0,1);
239.滑动窗口最大值
直接看官方解法了
优先队列
升序降序,大小顶堆写法
9/10
这里再说一下优先队列比较器的两种写法和排序规则
方法一:Javabean类实现Comparable接口指定比较规则
- 实现Comparable接口,重写compareTo方法;注意理解,compareTo( ) 方法中的参数是已经存在的元素(就理解为数组中存在的吧),this是新插入的元素,返回值一般都是新的减去旧的,结果大于0,记忆为新的更大,放到后面(旧的右边),所以是升序;
- 结果是0的话,下面是是基于TreeSet的,所以不允许重复;优先队列的话看上面,好像是不交换;
public class Student implements Comparable<Student>{private String name;private int age;@Override//this:表示当前要添加的元素//o:表示已经在(某种数据结构,TreeSet等)存在的元素//返回值://负数:表示当前要添加的元素是小的,存左边//正数:表示当前要添加的元素是大的,存右边//0 :表示当前要添加的元素已经存在,舍弃public int compareTo(Student o) {//指定排序的规则//只看年龄,我想要按照年龄的升序进行排列return this.getAge() - o.getAge();}
}
方法二:创建集合对象的时候,传递比较器Comparator指定规则
- 和上面的一样,第一个参数是新要插入的元素,第二个参数是已经存在的元素,新的减旧的,按照方法一理解。就是升序,排出来的是个升序数组,优先队列基于堆,拿的第一个元素,是最小的,所以这种方式是小顶堆;
- 下面是两种写法
public static void main(String[] args) {/*需求:请自行选择比较器排序和自然排序两种方式;要求:存入四个字符串, “c”, “ab”, “df”, “qwer”按照长度排序,如果一样长则按照首字母排序采取第二种排序方式:比较器排序*///1.创建集合//o1:表示当前要添加的元素//o2:表示已经在红黑树存在的元素//返回值规则跟之前是一样的TreeSet<String> ts = new TreeSet<>((o1, o2)->{// 按照长度排序int i = o1.length() - o2.length();//如果一样长则按照首字母排序i = i == 0 ? o1.compareTo(o2) : i;return i;});}
思路
总体的思路,不着急删除(不要想着窗口动一次删一次),因为我们要的是每个窗口的最大值:窗口每移动一次,就把新遍历到的元素加入优先队列,然后取到优先队列的队头元素(队列里所有元素当前的最大值)。
关键的是,如果这个元素不在当前的滑动窗口范围内,删除,继续取队头元素,直到取到的元素在当前窗口的范围内,再把这个答案放到结果集合里。
算法竞赛中的常用JAVA API:PriorityQueue(优先队列)_java priorityqueue api-CSDN博客
单调队列
. - 力扣(LeetCode)灵山
本质上单调是自己代码维护的,所以就是普通队列附加上代码维护的单调性;单调队列和单调栈的处理方式很像;
关键是维护队头到队尾是降序的特性,并不也无法要求每个元素都在队列中,因为单调的性质总会淘汰一些元素。
- 为了维护单调特性
- 初始化前k个时,每个新的元素x被添加到队尾时,都要删除掉所有在x之前且比x大的元素
- 滑动窗口移动时,添加新元素的时候也执行上述相同的操作
- 取每个滑动窗口的结果时,队头元素就是max,但是如果它不在滑动窗口的范围内,需要不断删除队头元素,直到队头元素在当前滑动窗口范围内
- 可以直接在单调队列里存入下标,不用存数字+下标,单调队列是双端队列Deque实现,不是Queue
分块+预处理
这个方法自己看题解吧,就先不实现了
76.最小覆盖子串
遍历长串,把所有的字符存到hashmap,key为字符,value为字符出现的位置集合。遍历目标串,拿到目标串每个字符的位置集合。
对于目标串中的重复元素,
4/29
看到一个题解说这题很像: 438找到字符串中所有字母异位词
9/10
滑动窗口
本质上就是滑动窗口,只不过是窗口移动时的判断条件变复杂了;
. - 力扣(LeetCode)灵山的题解,搭配视频理解,官方用的hashmap怎么遍历,后面有时间再写吧,这里先用数组;
滑动窗口就是暴力遍历的上位解法,同向双指针,(就像二分查找是顺序数组暴力查找的上位一样);定义先定义左右指针都指向index = 0;以右指针为基准,随着r++,总会到达满足条件的状态,此时再去l++,区间缩减,左指针向着右指针靠近;直到不满足条件,在这个缩减的过程里更新结果,因为需要的是最小长度的嘛,再去移动右指针;
再去看官方题解对滑动窗口的描述就很好理解了;
伪代码如下:其实也很好理解的,时间复杂度为O(n);虽然有两个循环
int len...
int l =0;
//for循环中定义r
for(int r = 0; r < len; r++){//r每到一个位置需要执行的操作状态更新while(满足条件){更新结果;状态更新移动左指针,l++;}
}
return 结果
接下来就是结合具体的条件了;用数组存储当前遍历到的字符串cur(l,r指针包含的串)和子串t的每个字符的出现次数;
- 进入for循环,在每次移动r时,更新cur串的字符出现次数
- while循序的条件是,cur串是否能顾覆盖子串t,字符种类和数量两个方面
- while中将结果串的左右指针暂时更新为l,r(如果长度更小)
- 因为要移动左指针,所以要提前更新l++造成的状态影响,最后再l++;这个顺序还是好好思考一下。
- 优化点:
- while的条件判断时,需要我们对cur和t进行覆盖的判断,需要遍历记录两个串字符数目的数组(或map),左右指针更新时都需要判断;
- 要对上述过程进行优化,我们定义一个变量less,对于子串 t 的每种字符cur串中满足的个数,即cur串中是否包含这个字符,以及数量是否足够;
- less的长度应为 t 的字符种类,数量是否够还是借助之前的数组判断;
- 优化具体到代码:
- r++之后,状态更新不仅要更新cur的字符数量,还要更新less,如果更新到的字符,能够包含了 t 中的某个字符,less--;这里有个坑,比较cur和 t 某个字符数量时,要用==判定为满足,因为这个字符在cur中只可能增加了;连续两个相同字符满足条件时,>=的话less会多减()。
- while的条件为less == 0
- while里的状态更新时,先假设l++带来的影响(当前 l 对其指向字符数量的变化,这个字,失去这个字符后还能满足覆盖t z中这个字符的条件);再进行l++
啰嗦了;
最后还有一点思考,之所以可以不断l++到不满足条件,是因为l位置一旦是不满足条件了,后面的l都不会再满足条件