程序员人生 网站导航

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

栏目:php教程时间:2015-03-17 08:52:49

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





------分隔线----------------------------
------分隔线----------------------------

最新技术推荐