Month: July 2017

Description:

https://leetcode.com/problems/unique-paths-ii/#/description

Algorithm:

check obstacle:

• obstacle = 1   dp[i][j] = 0
• obstacle = 0  dp[i][j] = dp[i – 1][j] + dp[i][j – 1]

Code:

class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp = vector<vector<int>>(m, vector<int>(n, 1));
dp[0][0] = (1 - obstacleGrid[0][0]);
for (int i = 1; i < m; i++)
dp[i][0] = (1 - obstacleGrid[i][0]) * dp[i - 1][0];
for (int i = 1; i < n; i++)
dp[0][i] = (1 - obstacleGrid[0][i]) * dp[0][i - 1];
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
dp[i][j] = (1 - obstacleGrid[i][j]) * (dp[i - 1][j] + dp[i][j - 1]);
}
}
return dp[m - 1][n - 1];
}
};


Timing:

best, 3ms

Description:

https://leetcode.com/problems/unique-paths/#/description

Algorithm:

recursion: TLE

Use dp, dp is easy and fast

Code:

class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp = vector<vector<int>>(m, vector<int>(n, 1));
dp[0][0] = 1;
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};

Timing:

best, 0ms

Description:

https://leetcode.com/problems/insert-interval/#/description

Algorithm:

Firstly, I used similar algorithm as I used in 56. Merge Intervals. The code is shown in Code1. The timing is 19ms (beats 26%). So other methods should be tried.

Use the property of ordered and non-overlap. Check one by one:

Use int start and pair to record the new merged interval, initialize start = newInterval.start, end = newInterval.end

• if intervals[i].end<start
  • push back intervals[i]
• if intervals[i].start>end
  • push back newInterval
  • push back intervals[i]
• else
  • push back min(start), max(end)

Code1:

class Solution1 {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> result;
if (intervals.size() == 0)
{
result.push_back(newInterval);
return result;
}
Interval tmp;
map <int, int> mapping;
for (int i = 0; i < intervals.size();i++)
{
mapping[intervals[i].start] = INT_MIN;
}
mapping[newInterval.start] = INT_MIN;
for (int i = 0; i < intervals.size();i++)
{
mapping[intervals[i].start] = max(intervals[i].end, mapping[intervals[i].start]);
}
mapping[newInterval.start] = max(mapping[newInterval.start], newInterval.end);

map<int, int>::iterator it = mapping.begin();
int begin = it->first, end = it->second;
for (it = mapping.begin(); it != mapping.end();it++)
{
if (it->first <= end)
{
end = max(it->second, end);
}
else
{
tmp = Interval(begin, end);
result.push_back(tmp);
begin = it->first;
end = it->second;
}
}
tmp = Interval(begin, end);
result.push_back(tmp);
return result;
}
};

Code2:

class Solution2 {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
int start = newInterval.start, end = newInterval.end;
vector<Interval> res;
int inserted = false;
for (int i = 0;i<intervals.size();i++)
{
if (inserted == false)
{
if (intervals[i].start>end)
{
res.push_back(Interval(start, end));
res.push_back(intervals[i]);
inserted = true;
}
else if (intervals[i].end<start)
{
res.push_back(intervals[i]);
}
else
{
start = min(start, intervals[i].start);
end = max(end, intervals[i].end);
}
}
else
{
res.push_back(intervals[i]);
}
}
if (inserted == false) res.push_back(Interval(start, end));
return res;

}
};

Timing:

O(n)

Timing of the maps: http://blog.csdn.net/wusecaiyun/article/details/46723363

 

Description:

https://leetcode.com/problems/merge-intervals/#/description

Algorithm:

Use [1,3],[2,6],[8,10],[15,18] as example

Firstly use map to take record of the intervals. Remember to initialize the map to INT_MIN and then start recording.

Let mapping->second = max(mapping->second, interval[i].end);

We do this to avoid the situation that the new interval and old interval have the same start so the end of old interval is erased in the mapping. e.g intervals = [ [2,3], [2,2], [5,5] ] . The end of [2,3] is replaced by the end of [2,2]

_-____-____-__________-________-______-________-______-___

 1         2          3                          6                     8              10                   15            18

From the first,  start = 1, end  = 3

The second pair: begin2 = 2 <= end = 3, end = max(end1, end2) = end2 = 6 /*Here it must be  if (it->first <= end)*/

The third pair: begin3 = 8 > end = 6, push back(begin = 1, end = 6) and let begin = begin3 = 8, end = end3 = 10

The fourth pair: begin4 = 15 > end = 10, push back(begin  = 8, end = 10) and let begin = begin4 = 15, end = end4 = 18

The iterator reaches end, push back(begin  = 15, end = 18)

Code:

class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
if (intervals.size() == 0) return{};
vector<Interval> result;
Interval tmp;
map <int, int> mapping;
for (int i = 0; i < intervals.size();i++)
{
mapping[intervals[i].start] = INT_MIN;
}
for (int i = 0; i < intervals.size();i++)
{
mapping[intervals[i].start] = max(intervals[i].end, mapping[intervals[i].start]);
}
map<int, int>::iterator it = mapping.begin();
int begin = it->first, end = it->second;
for (it = mapping.begin(); it != mapping.end();it++)
{
if (it->first <= end)
{
end = max(it->second, end);
}
else
{
tmp = Interval(begin, end);
result.push_back(tmp);
begin = it->first;
end = it->second;
}
}
tmp = Interval(begin, end);
result.push_back(tmp);
return result;
}
};

Timing:

Timing is 12ms(beats 70%), the best is 9ms

The insert of map is O(logn)

The complexity of merging intervals is O(n)