-
第 73 楼 / webdriver
- 时间: 2014-9-27 23:51S算法问题: Insert Interval
问题描述:
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:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10]. -
-
- 时间: 2014-9-27 23:51算法问题推荐解法来了...
For example 2:
1. compare [1,2] with [4,9], then insert [1,2];
2. merge [3,5] with [4,9], get newInterval = [3,9];
3. merge [6,7] with [3,9], get newInterval = [3,9];
4. merge [8,10] with [3,9], get newInterval = [3,10];
5. compare [12,16] with [3,10], insert newInterval [3,10], then all the remaining intervals...
解法（Java）
代码:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class InsertInterval {
public class IntervalCmp implements Comparator<Interval> {
@Override
public int compare(Interval i1, Interval i2) {
if (i1.start < i2.start) {
return -1;
}
if (i1.start == i2.start && i1.end <= i2.end) {
return -1;
}
return 1;
}
}
public ArrayList<Interval> insert(ArrayList<Interval> intervals,
Interval newInterval) {
intervals.add(newInterval);
Interval[] arr = new Interval[intervals.size()];
intervals.toArray(arr);
Arrays.sort(arr, new IntervalCmp());
intervals.clear();
int start = arr[0].start;
int end = arr[0].end;
for (int i = 1; i < arr.length; i++) {
if (arr[i].start <= end) {
end = Math.max(end, arr[i].end);
} else {
intervals.add(new Interval(start, end));
start = arr[i].start;
end = arr[i].end;
}
}
intervals.add(new Interval(start, end));
return intervals;
}
}
-
-
- 时间: 2014-9-27 23:53算法问题推荐解法来了...
...
解法（Java）
代码:
public class InsertionSortList {
public ListNode insertionSortList(ListNode head) {
ListNode ret = new ListNode(Integer.MIN_VALUE);
ListNode result = ret;
ListNode cur = new ListNode(0);
cur.next = head;
while (cur.next != null) {
while (result.next != null && cur.next.val > result.next.val) {
result = result.next;
}
ListNode tmp = cur.next;
cur.next = cur.next.next;
if (result.next == null) {
result.next = tmp;
tmp.next = null;
} else {
ListNode tmp2 = result.next;
result.next = tmp;
tmp.next = tmp2;
}
result = ret;
}
return result.next;
}
}
-
- 时间: 2014-9-27 23:54
-
- 时间: 2014-9-27 23:54算法问题推荐解法来了...
Buffer the roman numbers.
解法（Java）
代码:
public class IntegertoRoman {
public String intToRoman(int num) {
String a[][] = {
{ "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" },
{ "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" },
{ "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" },
{ "M", "MM", "MMM", "", "", "", "", "", "" } };
String result = "";
int key = 0;
while (num != 0) {
int d = num - num / 10 * 10;
if (d != 0) {
result = a[key][d - 1] + result;
}
num /= 10;
key++;
}
return result;
}
} -
- 时间: 2014-9-27 23:55
-
- 时间: 2014-9-27 23:55算法问题推荐解法来了...
1. dp. O(MN) time & space. 'dp[i][j] == true' means that there is at least one way to construct
the string s3[0...i+j-1] by interleaving s1[0...j-1] and s2[0...i-1].
2. Recursion. Okay for Small but TLE for Large Test data.
解法（Java）
代码:
public class InterleavingString {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length())
return false;
boolean[][] mat = new boolean[s1.length() + 1][s2.length() + 1];
mat[0][0] = true;
for (int i = 1; i <= s1.length(); ++i)
mat[i][0] = mat[i - 1][0] && (s3.charAt(i - 1) == s1.charAt(i - 1));
for (int i = 1; i <= s2.length(); ++i)
mat[0][i] = mat[0][i - 1] && (s3.charAt(i - 1) == s2.charAt(i - 1));
for (int i = 1; i <= s1.length(); ++i)
for (int j = 1; j <= s2.length(); ++j)
mat[i][j] = (mat[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i
+ j - 1))
|| (mat[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i
+ j - 1));
return mat[s1.length()][s2.length()];
}
} -
- 时间: 2014-9-27 23:57
-
- 时间: 2014-9-27 23:57
-
- 时间: 2014-9-27 23:58S算法问题: 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.
For example:
Given array A = [2,3,1,1,4]
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.)
Leetcode Hacking Practice -- Solution in Java Part 1
