update

OneCodeMonkey · OneCodeMonkey · commit 2b85843225e3 · 2024-10-27T17:35:17.000+08:00
diff --git a/codeForces/Codeforces_2001A_Make_All_Equal.java b/codeForces/Codeforces_2001A_Make_All_Equal.java
@@ -0,0 +1,28 @@
+// AC: 312 ms 
+// Memory: 700 KB
+// Greedy.
+// T:O(sum(ni)), S:O(max(ni))
+// 
+import java.util.HashMap;
+import java.util.Scanner;
+
+public class Codeforces_2001A_Make_All_Equal {
+    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();
+            HashMap<Integer, Integer> record = new HashMap<>();
+            for (int j = 0; j < n; j++) {
+                int a = sc.nextInt();
+                record.merge(a, 1, Integer::sum);
+            }
+            int maxTime = 1;
+            for (int key : record.keySet()) {
+                maxTime = Math.max(maxTime, record.get(key));
+            }
+
+            System.out.println(n - maxTime);
+        }
+    }
+}
diff --git a/codeForces/Codeforces_2003A_Turtle_and_Good_Strings.java b/codeForces/Codeforces_2003A_Turtle_and_Good_Strings.java
@@ -0,0 +1,19 @@
+// AC: 328 ms 
+// Memory: 700 KB
+// Greedy. Only check head and tail.
+// T:O(sum(ni)), S:O(max(ni))
+// 
+import java.util.Scanner;
+
+public class Codeforces_2003A_Turtle_and_Good_Strings {
+    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();
+            String s = sc.next();
+
+            System.out.println(s.charAt(0) != s.charAt(n - 1) ? "YES" : "NO");
+        }
+    }
+}
diff --git a/leetcode_solved/leetcode_1233_Remove_Sub_Folders_from_the_Filesystem.java b/leetcode_solved/leetcode_1233_Remove_Sub_Folders_from_the_Filesystem.java
@@ -0,0 +1,25 @@
+// Solution 1: Sort and see regular.
+// Runtime 42 ms Beats 75.31%
+// Memory 55.70 MB Beats 46.94%
+// If sorted, the sequence like "/a", "/a/b", "/aa" can be compared straightly, we check the last one is start with the former one + '/'.
+// T:O(n), S:O(n)
+// 
+class Solution {
+    public List<String> removeSubfolders(String[] folder) {
+        List<String> ret = new ArrayList<>();
+        Arrays.sort(folder);
+        String prev = "";
+        for (String s : folder) {
+            if (ret.isEmpty() || !s.startsWith(prev + '/')) {
+                ret.add(s);
+                prev = s;
+            }
+        }
+
+        return ret;
+    }
+}
+
+
+// Solution 2: Trie tree solution.
+// todo-understand: https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/solutions/409626/java-trie-solution/?envType=daily-question&envId=2024-10-25
diff --git a/leetcode_solved/leetcode_3314_Construct_the_Minimum_Bitwise_Array_I.java b/leetcode_solved/leetcode_3314_Construct_the_Minimum_Bitwise_Array_I.java
@@ -0,0 +1,25 @@
+// Runtime 2 ms Beats 92.44%
+// Memory 45.00 MB Beats 13.50%
+// Brute-force.
+// T:O(n * k), S:O(1)
+// 
+class Solution {
+    public int[] minBitwiseArray(List<Integer> nums) {
+        int len = nums.size(), pos = 0;
+        int[] ret = new int[len];
+        for (int num : nums) {
+            if (num % 2 == 0) {
+                ret[pos++] = -1;
+            } else {
+                for (int i = num / 2; i <= num - 1; i++) {
+                    if ((i | (i + 1)) == num) {
+                        ret[pos++] = i;
+                        break;
+                    }
+                }
+            }
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_3315_Construct_the_Minimum_Bitwise_Array_II.java b/leetcode_solved/leetcode_3315_Construct_the_Minimum_Bitwise_Array_II.java
@@ -0,0 +1,20 @@
+// Runtime 1 ms Beats 100.00%
+// Memory 44.85 MB Beats 59.36%
+// Bitmap: 找到从右边起，第一个 0 bit 位，然后原数字 A 减去这个 0 位对应的 1XXX 二进制对应值的一半 1XX. 减去这个 1XX 得到的 ans 可满足 ans|(ans+1) = A.
+// T:O(n * logk), S:O(1)
+// 
+class Solution {
+    public int[] minBitwiseArray(List<Integer> nums) {
+        int len = nums.size(), pos = 0;
+        int[] ret = new int[len];
+        for (int num : nums) {
+            if (num % 2 == 0) {
+                ret[pos++] = -1;
+            } else {
+                ret[pos++] = num - ((num + 1) & (-num - 1)) / 2;
+            }
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_3318_Find_X_Sum_of_All_K_Long_Subarrays_I.java b/leetcode_solved/leetcode_3318_Find_X_Sum_of_All_K_Long_Subarrays_I.java
@@ -0,0 +1,54 @@
+// Runtime 17 ms Beats 19.09%
+// Memory 45.83 MB Beats 6.72%
+// Hashmap & sort.
+// T:O(n * k), S:O(k)
+// 
+class Solution {
+    public int[] findXSum(int[] nums, int k, int x) {
+        int len = nums.length, pos = 0;
+        int[] ret = new int[len - k + 1];
+        HashMap<Integer, Integer> record = new HashMap<>();
+        for (int i = 0; i < len; i++) {
+            record.merge(nums[i], 1, Integer::sum);
+            if (i < k - 1) {
+                continue;
+            }
+            int sum = 0, countX = x;
+            TreeMap<Integer, List<Integer>> sort = new TreeMap<>(Comparator.reverseOrder());
+            for (int key : record.keySet()) {
+                int freq = record.get(key);
+                if (sort.containsKey(freq)) {
+                    sort.get(freq).add(key);
+                } else {
+                    List<Integer> list1 = new ArrayList<>();
+                    list1.add(key);
+                    sort.put(freq, list1);
+                }
+            }
+            for (int freq : sort.keySet()) {
+                List<Integer> elems = sort.get(freq);
+                if (elems.size() <= countX) {
+                    for (int elem : elems) {
+                        sum += elem * freq;
+                    }
+                    countX -= elems.size();
+                } else {
+                    elems.sort(Collections.reverseOrder());
+                    for (int j = 0; j < countX; j++) {
+                        sum += elems.get(j) * freq;
+                    }
+                    countX = 0;
+                }
+
+                if (countX == 0) {
+                    break;
+                }
+            }
+
+            record.merge(nums[i + 1 - k], -1, Integer::sum);
+            ret[pos++] = sum;
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_3324_Find_the_Sequence_of_Strings_Appeared_on_the_Screen.java b/leetcode_solved/leetcode_3324_Find_the_Sequence_of_Strings_Appeared_on_the_Screen.java
@@ -0,0 +1,24 @@
+// Runtime 7 ms Beats 55.54%
+// Memory 55.34 MB Beats 90.57%
+// .
+// T:O(n), S:O(n)
+// 
+class Solution {
+    public List<String> stringSequence(String target) {
+        List<String> ret = new ArrayList<>();
+        StringBuilder sb = new StringBuilder();
+        for (char c : target.toCharArray()) {
+            int c1 = c - 'a';
+            for (int i = 0; i <= c1; i++) {
+                char c2 = (char) ('a' + i);
+                sb.append(c2);
+                ret.add(sb.toString());
+                if (i != c1) {
+                    sb.deleteCharAt(sb.length() - 1);
+                }
+            }
+        }
+
+        return ret;
+    }
+}
