上岸算法 I LeetCode Weekly Contest 232解题报告

, A$ h, h" I5 V) t. W. C- n

No.1 仅执行一次字符串交换能否使两个字符串相等

解题思路

签到题，枚举一遍统计出所有不想等的位置。

代码展示

1. class Solution {
   . I* Y+ i$ f; c! J: k: V
2.     public boolean areAlmostEqual(String s1, String s2) {
   9 v# Y+ J1 X% X1 Y3 L7 n& [' t
3.         List<Integer> differ = new ArrayList<>();
   
4.         for (int i = 0; i < s1.length(); i++) {
   7 l6 v6 P1 q3 ^) k
5.             if (s1.charAt(i) != s2.charAt(i)) {
   
6.                 differ.add(i);
   
7.             }
   * M, b* o2 o1 J$ ^3 ~; f1 p
8.         }
   
9.         return differ.size() == 0 ||
   # k+ j/ \. k! B, r
10.                 (differ.size() == 2 &&
    * |: U; s  n# M# M# e9 v( B
11.                         s1.charAt(differ.get(0)) == s2.charAt(differ.get(1)) &&
    
12.                         s1.charAt(differ.get(1)) == s2.charAt(differ.get(0))
    
13.                 );
    
14.     }
    
15. }

复制代码

No.2 找出星型图的中心节点

解题思路

n 个点 n - 1 条边必然是树。因为是星型图，所以叶子结点的度数均为 1. 只要一个节点在边中出现了两次以上，它必然是中心节点。

代码展示

1. class Solution {
   
2.     public int findCenter(int[][] edges) {
   - \# s0 g& ^( R% v- x1 a: g& Z2 H4 `) a
3.         Set<Integer> set = new HashSet<>();
   3 n4 f9 p/ B5 j7 ?7 }
4.         for (var edge : edges) {
   
5.             for (int e : edge) {
   : W1 h; l7 t4 H  [9 t- s/ P! ~
6.                 if (set.contains(e)) {
   : ]$ |8 ]3 T8 x- q
7.                     return e;
   
8.                 }
     u9 B  c0 Q: h2 m; ~$ ?/ U, _
9.                 set.add(e);
   
10.             }
    
11.         }
    . E6 {& V5 x9 m" i
12.         return -1;
    
13.     }
    9 c4 i) u* d! L& v7 j" i
14. }

复制代码

No.3 最大平均通过率

解题思路

贪心，每次放一个学生进入某一个班级，进入能提升通过率提升地最多的那个班级。

代码展示

1. class Solution {
   
2.     static class Class {
   
3.         int pass;
   
4.         int total;
   ; R8 q$ F# s  ^" A8 e/ \
5. 
   
6.         public Class(int pass, int total) {
   
7.             this.pass = pass;
   
8.             this.total = total;
   
9.         }
   , ]6 E3 ?  |+ W% m' `0 V0 D5 U4 x
10. 
    
11.         double differ() {
    
12.             return (double) (pass + 1) / (total + 1) - (double) pass / total;
    
13.         }
      x7 U7 x( H# D$ K' n
14.     }
    5 g2 [2 }# r; `/ g
15. 
    : g: b- z: X8 L$ ]! s
16.     public double maxAverageRatio(int[][] classes, int extraStudents) {
    
17.         PriorityQueue<Class> heap = new PriorityQueue<>((c1, c2) -> c1.differ() > c2.differ() ? -1 : 1);
    
18.         for (var c : classes) {
    6 U5 F  e. O5 y) V
19.             heap.add(new Class(c[0], c[1]));
    
20.         }
    
21.         for (int i = 0; i < extraStudents; i++) {
    
22.             Class c = heap.poll();
    
23.             heap.add(new Class(c.pass + 1, c.total + 1));
    
24.         }
    
25.         double sum = 0;
    . e. ]: I% S9 x
26.         while (!heap.isEmpty()) {
    ) E% c# ?2 y1 x; s# t
27.             Class c = heap.poll();
    # M2 o1 Z9 ]0 V' X/ x- F) L
28.             sum += (double) c.pass / c.total;
    9 m2 z/ m# |. J9 p3 ~; v
29.         }
    
30.         return sum / classes.length;
    - l- @0 M: [6 y. G  f
31.     }
    4 N: o& P, }2 i+ C; p) {" X
32. }

复制代码

No.4 好子数组的最大分数

解题思路

单调栈，与最大柱状图类似，找到一个值的左右侧第一个比它小的即可。

代码展示

1. class Solution {
   1 p6 B4 b1 ], V
2.     public int maximumScore(int[] nums, int k) {
   3 I8 }3 Q. S0 Z2 u
3.         int[] heap = new int[nums.length + 5];
   - w- k: K( M* ]% v; h
4.         int top = 0;
   6 M) v0 M: c0 k: f  P: h5 w8 a
5.         int res = 0;
   
6.         for (int i = 0; i < nums.length; i++) {
   % K. f+ M5 c; \2 i# t% r" N
7.             while (top > 0 && nums[heap[top]] > nums[i]) {
   $ r/ t) c2 X1 C
8.                 int right = i;
     T; U( o/ z% X) e  u
9.                 int left = top > 1 ? heap[top - 1] : -1;
   7 I/ q3 v$ R; t9 b% s0 X6 v$ u
10.                 if (left < k && right > k) {
    
11.                     res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    3 T, J* K0 Y: [! ~; G2 w' h; a
12.                 }
    5 s, M8 J3 ^7 j7 [) D, c6 N/ s
13.                 top--;
    " m7 [# G) ^+ A, D
14.             }
    
15.             heap[++top] = i;
    
16.         }
    + Q9 u7 g, {: B* G
17.         while (top > 0) {
      q# W" F1 H$ q; ~' U1 Z* ?- c
18.             int right = nums.length;
    : T% t; P9 g* ?0 I4 O' b: w5 N' Q; C
19.             int left = top > 1 ? heap[top - 1] : -1;
    & y5 C- X/ p) E3 U: ?4 {% @: G
20.             if (left < k && right > k) {
    7 K: f" j+ q" }' G2 k
21.                 res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    : c6 F2 k  u) [1 `+ u) K
22.             }
    
23.             top--;
    - ~/ {3 S! j8 Z3 N: r; ]$ S
24.         }
    9 D/ j# t3 r! x
25.         return res;
    5 x7 u! J* L4 q
26.     }
    
27. }

复制代码

联系上岸小助手年糕，参与免费带刷
# k6 W2 M$ ~9 V# u