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

& n" A% B- i$ e+ j3 D

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

解题思路

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

代码展示

1. class Solution {
   
2.     public boolean areAlmostEqual(String s1, String s2) {
   2 _; P  @$ v# M6 c- j; n* b0 l8 I
3.         List<Integer> differ = new ArrayList<>();
   . \& B$ H. h% T
4.         for (int i = 0; i < s1.length(); i++) {
   
5.             if (s1.charAt(i) != s2.charAt(i)) {
   
6.                 differ.add(i);
   
7.             }
   - M# _8 g1 x% y) _$ n& e+ N0 J9 ^
8.         }
   
9.         return differ.size() == 0 ||
   
10.                 (differ.size() == 2 &&
    
11.                         s1.charAt(differ.get(0)) == s2.charAt(differ.get(1)) &&
    
12.                         s1.charAt(differ.get(1)) == s2.charAt(differ.get(0))
    * ?7 |1 I& U* l! ^7 P' e
13.                 );
    
14.     }
    
15. }

复制代码

5 N. W/ p, b1 M- M+ K

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

解题思路

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

代码展示

1. class Solution {
   $ F4 M( j# r4 @6 t9 \
2.     public int findCenter(int[][] edges) {
   4 S9 I+ n+ w* F! Q
3.         Set<Integer> set = new HashSet<>();
   # J/ `( B. L+ u! s- N  I
4.         for (var edge : edges) {
   ; I4 Y# j# h0 Y
5.             for (int e : edge) {
   9 m$ Z9 n1 _) H2 d
6.                 if (set.contains(e)) {
   
7.                     return e;
   ) T3 M, x) @& A  B7 I6 C
8.                 }
   
9.                 set.add(e);
   
10.             }
    
11.         }
    : A% [% _7 q8 s& z( ~4 a0 j+ O5 |2 w
12.         return -1;
    ' {9 |7 R/ p8 b) h* v+ Z
13.     }
    
14. }

复制代码

No.3 最大平均通过率

解题思路

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

代码展示

1. class Solution {
   : `+ ~+ m8 @" N- d1 H& {5 F2 Y1 B1 E
2.     static class Class {
   2 S6 o' P& X" |$ m
3.         int pass;
   
4.         int total;
   
5. 
   
6.         public Class(int pass, int total) {
   , k' g* F7 R) S
7.             this.pass = pass;
   
8.             this.total = total;
   
9.         }
     v1 o! z) [% v7 N  I
10. 
    
11.         double differ() {
    7 ~& O. D! X3 F. w4 _8 _3 V& [0 ~
12.             return (double) (pass + 1) / (total + 1) - (double) pass / total;
    0 Q6 C. C4 O+ ?& v# e! N3 Y
13.         }
    - K8 e4 F* r1 j; f& F) J) N
14.     }
    
15. 
    ! a' O: L5 E% E* g+ F  w
16.     public double maxAverageRatio(int[][] classes, int extraStudents) {
    
17.         PriorityQueue<Class> heap = new PriorityQueue<>((c1, c2) -> c1.differ() > c2.differ() ? -1 : 1);
    6 T" v; `  m  t3 O
18.         for (var c : classes) {
    4 x. {) C7 T8 e/ e# u  ]( P6 B: Y
19.             heap.add(new Class(c[0], c[1]));
    
20.         }
    7 U- T* o% F; A9 A5 d
21.         for (int i = 0; i < extraStudents; i++) {
    ' ~# I' _) U, g( |
22.             Class c = heap.poll();
    
23.             heap.add(new Class(c.pass + 1, c.total + 1));
    8 A. Z" C. \9 r% N$ x, n% x5 L
24.         }
    
25.         double sum = 0;
    
26.         while (!heap.isEmpty()) {
    
27.             Class c = heap.poll();
    9 f, w5 F) e( u  R- E
28.             sum += (double) c.pass / c.total;
    3 I" m, a  v! l% i$ e
29.         }
    ( `0 [$ x7 F3 u: K1 x/ a# ~
30.         return sum / classes.length;
    
31.     }
    7 }7 J# O) Q6 F0 Q. D5 L( n
32. }

复制代码

3 ~: Q& c* V, A/ _% K( b

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

解题思路

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

代码展示

1. class Solution {
   9 @  N  R$ {' l' q- E- P8 X
2.     public int maximumScore(int[] nums, int k) {
   / C& d( F6 c( `% A! ]7 x- L; ^% h
3.         int[] heap = new int[nums.length + 5];
   5 w$ v( R: M! h
4.         int top = 0;
   
5.         int res = 0;
   
6.         for (int i = 0; i < nums.length; i++) {
   5 B$ k/ U$ o4 ~; p  _; w, ]9 P
7.             while (top > 0 && nums[heap[top]] > nums[i]) {
   
8.                 int right = i;
   ' C, L  A8 \' u: P, E
9.                 int left = top > 1 ? heap[top - 1] : -1;
   
10.                 if (left < k && right > k) {
    
11.                     res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    
12.                 }
    
13.                 top--;
    
14.             }
    
15.             heap[++top] = i;
    ' f0 o1 @7 G& B5 K, X4 W
16.         }
    
17.         while (top > 0) {
    
18.             int right = nums.length;
    
19.             int left = top > 1 ? heap[top - 1] : -1;
    
20.             if (left < k && right > k) {
    ) P8 O1 n2 B0 b- C7 F, d
21.                 res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    : j2 I" y& z0 i& k; y: K
22.             }
    + Y  o9 ^' v/ [8 A
23.             top--;
    $ \! g. [3 ^" T$ n
24.         }
    
25.         return res;
    : [. ]/ s8 j8 h: h% s
26.     }
    
27. }

复制代码

联系上岸小助手年糕，参与免费带刷
5 i& {3 |+ m- Z1 U6 ^