[Leetcode] Meeting Rooms, Solution

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

[Thoughts]
把所有的interval按照开始时间来排序，然后比较相邻的interval是否有重叠即可。

[Code]

1:    bool canAttendMeetings(vector<Interval>& intervals) {  
2:      if(intervals.size() == 0) return true;  
3:      sort(intervals.begin(), intervals.end(), compare);  
4:      for(int i = 0; i< intervals.size() -1; i++) {  
5:        if(intervals[i].end > intervals[i+1].start)  
6:          return false;  
7:      }  
8:      return true;  
9:    }  
10:      
11:    static bool compare(Interval& interval1, Interval& interval2) {  
12:      return interval1.start < interval2.start;  
13:    }  

[Leetcode] Find the Duplicate Number, Solution

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

[Thoughts]

这题想清楚了就不难，想不清楚就麻烦。

假设数组A长度是n, 里面存储1到n的整数，那么很清楚，我们可以在按照A[i] = i+1，进行排序。但是现在有n+1个整数，而且至少有一个数字存在冗余。如果我们仍然按照A[i] = i+1来排序数组的话，那么当发现A[i]上已经是i+1的值时，说明我们已经找到了冗余数了。

举个例子，

简单的说，就是遍历数组的同时，按照A[i]应该放到A[A[i]]原则，进行swap，第一个无法swap的数字就是所求。

[Code]

1:  class Solution {  
2:  public:  
3:    int findDuplicate(vector<int>& nums) {  
4:      int length = nums.size();  
5:      for(int i =0; i< length; i++) {  
6:        if(nums[i] == i+1) {  
7:          continue;  
8:        }  
9:        int oldIndex = i;  
10:        int newIndex = nums[i]-1;  
11:        while(nums[oldIndex] != oldIndex +1 ) {  
12:          if(nums[oldIndex] == nums[newIndex] ) {  
13:            return nums[oldIndex];  
14:          }  
15:          int temp = nums[newIndex];  
16:          nums[newIndex] = nums[oldIndex];  
17:          nums[oldIndex] = temp;  
18:          newIndex = nums[oldIndex] -1;  
19:        }  
20:      }  
21:    }  
22:  };  

github: https://github.com/codingtmd/leetcode/blob/master/src/Find_the_Duplicate_Number.cpp

[LeetCode] First Missing Positive 解题报告

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

» Solve this problem

[解题思路]
其实就是桶排序，只不过不许用额外空间。所以，每次当A[i]!= i的时候，将A[i]与A[A[i]]交换，直到无法交换位置。终止条件是 A[i]== A[A[i]]。
然后i -> 0 到n走一遍就好了。

[Code]

1:   int firstMissingPositive(int A[], int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int i =0;  
5:      for(int i =0; i< n; i++)  
6:      {  
7:        while(A[i] != i+1)  
8:        {        
9:          if(A[i] <= 0 || A[i] >n || A[i] == A[A[i] -1]) break;  
10:          int temp = A[i];  
11:          A[i] = A[temp-1];  
12:          A[temp-1] = temp;          
13:        }  
14:      }  
15:      for(int i =0; i< n; i++)  
16:       if(A[i]!=i+1)  
17:        return i+1;  
18:      return n+1;  
19:    }  

[注意]
题目说清楚了，很简单，但是实现起来还是有些细节比较烦人。首先，不能按照A[i] = i来存，因为题目要求寻找正数，如果A[0]用来存储0的话，会影响数据处理。比如当A = {1}的时候，如果A[0] = 0的话，根本没地方存1的值了。所以正确的存储方式应该是A[i]= i+1.
但是由此带来的是，Line 7, 9, 11, 12, 16, 17都需要更改，以反映出这种映射。
还有一点容易遗忘的就是Line18，如果当前数组找不到目标值的话，那么目标值就应该是n+1.这个容易漏了。