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

" H/ h# Y( }/ F: b  m! N

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

解题思路

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

代码展示

1. class Solution {
   
2.     public boolean areAlmostEqual(String s1, String s2) {
   9 Y9 @9 a2 P3 d* ^& e
3.         List<Integer> differ = new ArrayList<>();
   ' {" w. R- i" E1 V* f
4.         for (int i = 0; i < s1.length(); i++) {
   
5.             if (s1.charAt(i) != s2.charAt(i)) {
   
6.                 differ.add(i);
   : w0 \0 ]" [  v8 I- o! B( K
7.             }
   $ b3 d" \5 h( n, S
8.         }
   ( V# D$ r* g6 d0 y* _6 g& }, z
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))
    
13.                 );
    $ D6 a2 x& b* W6 I; t# E5 j* F
14.     }
    
15. }

复制代码

/ c" {3 u" h/ ?. i) K9 K

5 a5 d4 e7 k2 d

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

解题思路

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

代码展示

1. class Solution {
   ; y3 r' `3 C% N7 L3 m
2.     public int findCenter(int[][] edges) {
   3 t9 o2 K, b' N! l# ?5 W) c
3.         Set<Integer> set = new HashSet<>();
   
4.         for (var edge : edges) {
   
5.             for (int e : edge) {
   
6.                 if (set.contains(e)) {
   : N! y1 B# U2 E: G& r9 I* X
7.                     return e;
   + o$ d, B- b4 w+ Z4 o8 w0 n: @0 e
8.                 }
   * a3 D4 @' J( F& u6 ?' U4 ^: y% u9 p
9.                 set.add(e);
   . s5 E  T; q8 [" c$ P. N
10.             }
    
11.         }
    
12.         return -1;
    0 z6 |. Y( K4 _5 S# W2 q' k
13.     }
      d) g1 n8 b5 O+ y
14. }

复制代码

No.3 最大平均通过率

解题思路

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

代码展示

1. class Solution {
   , a5 g0 h  F7 }5 Y. Z
2.     static class Class {
   * X+ E# d0 s. N. Q" ^& `# p
3.         int pass;
   
4.         int total;
   
5. 
   
6.         public Class(int pass, int total) {
   
7.             this.pass = pass;
   
8.             this.total = total;
   ' X1 I% X# [4 o8 d& [1 a" i9 _
9.         }
   9 h# z. J5 r0 n0 v
10. 
    . @; o0 z+ R0 v- [: y0 w
11.         double differ() {
    
12.             return (double) (pass + 1) / (total + 1) - (double) pass / total;
    
13.         }
    
14.     }
    ) I3 X, `2 x1 n+ d/ Q
15. 
    
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) {
    4 S2 O! F# M4 P5 d$ f) m$ I
19.             heap.add(new Class(c[0], c[1]));
    
20.         }
    ( Y: h2 W; n5 a, Z- I7 }
21.         for (int i = 0; i < extraStudents; i++) {
    5 j# B& ~2 r# Q" L' Y6 L
22.             Class c = heap.poll();
    
23.             heap.add(new Class(c.pass + 1, c.total + 1));
    
24.         }
    5 Z# u. J+ @& P" A$ g- V/ Z
25.         double sum = 0;
    
26.         while (!heap.isEmpty()) {
    . R9 r( ^  u! E( X
27.             Class c = heap.poll();
    
28.             sum += (double) c.pass / c.total;
    
29.         }
    . e" o/ m/ y# e
30.         return sum / classes.length;
    & P0 e4 @- F( {0 H' G
31.     }
    
32. }

复制代码

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

解题思路

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

代码展示

1. class Solution {
   
2.     public int maximumScore(int[] nums, int k) {
   - ]4 M( w% n/ g- F) ?# k0 n
3.         int[] heap = new int[nums.length + 5];
   
4.         int top = 0;
   % G3 T5 m: ~. h) ?0 k' K4 O
5.         int res = 0;
   
6.         for (int i = 0; i < nums.length; i++) {
   ) f6 M1 ~9 B" \
7.             while (top > 0 && nums[heap[top]] > nums[i]) {
   
8.                 int right = i;
   1 R2 h" X4 t# \2 G
9.                 int left = top > 1 ? heap[top - 1] : -1;
   
10.                 if (left < k && right > k) {
    7 q$ U, W1 k! ]: X" t
11.                     res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    7 j/ r3 z" p/ B9 e
12.                 }
    
13.                 top--;
    
14.             }
    
15.             heap[++top] = i;
    / v+ I% M: [9 c4 K2 ~2 U9 o2 C, q
16.         }
    
17.         while (top > 0) {
    8 a! E4 g+ c" a4 G
18.             int right = nums.length;
    
19.             int left = top > 1 ? heap[top - 1] : -1;
    
20.             if (left < k && right > k) {
    " z9 q- v! [; s# q" M# @8 V+ O
21.                 res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    0 c7 I; h3 J. l! r( f
22.             }
    
23.             top--;
    
24.         }
    
25.         return res;
    4 E5 o( b1 @/ J, C. D( z( W
26.     }
    
27. }

复制代码

联系上岸小助手年糕，参与免费带刷
+ ^4 O: h7 b) A- M: X. f+ a3 u