专栏简介
上一个专栏，《竞赛算法速成日记》是我为了应对大一下所到来的蓝桥杯国赛和CSP认证所临时准备所学习的算法思想，只能说是提高了广度，并没有学到精髓，在竞赛中发挥的作用并不大（蓝桥杯PyB组喜提国三，CSP认证喜提前60%）。所以，我认为确实有必要系统的，多投入一些时间去学习算法的一整套体系，来应对后面更重要的工作面试。
总体学习路线，我是参照灵茶山艾府大神的这篇文章：分享｜如何科学刷题？
我从文章中扒了一张图，大体就是这样：
算法的知识面是非常广的，我也不奢求完美完成每一个模块。我力求在1年内把所有基础的题目都做完，并且每做完一个板块，就来这里更新我自认为这一块知识点的精髓内容(如果我半个月没有更新，欢迎催更~)。当然这最主要的是为了加深我自己的理解，如果能顺带帮到你，那就更好了。
所以，总结一下，这个专栏，《算法笔记》，就是我为了总结消化我所学习到的算法知识，顺带还能帮助到你一点的一个专栏。下面开始正文内容。
1.滑动窗口 250704
1.1.定长滑动窗口
最初的样子
滑动窗口这个算法，算是我第一次打开leetcode刷题时就有接触到的算法了，当时也是把我狠狠震撼到了。
我之前学习到的滑动窗口是这样的：给定一个字符串和一个子串，求该子串在该字符串中出现的次数(重叠也算)，如果不存在请输出-1。
当时反正是拿双指针折腾了半天，结果最后还超时了，整了个O(n^2)的复杂度。其实正确的做法是，只需要一个指针，然后不断的按照该子串的长度，在字符串中从前到后切片，不断对比这个切片和给定子串，如果相等，则次数加一。这就像我在字符串中画了一片固定大小的区域，把它慢慢往后移动，就像滑动的窗户一样。这样就能以O(n)的时间复杂度完成这道题目。
这是它最初的样子，让人看到恍然大悟，且一秒钟就能理解。
但是现在，它又不一样了。
现在的版本
先看题：定长子串中元音的最大数目
我的第一版本的做法就和上面一致：直接滑窗，然后傻傻的又开了一个循环数里面元音的个数。
毫无意外，O(n^2)的复杂度，超时了。
百思不得其解，我去看题解，发现我已经落后于时代。现在的做法是这样的：
将滑动的窗户看成一个队列，当窗户向后滑一格时，把出去的那一格元素认为是出队；相反，滑进来的那一格元素认为是入队。如果出队的那一格元素是元音，那就将窗户当前的元音数量减一；如果进来的那一格元素是元音，那就把窗户当前的元音数量加一。因为窗户在滑动的过程中，除了出去的元素和进来的元素，其他元素都待在窗户里面，和上一次一样，都属于这个窗户，所以不需要去管它们的状态。当然，第一次进入循环的时候，还是得老老实实数元音的个数，不过就这一次，窗户向后滑之后，就只需要用上面的方法，管进来的和出去的就行了。最后时间复杂度O(n)，轻松解决。
这个做法是非常通用的，如果具备一定的应变能力(到底啥是应变能力，你下面就知道了)，它能解决90%的定长滑窗题目(计数或者求和等)。
奉上我的AC代码(最近在重温go语言，所以用go写的，当C语言看就行了，一样的)：
func isYuan(b byte) bool {//判断是否是元音的函数
return b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u'
}
func maxVowels(s string, k int) int {
maxCnt := 0//维护一个最大元音个数的计数器
cnt := 0//维护一个当前元音个数的计数器
for i := 0; i <= len(s)-k; i++ {
ns := s[i : i+k]//切片，切出窗户
if i == 0 { //计算第一个窗口的元音个数
cnt = 0
for j := 0; j < k; j++ {
if isYuan(ns[j]) {
cnt++
}
}
} else {
if isYuan(s[i-1]) { //如果出去的是元音
cnt-- //当前元音个数减一
}
if isYuan(s[i+k-1]) { //如果进来的是元音
cnt++ //当前元音个数加一
}
}
maxCnt = max(maxCnt, cnt)//维护一个最大元音个数
}
return maxCnt
}还能配合哈希使用
先看题：几乎唯一子数组的最大和
我先说人话翻译一下这个题目：滑窗，如果这个窗户内的元素种类>=m，那就求它的和，然后找所有满足这个条件的窗户内的和的最大值。
有什么东西能够自动去重，并且能够快速查询想要的元素？那就是哈希。在各类编程语言中，都有相对应的使用了哈希的容器。Python是字典(dict)和集合(set)，cpp和go中是映射(map)。
将数据以哈希的形式存放，查询它是否存在、查询它对应键值对的值、删除它等操作的时间复杂度平均下来都是O(1)，非常快。
在这道题目中，我们继续套用上面的滑窗逻辑，将它和map相结合：
map容器的长度就是元素种类的个数，因为是键值对，还能顺带统计每个种类元素的数量。
对于出窗户的元素，将它在map中的值减一，如果已经是1，那就将它从map中删除；对于入窗户的元素，如果已经存在于map中，那就将它在map中的值加一，如果不存在，就用该元素创建一个键，指向1。这样我们就完成了在滑窗时，哈希的处理。
题目还要求我们求和，那只需要我们用上面的老方法一直维护一个和就行了。当map的长度达到要求，说明这个窗户的和有资格参加最大和的竞争，此时才去拿他和一个一直在维护的最大和去比较。
这样跑下来，时间复杂度O(n)，完美过所有数据。
Talk is cheap, show you my code:
func maxSum(nums []int, m int, k int) int64 {
hash := make(map[int]int)//用于统计元素种类和各种类元素数量的哈希容器，并且具备自动去重功能
var maxxSum, curSum int64//初始化最大和、当前和
for i := 0; i <= len(nums)-k; i++ {
if i == 0 { //第一次进入，做好初始化工作
for j := 0; j < i+k; j++ {//正常初始化当前和，以及哈希容器
_, ok := hash[nums[j]]//检查该元素是否存在于map容器中
if ok {
hash[nums[j]]++ //如果存在，直接次数加一就行
} else {
hash[nums[j]] = 1 //如果不存在，就创建
}
}
for j := 0; j < i+k; j++ {
curSum += int64(nums[j])//此处正常累加求和
}
} else {
curSum -= int64(nums[i-1])//出窗口，减去出去元素的值
if hash[nums[i-1]] == 1 { //如果该元素次数已经只有一次了
delete(hash, nums[i-1])//直接删掉
} else {//否则次数减一即可
hash[nums[i-1]]--
}
_, ok := hash[nums[i+k-1]] //检查新加入窗口的元素是否在hash内
if ok {//如果在，次数加一
hash[nums[i+k-1]]++
} else {//否则创建
hash[nums[i+k-1]] = 1
}
curSum += int64(nums[i+k-1])//进窗口，加上进来元素的值
}
if len(hash) >= m {//如果map容器的长度，即元素种类的数量达到了m个的要求
maxxSum = max(maxxSum, curSum)//说明该窗户内的元素有资格参与最大和的竞争，维护一个最大和
}
}
return maxxSum
}随机应变这一块
先看题：可获得的最大点数
一看到这个题，我第一反应是用双指针去做(差不多就是在两端放指针，哪边大就取那边)，但是我很快发现了问题，怎么也想不出来。
一看题解，我傻了：这不就是反过来的滑动窗口吗？？？
做法是这样的：
我们要让只能两端取牌的总点数最大，而且能取牌的个数固定，那就是相当于找一个(总长度-取牌个数)长度的滑窗，使这个滑窗的和最小，再用总和减去这个最小的和，相当于剩下的就是最大的。
所以第一步，遍历整套牌，算出总点数。
第二步，用(总长度-取牌个数)长度的窗户正常滑窗，维护出一个最小和。
第三步，用总点数减去这个最小和，得到答案。
代码是这样的，我说的已经很清楚了，就不注释了：
func maxScore(cardPoints []int, k int) int {
minWindowSum := int(10e9)
curSum := 0
//1.先计算出总点数
totalPoints := 0
for i := 0; i < len(cardPoints); i++ {
totalPoints += cardPoints[i]
}
//2.开始滑窗
l := len(cardPoints) - k
for i := 0; i <= k; i++ {
if i == 0 { //初次进入
for j := 0; j < l; j++ {
curSum += cardPoints[j]
}
} else {
curSum -= cardPoints[i-1]
curSum += cardPoints[i+l-1]
}
minWindowSum = min(minWindowSum, curSum)
}
return totalPoints - minWindowSum
}还有一些很阴的题目
看题，我就简单讲讲：爱生气的书店老板
这道题还是有一些弯弯绕的，当然本质逻辑还是那一套滑动窗口。我想了挺久，最后才想出来去同时维护快乐时和生气时的顾客快乐总数，最后也是没看题解做出来了。这里我就直接贴代码了，注释详细一点，就不放文字版的做法了：
func maxSatisfied(customers []int, grumpy []int, minutes int) int {
var maxSum, happySum, normalSum, total, curSum int
//1.先求正常情况下感到满意的顾客人数
for i := 0; i < len(customers); i++ {
if grumpy[i] == 0 {//只有老板不生气时，才加上该时段的顾客人数
total += customers[i]
}
}
//2.然后开始滑窗
for i := 0; i <= len(customers)-minutes; i++ {
if i == 0 { //初次进入
for j := 0; j < minutes; j++ {
happySum += customers[j]//维护一个快乐的和，一直正常累加就行了
if grumpy[j] == 0 {
normalSum += customers[j]//维护正常的和，只有老板不生气时才累加
}
}
} else {
happySum -= customers[i-1]//用正常滑窗方法维护这个和就行了
happySum += customers[i+minutes-1]
if grumpy[i-1] == 0 {//如果出窗户时，老板没生气
normalSum -= customers[i-1]//那么说明我正常的和是加了这个时段的顾客数量的，得把它减去
}
if grumpy[i+minutes-1] == 0 {//同理
normalSum += customers[i+minutes-1]
}
}
curSum = total - normalSum + happySum//正常总和-现在的正常和+把魔法用在此处的顾客和=在当前位置使用魔法的不生气顾客和
maxSum = max(maxSum, curSum)//维护一个最大不生气顾客和
}
return maxSum
}还有一道题，先看题：拆炸弹
这题的弯弯绕稍微少一些，如果一定要说哪里比较阴，那就是循环取元素和边界的判断。前者倒是还好，我一开始就想到将这个密码*2，后者找边界是真的恶心，花了我不少时间，好在只要能过用例，说明边界就找对了。
看代码：
func decrypt(code []int, k int) []int {
doubleCode := append(code, code...)//将密码*2
if k == 0 {//处理k为0的情况
var ret []int
for i := 0; i < len(code); i++ {
ret = append(ret, 0)
}
return ret
}
var st, curSum int
var pwd []int
if k < 0 {//处理k<0的情况
st = len(code) - 1
k = -k
for i := st; i < len(doubleCode)-1; i++ {//找边界后正常滑窗就行了
if i == st { //第一次进入
for j := i - k + 1; j <= i; j++ {
curSum += doubleCode[j]
}
} else {
curSum -= doubleCode[i-k]
curSum += doubleCode[i]
}
pwd = append(pwd, curSum)
}
} else {//处理k>0的情况
st = 1
for i := st; i <= len(code); i++ {//找边界后正常滑窗就行了
if i == st { //第一次进入
for j := i; j < i+k; j++ {
curSum += doubleCode[j]
}
} else {
curSum -= doubleCode[i-1]
curSum += doubleCode[i+k-1]
}
pwd = append(pwd, curSum)
}
}
return pwd
}