8000 add 1005 · deepakvish001/Leetcode@d00895a · GitHub
[go: up one dir, main page]
Skip to content

Commit d00895a

Browse files
fishercoder1534fishercoder1534
committed
add 1005
1 parent 37c7fbf commit d00895a

File tree

3 files changed

+115
-0
lines changed

3 files changed

+115
-0
lines 8000 changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -75,6 +75,7 @@ _If you like this project, please leave me a star._ ★
7575
|1010|[Pairs of Songs With Total Durations Divisible by 60](https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1010.java) | |Easy|
7676
|1009|[Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1009.java) | |Easy|
7777
|1008|[Construct Binary Search Tree from Preorder Traversal](https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1008.java) | |Medium| Recursion
78+
|1005|[Maximize Sum Of Array After K Negations](https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1005.java) | |Easy|
7879
|1003|[Check If Word Is Valid After Substitutions](https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1003.java) | |Medium|
7980
|1002|[Find Common Characters](https://leetcode.com/problems/find-common-characters/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1002.java) | |Easy|
8081
|999|[Available Captures for Rook](https://leetcode.com/problems/available-captures-for-rook/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_999.java) | |Easy|

‎src/main/java/com/fishercoder/solutions/_1005.java

Lines changed: 72 additions & 0 deletions
< 8000 td data-grid-cell-id="diff-8c78f76c11cba8c956bf5649fb47c89390e525ce1b8159f752442faa33f6e5b4-empty-24-0" data-selected="false" role="gridcell" style="background-color:var(--diffBlob-additionNum-bgColor, var(--diffBlob-addition-bgColor-num));text-align:center" tabindex="-1" valign="top" class="focusable-grid-cell diff-line-number position-relative left-side">
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.Arrays;
4+
import java.util.PriorityQueue;
5+
6+
/**
7+
* 1005. Maximize Sum Of Array After K Negations
8+
*
9+
* Given an array A of integers, we must modify the array in the following way:
10+
* we choose an i and replace A[i] with -A[i], and we repeat this process K times in total.
11+
* (We may choose the same index i multiple times.)
12+
*
13+
* Return the largest possible sum of the array after modifying it in this way.
14+
*
15+
* Example 1:
16+
* Input: A = [4,2,3], K = 1
17+
* Output: 5
18+
* Explanation: Choose indices (1,) and A becomes [4,-2,3].
19+
*
20+
* Example 2:
21+
* Input: A = [3,-1,0,2], K = 3
22+
* Output: 6
23+
* Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].
24+
* Example 3:
25+
*
26+
* Input: A = [2,-3,-1,5,-4], K = 2
27+
* Output: 13
28+
* Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].
29+
*
30+
*
31+
* Note:
32+
*
33+
* 1 <= A.length <= 10000
34+
* 1 <= K <= 10000
35+
* -100 <= A[i] <= 100
36+
* */
37+
public class _1005 {
38+
public static class Solution1 {
39+
/**credit: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252228/A-very-simple-java-solution*/
40+
public int largestSumAfterKNegations(int[] A, int K) {
41+
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
42+
for (int num : A) {
43+
minHeap.offer(num);
44+
}
45+
while (K-- > 0) {
46+
minHeap.offer(-minHeap.poll());
47+
}
48+
int sum = 0;
49+
while (!minHeap.isEmpty()) {
50+
sum += minHeap.poll();
51+
}
52+
return sum;
53+
}
54+
}
55+
56+
public static class Solution2 {
57+
/**credit: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252254/JavaC%2B%2BPython-Sort*/
58+
public int largestSumAfterKNegations(int[] A, int K) {
59+
Arrays.sort(A);
60+
for (int i = 0; i < A.length && K > 0 && A[i] < 0; i++, K--) {
61+
A[i] = -A[i];
62+
}
63+
int sum = 0;
64+
int min = Integer.MAX_VALUE;
65+
for (int i = 0; i < A.length; i++) {
66+
min = Math.min(min, A[i]);
67+
sum += A[i];
68+
}
69+
return K % 2 == 0 ? sum : sum - min * 2;
70+
}
71+
}
72+
}

‎src/test/java/com/fishercoder/_1005Test.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1005;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
public class _1005Test {
10+
private static _1005.Solution1 solution1;
11+
private static _1005.Solution2 solution2;
12+
13+
@BeforeClass
14 67E6 +
public static void setup() {
15+
solution1 = new _1005.Solution1();
16+
solution2 = new _1005.Solution2();
17+
}
18+
19+
@Test
20+
public void test1() {
21+
assertEquals(5, solution1.largestSumAfterKNegations(new int[]{4, 2, 3}, 1));
22+
assertEquals(5, solution2.largestSumAfterKNegations(new int[]{4, 2, 3}, 1));
23+
}
24+
25+
@Test
26+
public void test2() {
27+
assertEquals(6, solution1.largestSumAfterKNegations(new int[]{3, -1, 0, 2}, 3));
28+
assertEquals(6, solution2.largestSumAfterKNegations(new int[]{3, -1, 0, 2}, 3));
29+
}
30+
31+
@Test
32+
public void test3() {
33+
assertEquals(13, solution1.largestSumAfterKNegations(new int[]{2, -3, -1, 5, -4}, 2));
34+
assertEquals(13, solution2.largestSumAfterKNegations(new int[]{2, -3, -1, 5, -4}, 2));
35+
}
36+
37+
@Test
38+
public void test4() {
39+
assertEquals(22, solution1.largestSumAfterKNegations(new int[]{-8, 3, -5, -3, -5, -2}, 6));
40+
assertEquals(22, solution2.largestSumAfterKNegations(new int[]{-8, 3, -5, -3, -5, -2}, 6));
41+
}
42+
}

0 commit comments

Comments
 (0)
0