Java-一道java英文题

Question

Given a set of intervals - [a0,b0] [a1,b1] [a2,b2] [a3,b3] ......

Let’s assume the first interval [a0,b0] to be set A, and the union of all the rest intervals to be set B. Please write a program to calculate the intersection of A and B.

=============================================================

Ground Rules:

1. All intervals are finite closed intervals, their boundaries are integers. e.g. [2,17] [-9,0]
2. Input: the given intervals are in the format like [3,5] [5,17] [1,6] [-2,0]. intervals are separated by a space, the boundaries are separated by a comma. please note there are no spaces inside the brackets []. The intervals are unordered and may overlap with one another.
3. Output: the intersection should be printed in the same format as the input. when the intersection includes more than one intervals, the intervals must NOT overlap and they should be sorted in ascending order. when the intersection is an empty set, please print empty. If the input is invalid, please print invalid.

====================================================
Sample:
1. input:
[6,27] [5,7] [21,34] [13,25]
output:
[6,7] [13,27]
2. input:
[24,35] [3,20] [-2,9] [37,40]
output:

empty

Answer 1

// 有点小bug，但是整体思路没问题
// 你也可以自己写集合的并和交操作

package main;

import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Tuple {
public int s;
public int e;

public Tuple(int s, int e) {
this.s = s;
this.e = e;
}

public String toString() {
return "[" + s + "," + e + "]";
}
}

public class Intersection {

public static boolean checkFormat(String input) {

String[] intervals = input.split(" ");
String reg = "^\[-?[0-9]\d*\,-?[0-9]\d*\]$";
Pattern pattern = Pattern.compile(reg);
for (String interval : intervals) {
Matcher matcher = pattern.matcher(interval);
if (!matcher.find()) {
return false;
}
}
return true;
}

public static Tuple tranfer(String t) {
String removed = t.substring(1, t.length() - 1);
Tuple tuple = new Tuple(Integer.valueOf(removed.split(",")[0]),
Integer.valueOf(removed.split(",")[1]));
return tuple;
}

public static int[] findBound(List<Tuple> intervals) {

int min = intervals.get(0).s;
int max = intervals.get(0).e;
for (Tuple tuple : intervals) {
if (min > tuple.s) {
min = tuple.s;
}
if (max < tuple.e) {
max = tuple.e;
}
}
int[] bound = new int[2];
bound[0] = min;
bound[1] = max;
return bound;
}

public static String findIntersection(String input) {

// 检查format是否正确
if (!checkFormat(input)) {
return "your input format is not correct";
}

String[] unTranferedIntervals = input.split(" ");
List<Tuple> intervals = new LinkedList<Tuple>();

// 将字符串转换成Tuple对象
for (String unTranferedInterval : unTranferedIntervals) {
intervals.add(tranfer(unTranferedInterval));
}

// 抓到整个结果的上下界
int[] bounds = findBound(intervals);
int[] hitArray = new int[bounds[1] - bounds[0]];

// 属于intervalB的全部标记为1
for (int i = 1; i < intervals.size(); i++) {
for (int j = intervals.get(i).s; j <= intervals.get(i).e; j++) {
hitArray[j - bounds[0] - 1] = 1;
}
}

// 属于intervalA和intervalB的全部标记为2
for (int i = intervals.get(0).s; i <= intervals.get(0).e; i++) {
if (hitArray[i - bounds[0]] == 1) {
hitArray[i - bounds[0]] = 2;
}
}

List<Tuple> result = new ArrayList<Tuple>();
int start = bounds[0];
int end = bounds[1];
boolean hit = false;

// 转换成tuple对象
for (int i = 0; i < hitArray.length; i++) {
if (!hit && hitArray[i] == 2) {
start = i + bounds[0] + 1;
hit = true;
}

if (hit && hitArray[i] < 2) {
end = i + bounds[0] - 1;
result.add(new Tuple(start, end));
hit = false;
}
}

// toString
StringBuffer sb = new StringBuffer();
for (Tuple tuple : result) {
sb.append(tuple.toString() + " ");
}

if (sb.length() > 0) {
return sb.subSequence(0, sb.length() - 1).toString();
} else {
return "empty";
}
}

public static void main(String[] args) {
System.out.println(findIntersection("[-10,20] [10,23] [43,54] [-9,1]"));
}

}

