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

56. 合并区间

题目描述 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。 https://leetcode-cn.com/problems/merge-intervals/ 解法1 为了便于描述,我们将区间记为interval,左边界记为interval.start, 右边界记为interval.end。我们将区间列表按照start排序,如果区间i与区间j相交,那么有interval[j].start <= interval[i].end(i<j)。 图1与图2绘制了区间合并的两种case,我们已经将区间列表按照start排序好了。图1中区间{1, 3}与{2, 6}相交,第二个区间的end=6大于第一个区间的end = 3,合并后区间为{1, 6}。图2中区间{1, 4}与区间{2, 3}相交,第二个区间的end=3小于第一个区间的end=4,合并后区间为{1, 4}。通过这两个case能够启发我们,如果区间i与区间j合并,那么合并后区间的end应该取二者较大的。 现在我们描述下算法流程,首先将第一个区间加入结果集,结果集是存放合并后区间的容器。然后遍历余下的每个区间(记为currInterval),我们取结果集最后一个区间(记为lastInterval),将currInterval与lastInterval对比,如果存在交集,将currInterval与lastInterval合并,合并后的区间写回lastInterval;如果不存在交集,将currInterval追加到结果集。 目前,leetcode-cn上这道题目的函数签名为“public List merge(List intervals) ”,但是实际上函数签名已经改为“public int[][] merge(int[][] intervals)”。intervals[i][0]代表第i个区间的左边界,intervals[i][1]代表第i个区间的右边界。下面是全部代码,因为涉及到排序,所以时间复杂度O(nlogn),空间复杂度O(n)。

Read more

289. 生命游戏

题目描述 根据百度百科,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。 给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live(1)即为活细胞, 或 dead(0)即为死细胞。每个细胞与其八个相邻位置(水平,垂直,对角线)的细胞都遵循以下四条生存定律: 如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡; 如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活; 如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡; 如果死细胞周围正好有三个活细胞,则该位置死细胞复活; 根据当前状态,写一个函数来计算面板上细胞的下一个(一次更新后的)状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的,其中细胞的出生和死亡是同时发生的。 示例: 输入: [   [0,1,0],   [0,0,1],   [1,1,1],   [0,0,0] ] 输出: [   [0,0,0],   [1,0,1],   [0,1,1],   [0,1,0] ] 进阶: 你可以使用原地算法解决本题吗?请注意,面板上所有格子需要同时被更新:你不能先更新某些格子,然后使用它们的更新后的值再更新其他格子。 本题中,我们使用二维数组来表示面板。原则上,面板是无限的,但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题? 解法1 这道题本身没什么难度,类似于迭代算法,利用i-1轮的输出作为第i轮第输入,但是题目只要求一次更新后的状态,那么我们再开辟一个数组ans[m][n]存储第i轮第状态。因为题目说了不能先更新某些格子,再使用它们更新其他格子。 题目要求8个方向,我们可以定义数组dirI={-1,-1,-1,1,1,1,0,0}与dirJ={-1,0,1,-1,0,1,-1,1},这样可以方便的利用dirI与dirJ将当前坐标(i,j)变换为(i+dirI[k], j+dirJ[k]), 0 <=k<8,来计算8个方向第坐标。 如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡; 如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活; 如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡; 如果死细胞周围正好有三个活细胞,则该位置死细胞复活; 另外需要理清下逻辑,虽然题目给了4个规则,但是他们可以化简成两条: 如果细胞周围有三个活细胞,则该位置的细胞下一次更新存活(无论当前细胞是死是活) 如果活细胞周围有两个活细胞,则该位置的细胞下一次仍存活 全部代码如下,时间复杂度O(m*n),空间复杂度O(m*n)。 解法1优化 题目给了进阶要求,可以使用原地算法吗?矩阵board只用了0,1来表示该位置细胞的死活,但却用int型存储,这就浪费了31…

Read more

315.计算右侧小于当前元素的个数

题目描述 给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。 示例: 输入: [5,2,6,1] 输出: [2,1,1,0] 解释: 5 的右侧有 2 个更小的元素 (2 和 1). 2 的右侧仅有 1 个更小的元素 (1). 6 的右侧有 1 个更小的元素 (1). 1 的右侧有 0 个更小的元素. https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/ 解法1 解法1采用Merge sort。之所以采用Sort是因为第i个数右边小于nums[i]的数字在排序后都会跑到nums[i]的左边,我们只需要在排序的过程中跟踪那些从nums[i]右边跑到nums[i]左边元素的个数,就能够求得答案。 我们举例nums = [5,4,3,1],解释使用Merge sort计算计算过程。 在执行Merge sort过程中,Sort([5, 4, 3, 1])会被拆分为{Sort([5, 4]), Sort([3, 1])},然后Sort([5, 4])又会被拆分为{Sort([5]), Sort([4])}。当发现对独立的元素排序(如Sort([5])),它自然是有序的,将不会执行任何操作直接返回。为了简化图1,我并没有绘制对于单个元素sort的调用过程。 当Sort([5])与Sort([4])返回后,将两个有序的列表[5]与[4]进行Merge。而在Merge的过程中,我们就可以“跟踪”那些从num[i]后面跑到num[i]前面的元素个数,这也正是我们要求的counts[i]。 需要注意,我们对nums直接排序会破坏nums的顺序,而题目要求我们按照nums原有的顺序输出到counts。为了不破坏nums,我们不能对nums排序,而是使用索引数组originIndices记录nums元素对应的索引,我们将nums的索引排序。 排序前nums = [5, 4, 3, 1]originIndices…

Read more

321. 拼接最大数

题目描述 给定长度分别为 m 和 n 的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。 说明: 请尽可能地优化你算法的时间和空间复杂度。 示例 1: 输入: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 输出: [9, 8, 6, 5, 3] 示例 2: 输入: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 输出: [6, 7, 6, 0, 4]…

Read more

4. 寻找两个有序数组的中位数

题目描述 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/ 解法1 解法1使用Binary Search。考虑两个排序数组nums1与nums2,合并后后形成有序数组nums。记|nums1| = n1, |nums2| = n2, |nums| = n, 有n = n1 + n2。对nums求中位数,那么需要取nums的第k个数(n是奇数)或与第k+1个数取平均(n是偶数),其中k =…

Read more

287. 寻找重复数

题目描述 给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。 示例 1: 输入: [1,3,4,2,2] 输出: 2 示例 2: 输入: [3,1,3,4,2] 输出: 3 说明: 不能更改原数组(假设数组是只读的)。 只能使用额外的 O(1) 的空间。 时间复杂度小于 O(n2) 。 数组中只有一个重复的数字,但它可能不止重复出现一次。 https://leetcode-cn.com/problems/find-the-duplicate-number/ 解法1 首先,题目说了不能更改数组、且空间复杂度为O(1),那么我们就不能够使用排序算法。此外,时间复杂度要求小于O(n^2),就不能够使用暴力法(双重循环遍历每个元素)。 题目描述了有n+1个元素,值域为[1, n],这就提示我们:我们可以用数组内容作为数组的索引。例如nums = [1,3,4,2,2]: 索引 0 1 2 3 4内容 1 3 4 2 2从索引为0开始,使用数组内容作为索引遍历:nums[0] = 1nums[1] = 3nums[3] = 2nums[2] = 4nums[4] = 2nums[2]…

Read more

128. 最长连续序列

题目描述 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。 https://leetcode-cn.com/problems/longest-consecutive-sequence/ 解法1 题目要求时间复杂度O(n),那就说明只能扫描一次,排序什么的是不行的。我们可以举个简单的例子,来启发我们寻找合适的算法解决问题。 例1: nums = {1,2,0,5,4,3,-1} 遇到1,那么1独立成一个序列,长度是1; 遇到2,1和2能连在一起成为长度为2的序列{1,2}; 遇到0,那么0可以和刚刚{1,2}的序列成为长度为3的连续序列{0,1,2}; 遇到5,那么5需要独立成一个序列,长度是1; 遇到4,那么5和4能够接上,形成长度为2的序列{4,5}; 遇到3,那么3会将刚刚发现的两个序列{0,1,2}与{4,5}接上,形成{0,1,2,3,4,5},长度为6。 遇到-1,那么-1将会与刚刚形成的序列{0,1,2,3,4,5}连接,形成长度为7的序列{-1,0,1,2,3,4,5} 根据例1,我们可以使用map来记录数字与数字所对应序列的长度。每当添加一个新的数字num,检查num-1与num+1是否存在;如果存在,那么就将左右两部分与新添加的数字num连接起来,形成新的序列。然后更新新序列两端,为新序列的长度。 为什么只需要更新新序列左右两端的值,而不是新序列每一个数字的值?这是因为,序列相联时,只会取端点的值。根据上面的分析,我们能够编写出下面代码。时间复杂度O(n), 空间复杂度O(n)。

Read more