add a solution for 2080

fishercoder1534 · fishercoder1534 · commit ca5b470529da · 2021-11-21T14:45:40.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_2080.java b/src/main/java/com/fishercoder/solutions/_2080.java
@@ -35,4 +35,31 @@ public int query(int left, int right, int value) {
             }
         }
     }
+
+    public static class Solution2 {
+        public static class RangeFreqQuery {
+            Map<Integer, TreeMap<Integer, Integer>> map;
+
+            public RangeFreqQuery(int[] arr) {
+                map = new HashMap<>();
+                for (int i = 0; i < arr.length; i++) {
+                    map.putIfAbsent(arr[i], new TreeMap<>());
+                    map.get(arr[i]).put(i, map.get(arr[i]).size());
+                }
+            }
+
+            public int query(int left, int right, int value) {
+                if (!map.containsKey(value)) {
+                    return 0;
+                }
+                TreeMap<Integer, Integer> indexMap = map.get(value);
+                Integer start = indexMap.ceilingKey(left);
+                Integer end = indexMap.floorKey(right);
+                if (start == null || end == null) {
+                    return 0;
+                }
+                return indexMap.get(end) - indexMap.get(start) + 1;
+            }
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_2080Test.java b/src/test/java/com/fishercoder/_2080Test.java
@@ -6,32 +6,50 @@
 import static org.junit.Assert.assertEquals;
 
 public class _2080Test {
-    private static _2080.Solution1.RangeFreqQuery rangeFreqQuery;
+    private static _2080.Solution1.RangeFreqQuery rangeFreqQuery1;
+    private static _2080.Solution2.RangeFreqQuery rangeFreqQuery2;
 
     @Test
     public void test1() {
-        rangeFreqQuery = new _2080.Solution1.RangeFreqQuery(new int[]{12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56});
-        assertEquals(1, rangeFreqQuery.query(1, 2, 4));
-        assertEquals(2, rangeFreqQuery.query(0, 11, 33));
+        rangeFreqQuery1 = new _2080.Solution1.RangeFreqQuery(new int[]{12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56});
+        assertEquals(1, rangeFreqQuery1.query(1, 2, 4));
+        assertEquals(2, rangeFreqQuery1.query(0, 11, 33));
+
+        rangeFreqQuery2 = new _2080.Solution2.RangeFreqQuery(new int[]{12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56});
+        assertEquals(1, rangeFreqQuery2.query(1, 2, 4));
+        assertEquals(2, rangeFreqQuery2.query(0, 11, 33));
     }
 
     @Test
     public void test2() {
-        rangeFreqQuery = new _2080.Solution1.RangeFreqQuery(new int[]{1, 1, 1, 2, 2});
-        assertEquals(0, rangeFreqQuery.query(0, 1, 2));
-        assertEquals(3, rangeFreqQuery.query(0, 2, 1));
-        assertEquals(1, rangeFreqQuery.query(3, 3, 2));
-        assertEquals(1, rangeFreqQuery.query(2, 2, 1));
+        rangeFreqQuery1 = new _2080.Solution1.RangeFreqQuery(new int[]{1, 1, 1, 2, 2});
+        assertEquals(0, rangeFreqQuery1.query(0, 1, 2));
+        assertEquals(3, rangeFreqQuery1.query(0, 2, 1));
+        assertEquals(1, rangeFreqQuery1.query(3, 3, 2));
+        assertEquals(1, rangeFreqQuery1.query(2, 2, 1));
+
+        rangeFreqQuery2 = new _2080.Solution2.RangeFreqQuery(new int[]{1, 1, 1, 2, 2});
+        assertEquals(0, rangeFreqQuery2.query(0, 1, 2));
+        assertEquals(3, rangeFreqQuery2.query(0, 2, 1));
+        assertEquals(1, rangeFreqQuery2.query(3, 3, 2));
+        assertEquals(1, rangeFreqQuery2.query(2, 2, 1));
     }
 
     @Test
     public void test3() {
-        rangeFreqQuery = new _2080.Solution1.RangeFreqQuery(new int[]{3, 4, 5, 3, 3, 2, 2, 2, 5, 4});
-//        assertEquals(2, rangeFreqQuery.query(2, 6, 3));
-//        assertEquals(0, rangeFreqQuery.query(5, 6, 5));
-//        assertEquals(2, rangeFreqQuery.query(1, 6, 2));
-        assertEquals(1, rangeFreqQuery.query(0, 2, 3));
-        assertEquals(0, rangeFreqQuery.query(5, 6, 4));
+        rangeFreqQuery1 = new _2080.Solution1.RangeFreqQuery(new int[]{3, 4, 5, 3, 3, 2, 2, 2, 5, 4});
+        assertEquals(2, rangeFreqQuery1.query(2, 6, 3));
+        assertEquals(0, rangeFreqQuery1.query(5, 6, 5));
+        assertEquals(2, rangeFreqQuery1.query(1, 6, 2));
+        assertEquals(1, rangeFreqQuery1.query(0, 2, 3));
+        assertEquals(0, rangeFreqQuery1.query(5, 6, 4));
+
+        rangeFreqQuery2 = new _2080.Solution2.RangeFreqQuery(new int[]{3, 4, 5, 3, 3, 2, 2, 2, 5, 4});
+        assertEquals(2, rangeFreqQuery2.query(2, 6, 3));
+        assertEquals(0, rangeFreqQuery2.query(5, 6, 5));
+        assertEquals(2, rangeFreqQuery2.query(1, 6, 2));
+        assertEquals(1, rangeFreqQuery2.query(0, 2, 3));
+        assertEquals(0, rangeFreqQuery2.query(5, 6, 4));
     }
 
 }
