Commit223ea6e

committed

add 2080

1 parent4366dd6 commit223ea6eCopy full SHA for 223ea6e

File tree

+76

-0

lines changed

README.md
src
- main/java/com/fishercoder/solutions
  - _2080.java
- test/java/com/fishercoder
  - _2080Test.java

+76

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ ★`
`8`	`8`
`9`	`9`	`\| # \| Title \| Solutions \| Video \| Difficulty \| Tag`
`10`	`10`	`\|-----\|----------------\|---------------\|--------\|-------------\|-------------`
	`11`	`+\|2080\|[Range Frequency Queries](https://leetcode.com/problems/range-frequency-queries/)\|[Java](../master/src/main/java/com/fishercoder/solutions/_2080.java)\|\|Medium\|Array, Binary Seaarch\|`
`11`	`12`	`\|2079\|[Watering Plants](https://leetcode.com/problems/watering-plants/)\|[Java](../master/src/main/java/com/fishercoder/solutions/_2079.java)\|\|Medium\|\|`
`12`	`13`	`\|2078\|[Two Furthest Houses With Different Colors](https://leetcode.com/problems/two-furthest-houses-with-different-colors/)\|[Java](../master/src/main/java/com/fishercoder/solutions/_2078.java)\|\|Easy\|\|`
`13`	`14`	`\|2076\|[Process Restricted Friend Requests](https://leetcode.com/problems/process-restricted-friend-requests/)\|[Java](../master/src/main/java/com/fishercoder/solutions/_2076.java)\|\|Hard\|\|`

Lines changed: 38 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,38 @@`
	`1`	`+packagecom.fishercoder.solutions;`
	`2`	`+`
	`3`	`+importjava.util.*;`
	`4`	`+`
	`5`	`+publicclass_2080 {`
	`6`	`+publicstaticclassSolution1 {`
	`7`	`+`
	`8`	`+publicstaticclassRangeFreqQuery {`
	`9`	`+/**`
	`10`	`+ * This post explains it well: https://leetcode.com/problems/range-frequency-queries/discuss/1589019/Java-or-Binary-Search-or-Log(n)-for-every-query`
	`11`	`+ */`
	`12`	`+`
	`13`	`+Map<Integer,List<Integer>>map;`
	`14`	`+`
	`15`	`+publicRangeFreqQuery(int[]arr) {`
	`16`	`+map =newHashMap<>();`
	`17`	`+for (inti =0;i <arr.length;i++) {`
	`18`	`+List<Integer>list =map.getOrDefault(arr[i],newArrayList<>());`
	`19`	`+list.add(i);`
	`20`	`+map.put(arr[i],list);`
	`21`	`+ }`
	`22`	`+ }`
	`23`	`+`
	`24`	`+publicintquery(intleft,intright,intvalue) {`
	`25`	`+List<Integer>list =map.getOrDefault(value,newArrayList<>());`
	`26`	`+intstart =Collections.binarySearch(list,left);`
	`27`	`+intend =Collections.binarySearch(list,right);`
	`28`	`+if (start <0) {`
	`29`	`+start = (start +1) * -1;`
	`30`	`+ }`
	`31`	`+if (end <0) {`
	`32`	`+end = (end +2) * -1;`
	`33`	`+ }`
	`34`	`+returnend -start +1;`
	`35`	`+ }`
	`36`	`+ }`
	`37`	`+ }`
	`38`	`+}`

Lines changed: 37 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,37 @@`
	`1`	`+packagecom.fishercoder;`
	`2`	`+`
	`3`	`+importcom.fishercoder.solutions._2080;`
	`4`	`+importorg.junit.Test;`
	`5`	`+`
	`6`	`+importstaticorg.junit.Assert.assertEquals;`
	`7`	`+`
	`8`	`+publicclass_2080Test {`
	`9`	`+privatestatic_2080.Solution1.RangeFreqQueryrangeFreqQuery;`
	`10`	`+`
	`11`	`+@Test`
	`12`	`+publicvoidtest1() {`
	`13`	`+rangeFreqQuery =new_2080.Solution1.RangeFreqQuery(newint[]{12,33,4,56,22,2,34,33,22,12,34,56});`
	`14`	`+assertEquals(1,rangeFreqQuery.query(1,2,4));`
	`15`	`+assertEquals(2,rangeFreqQuery.query(0,11,33));`
	`16`	`+ }`
	`17`	`+`
	`18`	`+@Test`
	`19`	`+publicvoidtest2() {`
	`20`	`+rangeFreqQuery =new_2080.Solution1.RangeFreqQuery(newint[]{1,1,1,2,2});`
	`21`	`+assertEquals(0,rangeFreqQuery.query(0,1,2));`
	`22`	`+assertEquals(3,rangeFreqQuery.query(0,2,1));`
	`23`	`+assertEquals(1,rangeFreqQuery.query(3,3,2));`
	`24`	`+assertEquals(1,rangeFreqQuery.query(2,2,1));`
	`25`	`+ }`
	`26`	`+`
	`27`	`+@Test`
	`28`	`+publicvoidtest3() {`
	`29`	`+rangeFreqQuery =new_2080.Solution1.RangeFreqQuery(newint[]{3,4,5,3,3,2,2,2,5,4});`
	`30`	`+// assertEquals(2, rangeFreqQuery.query(2, 6, 3));`
	`31`	`+// assertEquals(0, rangeFreqQuery.query(5, 6, 5));`
	`32`	`+// assertEquals(2, rangeFreqQuery.query(1, 6, 2));`
	`33`	`+assertEquals(1,rangeFreqQuery.query(0,2,3));`
	`34`	`+assertEquals(0,rangeFreqQuery.query(5,6,4));`
	`35`	`+ }`
	`36`	`+`
	`37`	`+}`

Comments

(0)