update

OneCodeMonkey · OneCodeMonkey · commit 81759de579fa · 2023-12-24T11:48:07.000+08:00
diff --git a/codeForces/Codeforces_0515C_Drazil_and_Factorial.java b/codeForces/Codeforces_0515C_Drazil_and_Factorial.java
@@ -0,0 +1,48 @@
+// AC: 187 ms 
+// Memory: 0 KB
+// Factorial replace: 4! = 2! * 2!, 6! = 5! * 3!, 8! = 7! * 2! * 2! * 2!, 9! = 7! * 3! * 3! * 2!
+// T:O(n), S:O(n)
+//
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Scanner;
+
+public class Codeforces_0515C_Drazil_and_Factorial {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int n = sc.nextInt();
+        String num = sc.next();
+        List<Integer> digits = new ArrayList<>();
+        for (int i = 0; i < num.length(); i++) {
+            char c = num.charAt(i);
+            if (c == '2' || c == '3' || c == '5' || c == '7') {
+                digits.add(c - '0');
+            } else if (c == '4') {
+                digits.add(3);
+                digits.add(2);
+                digits.add(2);
+            } else if (c == '6') {
+                digits.add(5);
+                digits.add(3);
+            } else if (c == '8') {
+                digits.add(7);
+                digits.add(2);
+                digits.add(2);
+                digits.add(2);
+            } else if (c == '9') {
+                digits.add(7);
+                digits.add(3);
+                digits.add(3);
+                digits.add(2);
+            }
+        }
+        digits.sort(Collections.reverseOrder());
+        StringBuilder ret = new StringBuilder();
+        for (int digit : digits) {
+            ret.append(digit);
+        }
+
+        System.out.println(ret);
+    }
+}
diff --git a/leetcode_solved/leetcode_0661_Image_Smoother.java b/leetcode_solved/leetcode_0661_Image_Smoother.java
@@ -0,0 +1,27 @@
+// AC: Runtime 7 ms Beats 50.42% of users with Java
+// Memory 44.70 MB Beats 46.78% of users with Java
+// Calculate by each cell.
+// T:O(m * n * 9), S:O(m * n)
+// 
+class Solution {
+    public int[][] imageSmoother(int[][] img) {
+        int row = img.length, col = img[0].length;
+        int[][] ret = new int[row][col];
+        for (int i = 0; i < row; i++) {
+            for (int j = 0; j < col; j++) {
+                int sum = 0, count = 0;
+                for (int k = i - 1; k <= i + 1; k++) {
+                    for (int t = j - 1; t <= j + 1; t++) {
+                        if (k >= 0 && k < row && t >= 0 && t < col) {
+                            sum += img[k][t];
+                            count++;
+                        }
+                    }
+                }
+                ret[i][j] = (int) Math.floor(sum * 1.0 / count);
+            }
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_2353_Design_a_Food_Rating_System.java b/leetcode_solved/leetcode_2353_Design_a_Food_Rating_System.java
@@ -0,0 +1,44 @@
+// AC: Runtime 906 ms Beats 5.08% of users with Java
+// Memory 70.56 MB Beats 83.62% of users with Java
+// PriorityQueue & inner class sorting.
+// T:O(logn), S:O(n)
+// 
+class FoodRatings {
+    HashMap<String, Food> foodInfo;
+    HashMap<String, PriorityQueue<Food>> cuisineToFood;
+
+    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
+        foodInfo = new HashMap<>();
+        cuisineToFood = new HashMap<>();
+        for (int i = 0; i < foods.length; i++) {
+            Food food = new Food(foods[i], cuisines[i], ratings[i]);
+            foodInfo.put(foods[i], food);
+            PriorityQueue<Food> pq = new PriorityQueue<>((a, b) ->
+                    !a.rating.equals(b.rating) ? (b.rating - a.rating) : a.name.compareTo(b.name));
+            cuisineToFood.putIfAbsent(cuisines[i], pq);
+            cuisineToFood.get(cuisines[i]).add(food);
+        }
+    }
+
+    public void changeRating(String food, int newRating) {
+        PriorityQueue<Food> pq = cuisineToFood.get(foodInfo.get(food).cuisine);
+        pq.remove(foodInfo.get(food));
+        foodInfo.get(food).rating = newRating;
+        pq.add(foodInfo.get(food));
+    }
+
+    public String highestRated(String cuisine) {
+        return cuisineToFood.get(cuisine).peek().name;
+    }
+
+    static class Food {
+        Integer rating;
+        String name, cuisine;
+
+        Food(String name, String cuisine, Integer rating) {
+            this.rating = rating;
+            this.name = name;
+            this.cuisine = cuisine;
+        }
+    }
+}
diff --git a/leetcode_solved/leetcode_2789_Largest_Element_in_an_Array_after_Merge_Operations.java b/leetcode_solved/leetcode_2789_Largest_Element_in_an_Array_after_Merge_Operations.java
@@ -0,0 +1,21 @@
+// AC: Runtime 1 ms Beats 100.00% of users with Java
+// Memory 58.48 MB Beats 21.79% of users with Java
+// Greedy.
+// T:O(n), S:O(1)
+// 
+class Solution {
+    public long maxArrayValue(int[] nums) {
+        int len = nums.length;
+        long curMax = nums[len - 1], ret = curMax;
+        for (int i = len - 1; i >= 1; i--) {
+            if (curMax >= nums[i - 1]) {
+                curMax += nums[i - 1];
+            } else {
+                curMax = nums[i - 1];
+            }
+            ret = Math.max(ret, curMax);
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_2958_Length_of_Longest_Subarray_With_at_Most_K_Frequency.java b/leetcode_solved/leetcode_2958_Length_of_Longest_Subarray_With_at_Most_K_Frequency.java
@@ -0,0 +1,23 @@
+// AC: Runtime 59 ms Beats 87.90% of users with Java
+// Memory 55.86 MB Beats 97.17% of users with Java
+// Sliding-window.
+// T:O(n), S:O(1)
+// 
+class Solution {
+    public int maxSubarrayLength(int[] nums, int k) {
+        HashMap<Integer, Integer> count = new HashMap<>();
+        int leftPos = 0, ret = 0, len = nums.length;
+        for (int i = 0; i < len; i++) {
+            count.merge(nums[i], 1, Integer::sum);
+            if (count.get(nums[i]) > k) {
+                while (count.get(nums[i]) > k) {
+                    count.merge(nums[leftPos], -1, Integer::sum);
+                    leftPos++;
+                }
+            }
+            ret = Math.max(ret, i - leftPos + 1);
+        }
+
+        return ret;
+    }
+}
diff --git a/leetcode_solved/leetcode_2965_Find_Missing_and_Repeated_Values.java b/leetcode_solved/leetcode_2965_Find_Missing_and_Repeated_Values.java
@@ -0,0 +1,24 @@
+// AC: Runtime 4 ms Beats 100.00% of users with Java
+// Memory 44.24 MB Beats 100.00% of users with Java
+// .
+// T:O(n^2), S:O(n^2)
+// 
+class Solution {
+    public int[] findMissingAndRepeatedValues(int[][] grid) {
+        int row = grid.length, repeated = 0;
+        long sum = 0, target = (1 + (long) row * row) * row * row / 2;
+        HashSet<Integer> record = new HashSet<>();
+        for (int[] rowItem : grid) {
+            for (int i : rowItem) {
+                sum += i;
+                if (record.contains(i)) {
+                    repeated = i;
+                } else {
+                    record.add(i);
+                }
+            }
+        }
+
+        return new int[]{repeated, (int) (target - sum + repeated)};
+    }
+}
diff --git a/leetcode_solved/leetcode_2966_Divide_Array_Into_Arrays_With_Max_Difference.java b/leetcode_solved/leetcode_2966_Divide_Array_Into_Arrays_With_Max_Difference.java
@@ -0,0 +1,22 @@
+// AC: Runtime 24 ms Beats 33.33% of users with Java
+// Memory 56.77 MB Beats 66.67% of users with Java
+// .
+// T:O(n), S:O(n)
+// 
+class Solution {
+    public int[][] divideArray(int[] nums, int k) {
+        Arrays.sort(nums);
+        int len = nums.length;
+        for (int i = 0; i < len / 3; i++) {
+            if (nums[3 * i + 2] - nums[3 * i] > k) {
+                return new int[0][];
+            }
+        }
+        int[][] ret = new int[len / 3][3];
+        for (int i = 0; i < len / 3; i++) {
+            ret[i] = new int[]{nums[3 * i], nums[3 * i + 1], nums[3 * i + 2]};
+        }
+
+        return ret;
+    }
+}
