# 面试10大算法题汇总-字符串和数组5

7.合并重复区间

[0,7],[8,10],[15,18].

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 {
prev = curr;
}
}

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>();

ArrayList<Interval> temp = new ArrayList<Interval>();

temp = s.merge(intervals);
for (Interval t : temp) {
System.out.println(t);
}
}
}

8.插入间隔

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) {
} else if (interval.start > newInterval.end) {
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));
}
}

return result;
}
}

public static void main(String[] args) {
Solution s = new Solution();
ArrayList<Interval> intervals = new ArrayList<Interval>();

ArrayList<Interval> temp = new ArrayList<Interval>();

temp = s.insert(intervals, new Interval(2, 5));
for (Interval t : temp) {
System.out.println(t);
}
}
}

9.两数字之和

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);
}
}

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]);
}
}

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！