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

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

解题思路

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

代码展示

1. class Solution {
   
2.     public boolean areAlmostEqual(String s1, String s2) {
   2 N0 K  E* l! V7 T, \
3.         List<Integer> differ = new ArrayList<>();
   8 R; _  h% c5 Q7 g7 n; j
4.         for (int i = 0; i < s1.length(); i++) {
   
5.             if (s1.charAt(i) != s2.charAt(i)) {
   2 _7 g! d# L4 K
6.                 differ.add(i);
   
7.             }
   
8.         }
   
9.         return differ.size() == 0 ||
   # ]5 y8 N$ [4 _/ l$ e" O9 M
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.                 );
    4 b; W+ c% C0 P) c& l1 l! K
14.     }
    , q9 r8 `6 \1 z6 e
15. }

复制代码

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

解题思路

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

代码展示

1. class Solution {
   ( I5 Y; K/ U5 Z9 L% }5 Q3 u
2.     public int findCenter(int[][] edges) {
   1 S1 |9 J5 g1 E9 ~% c  k
3.         Set<Integer> set = new HashSet<>();
   
4.         for (var edge : edges) {
   , Z* ~7 K6 _2 C5 A- X# L
5.             for (int e : edge) {
   ) _1 Y: p* R4 q% J
6.                 if (set.contains(e)) {
   - z# \& o9 A7 U3 L0 B1 ~
7.                     return e;
   
8.                 }
   
9.                 set.add(e);
   
10.             }
    # E/ V2 E- I$ [: N" _
11.         }
    
12.         return -1;
    " }3 W5 d2 f: W
13.     }
    
14. }

复制代码

" c9 f) n6 D% J, O+ m2 C

No.3 最大平均通过率

解题思路

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

代码展示

1. class Solution {
   
2.     static class Class {
   
3.         int pass;
   
4.         int total;
   
5. 
   
6.         public Class(int pass, int total) {
   
7.             this.pass = pass;
   
8.             this.total = total;
   
9.         }
   0 h1 H1 T0 u5 V! q
10. 
    
11.         double differ() {
    
12.             return (double) (pass + 1) / (total + 1) - (double) pass / total;
    
13.         }
    
14.     }
    ; a; @# F/ ?( x* s% e; M+ M$ r
15. 
    
16.     public double maxAverageRatio(int[][] classes, int extraStudents) {
    3 K9 }" k+ z8 R& {# |
17.         PriorityQueue<Class> heap = new PriorityQueue<>((c1, c2) -> c1.differ() > c2.differ() ? -1 : 1);
    
18.         for (var c : classes) {
    
19.             heap.add(new Class(c[0], c[1]));
    4 m% C( E. W- g1 l' l
20.         }
    : ?9 y; d, T( z. x6 U3 n- b) X
21.         for (int i = 0; i < extraStudents; i++) {
    ) v) ]# M. |- N# S  j) `( s1 d
22.             Class c = heap.poll();
    
23.             heap.add(new Class(c.pass + 1, c.total + 1));
    + W  x' t; Q% ]/ L' o$ D0 m
24.         }
    % V0 t: X$ r  {& [# b# r6 A
25.         double sum = 0;
    1 u! y& K1 e& b! [* f/ w5 b
26.         while (!heap.isEmpty()) {
    
27.             Class c = heap.poll();
    ' f" c' H2 Y7 B0 `  c) u
28.             sum += (double) c.pass / c.total;
    $ H# W' N* e5 D' u* g/ J  H# ^+ X
29.         }
    & n4 b! E7 W  R. l) c) d
30.         return sum / classes.length;
    % l2 x4 y5 s2 x. W; W/ H1 G
31.     }
    ) s$ _9 q& u. N2 V; g
32. }

复制代码

No.4 好子数组的最大分数
9 z$ ?; c3 N( E1 T' S4 O

解题思路

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

代码展示

1. class Solution {
   ( F" J0 ?1 x: O1 r+ P0 z. f
2.     public int maximumScore(int[] nums, int k) {
   
3.         int[] heap = new int[nums.length + 5];
   4 Z* V- \) o4 I
4.         int top = 0;
   2 O$ d9 c* U4 w
5.         int res = 0;
   
6.         for (int i = 0; i < nums.length; i++) {
   
7.             while (top > 0 && nums[heap[top]] > nums[i]) {
   8 |0 v6 O* {4 y) ~/ Q1 q# H# X2 a
8.                 int right = i;
   
9.                 int left = top > 1 ? heap[top - 1] : -1;
   ; f( l* `4 e6 F$ k0 ]; E
10.                 if (left < k && right > k) {
    ' `( G5 X% E2 E9 Z2 M3 M
11.                     res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    ; ^6 k! L- T, {$ ]
12.                 }
    7 c+ k7 x0 A( g( b" T
13.                 top--;
    8 y; o6 w% M+ O7 D' N
14.             }
    
15.             heap[++top] = i;
    # P6 X) a( O# s- ~+ y% o! [. m
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) {
    
21.                 res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    $ |: |0 x: p- U, ~* o. r$ R
22.             }
    
23.             top--;
    
24.         }
    
25.         return res;
    
26.     }
    
27. }

复制代码

联系上岸小助手年糕，参与免费带刷
; m& \. l9 H; \2 r, `/ i