283. 移动零

题目描述 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作,不能拷贝额外的数组。 尽量减少操作次数。 https://leetcode-cn.com/problems/move-zeroes/ 解法1 – 选择排序思想O(n^2) 这道题比较简单,一开始我想的是用选择排序的思想,如果nums[i] == 0,我们就从j = [i+1, |nums|)中找第一个不为0的元素交换到nums[i],然后i++。这种做法是可行的,但是时间复杂度为O(n^2),太蠢了。 解法2 – 双指针O(n) 解法2采用双指针法,首先我们用header指针指向数组第0个元素,然后使用指针i遍历nums数组每个元素,当nums[i] != 0时,我们将nums[i]覆盖到数组头部,即nums[header++] = nums[i]。当i指针遍历到数组末尾,header之前所有的元素都是非0元素,我们将header指向位置之后的所有元素用0填充就是答案。 时间复杂度O(n),空间复杂度O(1)。全部代码如下:

Read more

75. 颜色分类

题目描述 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意:不能使用代码库中的排序函数来解决这道题。 示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶: 一个直观的解决方案是使用计数排序的两趟扫描算法。首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗? https://leetcode-cn.com/problems/sort-colors/ 解法1 – 桶排序 – O(n) 就像题目描述的直观方法那样,我们声明一个长度为3的数组,下标为0,1,2的位置分别记录0、1、2数字出现的次数。第一次扫描填充桶,第二遍扫描从桶里取数,回填到数组中。 时间复杂度O(n),准确的说是O(2*n);空间复杂度O(1)。全部代码如下: 解法2 – Partition函数 – O(n) 记得快速排序的Partition函数吗?找一个pivot,两个指针指向数组两端,调用partition函数使得左边的元素都小于pivot;右边的元素都大于pivot。这里我们借用Partition函数的思想,用3个指针i、j、k。使得[0, i)的元素都是0、(j, |nums|)的元素都是2,而指针k扫描[0, |nums|)。 当k指向的当前元素是0,就把它与i所指的位置交换,然后i++;当k指向的当前元素是2,就把它与j所指的位置交换,然后j–;如果k指向的元素是1,那就k++。需要注意的是边界问题,k需要满足0<=i <=k <=j<|nums|。下面的条件k>=i实际上是限制i,如果我们不限制,就会使得i超越k,导致越界;对于变量j也是同理。 时间复杂度O(n),空间复杂度O(1)。全部代码如下:

Read more

53. 最大子序和

题目描述 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。 https://leetcode-cn.com/problems/maximum-subarray/ 解法1 – 使用DP,O(n) 我们定义一维数组|dp| = |nums|,dp[i]表示必须使用nums[i]元素,得到的连续子数组的最大和。那么有dp[i] = max(nums[i], dp[i – 1] + nums[i])。 解释一下,如果前面累积的最大和是负数,那么使用累积的和与nums[i]相加会使得和更小,我们还不如直接使用nums[i]作为新的连续子数组。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 我们观察到dp[i]只依赖于dp[i-1],因此我们可以使空间复杂度压缩到O(1)。 解法2 – 分治法,O(nlogn) 我们定义函数maxSubArray(nums, l, r),表示区间[l, r]内找到的连续子数组的最大和。那么在区间[l, r]内的连续子数组最大和有3种来源: 来源于[l, m) (m = (l + r) / 2),记为max1; 来源与(m, r],记为max2; 来源于跨中间元素m的区间,记为max3 那么[l, r]区间的连续子数组最大和有max(max1, max2, max3)。其中,第3种情况比较复杂。我们需要从m的左右两侧出发,通过扫描来求和,如图1所示。 我们递归求解区间[l,…

Read more

209. 长度最小的子数组

题目描述 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例:  输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 进阶: 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 https://leetcode-cn.com/problems/minimum-size-subarray-sum/ 解法1 – 朴素算法O(n^2) 解法1使用朴素算法,我们使用指针i, j(0<=i<=j<|nums|)来描述子数组,然后计算i到j区间元素到和,如果大于等于s则取j – i + 1作为可能到解ans;如果小于s则j右移。为了实现O(1)时间复杂度的区间求和,我们可以使用prefix sum算法预先计算前缀和。当指针i和j扫描完所有的连续区间,我们取最小的解就是答案。如果找不到子数组当和大于等与s,就返回0。 需要注意一点,当找到一对i, j我们就可以退出内层循环。因为继续找下去的子序列长度已定大于(i-j+1),否则会TLE。算法的时间复杂度为O(n^2),空间复杂度为O(n) (存放前缀和)。全部代码如下: 解法2 – 优化的朴素算法O(nlogn) 我们沿用解法1的思路,但是对寻找连续区间上进行优化。我们让i = [0, |nums|),使用二分搜索寻找j,其中i <= j < |nums|。因为我们有前缀和数组prefix,我们可以在O(logn)的时间内找到一个下界(lower bound),使得prefix[j] – prefix[i] >= s。那么,j – i +1就是其中一个解,当i遍历完整个数组时,就取最小的那个解作为答案。…

