update

OneCodeMonkey · OneCodeMonkey · commit f10804812f87 · 2024-02-03T18:15:26.000+08:00
diff --git a/codeForces/Codeforces_0507B_Amr_and_Pins.java b/codeForces/Codeforces_0507B_Amr_and_Pins.java
@@ -0,0 +1,20 @@
+// AC: 280 ms 
+// Memory: 500 KB
+// Geometry.
+// T:O(1), S:O(1)
+// 
+import java.util.Scanner;
+
+public class Codeforces_0507B_Amr_and_Pins {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        long r = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt(), x1 = sc.nextInt(), y1 = sc.nextInt(),
+                xDelta = Math.abs(x - x1), yDelta = Math.abs(y - y1);
+        double dis = Math.sqrt(xDelta * xDelta + yDelta * yDelta);
+        int ret = (int) (dis / (2 * r));
+        if (dis > 2 * r * ret) {
+            ret++;
+        }
+        System.out.println(ret);
+    }
+}
diff --git a/codeForces/Codeforces_1213A_Chips_Moving.java b/codeForces/Codeforces_1213A_Chips_Moving.java
@@ -0,0 +1,20 @@
+// AC: 296 ms 
+// Memory: 600 KB
+// .
+// T:O(n), S:O(1)
+// 
+import java.util.Scanner;
+
+public class Codeforces_1213A_Chips_Moving {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int n = sc.nextInt(), oddCount = 0;
+        for (int i = 0; i < n; i++) {
+            int x = sc.nextInt();
+            if (x % 2 == 1) {
+                oddCount++;
+            }
+        }
+        System.out.println(Math.min(oddCount, n - oddCount));
+    }
+}
diff --git a/codeForces/Codeforces_1352D_Alice_Bob_and_Candies.java b/codeForces/Codeforces_1352D_Alice_Bob_and_Candies.java
@@ -0,0 +1,45 @@
+// AC: 608 ms 
+// Memory: 500 KB
+// do as it say.
+// T:O(n), S:O(n)
+// 
+import java.util.Scanner;
+
+public class Codeforces_1352D_Alice_Bob_and_Candies {
+    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(), cur = 0, round = 0, sum1 = 0, sum2 = 0;
+            int[] arr = new int[n];
+            for (int j = 0; j < n; j++) {
+                arr[j] = sc.nextInt();
+            }
+            for (int left = 0, right = n - 1; left <= right; round++) {
+                int sum = 0;
+                if (round % 2 == 0) {
+                    sum = arr[left++];
+                    while (sum <= cur) {
+                        if (left > right) {
+                            break;
+                        }
+                        sum += arr[left++];
+                    }
+                    cur = Math.max(cur, sum);
+                    sum1 += sum;
+                } else {
+                    sum = arr[right--];
+                    while (sum <= cur) {
+                        if (left > right) {
+                            break;
+                        }
+                        sum += arr[right--];
+                    }
+                    cur = Math.max(cur, sum);
+                    sum2 += sum;
+                }
+            }
+            System.out.println(round + " " + sum1 + " " + sum2);
+        }
+    }
+}
diff --git a/codeForces/Codeforces_1748A_The_Ultimate_Square.java b/codeForces/Codeforces_1748A_The_Ultimate_Square.java
@@ -0,0 +1,17 @@
+// AC: 342 ms 
+// Memory: 500 KB
+// It can be proved that when n is odd, the sum is always a square number, so the maximum side length is Math.ceil(n / 2).
+// T:O(t), S:O(1)
+// 
+import java.util.Scanner;
+
+public class Codeforces_1748A_The_Ultimate_Square {
+    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();
+            System.out.println(n % 2 == 0 ? n / 2 : (n / 2 + 1));
+        }
+    }
+}
diff --git a/codeForces/Codeforces_1778A_Flip_Flop_Sum.java b/codeForces/Codeforces_1778A_Flip_Flop_Sum.java
@@ -0,0 +1,40 @@
+// AC: 436 ms 
+// Memory: 500 KB
+// Can only flip once, so first find adjacent -1 pair, if not, check if has any -1, 
+// if not, we have to conver "1 1" to "-1 -1", thus the sum will be minus by 4.
+// T:O(sum(ni)), S:O(1)
+// 
+import java.util.Scanner;
+
+public class Codeforces_1778A_Flip_Flop_Sum {
+    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(), countNega = 0, sum = 0, prev = 0, ret = 0;
+            boolean hasAdjacentNega = false;
+            for (int j = 0; j < n; j++) {
+                int a = sc.nextInt();
+                if (a < 0) {
+                    countNega++;
+                }
+                if (prev != 0) {
+                    if (!hasAdjacentNega && a == -1 && prev == -1) {
+                        hasAdjacentNega = true;
+                    }
+                }
+                sum += a;
+                prev = a;
+            }
+            if (countNega == 0) {
+                ret = sum - 4;
+            } else if (hasAdjacentNega) {
+                ret = sum + 4;
+            } else {
+                ret = sum;
+            }
+
+            System.out.println(ret);
+        }
+    }
+}
diff --git a/leetcode_solved/leetcode_0150_Evaluate_Reverse_Polish_Notation.java b/leetcode_solved/leetcode_0150_Evaluate_Reverse_Polish_Notation.java
@@ -0,0 +1,29 @@
+// Runtime 5 ms Beats 97.05% of users with Java
+// Memory 44.39 MB Beats 62.56% of users with Java
+// Math: 逆波兰表达式，算术表达式解析
+// T:O(n), S:O(1)
+// 
+class Solution {
+    public int evalRPN(String[] tokens) {
+        Stack<Integer> record = new Stack();
+        for (String token : tokens) {
+            if ("+".equals(token)) {
+                int a = record.pop(), b = record.pop();
+                record.add(a + b);
+            } else if ("-".equals(token)) {
+                int a = record.pop(), b = record.pop();
+                record.add(b - a);
+            } else if ("*".equals(token)) {
+                int a = record.pop(), b = record.pop();
+                record.add(a * b);
+            } else if ("/".equals(token)) {
+                int a = record.pop(), b = record.pop();
+                record.add(b / a);
+            } else {
+                record.add(Integer.parseInt(token));
+            }
+        }
+
+        return record.peek();
+    }
+}
diff --git a/leetcode_solved/leetcode_1291_Sequential_Digits.java b/leetcode_solved/leetcode_1291_Sequential_Digits.java
@@ -1,7 +1,7 @@
 // AC: Runtime: 0 ms, faster than 100.00% of Java online submissions for Sequential Digits.
 // Memory Usage: 36.6 MB, less than 58.00% of Java online submissions for Sequential Digits.
 // see the annotation
-// T:O(9 * log10(high)) ~ O(log(n), S:O(1)
+// T:O(9 * log10(high)) ~ O(log(n)), S:O(1)
 //
 class Solution {
     public List<Integer> sequentialDigits(int low, int high) {
diff --git a/leetcode_solved/leetcode_3019_Number_of_Changing_Keys.java b/leetcode_solved/leetcode_3019_Number_of_Changing_Keys.java
@@ -0,0 +1,21 @@
+// AC: Runtime 1 ms Beats 100.00% of users with Java
+// Memory 42.13 MB Beats 100.00% of users with Java
+// .
+// T:O(n), S:O(1)
+// 
+class Solution {
+    public int countKeyChanges(String s) {
+        int ret = 0;
+        char prev = s.charAt(0);
+        for (int i = 1; i < s.length(); i++) {
+            char cur = s.charAt(i);
+            if (prev == cur || Math.abs(prev - cur) == ('a' - 'A')) {
+                continue;
+            }
+            ret++;
+            prev = cur;
+        }
+
+        return ret;
+    }
+}