Answer 2

/**
* 2014-7-31
* 功能描述：<解析一道英文题>
* 联系方式：1032176134
* author：summer
*/
public class Test {

public final static Pattern regular_str = Pattern.compile("^\[-?[0-9]\d*\,\d+\]$");
public static Inputint _ainputint; //第一个闭合区间的对象
public static Integer _astart; //output的a_start
public static Integer _bstart; //output的b_start
public static Integer _aend; //output的a_end
public static Integer _bend; //output的b_end

public static boolean isFirstA = true; //用于判断是否第一次获取a_start

/**
* 2014-7-31
* 功能描述：<验证数据格式的正确性>
*/
public static boolean validStr(String varStr){
boolean b = true;
String[] arryStrs = varStr.split(" ");
if(null != arryStrs){
for(int i = 0;i<arryStrs.length;i++){
String arr = arryStrs[i];
if(!matchRegular(regular_str,arr)){
b = false;
break;
}
Inputint inputintstr;
inputintstr = getConvertInt(arr);
if(null == inputintstr){
b = false;
break;
}
else{
if(i==0){
_ainputint = inputintstr;
_astart = _ainputint.getBegin();
_bend = _ainputint.getEnd();
}
else{
if(isFirstA){
if(inputintstr.getEnd() > _astart){
isFirstA = false;
_aend = inputintstr.getEnd();
}
}
else{
if(inputintstr.getEnd() > _astart && inputintstr.getEnd() < _aend){
_aend = inputintstr.getEnd();
}
}

if(null != _aend){
if(_aend < inputintstr.getBegin() && inputintstr.getBegin() < _bend){
_bstart = inputintstr.getBegin();
}
}

}
}

}
}
return b;
}

/**
* 2014-7-31
* 功能描述：<从单个的闭合区间获取开始和结束的整数 ps:[3,27]>
*/
public static Inputint getConvertInt(String str){
Inputint inputint = null;
if(null != str){
String[] arrys = str.split(",");
int start = Integer.parseInt(arrys[0].replace("[", ""));
int end = Integer.parseInt(arrys[1].replace("]", ""));
if(start < end){
inputint = new Inputint();
inputint.setBegin(start);
inputint.setEnd(end);
}
}
return inputint;
}

/**
* 功能描述：<匹配正则>
*
* @param p 正则规则
* @param str 匹配参数 2014年08月01日
*/
public static boolean matchRegular(Pattern p, String str) {
Matcher m = p.matcher(str);
return m.matches();
}

/**
* 2014-8-1
* 功能描述：<打印结果>
*/
private static String printResult(String varStr){
String strResult = "";
if(!validStr(varStr)){
strResult = "字符串格式错误，请检查";
}
else{
if(null != _astart && null != _aend){
strResult = "["+_astart+","+_aend+"] ";
}
if(null != _bstart && null != _bend){
strResult = strResult + "["+_bstart+","+_bend+"]";
}
}

return strResult;
}

/**
* 2014-8-1
* 功能描述：<测试的额主函数>
*/
public static void main(String[] str){
Scanner scanner = new Scanner(System.in);
System.out.println("print you str:");
String varStr = scanner.nextLine();
varStr = varStr.trim();
varStr = printResult(varStr);
System.out.println(varStr);
}

/**
* 2014-7-31
* 功能描述：<内部类存储闭合区间的起始和结束整数>
* 联系方式：1032176134
* author：summer
*/
static class Inputint{
int begin = 0;
int end = 0;

public int getBegin() {
return begin;
}
public void setBegin(int begin) {
this.begin = begin;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}

}
}