Read more

295. 数据流的中位数

题目描述 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构: void addNum(int num) – 从数据流中添加一个整数到数据结构中。 double findMedian() – 返回目前所有元素的中位数。 示例: addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 进阶: 如果数据流中所有整数都在 0 到 100 范围内,你将如何优化你的算法? 如果数据流中 99% 的整数都在 0 到 100 范围内,你将如何优化你的算法? https://leetcode-cn.com/problems/find-median-from-data-stream/ 解法1 解法1采用朴素算法,我们声明数组List<Integer> nums存放新增的元素。当addNum被调用时,我们向nums合适的位置插入元素使得nums有序。当调用findMedian时,如果数组中有奇数个元素,就返回nums[|nums| / 2];否则返回(nums[|nums| / 2]…

Read more

239. 滑动窗口最大值

题目描述 给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。 返回滑动窗口最大值。 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 ————— —– [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5…

Read more

352. 将数据流变为多个不相交区间

题目描述 给定一个非负整数的数据流输入 a1,a2,…,an,…,将到目前为止看到的数字总结为不相交的区间列表。 例如,假设数据流中的整数为 1,3,7,2,6,…,每次的总结为: [1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7] 进阶:如果有很多合并,并且与数据流的大小相比,不相交区间的数量很小,该怎么办? 提示:特别感谢 @yunhong 提供了本问题和其测试用例。 https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/ 解法1 这道题我们使用TreeMap来解决。TreeMap的底层实现是R-B Tree,它的平衡性很好,对于get、put、remove、contains等操作都能够达到O(logn)的时间复杂度。我们使用的TreeMap的Key为插入操作的值,Value为能够表示插入值的最小区间。例如,我们向map中插入2,用[2,2]能够表示,用[1,3]能够表示,用[-1000,1000]也能够表示,但是我们选择最小的区间[2, 2],这样做能做到题目要求的“目前为止看到的数字总结为不相交的区间列表“。 这里我们还用到了TreeMap提供的两个重要的操作floorEntry与ceilingEntry。floorEntry(k)返回小于等于k的最大元组;ceilingEntry(k)返回大于等于k的最小元组。我们记leftValInterval = map.floorEntry(val),rightValInterval = map.ceilingEntry(val)。 我们将插入的值与区间已有的值的关系分为图1的6种情况。case1、case3、case5表示已有的区间能够表示插入的值,其实case5能够和case1或case3合并。case2与case4表示插入值与已有的区间连续,那么将已有的区间扩大一个单元就能够表示插入值,例如向[1, 3]插入4,向[3, 4]插入2。case6表示如果有了插入值,就能够使得已有的左右区间连续,例如向[1, 4]和[6, 9]插入5。 如果我们清晰的分析出来这些情况,编写代码就不难了。对于新插入的值val,我们首先判断他们在TreeMap中是否存在,如果存在则返回。否则,查询val的floorEntry与ceilingEntry。如果floorEntry的右边界等于val-1,就说明我们可以将val合并到floorEntry对应的区间,将区间扩大,如图1中case2所示。对于ceilingEntry的处理同理,如图1中case4所示。如果floorEntry的右边界等于val-1且ceilingEntry的左边界等于val+1,说明我们将val插入到这两个区间后,能够使得这两个区间连续,如图1中case6所示。如果不满足图1中任何一个case,说明val无法被TreeMap中已有的区间无法表示,我们需要向TreeMap插入新区间[val, val]。 全部代码如下所示,时间复杂度O(nlogn),空间复杂度O(n)。

Read more

919. Meeting Rooms II [LintCode]

题目描述 给定一系列的会议时间间隔intervals,包括起始和结束时间[[s1,e1],[s2,e2],…] (si < ei),找到所需的最小的会议室数量。 样例1 样例2 https://www.lintcode.com/problem/meeting-rooms-ii/description 解法1 这种区间问题可以使用扫描线算法,我们将区间按照时间点排序,如果时间点相同,我们按照终点、起点顺序排序。这是因为在相同时间点上,当上一个会议结束后,该会议室就空出来了,在同一时间点的下一个会议就可以利用这个房间。例如时间段为{[1,5]、[5,10]},其实只需要一个会议室就够了,因为当[1,5]的会议结束后,[5,10]就可以利用这个房间。 图1绘制了扫描线算法的执行流程,实际上我们并不需要按照最细的时间粒度来扫描,我们只需要扫描每个区间的起始点与结束点。因为只有在这些时间点上,需要的房间数量才会发生变化。上面提到过,遇到相同的时间点,我们应当将end排在start前面,因为当上一个会议结束就会空出一个会议室,在这个时间点的下一个会议就可以利用这个房间。 在实现上,我们将起始与终止的时间点用一维数组表示,第0个元素是时间点,第1个元素表示起始还是终止,用0表示end,用1表示start。这样我们可以实现Comparator来排序,首先对比时间点,当时间点相同对比起止。当时间点数组排好序后,我们顺序扫描时间点,用parallel变量表示该时刻需要使用的会议室数量。遇到起始点时parallel++;遇到结束点时parallel–,parallel出现的最大值就是所需的最小会议室数量。 全部代码如下,时间复杂度O(nlogn),空间复杂度O(n)。

Read more

920. Meeting Rooms [LintCode]

题目描述 给定一系列的会议时间间隔,包括起始和结束时间[[s1,e1],[s2,e2],…(si < ei),确定一个人是否可以参加所有会议。 样例1 样例2 https://www.lintcode.com/problem/meeting-rooms/description 解法1 首先把时间段按照起始时间排序,如果存在任意的会议开始于前一个会议结束之前,则这个人无法参加所有回忆。我们将这种情况表示为,当∃ i ∈ [1, |intervals|),使得intervals[i-1].end > intervals[i].start则无法参加所有会议,否则能够参加所有会议。还有一个特殊的case要处理,那就是没有会议时,我们应当将这种情况认定为能够参加所有会议。因为不能参加全部会议只有一个标准,就是下一个会议开始时,上一个会议没有结束;否则就应当认定为能够参加全部会议。 全部代码如下,时间复杂度O(nlogn),空间复杂度O(1)。

Read more

57. 插入区间

题目 给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]] 示例 2: 输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出: [[1,2],[3,10],[12,16]] 解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。 https://leetcode-cn.com/problems/insert-interval/ 解法1 解法1的思路很简单,因为区间无重叠且按照起始点排序,那么我们可以借助56题的方法,先将newInterval插入到合适的位置,然后用56题方法合并区间。合适的位置指的是intervals[i].start <= newInterval.start但intervals[i+1].start > newInterval.start。 题目函数签名为“public int[][] insert(int[][] intervals, int[] newInterval) ”,因为插入新的区间会改变区间个数,使用int[][]不方便实现insert操作,所以我们使用容器List<int[]>来存放区间。题目要求结果存放在int[][]型数组中,我们在输出时还需要将List转换成Array。题目全部代码如下,时间复杂度O(n),空间复杂度O(n)。 解法2 解法2将intervals拆分成3部分,左半部分与newInterval没有交集,右半部分与newInterval没有交集,中间部分是与newInterval有交集的区间。假设前i个intervals中的区间与newInterval没有交集,第i+1个interval与newInterval有交集,我们将这两个区间合并形成[start, end],然后i++寻找下一个区间,直到找到与newInterval不相交的区间为止。此时,我们将合并后的区间[start, end]追加到结果集,然后将intervals中剩余的区间追加到结果集。 我们分析下interval[i]与newInterval不相交,但interval[i+1]与newInterval相交有哪些情况 图1列出了区间相交的集中情况。从图中可以看出,当intervals[i+1]与newInterval合并的时候,我们需要取两者左边界的最小值,右边界的最大值。 在合并的过程中,我们需要判断什么时候终止。如图2所示,终止条件是当newInterval的后沿小于第i+1个区间的前沿,即newInterval.end < intervals[i+1].start。那我们用不用判断newInterval的前沿与第i个区间后沿的关系呢?是不用的!因为前面我们提到,首先寻找与newInterval不相交的区间,加入到结果集,在这个过程中,我们的判断条件就是intervals[i].end < newIntervals.start。当发生合并的时候一定有intervals[i].end >=…

Read more