נתונה המחלקה Range (טווח), ולה שתי תכונות: low ו-high, המקיימות high ≥ low, עם get/set. מספר x "מוכל" בעצם Range אם low ≤ x ≤ high. שרשרת חוליות lst1 מטיפוס מספר שלם "מוכלת" בשרשרת חוליות lst2 מטיפוס Range אם עבור כל מספר בשרשרת lst1 קיימת חוליה בשרשרת lst2 שמכילה אותו. הנחות: lst1 ו-lst2 אינן null; כל העצמים בשרשרת lst2 אינם null; השרשרת lst1 ממוינת בסדר עולה; השרשרת lst2 ממוינת בסדר עולה, כלומר עבור כל חוליה קטן ה-high שלה מה-low של החוליה הבאה אחריה בשרשרת.
נתונה המחלקה Range (טווח), ולה שתי תכונות: low ו-high, המקיימות high ≥ low, עם get/set. מספר x "מוכל" בעצם Range אם low ≤ x ≤ high. שרשרת חוליות lst1 מטיפוס מספר שלם "מוכלת" בשרשרת חוליות lst2 מטיפוס Range אם עבור כל מספר בשרשרת lst1 קיימת חוליה בשרשרת lst2 שמכילה אותו. הנחות: lst1 ו-lst2 אינן null; כל העצמים בשרשרת lst2 אינם null; השרשרת lst1 ממוינת בסדר עולה; השרשרת lst2 ממוינת בסדר עולה, כלומר עבור כל חוליה קטן ה-high שלה מה-low של החוליה הבאה אחריה בשרשרת.
public class Node<T> {
private T value;
private Node<T> next;
public Node(T value) { this.value = value; this.next = null; }
public T getValue() { return value; }
public void setValue(T value) { this.value = value; }
public Node<T> getNext() { return next; }
public void setNext(Node<T> next) { this.next = next; }
}
public class Range {
private int low;
private int high;
public Range(int low, int high) { this.low = low; this.high = high; }
public int getLow() { return low; }
public void setLow(int low) { this.low = low; }
public int getHigh() { return high; }
public void setHigh(int high) { this.high = high; }
}
שרשרת lst1 המוכלת בשרשרת lst2 (דוגמת השאלון)
lst1: (-9)->(-8)->(-7)->(12)->(14)->(15)->null
lst2: [-20,-10]->[-9,0]->[2,4]->[12,12]->[14,17]->null
ממשו את הפעולה החיצונית שלהלן: הפעולה מחזירה true אם lst1 "מוכלת" ב-lst2, אחרת מחזירה false. הפעולה חייבת לעבוד בסיבוכיות זמן ריצה של O(N), כאשר N הוא אורך השרשרת הארוכה מבין שתי השרשראות.
public static boolean isIncluded (Node<Integer> lst1, Node<Range> lst2)
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.