Commit1d77174

committed

add 1981

1 parentf9a106f commit1d77174Copy full SHA for 1d77174

File tree

+67

-0

lines changed

README.md
src
- main/java/com/fishercoder/solutions
  - _1981.java
- test/java/com/fishercoder
  - _1981Test.java

+67

-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`	`+\|1981\|[Minimize the Difference Between Target and Chosen Elements](https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1981.java)\|\|Medium\|DP\|`
`11`	`12`	`\|1980\|[Find Unique Binary String](https://leetcode.com/problems/find-unique-binary-string/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1980.java)\|\|Medium\|\|`
`12`	`13`	`\|1979\|[Find Greatest Common Divisor of Array](https://leetcode.com/problems/find-greatest-common-divisor-of-array/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1979.java)\|\|Easy\|\|`
`13`	`14`	`\|1974\|[Minimum Time to Type Word Using Special Typewriter](https://leetcode.com/problems/minimum-time-to-type-word-using-special-typewriter/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1974.java)\|\|Easy\|\|`

Lines changed: 34 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,34 @@`
	`1`	`+packagecom.fishercoder.solutions;`
	`2`	`+`
	`3`	`+publicclass_1981 {`
	`4`	`+publicstaticclassSolution1 {`
	`5`	`+/**`
	`6`	`+ * creidt: https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/discuss/1418614/Java-dp-code-with-proper-comments-and-explanation`
	`7`	`+ */`
	`8`	`+intans =Integer.MAX_VALUE;`
	`9`	`+boolean[][]dp;`
	`10`	`+`
	`11`	`+publicintminimizeTheDifference(int[][]mat,inttarget) {`
	`12`	`+dp =newboolean[mat.length][4900];//we use 4900 due to the contraints in this problem: 70 * 70 = 4900`
	`13`	`+memo(mat,0,0,target);`
	`14`	`+returnans;`
	`15`	`+ }`
	`16`	`+`
	`17`	`+privatevoidmemo(int[][]mat,introw,intsum,inttarget) {`
	`18`	`+if (dp[row][sum]) {`
	`19`	`+return;`
	`20`	`+ }`
	`21`	`+if (row ==mat.length -1) {`
	`22`	`+for (inti =0;i <mat[0].length;i++) {`
	`23`	`+ans =Math.min(ans,Math.abs(sum +mat[row][i] -target));`
	`24`	`+ }`
	`25`	`+dp[row][sum] =true;`
	`26`	`+return;`
	`27`	`+ }`
	`28`	`+for (inti =0;i <mat[0].length;i++) {`
	`29`	`+memo(mat,row +1,sum +mat[row][i],target);`
	`30`	`+ }`
	`31`	`+dp[row][sum] =true;`
	`32`	`+ }`
	`33`	`+ }`
	`34`	`+}`

Lines changed: 32 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,32 @@`
	`1`	`+packagecom.fishercoder;`
	`2`	`+`
	`3`	`+importcom.fishercoder.common.utils.CommonUtils;`
	`4`	`+importcom.fishercoder.solutions._1981;`
	`5`	`+importorg.junit.Test;`
	`6`	`+`
	`7`	`+importstaticorg.junit.Assert.assertEquals;`
	`8`	`+`
	`9`	`+publicclass_1981Test {`
	`10`	`+privatestatic_1981.Solution1solution1;`
	`11`	`+`
	`12`	`+@BeforeEach`
	`13`	`+publicstaticvoidsetup() {`
	`14`	`+solution1 =new_1981.Solution1();`
	`15`	`+ }`
	`16`	`+`
	`17`	`+@Test`
	`18`	`+publicvoidtest1() {`
	`19`	`+assertEquals(0,solution1.minimizeTheDifference(CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,2,3],[4,5,6],[7,8,9]"),13));`
	`20`	`+ }`
	`21`	`+`
	`22`	`+@Test`
	`23`	`+publicvoidtest2() {`
	`24`	`+assertEquals(94,solution1.minimizeTheDifference(CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1],[2],[3]"),100));`
	`25`	`+ }`
	`26`	`+`
	`27`	`+@Test`
	`28`	`+publicvoidtest3() {`
	`29`	`+assertEquals(1,solution1.minimizeTheDifference(CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,2,9,8,7]"),6));`
	`30`	`+ }`
	`31`	`+`
	`32`	`+}`

Comments

(0)