面试10大算法题汇总-字符串和数组5
|
7.合并重复区间 给定1组区间，合并其中重复的。例： 给定[1,3],[0,7],[2,6],[8,10],[15,18],其中[1,3]与[0,7]及[2,6]区间有重复，因此将其合并成1个区间：[0,7]。终究返回： [0,18].
书上的解法用到了Comparator，其大致思路以下： 1. 创建1个间隔类Interval，其成员变量为start和end，分别表示间隔区间的开始和结束。 2. 创建1个Solution类，其包括merge方法，输入参数intervals及返回值result均为1个Interval类的List，用于表示输入&输出的间隔。merge方法用于合并重复区间：首先将输入的区间List按intervals按其中各interval的start大小从小到大排列。排序后的inatervals为：[0,[1,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,[6,9] 插入间隔：[2,5] 终究结果：由于[2,5]与[1,3]有重复，因此输出结果为[1,5],9]. 实例2： 原间隔List：[1,2],[3,[12,16] 插入间隔：[4,9] 终究结果：由于[4,9]与[3,10] 有重复，因此输出结果为[1,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,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,15 };
getResult(numbers,9);
}
}
解法2：用HashMap。其中key的意思为还需加多少和才能为taget，value代表该值在数组中的位置。即numbers[value] + key ==target。这么说比较乱，继续看例子： 数组numbers={2,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,15 };
int[] result = Solution.twoSum(numbers,9);
System.out.println("index1:" + result[0] + ",index2:" + result[1]);
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |