update

OneCodeMonkey · OneCodeMonkey · commit c189c7171ac9 · 2024-06-08T15:47:22.000+08:00
diff --git a/codeForces/Codeforces_1497A_Meximization.java b/codeForces/Codeforces_1497A_Meximization.java
@@ -0,0 +1,44 @@
+// AC: 280 ms 
+// Memory: 1500 KB
+// Sort & place duplicate elements behind.
+// T:O(sum(ni * logni)), S:O(max(ni))
+// 
+import java.util.Arrays;
+import java.util.Scanner;
+
+public class Codeforces_1497A_Meximization {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int t = sc.nextInt();
+        for (int i = 0; i < t; i++) {
+            int n = sc.nextInt();
+            Integer[] arr = new Integer[n];
+            for (int j = 0; j < n; j++) {
+                int a = sc.nextInt();
+                arr[j] = a;
+            }
+            Arrays.sort(arr);
+            StringBuilder ret = new StringBuilder(), dup = new StringBuilder();
+            int prev = -1;
+            for (int j = 0; j < n; j++) {
+                if (arr[j] == prev) {
+                    dup.append(arr[j]);
+                    if (j != n - 1) {
+                        dup.append(" ");
+                    }
+                } else {
+                    ret.append(arr[j]);
+                    if (j != n - 1) {
+                        ret.append(" ");
+                    }
+                    prev = arr[j];
+                }
+            }
+            if (!dup.toString().isEmpty()) {
+                ret.append(" ");
+                ret.append(dup);
+            }
+            System.out.println(ret);
+        }
+    }
+}
diff --git a/leetcode_solved/leetcode_0846_Hand_of_Straights.java b/leetcode_solved/leetcode_0846_Hand_of_Straights.java
@@ -0,0 +1,45 @@
+// Runtime 22 ms Beats 96.11% of users with Java
+// Memory 44.82 MB Beats 93.23% of users with Java
+// Sort & hashmap.
+// T:O(nlogn), S:O(1) ~ O(n)
+// 
+class Solution {
+    public boolean isNStraightHand(int[] hand, int groupSize) {
+        if (groupSize == 1) {
+            return true;
+        }
+        int len = hand.length;
+        if (len % groupSize != 0) {
+            return false;
+        }
+        Arrays.sort(hand);
+        HashMap<Integer, Integer> record = new HashMap<>();
+        record.put(hand[0], 1);
+        int countSame = 1, maxDup = len / groupSize;
+        for (int i = 1; i < len; i++) {
+            if (hand[i] == hand[i - 1]) {
+                countSame++;
+                if (countSame > maxDup) {
+                    return false;
+                }
+            } else {
+                countSame = 1;
+            }
+            record.merge(hand[i], 1, Integer::sum);
+        }
+        for (int elem : hand) {
+            if (record.getOrDefault(elem, 0) == 0) {
+                continue;
+            }
+            record.merge(elem, -1, Integer::sum);
+            for (int j = elem + 1; j <= elem + groupSize - 1; j++) {
+                if (record.getOrDefault(j, 0) == 0) {
+                    return false;
+                }
+                record.merge(j, -1, Integer::sum);
+            }
+        }
+
+        return true;
+    }
+}
diff --git a/leetcode_solved/leetcode_1171_Remove_Zero_Sum_Consecutive_Nodes_from_Linked_List.java b/leetcode_solved/leetcode_1171_Remove_Zero_Sum_Consecutive_Nodes_from_Linked_List.java
@@ -0,0 +1,54 @@
+// Solution 1: Brute-force & prefix sum.
+// Runtime 14 ms Beats 6.72% of users with Java
+// Memory 44.88 MB Beats 5.93% of users with Java
+// Hashmap, prefix sum, brute-foce
+// T:O(n ^ 2), S:O(n)
+// 
+class Solution {
+    public ListNode removeZeroSumSublists(ListNode head) {
+        List<ListNode> nodes = new ArrayList<>();
+        ListNode headCopy = head;
+        while (headCopy != null) {
+            nodes.add(headCopy);
+            headCopy = headCopy.next;
+        }
+
+        while (true) {
+            HashMap<Integer, Integer> record = new HashMap<>();
+            record.put(0, 0);
+            int count = 0, sum = 0;
+            boolean changed = false;
+            for (int i = 0; i < nodes.size(); i++) {
+                sum += nodes.get(i).val;
+                count++;
+                if (record.containsKey(sum)) {
+                    int indexStart = record.get(sum);
+                    nodes.subList(indexStart, count).clear();
+                    changed = true;
+                    break;
+                }
+                record.putIfAbsent(sum, count);
+            }
+
+            if (!changed) {
+                break;
+            }
+        }
+
+        if (nodes.isEmpty()) {
+            return null;
+        }
+
+        ListNode ret = nodes.get(0);
+        for (int i = 0; i < nodes.size() - 1; i++) {
+            nodes.get(i).next = nodes.get(i + 1);
+        }
+        nodes.get(nodes.size() - 1).next = null;
+
+        return ret;
+    }
+}
+
+
+// Solution 2: todo
+// 
diff --git a/leetcode_solved/leetcode_1296_Divide_Array_in_Sets_of_K_Consecutive_Numbers.java b/leetcode_solved/leetcode_1296_Divide_Array_in_Sets_of_K_Consecutive_Numbers.java
@@ -0,0 +1,45 @@
+// Runtime 38 ms Beats 99.25% of users with Java
+// Memory 57.62 MB Beats 62.44% of users with Java
+// Sort & hashmap.
+// T:O(nlogn), S:O(1) ~ O(n)
+// 
+class Solution {
+    public boolean isPossibleDivide(int[] nums, int k) {
+        if (k == 1) {
+            return true;
+        }
+        int len = nums.length;
+        if (len % k != 0) {
+            return false;
+        }
+        Arrays.sort(nums);
+        HashMap<Integer, Integer> record = new HashMap<>();
+        record.put(nums[0], 1);
+        int countSame = 1, maxDup = len / k;
+        for (int i = 1; i < len; i++) {
+            if (nums[i] == nums[i - 1]) {
+                countSame++;
+                if (countSame > maxDup) {
+                    return false;
+                }
+            } else {
+                countSame = 1;
+            }
+            record.merge(nums[i], 1, Integer::sum);
+        }
+        for (int elem : nums) {
+            if (record.getOrDefault(elem, 0) == 0) {
+                continue;
+            }
+            record.merge(elem, -1, Integer::sum);
+            for (int j = elem + 1; j <= elem + k - 1; j++) {
+                if (record.getOrDefault(j, 0) == 0) {
+                    return false;
+                }
+                record.merge(j, -1, Integer::sum);
+            }
+        }
+
+        return true;
+    }
+}
diff --git a/leetcode_solved/leetcode_1404_Number_of_Steps_to_Reduce_a_Number_in_Binary_Representation_to_One.java b/leetcode_solved/leetcode_1404_Number_of_Steps_to_Reduce_a_Number_in_Binary_Representation_to_One.java
@@ -0,0 +1,37 @@
+// Runtime 3 ms Beats 20.13% of users with Java
+// Memory 41.17 MB Beats 70.44% of users with Java
+// Implementation.
+// T:O(n), S:O(n)
+// 
+class Solution {
+    public int numSteps(String s) {
+        int len = s.length(), ret = 0;
+        List<Integer> digits = new ArrayList<>(len);
+        for (char c : s.toCharArray()) {
+            digits.add(c - '0');
+        }
+        for (int i = len - 1; i >= 0; i--) {
+            if (digits.get(i) == 0) {
+                ret++;
+            } else {
+                if (i == 0) {
+                    continue;
+                }
+                int j = i;
+                while (j - 1 >= 0 && digits.get(j - 1) == 1) {
+                    j--;
+                }
+                for (int k = j; k <= i; k++) {
+                    digits.set(k, 0);
+                }
+                if (j > 0) {
+                    digits.set(j - 1, 1);
+                }
+                ret++;
+                i++;
+            }
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_3168_Minimum_Number_of_Chairs_in_a_Waiting_Room.java b/leetcode_solved/leetcode_3168_Minimum_Number_of_Chairs_in_a_Waiting_Room.java
@@ -0,0 +1,20 @@
+// Runtime 1 ms Beats 100.00% of users with Java
+// Memory 41.94 MB Beats 100.00% of users with Java
+// .
+// T:O(n), S:O(1)
+// 
+class Solution {
+    public int minimumChairs(String s) {
+        int cur = 0, ret = 0;
+        for (char c : s.toCharArray()) {
+            if (c == 'E') {
+                cur++;
+                ret = Math.max(ret, cur);
+            } else {
+                cur--;
+            }
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_3169_Count_Days_Without_Meetings.java b/leetcode_solved/leetcode_3169_Count_Days_Without_Meetings.java
@@ -0,0 +1,39 @@
+// Runtime 61 ms Beats 100.00% of users with Java
+// Memory 99.61 MB Beats 100.00% of users with Java
+// Sort And get all dis-joint continous segment.
+// T:O(nlogn), S:(n)
+// 
+class Solution {
+    public int countDays(int days, int[][] meetings) {
+        Arrays.sort(meetings, (a, b) -> a[0] != b[0] ? (a[0] - b[0]) : (a[1] != b[1] ? (a[1] - b[1]) : 0));
+        List<List<Integer>> segment = new ArrayList<>();
+        for (int[] meeting : meetings) {
+            if (segment.isEmpty()) {
+                List<Integer> list = new ArrayList<>();
+                list.add(meeting[0]);
+                list.add(meeting[1]);
+                segment.add(list);
+            } else {
+                List<Integer> list = segment.get(segment.size() - 1);
+                if (meeting[0] == list.get(1)) {
+                    list.set(1, meeting[1]);
+                } else if (meeting[0] < list.get(1)) {
+                    if (meeting[1] > list.get(1)) {
+                        list.set(1, meeting[1]);
+                    }
+                } else {
+                    List<Integer> list2 = new ArrayList<>();
+                    list2.add(meeting[0]);
+                    list2.add(meeting[1]);
+                    segment.add(list2);
+                }
+            }
+        }
+        int count = 0;
+        for (List<Integer> segmentItem : segment) {
+            count += segmentItem.get(1) - segmentItem.get(0) + 1;
+        }
+
+        return days - count;
+    }
+}
