一维差分总结
适用情景如果要对数组的多个区间内的元素进行增减操作，可以考虑使用差分数组进行批量化操作。 思路一般思路差分数组实质上是前缀和数组的逆过程。 如果要对区间[l, r]内的元素加val，先求差分数组diff，diff数组大小为n+2, 可以避免讨论边界条件，其中diff数组内元素为原数组前后两个元素的差。接下来依次按如下过程操作： diff[l+1] +...
求第一个入环的点
基本思路 开始时快指针走两步，慢指针走一步 如果相遇，则找到第一个相遇的点 快指针回到头结点，慢指针原地不动 快慢指针各走一步，这时再相遇的点就是入环节点 链表类型例题LCR 022. 环形链表 II 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 ...
归并分治
思路简要来说，归并分治的思路就是，在归并排序的基础上，统计答案。 具体而言，可以从以下步骤进行考虑： 答案是否可以从左区间、右区间和左跨右区间得到。 排序是否对寻找答案有利。 例题分析翻转对 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的...
向上取整的方法
对一个数进行向上取整，对于cpp来说，可以使用库函数ceil进行取整。对于非负数来说，可以使用下面的方法进行方便的取整。公式如下： (a + b - 1) / b 证明思路如下图所示：