原文地址: https://leetcode.cn/problems/SsGoHC/solution/c-by-algo-goer-gzym/ Algo-Goer 769 发布于 2022-04-30 来自浙江 题目 剑指 Offer II 074. 合并区间 Medium 合并区间 Medium 区间重叠合并/扫描线相关题 毯子覆盖的最多白色砖块数 Medium (力扣第78场双周赛第三题) 会议室 Easy 会议室 II Medium 我的日程安排表 III Hard 员工空闲时间 Hard 拼车 Medium…

题号 题目 知识点 备注 剑指 Offer II 074 合并区间 排序, 区间合并 区间如何分片 56 合并区间 排序, 区间合并 区间如何分片 57 插入区间 二分找到位置, 然后区间合并 十个二分, 九个错 228 汇总区间 xxx yyy 370 区间加法 xxx yyy 1272 删除区间 xxx yyy 763 划分字母区间 xxx yyy 435 无重叠区间 xxx yyy 436 寻找右区间 xxx yyy 795 区间子数组个数 xxx yyy 986 区间列表的交集 xxx yyy 163 缺失…

容斥原理用于计数 求top K的 $n \log k$ 或者 $O(n)$ 时间复杂度的算法: 堆或者快排思想

https://zhuanlan.zhihu.com/p/126116878 排序算法系列目录说明 冒泡排序（Bubble Sort） 插入排序（Insertion Sort） 希尔排序（Shell Sort） 选择排序（Selection Sort） 快速排序（Quick Sort） 归并排序（Merge Sort） 堆排序（Heap Sort） 计数排序（Counting Sort） 桶排序（Bucket Sort） 基数排序（Radix Sort） 基数排序（RadixSort） 基数排序（Radix sor…

题目来源 169. 多数元素 作者:LeetCode-Solution 链接:https://leetcode.cn/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/ 来源: 力扣 (LeetCode) 著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处. Boyer-Moore 投票算法 思路 如果我们把众数记为 $+1$, 把其他数记为 $−1$, 将它们全部加起来, 显然和大于 $0$, 从结果…

需要善于利用题目, 不要想太多, 比如这个题775. 全局倒置与局部倒置, 题目问题的是给定数组的全局倒置和局部倒置是否一样多? 问得是是否一样多, 并不一定要求出两个各自的数值, 只要能找出二者之间存在差异即可.

https://oi-wiki.org/basic/prefix-sum/ class NumArray { public: vector<int> prefixeSum = vector<int>(10001, 0); NumArray(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; ++i) { prefixeSum[i+1] = prefixeSum[i] + nums[i]; …

KMP 算法是应用了滑动窗口最典型的例子, 但此片文章不以 KMP 算法来做讲解例子, 因为这个算法里面已经容纳了很多前人的处理与思想, 难懂的同时可能自带劝退属性. 数组是一种基本的数据结构, 会写代码的人不会数组操作都不敢出门见人, 但是很多基于数据的操作会浪费大量的时间, 滑动窗口就是为了帮助我们提升效率的一种算法. 滑动窗口模板 // int n = 数组长度; for(int l = 0, r = 0; r < n; ++r) { // 右边滑入窗口; // while(不符合条件) // 左边滑出…

class Solution { public: int countConsistentStrings(string allowed, vector<string>& words) { int mask = 0; for (auto c : allowed) { mask |= 1 << (c - 'a'); } int res = 0; for (auto &&word : words) { int mask1 = 0; for (auto c …

sort 函数可以三个参数也可以两个参数, 必须的头文件 #include < algorithm> 和 using namespace std; 它使用的排序方法是类似于快排的方法, 时间复杂度为 $n\log n$ 两个参数的 sort 默认升序排序 (a>b 说明 a 比 b 大的时候排在 b 的前面) 返回值为 true, 则代表比较的两个数不进行交换, 为 false 则进行交换. 一句话: 符号与规则一致. 想要从小到大的顺序, 则为 < 号, 想要从大到小的规则, 则使用 &g…

最小生成树的应用 最小生成树的应用场景很多, 小到我们要来个欧洲十国游, 怎么规划路径让交通费用最低, 大到国家的电力网, 公路网, 通信网, 怎么规划路径可以让建设成本最低, 学习了最小生成树后, 你就可以通过算法来计算出最佳路径了, 不仅如此, 所有涉及连接网络中所有节点的最优路径问题, 都可以通过最小生成树来处理. 概念 连通图: 在无向图中, 若任意两个顶点 $u$ 与 $v$ 都有路径相通, 则称该无向图为连通图. 强连通图: 在有向图中, 若任意两个顶点 $u$ 与 $v$ 都有路径相通, 则称该有向图…