太原网站推广怎么做,网站首页psd下载,免费网站服务器安全,企业营销培训2024/4/20—4/21
560.和为K的子数组 前缀和哈希表#xff0c;做二叉树的时候也有这个套路。注意细节#xff0c;遍历到当前前缀和的时候是先找结果个数还是先加入哈希#xff1f;应该先找结果个数#xff0c;不然的话#xff0c;当前位置也算上了#xff08;因为是前缀和…2024/4/20—4/21
560.和为K的子数组 前缀和哈希表做二叉树的时候也有这个套路。注意细节遍历到当前前缀和的时候是先找结果个数还是先加入哈希应该先找结果个数不然的话当前位置也算上了因为是前缀和相减当前位置算的话当前 - 当前子数组就不存在了。注意先放入一个处理边界也就是子数组的长度为0肯定不算或者当前全长。 那个枚举的方法也就是遍历嘛主要是看懂时间复杂度的解释。
2024/9/10 关于为什么先统计count在把当前前缀加入map可以从下标意义的角度去考虑遍历到的当前位置的前缀和pre[i]对应的数组[0, i]map中已经存在的前缀数组下标为[0,j]; 重点是j的范围是0~i-1如果有符合题目条件的子数组它的下标范围肯定是[j1i] 如果先把当前前缀和放入mapj就可以取到i,结合上面的分析如果此时[0,j] ji是一个满足条件的pre[i] - k,那么对应的子数组长度为0不存在这种情况对应的k0; 同理可以明白为什么要先put(0,1); 239.滑动窗口最大值
直接看官方解法了
优先队列 升序降序大小顶堆写法 9/10
这里再说一下优先队列比较器的两种写法和排序规则
方法一Javabean类实现Comparable接口指定比较规则
实现Comparable接口重写compareTo方法注意理解compareTo( ) 方法中的参数是已经存在的元素就理解为数组中存在的吧this是新插入的元素返回值一般都是新的减去旧的结果大于0记忆为新的更大放到后面旧的右边所以是升序结果是0的话下面是是基于TreeSet的所以不允许重复优先队列的话看上面好像是不交换
public class Student implements ComparableStudent{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表示已经在红黑树存在的元素//返回值规则跟之前是一样的TreeSetString ts new TreeSet((o1, o2)-{// 按照长度排序int i o1.length() - o2.length();//如果一样长则按照首字母排序i i 0 ? o1.compareTo(o2) : i;return i;});}思路 总体的思路不着急删除不要想着窗口动一次删一次因为我们要的是每个窗口的最大值窗口每移动一次就把新遍历到的元素加入优先队列然后取到优先队列的队头元素队列里所有元素当前的最大值。 关键的是如果这个元素不在当前的滑动窗口范围内删除继续取队头元素直到取到的元素在当前窗口的范围内再把这个答案放到结果集合里。 算法竞赛中的常用JAVA APIPriorityQueue(优先队列)_java priorityqueue api-CSDN博客 单调队列
. - 力扣LeetCode灵山 本质上单调是自己代码维护的所以就是普通队列附加上代码维护的单调性单调队列和单调栈的处理方式很像 关键是维护队头到队尾是降序的特性并不也无法要求每个元素都在队列中因为单调的性质总会淘汰一些元素。
为了维护单调特性 初始化前k个时每个新的元素x被添加到队尾时都要删除掉所有在x之前且比x大的元素滑动窗口移动时添加新元素的时候也执行上述相同的操作取每个滑动窗口的结果时队头元素就是max但是如果它不在滑动窗口的范围内需要不断删除队头元素直到队头元素在当前滑动窗口范围内可以直接在单调队列里存入下标不用存数字下标单调队列是双端队列Deque实现不是Queue 分块预处理 这个方法自己看题解吧就先不实现了 76.最小覆盖子串 遍历长串把所有的字符存到hashmapkey为字符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 结果 接下来就是结合具体的条件了用数组存储当前遍历到的字符串curl,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 0while里的状态更新时先假设l带来的影响当前 l 对其指向字符数量的变化这个字失去这个字符后还能满足覆盖t z中这个字符的条件再进行l 啰嗦了
最后还有一点思考之所以可以不断l到不满足条件是因为l位置一旦是不满足条件了后面的l都不会再满足条件
