面试10大算法题汇总-字符串和数组5
来源：程序员人生 发布时间：2015-03-17 08:52:49 阅读次数：2743次
7.合并重复区间
给定1组区间，合并其中重复的。例：
给定[1,3],[0,7],[2,6],[8,10],[15,18],其中[1,3]与[0,7]及[2,6]区间有重复，因此将其合并成1个区间：[0,7]。终究返回：
[0,7],[8,10],[15,18].
书上的解法用到了Comparator，其大致思路以下：
1. 创建1个间隔类Interval，其成员变量为start和end，分别表示间隔区间的开始和结束。
2. 创建1个Solution类，其包括merge方法，输入参数intervals及返回值result均为1个Interval类的List，用于表示输入&输出的间隔。merge方法用于合并重复区间：首先将输入的区间List按intervals按其中各interval的start大小从小到大排列。排序后的inatervals为：[0,7],[1,3],[2,6],[8,10],[15,18]。最后创建result，遍历intervals，若遍历进程中存在重复区间，则合并，否则将该interval加入result
3. 返回result
Code：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class test {
public static class Interval {
int start;
int end;
Interval() {
start = 0;
end = 0;
}
Interval(int s, int e) {
start = s;
end = e;
}
public String toString() {
return "start:" + start + ",end:" + end + "
";
}
}
public static class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
if (intervals == null || intervals.size() <= 1)
return intervals;
// sort intervals by using self-defined Comparator
Collections.sort(intervals, new IntervalComparator());
for (Interval t : intervals) {
System.out.println(t);
}
ArrayList<Interval> result = new ArrayList<Interval>();
Interval prev = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (prev.end >= curr.start) {
// merged case
Interval merged = new Interval(prev.start, Math.max(
prev.end, curr.end));
prev = merged;
} else {
result.add(prev);
prev = curr;
}
}
result.add(prev);
return result;
}
}
public static class IntervalComparator implements Comparator<Interval> {
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
}
public static void main(String[] args) {
Solution s = new Solution();
ArrayList<Interval> intervals = new ArrayList<Interval>();
intervals.add(new Interval(1, 3));
intervals.add(new Interval(0, 7));
intervals.add(new Interval(2, 6));
intervals.add(new Interval(8, 10));
intervals.add(new Interval(15, 18));
ArrayList<Interval> temp = new ArrayList<Interval>();
temp = s.merge(intervals);
for (Interval t : temp) {
System.out.println(t);
}
}
}
8.插入间隔
实例1：
原间隔List：[1,3],[6,9]
插入间隔：[2,5]
终究结果：由于[2,5]与[1,3]有重复，因此输出结果为[1,5],[6,9].
实例2：
原间隔List：[1,2],[3,5],[6,7],[8,10],[12,16]
插入间隔：[4,9]
终究结果：由于[4,9]与[3,5],[6,7],[8,10] 有重复，因此输出结果为[1,2],[3,10],[12,16]
这个和上1次差不多
Code：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class test {
public static class Interval {
int start;
int end;
Interval() {
start = 0;
end = 0;
}
Interval(int s, int e) {
start = s;
end = e;
}
public String toString() {
return "start:" + start + ",end:" + end + "
";
}
}
public static class Solution {
public ArrayList<Interval> insert(ArrayList<Interval> intervals,
Interval newInterval) {
ArrayList<Interval> result = new ArrayList<Interval>();
for (Interval interval : intervals) {
if (interval.end < newInterval.start) {
result.add(interval);
} else if (interval.start > newInterval.end) {
result.add(newInterval);
newInterval = interval;
} else if (interval.end >= newInterval.start
|| interval.start <= newInterval.end) {
newInterval = new Interval(Math.min(interval.start,
newInterval.start), Math.max(newInterval.end,
interval.end));
}
}
result.add(newInterval);
return result;
}
}
public static void main(String[] args) {
Solution s = new Solution();
ArrayList<Interval> intervals = new ArrayList<Interval>();
intervals.add(new Interval(1, 3));
intervals.add(new Interval(6, 9));
ArrayList<Interval> temp = new ArrayList<Interval>();
temp = s.insert(intervals, new Interval(2, 5));
for (Interval t : temp) {
System.out.println(t);
}
}
}
9.两数字之和
给定1个数组numbers及1个target，要求返回index1和index2，使得numbers[index⑴]+numbers[index2⑴]== target ，其中index1 <index2
例：
输入：数组numbers={2,7, 11, 15}, target=9
输出：index1=1,index2=2
解法1：
首先想到的最简单的方法就是穷举。
Code：
public class test {
public static void getResult(int[] numbers, int target) {
int len = numbers.length;
int i = 0, j = 0;
for (i = 0; i < len; ++i)
for (j = i + 1; j < len; ++j)
if (numbers[i] + numbers[j] == target) {
++i;
++j;
String str = (i > j ? ("index1:" + j + ",index2:" + i)
: ("index1:" + i + ",index2:" + j));
System.out.println(str);
}
}
public static void main(String[] args) {
int[] numbers = { 2, 7, 11, 15 };
getResult(numbers, 9);
}
}
解法2：用HashMap。其中key的意思为还需加多少和才能为taget，value代表该值在数组中的位置。即numbers[value] + key ==target。这么说比较乱，继续看例子：
数组numbers={2,7, 11, 15}, target=9
解法：1.新建HashMap；2.遍历numbers；3.若map的key中有numbers的值，则表明找到了。
Code：
import java.util.HashMap;
public class test {
public static class Solution {
public static int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] result = new int[2];
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(numbers[i])) {
int index = map.get(numbers[i]);
result[0] = index + 1;
result[1] = i + 1;
break;
} else {
map.put(target - numbers[i], i);
}
}
return result;
}
}
public static void main(String[] args) {
int[] numbers = { 2, 7, 11, 15 };
int[] result = Solution.twoSum(numbers, 9);
System.out.println("index1:" + result[0] + ",index2:" + result[1]);
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
