每日一题+周赛总结
2023.12
| 周一 | 周二 | 周三 | 周四 | 周五 | 周六 | 周日 |
|---|---|---|---|---|---|---|
| [12.2] 差分数组 | [12.3] 滑动窗口 周赛 |
|||||
12.2
一维差分数组
区域性数字的加减，判断总体是否合法
回忆一下二维差分数组
12.3
前缀和
1423.可获得的最大点数 难度分：1574
逆向思维：滑动窗口 灵神太秀了
最后会剩余n-k个元素，找到剩余和最小的就行了
正向思维：
答案等于如下结果的最大值：
前 k 个数的和。
前 k−1 个数以及后 1个数的和。
前 k−2个数以及后 2 个数的和。
……
前 2个数以及后 k−2个数的和。
前 1个数以及后 k−1个数的和。
后 k个数的和。计算前 k 个数的和，记作 s。初始化答案
ans=s。
从i=1开始枚举到i=k
每次枚举，把 s增加cardPoints[n−i]−cardPoints[k−i]，然后更新ans的最大值
330.按要求补齐数组
374周赛q2总结原因：
tle的原因主要是在表示、更新区间的时候太复杂了，用数组存储，set表示，太复杂抓住精髓，
//初始时，假设可以得到
[0, s] //每次新添加一个数字x，就可以得到
[x+ 0, x+ s] //如果这个新区间 和 已经得到的可以连续上，那么就不用添加数字，否则就是填补上最小的数字
s+1 //如果补充数字i的话，区间就可以得到
[i, 2*i-1]