刷题day4
插入区间
一眼left right二分+合并区间。然后这个合并区间是只有三个区间。然后我就懒得写区间合并，然后就悲剧了
真神了，为什么要模拟，真的是神了，思路出来0s，模拟1h还不对。真不如区间合并板子用一下。就算我过了，不想改了
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 wellorbetter notes！
相关推荐
2026-06-07
刷题
LRU大概思路就是unordered_map hash+双向链表head,tail拿的时候hahsmap key int value node我能直接get拿到这个node，然后把这个node 先remove，然后插到链表头部put的时候，也是，如果有，就修改这个value，然后remove，再insert如果没有，new一个node，然后再看size和cap的关系，如果大于等于，就要先remove这个tail的一个，然后再insert头 class LRUCache {private: int cap; struct Node { int key, value; struct Node* prev; struct Node* next; Node(int key, int value): key(key), value(value) { } }; struct Node* head; struct Node* tail; unordered_map<int, Node*> m...
2026-05-07
刷题day5
最大正方形 个人思路，0s想出思路，二维前缀和+for nm len 遍历 n^3也能过 这里正解是dp，但是我是感觉这个dp理解起来很费解，感觉很难了。他这个dp ij表示的是边长，因为正方形面积实际上是和边长挂边的，但是边长更简单不用开根号。然后这里你表达的是最大的边长，这里来看的话，我理解你可能会由i-1 j-1 i-j&j-1这三个正方形转化而来110110001比如这个，那就是i-1&j-1011011001 这里就是i-1110110001 这里就是j-1但是实际上能走到扩大的只有111111111因为这三实际上是相互影响的。你如果i-1能扩展到i，那意味着，你这个i-1上面必须至少全部都是1，同理j-1,i-1&j-1要拓展过来，你这部分都得是1那很明显，那就是这三的最小值都得满足满1，然后才能+1那这里dpij >= min(这三个)+1那这里dp ij 能不能不止+1 能+2呢？假设这个最小值是m，然后这个如果dpij >= m+2，那这里就会存在m+2，m+2，这个正方形，它这里面能拆出三个m+1那这...
2026-04-22
刷题day3
哎，这个合并区间就是咋说呢，左+右对吧？就反正一个左一定要和一个右配对，那就简单了。反正pair排序，按照first排序之后，这个second来看，如果你这个second能比下一个first大，那就能合并，不然就push非常简单的模拟的思路，nlogn 具体写就sort一下begin end，加一个lambda [](&a, &b)然后就开始写区间，这个区间开头是l，r就0那个左右然后就开始更新，如果在区间内，就更新r，这个r就是当前这个两个r的max也就是当前r和这个r的最大值如果不是合并的，那就更新了，同时push一下然后最后剩下一组，就是更新了的最后一组/没更新的合并的，push没问题。 12345678910111213141516171819202122232425262728class Solution {public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort...
2026-04-21
刷题day2
移除元素给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作： 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。 题意大概意思就是给你一个数组，一个值，返回这个数组去除这个值的顺序数组 解法暴力遍历最简单 然后优化应该就是双指针了。就这样吧，你可以新开一个数组，然后顺序走++，因为你每次++都一定会填入一个你需要的数值然后这个数值的得到是通过原始num数组和val是否相等来的，这个也是顺序++判断的 题解还有个解法没仔细看，叫对撞指针？看不明白就这样吧
2026-05-24
刷题day8
岛屿数量已解答中等相关标签premium lock icon相关企业给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 咋说，比较简单，dfs秒了但是这个也能用并查集做，就差不多吧，反正遍历挨个合并就行了练一下模板吧 123456789101112131415161718const int N = 1e5 + 10;int parent[N], size[N];int find(x) { if (x != parent[x]) parent[x] = find(parent[x]); return parent[x];}int union(int a, int b) { int ra = find(a), rb = find(b); if (size[ra] < size[rb]) { int t = ra; ra = rb...
2026-04-20
刷题day1
题目给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作： 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。 思路这里要我返回这个顺序递增的这个数组，最暴力就是平移+排序然后我的思路是，你后面这个nums2, 他可以二分找到这个要插入的位置，然后这插入的这个位置是一个顺序set对应每个nums2的元素都需要对nums1来进行二分，如果num1 n, nums2 m,那这里复杂度就是mlogn，然后这里我需要对每个插入的这些nums2的这些元素分别来做排序也就是milogmi, sum mi = m; 每个桶大小 mi，排序 O(mi log mi)，总和 O(Σ mi log mi)，其中 Σmi = m由于 Σ mi log mi ≤ m log m（当所有元素集中在一个桶...
