面試10大算法題匯總-字符串和數組5
來源：程序員人生 發布時間：2015-03-17 08:52:49 閱讀次數：2937次
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]);
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
