>

Leetcode - Meeting Rooms II

- 编辑:正版管家婆马报彩图 -

Leetcode - Meeting Rooms II

图片 1Screenshot from 2016-02-27 23:23:55.png

图片 2Paste_Image.png

My code:

My code:

/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */public class Solution { public int minMeetingRooms(Interval[] intervals) { if (intervals == null || intervals.length == 0) return 0; int[] starter = new int[intervals.length]; int[] ender = new int[intervals.length]; for (int i = 0; i < intervals.length; i++) { starter[i] = intervals[i].start; ender[i] = intervals[i].end; }= Arrays.sort; Arrays.sort; int endPoint = 0; int counter = 0; for (int i = 0; i < intervals.length; i++) { if (starter[i] < ender[endPoint]) { counter++; } else { endPoint++; } } return counter; }}
public class Solution { public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) return false; return search(0, nums.length - 1, nums, target); } private boolean search(int begin, int end, int[] nums, int target) { if (begin > end) return false; else { int mid = (begin + end) / 2; if (nums[mid] > nums[end]) { // left is sorted if (nums[mid] < target) { int i = mid + 1; while (i <= end && nums[i] == nums[i - 1]) i++; if (i >= nums.length) return false; else return search(i, end, nums, target); } else if (nums[mid] > target) { if (nums[begin] > target) { // in the right int i = mid + 1; while (i <= end && nums[i] == nums[i - 1]) i++; if (i >= nums.length) return false; else return search(i, end, nums, target); } else if (nums[begin] == target) return true; else { // in the left int i = mid - 1; while (i >= begin && nums[i] == nums[i + 1]) i--; if  return false; else return search(begin + 1, i, nums, target); } } else return true; } else if (nums[mid] < nums[end]) { // right is sorted if (nums[mid] > target) { int i = mid - 1; while (i >= begin && nums[i] == nums[i + 1]) i--; if  return false; else return search(begin, i, nums, target); } else if (nums[mid] < target) { if (target < nums[end]) { int i = mid + 1; while (i <= end && nums[i] == nums[i - 1]) i++; if (i >= nums.length) return false; else return search(i, end, nums, target); } else if (target > nums[end]) { int i = mid - 1; while (i >= begin && nums[i] == nums[i + 1]) i--; if  return false; else return search(begin, i, nums, target); } else return true; } else return true; } else if (nums[mid] == target) return true; else return search(begin, end - 1, nums, target); } }}

这个方法比较巧,直接看的答案。解释下,为什么 start[i] >= end[ep] 时,为什么endPointer++, i 也需要 ++因为这个时候,start > end,那么,时间上是独立的,不需要新开一间房。于是,start跟end都往后移动一格,这个时候再开始算,如果有重复的,再给room加上去。

My test result:

参考网页:

图片 3

还有一个 O的做法,参考网页是:

这道题目还是和前面的差不多。然后就是要用while循环把重复的数字跳到。然后就是同样的注意点,当nums[mid] = nums[end] 时,可能出现两种情况,右侧已经排序好或者左侧已经排序好。所以不能确定。于是,就直接将end

Anyway, Good luck, Richardo!

  • 1,重新进行搜索。所以,如果数组数字都是一样的,需要进行 O复杂度,而不再是之前的binary search 的 O

My code:

**总结: Array, binary search**

/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */public class Solution { public int minMeetingRooms(Interval[] intervals) { if (intervals == null || intervals.length == 0) { return 0; } int[] start = new int[intervals.length]; int[] end = new int[intervals.length]; for (int i = 0; i < intervals.length; i++) { start[i] = intervals[i].start; end[i] = intervals[i].end; } Arrays.sort; Arrays.sort; int counter = 0; int endLocation = 0; for (int i = 0; i < start.length; i++) { if (start[i] < end[endLocation]) { counter++; } else { endLocation++; } } return counter; }}

Anyway, Good luck, Richardo!

还是看了以前的答案做出来的。很巧妙。

My code:

先把start, end 都排序。然后如果start >= end,那么说明,start这一个会议,可以和end那一组会议公用一个会议室。然后,这个会议室的结束时间就不再是现在的end了。而要往后延。如果 start < end, 那么必须开一个会议室,counter++

public class Solution { public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) return false; int begin = 0; int end = nums.length - 1; while (begin <= end) { int middle = (begin + end) / 2; if (nums[middle] < nums[end]) { // right part is sorted if (target < nums[middle]) { end = middle - 1; } else if (target == nums[middle]) { return true; } else if (target <= nums[end]) { begin = middle + 1; } else { end = middle - 1; } } else if (nums[middle] > nums[end]) { // left part is sorted if (target > nums[middle]) { begin = middle + 1; } else if (target == nums[middle]) { return true; } else if (target >= nums[0]) { end = middle - 1; } else { begin = middle + 1; } } else { if (target == nums[middle]) return true; else end = end - 1; } } return false; }}

Anyway, Good luck, Richardo! -- 09/15/2016

差不多的题目。就把之前的情况细分。nums[middle] < nums[end]nums[middle] > nums[end]nums[middle] == nums[end] -> end - 1差不多。然后因为出现了重复元素所以可以滑动,用while循环加速。但是我懒得写了。第一次的版本是写了的。

Anyway, Good luck, Richardo!

提供一种新的思路就是直接traverse, 复杂度是 O上面的做法, time complexity: best: O, worst: O

Anyway, Good luck, Richardo! -- 08/12/2016

My code:

public class Solution { public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) { return false; } int begin = 0; int end = nums.length - 1; while (begin <= end) { int mid = begin + (end - begin) / 2; if (target == nums[mid]) { return true; } else if (nums[begin] < nums[mid]) { // left is sorted if (nums[begin] <= target && target < nums[mid]) { end = mid - 1; } else { begin = mid + 1; } } else if (nums[begin] > nums[mid]) { // right is sorted if (nums[mid] < target && target <= nums[end]) { begin = mid + 1; } else { end = mid - 1; } } else { begin++; } } return false; }}

reference:

much simpler code

首先判断,左右那个部分是 sorted ,然后再进行下一步。

Anyway, Good luck, Richardo! -- 09/21/2016

本文由编程应用发布,转载请注明来源:Leetcode - Meeting Rooms II