Added tasks 1049, 1051.

javadev · web-flow · commit a07bab4e0bb9 · 2022-02-28T11:00:21.000+02:00
diff --git a/src/main/java/g1001_1100/s1049_last_stone_weight_ii/Solution.java b/src/main/java/g1001_1100/s1049_last_stone_weight_ii/Solution.java
@@ -0,0 +1,23 @@
+package g1001_1100.s1049_last_stone_weight_ii;
+
+// #Medium #Array #Dynamic_Programming #2022_02_28_Time_2_ms_(95.98%)_Space_41.8_MB_(31.51%)
+
+public class Solution {
+    public int lastStoneWeightII(int[] stones) {
+        // dp[i][j] i is the index of stones, j is the current weight
+        // goal is to find max closest to half and use it to get the diff
+        // 0-1 knapsack problem
+        int sum = 0;
+        for (int stone : stones) {
+            sum += stone;
+        }
+        int half = sum / 2;
+        int[] dp = new int[half + 1];
+        for (int cur : stones) {
+            for (int j = half; j >= cur; j--) {
+                dp[j] = Math.max(dp[j], dp[j - cur] + cur);
+            }
+        }
+        return sum - dp[half] * 2;
+    }
+}
diff --git a/src/main/java/g1001_1100/s1049_last_stone_weight_ii/readme.md b/src/main/java/g1001_1100/s1049_last_stone_weight_ii/readme.md
@@ -0,0 +1,41 @@
+1049\. Last Stone Weight II
+
+Medium
+
+You are given an array of integers `stones` where `stones[i]` is the weight of the <code>i<sup>th</sup></code> stone.
+
+We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights `x` and `y` with `x <= y`. The result of this smash is:
+
+*   If `x == y`, both stones are destroyed, and
+*   If `x != y`, the stone of weight `x` is destroyed, and the stone of weight `y` has new weight `y - x`.
+
+At the end of the game, there is **at most one** stone left.
+
+Return _the smallest possible weight of the left stone_. If there are no stones left, return `0`.
+
+**Example 1:**
+
+**Input:** stones = [2,7,4,1,8,1]
+
+**Output:** 1
+
+**Explanation:**
+
+We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
+
+we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
+
+we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
+
+we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.
+
+**Example 2:**
+
+**Input:** stones = [31,26,33,21,40]
+
+**Output:** 5
+
+**Constraints:**
+
+*   `1 <= stones.length <= 30`
+*   `1 <= stones[i] <= 100`
diff --git a/src/main/java/g1001_1100/s1051_height_checker/Solution.java b/src/main/java/g1001_1100/s1051_height_checker/Solution.java
@@ -0,0 +1,30 @@
+package g1001_1100.s1051_height_checker;
+
+// #Easy #Array #Sorting #Counting_Sort #2022_02_28_Time_1_ms_(94.01%)_Space_42.6_MB_(5.71%)
+
+public class Solution {
+    public int heightChecker(int[] heights) {
+        int heightDiff = 0;
+        int[] count = new int[101];
+        int[] actualLine = new int[heights.length];
+        for (int height : heights) {
+            count[height]++;
+        }
+        int heightLength = 0;
+        for (int i = 0; i < count.length; i++) {
+            if (count[i] > 0) {
+                for (int j = 0; j < count[i]; j++) {
+                    actualLine[heightLength] = i;
+                    heightLength++;
+                }
+                count[i] = 0;
+            }
+        }
+        for (int i = 0; i < heights.length; i++) {
+            if (actualLine[i] != heights[i]) {
+                heightDiff++;
+            }
+        }
+        return heightDiff;
+    }
+}
diff --git a/src/main/java/g1001_1100/s1051_height_checker/readme.md b/src/main/java/g1001_1100/s1051_height_checker/readme.md
@@ -0,0 +1,56 @@
+1051\. Height Checker
+
+Easy
+
+A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in **non-decreasing order** by height. Let this ordering be represented by the integer array `expected` where `expected[i]` is the expected height of the <code>i<sup>th</sup></code> student in line.
+
+You are given an integer array `heights` representing the **current order** that the students are standing in. Each `heights[i]` is the height of the <code>i<sup>th</sup></code> student in line (**0-indexed**).
+
+Return _the **number of indices** where_ `heights[i] != expected[i]`.
+
+**Example 1:**
+
+**Input:** heights = [1,1,4,2,1,3]
+
+**Output:** 3
+
+**Explanation:**
+
+heights: [1,1,4,2,1,3]
+
+expected: [1,1,1,2,3,4]
+
+Indices 2, 4, and 5 do not match.
+
+**Example 2:**
+
+**Input:** heights = [5,1,2,3,4]
+
+**Output:** 5
+
+**Explanation:**
+
+heights: [5,1,2,3,4]
+
+expected: [1,2,3,4,5]
+
+All indices do not match.
+
+**Example 3:**
+
+**Input:** heights = [1,2,3,4,5]
+
+**Output:** 0
+
+**Explanation:**
+
+heights: [1,2,3,4,5]
+
+expected: [1,2,3,4,5]
+
+All indices match.
+
+**Constraints:**
+
+*   `1 <= heights.length <= 100`
+*   `1 <= heights[i] <= 100`
diff --git a/src/test/java/g1001_1100/s1049_last_stone_weight_ii/SolutionTest.java b/src/test/java/g1001_1100/s1049_last_stone_weight_ii/SolutionTest.java
@@ -0,0 +1,18 @@
+package g1001_1100.s1049_last_stone_weight_ii;
+
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import org.junit.jupiter.api.Test;
+
+class SolutionTest {
+    @Test
+    void lastStoneWeightII() {
+        assertThat(new Solution().lastStoneWeightII(new int[] {2, 7, 4, 1, 8, 1}), equalTo(1));
+    }
+
+    @Test
+    void lastStoneWeightII2() {
+        assertThat(new Solution().lastStoneWeightII(new int[] {31, 26, 33, 21, 40}), equalTo(5));
+    }
+}
diff --git a/src/test/java/g1001_1100/s1051_height_checker/SolutionTest.java b/src/test/java/g1001_1100/s1051_height_checker/SolutionTest.java
@@ -0,0 +1,23 @@
+package g1001_1100.s1051_height_checker;
+
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import org.junit.jupiter.api.Test;
+
+class SolutionTest {
+    @Test
+    void heightChecker() {
+        assertThat(new Solution().heightChecker(new int[] {1, 1, 4, 2, 1, 3}), equalTo(3));
+    }
+
+    @Test
+    void heightChecker2() {
+        assertThat(new Solution().heightChecker(new int[] {5, 1, 2, 3, 4}), equalTo(5));
+    }
+
+    @Test
+    void heightChecker3() {
+        assertThat(new Solution().heightChecker(new int[] {1, 2, 3, 4, 5}), equalTo(0));
+    }
+}
