update

OneCodeMonkey · OneCodeMonkey · commit 5fa214a1a36e · 2024-04-20T23:26:51.000+08:00
diff --git a/codeForces/Codeforces_1675B_Make_It_Increasing.java b/codeForces/Codeforces_1675B_Make_It_Increasing.java
@@ -0,0 +1,38 @@
+// AC: 952 ms 
+// Memory: 800 KB
+// .
+// T:O(nlog(max(ai))), S:O(n)
+// 
+import java.util.Scanner;
+
+public class Codeforces_1675B_Make_It_Increasing {
+    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(), ret = 0;
+            int[] arr = new int[n];
+            boolean flag = true;
+            for (int j = 0; j < n; j++) {
+                int a = sc.nextInt();
+                arr[j] = a;
+            }
+            for (int j = n - 2; j >= 0; j--) {
+                if (arr[j + 1] < 1) {
+                    flag = false;
+                    break;
+                }
+                while (arr[j] >= arr[j + 1]) {
+                    arr[j] /= 2;
+                    ret++;
+                }
+                if (arr[j] < j) {
+                    flag = false;
+                    break;
+                }
+            }
+
+            System.out.println(flag ? ret : -1);
+        }
+    }
+}
diff --git a/codeForces/Codeforces_1703D_Double_Strings.java b/codeForces/Codeforces_1703D_Double_Strings.java
@@ -0,0 +1,39 @@
+// AC: 608 ms 
+// Memory: 14100 KB
+// Hashset.
+// T:O(sum(ni * k)), S:O(max(ni * k)), k = string length.
+//
+import java.util.HashSet;
+import java.util.Scanner;
+
+public class Codeforces_1703D_Double_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();
+            HashSet<String> record = new HashSet<>();
+            String[] arr = new String[n];
+            for (int j = 0; j < n; j++) {
+                String s = sc.next();
+                record.add(s);
+                arr[j] = s;
+            }
+            StringBuilder ret = new StringBuilder();
+            for (int j = 0; j < n; j++) {
+                String item = arr[j];
+                boolean flag = false;
+                for (int k = 0; k < item.length() - 1; k++) {
+                    String s1 = item.substring(0, k + 1), s2 = item.substring(k + 1);
+                    if (record.contains(s1) && record.contains(s2)) {
+                        flag = true;
+                        break;
+                    }
+                }
+                ret.append(flag ? 1 : 0);
+            }
+
+            System.out.println(ret);
+        }
+    }
+}
diff --git a/leetcode_solved/leetcode_0988_Smallest_String_Starting_From_Leaf.java b/leetcode_solved/leetcode_0988_Smallest_String_Starting_From_Leaf.java
@@ -0,0 +1,27 @@
+// Runtime 8 ms Beats 39.83% of users with Java
+// Memory 45.75 MB Beats 7.76% of users with Java
+// Recursion: Notice the path must starting from leaf node. We should always append the current char to the judge string front.
+// T:O(n), S:O(n)
+// 
+class Solution {
+    public String smallestFromLeaf(TreeNode root) {
+        return solve(root, "");
+    }
+
+    public String solve(TreeNode root, String cur) {
+        char currentChar = (char) (root.val + 'a');
+        if (root.left == null && root.right == null) {
+            return currentChar + cur;
+        }
+        if (root.left == null) {
+            return solve(root.right, currentChar + cur);
+        }
+        if (root.right == null) {
+            return solve(root.left, currentChar + cur);
+        }
+
+        String s1 = solve(root.left, currentChar + cur);
+        String s2 = solve(root.right, currentChar + cur);
+        return s1.compareTo(s2) <= 0 ? s1 : s2;
+    }
+}
diff --git a/leetcode_solved/leetcode_3110_Score_of_a_String.java b/leetcode_solved/leetcode_3110_Score_of_a_String.java
@@ -0,0 +1,15 @@
+// Runtime 1 ms Beats 100.00% of users with Java
+// Memory 41.92 MB Beats 50.00% of users with Java
+// .
+// T:O(n), S:O(1)
+// 
+class Solution {
+    public int scoreOfString(String s) {
+        int ret = 0;
+        for (int i = 0; i < s.length() - 1; i++) {
+            ret += Math.abs(s.charAt(i) - s.charAt(i + 1));
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_3111_Minimum_Rectangles_to_Cover_Points.java b/leetcode_solved/leetcode_3111_Minimum_Rectangles_to_Cover_Points.java
@@ -0,0 +1,36 @@
+// Runtime 18 ms Beats 50.00% of users with Java
+// Memory 81.02 MB Beats 100.00% of users with Java
+// HashSet & sort.
+// T:O(nlogn), S:O(n)
+// 
+class Solution {
+    public int minRectanglesToCoverPoints(int[][] points, int w) {
+        int ret = 0;
+        HashSet<Integer> xPosRecord = new HashSet<>();
+        for (int[] point : points) {
+            xPosRecord.add(point[0]);
+        }
+        if (w == 0) {
+            return xPosRecord.size();
+        }
+        int len = xPosRecord.size(), pos = 0, curStart = -1;
+        int[] arr = new int[len];
+        for (int i : xPosRecord) {
+            arr[pos++] = i;
+        }
+        Arrays.sort(arr);
+        for (int i = 0; i < len; i++) {
+            if (curStart == -1) {
+                curStart = arr[i];
+                ret++;
+            } else {
+                if (arr[i] > curStart + w) {
+                    curStart = arr[i];
+                    ret++;
+                }
+            }
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_3114_Latest_Time_You_Can_Obtain_After_Replacing_Characters.java b/leetcode_solved/leetcode_3114_Latest_Time_You_Can_Obtain_After_Replacing_Characters.java
@@ -0,0 +1,47 @@
+// Runtime 1 ms Beats 100.00% of users with Java
+// Memory 42.33 MB Beats 100.00% of users with Java
+// .
+// T:O(1), S:O(1)
+// 
+class Solution {
+    public String findLatestTime(String s) {
+        if (s.contains("?")) {
+            StringBuilder ret = new StringBuilder();
+            if (s.charAt(4) == '?') {
+                ret.append('9');
+            } else {
+                ret.append(s.charAt(4));
+            }
+            if (s.charAt(3) == '?') {
+                ret.append('5');
+            } else {
+                ret.append(s.charAt(3));
+            }
+            ret.append(':');
+            char c1 = s.charAt(0), c2 = s.charAt(1);
+            if (c1 == '?') {
+                if (c2 != '?' && c2 > '1') {
+                    c1 = '0';
+                } else {
+                    c1 = '1';
+                }
+            }
+            if (c1 == '1') {
+                if (c2 == '?') {
+                    c2 = '1';
+                }
+            } else {
+                if (c2 == '?') {
+                    c2 = '9';
+                }
+            }
+
+            ret.append(c2);
+            ret.append(c1);
+
+            return ret.reverse().toString();
+        }
+
+        return s;
+    }
+}
diff --git a/leetcode_solved/leetcode_3115_Maximum_Prime_Difference.java b/leetcode_solved/leetcode_3115_Maximum_Prime_Difference.java
@@ -0,0 +1,41 @@
+// Runtime 1 ms Beats 100.00% of users with Java
+// Memory 79.60 MB Beats 100.00% of users with Java
+// .
+// T:O(sum(sqrt(ki)), S:O(1)
+// 
+class Solution {
+    public int maximumPrimeDifference(int[] nums) {
+        int len = nums.length, left = -1, right = -1;
+        for (int i = 0; i < len; i++) {
+            if (checkPrime(nums[i])) {
+                left = i;
+                break;
+            }
+        }
+        if (left == -1 || left == len - 1) {
+            return 0;
+        }
+        for (int i = len - 1; i >= 0; i--) {
+            if (checkPrime(nums[i])) {
+                right = i;
+                break;
+            }
+        }
+
+        return right - left;
+    }
+
+    private boolean checkPrime(int n) {
+        if (n <= 2) {
+            return n == 2;
+        }
+        int top = (int) Math.sqrt(n);
+        for (int i = 2; i <= top; i++) {
+            if (n % i == 0) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+}
