Commit43ccd93

committed

add 775

1 parent31064d5 commit43ccd93Copy full SHA for 43ccd93

File tree

+69

-0

lines changed

README.md
src
- main/java/com/fishercoder/solutions
  - _775.java
- test/java/com/fishercoder
  - _775Test.java

+69

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -467,6 +467,7 @@ _If you like this project, please leave me a star._ ★`
`467`	`467`	`\|781\|[Rabbits in Forest](https://leetcode.com/problems/rabbits-in-forest/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_781.java) \|[:tv:](https://youtu.be/leiSa1i-QrI) \|Medium\| HashTable, Math`
`468`	`468`	`\|779\|[K-th Symbol in Grammar](https://leetcode.com/problems/k-th-symbol-in-grammar/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_779.java)\|\|Medium\|`
`469`	`469`	`\|776\|[Split BST](https://leetcode.com/problems/split-bst/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_776.java) \| \|Medium\| Recursion`
	`470`	`+\|775\|[Global and Local Inversions](https://leetcode.com/problems/global-and-local-inversions/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_775.java) \| \|Medium\| Array, Math`
`470`	`471`	`\|771\|[Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_771.java)\|\|Easy\|`
`471`	`472`	`\|769\|[Max Chunks To Make Sorted](https://leetcode.com/problems/max-chunks-to-make-sorted/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_769.java) \| \|Medium\| Array`
`472`	`473`	`\|767\|[Reorganize String](https://leetcode.com/problems/reorganize-string/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_767.java)\|\|Medium\|`

Lines changed: 46 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,46 @@`
	`1`	`+packagecom.fishercoder.solutions;`
	`2`	`+`
	`3`	`+publicclass_775 {`
	`4`	`+/**`
	`5`	`+ * credit: https://leetcode.com/problems/global-and-local-inversions/solution/`
	`6`	`+ */`
	`7`	`+publicstaticclassSolution1 {`
	`8`	`+/**`
	`9`	`+ * 1. a local inversion is also a global inversion;`
	`10`	`+ * 2. we only need to check if a this input has any non-local inversion, i.e. global inversions that are not local inversions`
	`11`	`+ * because local inversion is a subset of global inversions.`
	`12`	`+ * <p>`
	`13`	`+ * This one will result in TLE with a time complexity of O(n^2).`
	`14`	`+ */`
	`15`	`+publicbooleanisIdealPermutation(int[]A) {`
	`16`	`+for (inti =0;i <A.length;i++) {`
	`17`	`+for (intj =i +2;j <A.length;j++) {`
	`18`	`+if (A[i] >A[j]) {`
	`19`	`+returnfalse;`
	`20`	`+ }`
	`21`	`+ }`
	`22`	`+ }`
	`23`	`+returntrue;`
	`24`	`+ }`
	`25`	`+ }`
	`26`	`+`
	`27`	`+publicstaticclassSolution2 {`
	`28`	`+/**`
	`29`	`+ * from the above solution, we can tell that if we can find the minimum of A[j] where j >= i + 2, then we could quickly return false, so two steps:`
	`30`	`+ * 1. remembering minimum`
	`31`	`+ * 2. scanning from right to left`
	`32`	`+ * <p>`
	`33`	`+ * Time: O(n)`
	`34`	`+ */`
	`35`	`+publicbooleanisIdealPermutation(int[]A) {`
	`36`	`+intmin =A.length;`
	`37`	`+for (inti =A.length -1;i >=2;i--) {`
	`38`	`+min =Math.min(min,A[i]);`
	`39`	`+if (A[i -2] >min) {`
	`40`	`+returnfalse;`
	`41`	`+ }`
	`42`	`+ }`
	`43`	`+returntrue;`
	`44`	`+ }`
	`45`	`+ }`
	`46`	`+}`

Lines changed: 22 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,22 @@`
	`1`	`+packagecom.fishercoder;`
	`2`	`+`
	`3`	`+importcom.fishercoder.solutions._775;`
	`4`	`+importorg.junit.BeforeClass;`
	`5`	`+importorg.junit.Test;`
	`6`	`+`
	`7`	`+importstaticorg.junit.Assert.assertEquals;`
	`8`	`+`
	`9`	`+publicclass_775Test {`
	`10`	`+privatestatic_775.Solution1solution1;`
	`11`	`+`
	`12`	`+@BeforeClass`
	`13`	`+publicstaticvoidsetup() {`
	`14`	`+solution1 =new_775.Solution1();`
	`15`	`+ }`
	`16`	`+`
	`17`	`+@Test`
	`18`	`+publicvoidtest1() {`
	`19`	`+assertEquals(true,solution1.isIdealPermutation(newint[]{0,1}));`
	`20`	`+ }`
	`21`	`+`
	`22`	`+}`

Comments

(0)