update

OneCodeMonkey · OneCodeMonkey · commit ed0bb6f53869 · 2024-06-15T16:03:54.000+08:00
diff --git a/codeForces/Codeforces_1822A_TubeTube_Feed.java b/codeForces/Codeforces_1822A_TubeTube_Feed.java
@@ -0,0 +1,32 @@
+// AC: 343 ms 
+// Memory: 1100 KB
+// brute-force.
+// T:O(sum(ni)), S:O(max(ni))
+// 
+import java.util.Scanner;
+
+public class Codeforces_1822A_TubeTube_Feed {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int q = sc.nextInt();
+        for (int i = 0; i < q; i++) {
+            int n = sc.nextInt(), t = sc.nextInt(), ret = -1, retIndex = -1;
+            int[] arr1 = new int[n], arr2 = new int[n];
+            for (int j = 0; j < n; j++) {
+                arr1[j] = sc.nextInt();
+            }
+            for (int j = 0; j < n; j++) {
+                arr2[j] = sc.nextInt();
+            }
+            for (int j = 0; j < n; j++) {
+                if (arr1[j] <= t && arr2[j] > ret) {
+                    ret = Math.max(ret, arr2[j]);
+                    retIndex = j + 1;
+                }
+                t--;
+            }
+
+            System.out.println(retIndex);
+        }
+    }
+}
diff --git a/codeForces/Codeforces_1881B_Three_Threadlets.java b/codeForces/Codeforces_1881B_Three_Threadlets.java
@@ -0,0 +1,35 @@
+// AC: 358 ms 
+// Memory: 1300 KB
+// Discuss by situations.
+// T:O(t), S:O(t)
+// 
+import java.util.Arrays;
+import java.util.Scanner;
+
+public class Codeforces_1881B_Three_Threadlets {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int t = sc.nextInt(), maxOccurTime = 0;
+        for (int i = 0; i < t; i++) {
+            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
+            int[] arr = new int[]{a, b, c};
+            Arrays.sort(arr);
+            boolean ret = false;
+            if ((long) arr[1] * 4 < arr[2]) {
+                ret = false;
+            } else {
+                if (arr[0] == arr[2]) {
+                    ret = true;
+                } else if (arr[0] == arr[1]) {
+                    ret = (arr[2] == (arr[0] * 2)) || (arr[2] == (arr[0] * 3L)) || (arr[2] == (arr[0] * 4L));
+                } else if (arr[1] == arr[2]) {
+                    ret = arr[1] == (arr[0] * 2);
+                } else {
+                    ret = (arr[1] == (arr[0] * 2)) && (arr[2] == (arr[0] * 3L));
+                }
+            }
+
+            System.out.println(ret ? "YES" : "NO");
+        }
+    }
+}
diff --git a/codeForces/Codeforces_1895A_Treasure_Chest.java b/codeForces/Codeforces_1895A_Treasure_Chest.java
@@ -0,0 +1,20 @@
+// AC: 327 ms 
+// Memory: 800 KB
+// .
+// T:O(n), S:O(1)
+// 
+import java.util.Scanner;
+
+public class Codeforces_1895A_Treasure_Chest {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int n = sc.nextInt();
+        for (int i = 0; i < n; i++) {
+            int x = sc.nextInt(), y = sc.nextInt(), k = sc.nextInt(), ret = x;
+            if (y > x) {
+                ret = y + (k >= (y - x) ? 0 : (y - x - k));
+            }
+            System.out.println(ret);
+        }
+    }
+}
diff --git a/leetcode_solved/leetcode_0945_Minimum_Increment_to_Make_Array_Unique.java b/leetcode_solved/leetcode_0945_Minimum_Increment_to_Make_Array_Unique.java
@@ -0,0 +1,24 @@
+// Runtime 35 ms Beats 82.95% 
+// Memory 60.36 MB Beats 31.15%
+// Greedy & Sort. Or using set both are ok.
+// T:O(nlogn), S:O(1)
+// 
+class Solution {
+    public int minIncrementForUnique(int[] nums) {
+        int cur = -1, ret = 0;
+        Arrays.sort(nums);
+        for (int num : nums) {
+            if (num > cur) {
+                cur = num;
+            } else if (num == cur) {
+                ret += 1;
+                cur += 1;
+            } else {
+                ret += cur - num + 1;
+                cur += 1;
+            }
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_3174_Clear_Digits.java b/leetcode_solved/leetcode_3174_Clear_Digits.java
@@ -0,0 +1,25 @@
+// Runtime 2 ms Beats 100.00% of users with Java
+// Memory 42.66 MB Beats 100.00% of users with Java
+// Using stack
+// T:O(n), S:O(n)
+// 
+class Solution {
+    public String clearDigits(String s) {
+        Stack<Character> record = new Stack<>();
+        for (char c : s.toCharArray()) {
+            if (c >= '0' && c <= '9') {
+                if (!record.isEmpty()) {
+                    record.pop();
+                }
+            } else {
+                record.push(c);
+            }
+        }
+        StringBuilder ret = new StringBuilder();
+        while (!record.isEmpty()) {
+            ret.append(record.pop());
+        }
+
+        return ret.reverse().toString();
+    }
+}
diff --git a/leetcode_solved/leetcode_3178_Find_the_Child_Who_Has_the_Ball_After_K_Seconds.java b/leetcode_solved/leetcode_3178_Find_the_Child_Who_Has_the_Ball_After_K_Seconds.java
@@ -0,0 +1,15 @@
+// Runtime 0 ms Beats 100.00% of users with Java
+// Memory 40.54 MB Beats 100.00% of users with Java
+// .
+// T:O(1), S:O(1)
+// 
+class Solution {
+    public int numberOfChild(int n, int k) {
+        int remain = k % (2 * (n - 1));
+        if (remain <= n - 1) {
+            return remain;
+        } else {
+            return 2 * (n - 1) - remain;
+        }
+    }
+}
diff --git a/leetcode_solved/leetcode_3179_Find_the_N_th_Value_After_K_Seconds.java b/leetcode_solved/leetcode_3179_Find_the_N_th_Value_After_K_Seconds.java
@@ -0,0 +1,35 @@
+// Solution 1: Brute-force 暴力解法
+// Runtime 198 ms Beats 100.00% of users with Java
+// Memory 40.65 MB Beats 100.00% of users with Java
+// Brute-force.
+// T:O(n * k), S:O(1)
+// 
+class Solution {
+    public int valueAfterKSeconds(int n, int k) {
+        int[] arr = new int[n];
+        arr[0] = 1;
+        for (int i = 0; i <= k; i++) {
+            for (int j = 1; j < n; j++) {
+                arr[j] = (arr[j] + arr[j - 1]) % (1_000_000_000 + 7);
+            }
+        }
+
+        return arr[n - 1];
+    }
+}
+
+
+// Solution 2: 杨辉三角通项公式
+// 1
+// 1 1
+// 1 2 1
+// 1 3 3 1
+// 1 4 6 4 1
+// 1 5 10 10 5 1
+// 1 6 15 20 15 6 1
+// 1 7 21 35 35 21 7 1
+// 1 8 28 56 70 56 28 8 1
+// 
+
+// 结论：combination(k+n-1,n-1)
+// todo-补充理解思路，没搞懂
