SashkoKlincharov

[Java][АПС] - Love for the Twins (GFG)

Feb 6th, 2020
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.80 KB | None | 0 0
  1. import java.util.Scanner;
  2. import java.util.Hashtable;
  3. import java.util.LinkedHashMap;
  4.  
  5. class CBHT<K extends Comparable<K>, E> {
  6.  
  7. // An object of class CBHT is a closed-bucket hash table, containing
  8. // entries of class MapEntry.
  9. private SLLNode<MapEntry<K,E>>[] buckets;
  10.  
  11. @SuppressWarnings("unchecked")
  12. public CBHT(int m) {
  13. // Construct an empty CBHT with m buckets.
  14. buckets = (SLLNode<MapEntry<K,E>>[]) new SLLNode[m];
  15. }
  16.  
  17. private int hash(K key) {
  18. // Translate key to an index of the array buckets.
  19. return Math.abs(key.hashCode()) % buckets.length;
  20. }
  21.  
  22. public SLLNode<MapEntry<K,E>> search(K targetKey) {
  23. // Find which if any node of this CBHT contains an entry whose key is
  24. // equal
  25. // to targetKey. Return a link to that node (or null if there is none).
  26. int b = hash(targetKey);
  27. for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  28. if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
  29. return curr;
  30. }
  31. return null;
  32. }
  33.  
  34. public void insert(K key, E val) { // Insert the entry <key, val> into this CBHT.
  35. MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  36. int b = hash(key);
  37. for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  38. if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  39. // Make newEntry replace the existing entry ...
  40. curr.element = newEntry;
  41. return;
  42. }
  43. }
  44. // Insert newEntry at the front of the 1WLL in bucket b ...
  45. buckets[b] = new SLLNode<MapEntry<K,E>>(newEntry, buckets[b]);
  46. }
  47.  
  48. public void delete(K key) {
  49. // Delete the entry (if any) whose key is equal to key from this CBHT.
  50. int b = hash(key);
  51. for (SLLNode<MapEntry<K,E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  52. if (key.equals(((MapEntry<K,E>) curr.element).key)) {
  53. if (pred == null)
  54. buckets[b] = curr.succ;
  55. else
  56. pred.succ = curr.succ;
  57. return;
  58. }
  59. }
  60. }
  61.  
  62. public String toString() {
  63. String temp = "";
  64. for (int i = 0; i < buckets.length; i++) {
  65. temp += i + ":";
  66. for (SLLNode<MapEntry<K,E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  67. temp += curr.element.toString() + " ";
  68. }
  69. temp += "\n";
  70. }
  71. return temp;
  72. }
  73.  
  74. }
  75. class SLLNode<E> {
  76. protected E element;
  77. protected SLLNode<E> succ;
  78.  
  79. public SLLNode(E elem, SLLNode<E> succ) {
  80. this.element = elem;
  81. this.succ = succ;
  82. }
  83.  
  84. @Override
  85. public String toString() {
  86. return element.toString();
  87. }
  88. }
  89. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  90.  
  91. // Each MapEntry object is a pair consisting of a key (a Comparable
  92. // object) and a value (an arbitrary object).
  93. K key;
  94. E value;
  95.  
  96. public MapEntry (K key, E val) {
  97. this.key = key;
  98. this.value = val;
  99. }
  100.  
  101. public int compareTo (K that) {
  102. // Compare this map entry to that map entry.
  103. @SuppressWarnings("unchecked")
  104. MapEntry<K,E> other = (MapEntry<K,E>) that;
  105. return this.key.compareTo(other.key);
  106. }
  107.  
  108. public String toString () {
  109. return "<" + key + "," + value + ">";
  110. }
  111. }
  112.  
  113.  
  114. public class GFG {
  115.  
  116. public static void main(String[] args) {
  117. Scanner input = new Scanner(System.in);
  118. int n = input.nextInt();
  119. int zbir = 0;
  120. CBHT<Integer,Integer> hashtable = new CBHT<Integer,Integer>(300);
  121. for(int i=0;i<n;i++) {
  122. zbir = 0;
  123. int t = input.nextInt();
  124. for(int k=0;k<t;k++) {
  125. int prv = input.nextInt();
  126. SLLNode<MapEntry<Integer,Integer>> node = hashtable.search(prv);
  127. if(node!=null) {
  128. int val = node.element.value;
  129. hashtable.insert(node.element.key, ++val);
  130. if(node.element.value%2==0) {
  131. zbir+=2;
  132. }
  133. }
  134. else {
  135. hashtable.insert(prv,1);
  136. }
  137.  
  138. }
  139. System.out.println(zbir);
  140.  
  141. }
  142. }
  143.  
  144. }
Add Comment
Please, Sign In to add comment