Array Flashcards
- Car Pooling
You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)
Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle’s initial location.
Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.
Example 1:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Example 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Example 3:
Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true
Example 4:
Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true
Constraints:
trips.length <= 1000 trips[i].length == 3 1 <= trips[i][0] <= 100 0 <= trips[i][1] < trips[i][2] <= 1000 1 <= capacity <= 100000
Use dict to store all up and down location. Remember how many people need to add at this location.
Then for loop all position to calculate the passenger at every location.
only use a list to save the location and the people add or minus. The idea is after sorted. The negative people will be at the front. So every location, it will minus first then add.
- First Missing Positive
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
Follow up:
Your algorithm should run in O(n) time and uses constant extra space.
Modify the origin input.
Let the nums[i] put in the index nums[i]-1.
Use swap to keep the origin data.
The for loop again to check which index i doesn't has the value i+1. the answer is i+1.
Trick is use the origin input space.
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in xrange(len(nums)):
while(nums[i] <= len(nums) and nums[i] > 0 and nums[nums[i]-1] != nums[i]):
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in xrange(len(nums)):
if nums[i] - 1 != i: return i+1
return len(nums) + 1
- Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
- loop i
* 思路
i 一格一格走，不斷存最遠能到達的位置。一旦走到之前能到達最遠地方，那就再更新目前能到達最遠地方，並且res += 1
* code
```python
class Solution {
public:
int jump(vector& nums) {
int res = 0, n = nums.size(), last = 0, cur = 0;
for (int i = 0; i < n - 1; ++i) {
cur = max(cur, i + nums[i]);
if (i == last) {
last = cur;
++res;
if (cur >= n - 1) break;
}
}
return res;
}
};
終止條件是最遠位置超過，不段更新最遠位置，記得上次的最遠位置，從這個範圍找出新的最遠位置
* code
```python
class Solution(object):
def jump(self, nums):
“””
:type nums: List[int]
:rtype: int
“””
step ,far, prev_far, i = 0, 0, 0, 0
while far < len(nums) - 1: # use far to know when is reach the end
step += 1
prev_far = far
while i <= prev_far: # use another loop to find the max step
far = max(far, nums[i] + i)
i += 1
return step
~~~
- Merge Intervals
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Example 3:
Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Example 4:
Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]
Example 5:
Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]
Constraints:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 105
intervals is sorted by intervals[i][0] in ascending order.
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 105
分成左半部完全不重疊，右半部完全不重疊，剩下所有有重疊的取[min, max]這樣就merge了
- Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
online
用hash table存出現過的num的長度。如果重複出現的數字就跳過。如果新的數字有鄰居，那麼它的長度就是鄰居邊界的+1，也要update鄰居另一個邊界的值。
offline
先把list變成set，之後用這個來查找。loop nums.找到左邊界。從左邊界開始往下找n+1是否再set裡面，有的話就一值壘加，直到沒有
