Java是一種面向對象的編程語言,它可以輕松地實現求區間的交集和并集。區間交集和并集是計算機科學中的一種重要問題,通常用來解決有關時間、距離、空間等方面的問題。
下面是Java中實現求區間交集和并集的代碼。
public class Interval { public int start; public int end; public Interval() { start = 0; end = 0; } public Interval(int s, int e) { start = s; end = e; } } public class Solution { public ListintervalIntersection(List A, List B) { int i = 0, j = 0; List res = new ArrayList<>(); while (i< A.size() && j< B.size()) { Interval a = A.get(i), b = B.get(j); int startMax = Math.max(a.start, b.start); int endMin = Math.min(a.end, b.end); if (startMax<= endMin) { res.add(new Interval(startMax, endMin)); } if (a.end< b.end) { i++; } else { j++; } } return res; } public List intervalUnion(List A, List B) { List res = new ArrayList<>(); A.addAll(B); Collections.sort(A, (o1, o2) ->o1.start - o2.start); int i = 0; while (i< A.size()) { int start = A.get(i).start; int end = A.get(i).end; while (i + 1< A.size() && end >= A.get(i + 1).start) { end = Math.max(end, A.get(i + 1).end); i++; } res.add(new Interval(start, end)); i++; } return res; } }
以上代碼中,intervalIntersection方法用于求區間的交集,而intervalUnion方法用于求區間的并集。這兩個方法接收兩個參數,分別代表要求交集和并集的兩個區間列表。
在intervalIntersection方法中,我們使用雙指針來遍歷兩個區間列表,并計算區間的交集。具體來說,我們維護兩個指針i和j,分別指向列表A和B中的區間。然后,我們比較A[i]和B[j]的起點和終點,并計算它們的交集。如果交集存在,就將其加入到結果列表中。最后,我們移動指針i或j,使其指向下一個區間。 而在intervalUnion方法中,我們首先將兩個區間列表合并成一個列表。然后,我們對該列表按照起點進行排序。接下來,我們維護一個指針i,用于遍歷該列表,并計算區間的并集。具體來說,我們從第一個區間開始,依次計算它和后面各個區間的并集,直到找到一個沒有重疊的區間為止。然后,我們將計算出的區間加入到結果列表中。最后,我們移動指針i,重復以上步驟直至所有區間都被遍歷完畢。
下一篇css交互動效代碼