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

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

解题思路

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

代码展示

1. class Solution {
   
2.     public boolean areAlmostEqual(String s1, String s2) {
   
3.         List<Integer> differ = new ArrayList<>();
   , O# O) K( R, Q) B8 j2 G9 `
4.         for (int i = 0; i < s1.length(); i++) {
   : [8 S9 m/ F* m7 K, \* {
5.             if (s1.charAt(i) != s2.charAt(i)) {
   
6.                 differ.add(i);
   1 `8 U* D# ^, q/ @2 B
7.             }
   1 m" ~. b; M7 B# i3 s
8.         }
   
9.         return differ.size() == 0 ||
   7 G- x6 q5 K& v' s
10.                 (differ.size() == 2 &&
    * I' C: K8 V8 x' e/ S
11.                         s1.charAt(differ.get(0)) == s2.charAt(differ.get(1)) &&
    8 C+ e& B$ W: b6 y  U
12.                         s1.charAt(differ.get(1)) == s2.charAt(differ.get(0))
    
13.                 );
    
14.     }
    8 Q# _8 u2 J/ |" q- h
15. }

复制代码

8 I3 l9 E3 E  t6 ]/ P2 B' f

, X7 {- z  P+ o; m4 W

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

解题思路

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

代码展示

1. class Solution {
   # T$ ~+ v8 ~, }
2.     public int findCenter(int[][] edges) {
   
3.         Set<Integer> set = new HashSet<>();
   % ]# T# ], Q* l0 ]# K" N) v
4.         for (var edge : edges) {
   
5.             for (int e : edge) {
   0 `1 F, E+ k( t5 y: I( W0 A
6.                 if (set.contains(e)) {
   8 m8 Z4 P5 o7 L# x
7.                     return e;
   # Y/ O" H; J2 }9 v+ @# D
8.                 }
   
9.                 set.add(e);
   
10.             }
    # ]7 d( f( M/ |
11.         }
    
12.         return -1;
    & m) Z( v- C! b& z* w' V
13.     }
    
14. }

复制代码

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 x, L/ R# b; x- c$ _5 ?
8.             this.total = total;
   
9.         }
   
10. 
    
11.         double differ() {
    
12.             return (double) (pass + 1) / (total + 1) - (double) pass / total;
    ! S) ^: K! \3 _& T: c; E
13.         }
    
14.     }
    . Y, R9 Y" N8 Y3 X/ D! C
15. 
    
16.     public double maxAverageRatio(int[][] classes, int extraStudents) {
    - R) I2 i0 K' b/ M( u3 ?# y7 }
17.         PriorityQueue<Class> heap = new PriorityQueue<>((c1, c2) -> c1.differ() > c2.differ() ? -1 : 1);
    + ^4 j- O0 `% ^
18.         for (var c : classes) {
    & U0 K4 `0 D0 G& w
19.             heap.add(new Class(c[0], c[1]));
    8 u; {9 A( N* e  Y9 `
20.         }
    4 f# X' o5 I9 f
21.         for (int i = 0; i < extraStudents; i++) {
    
22.             Class c = heap.poll();
    
23.             heap.add(new Class(c.pass + 1, c.total + 1));
    - I9 h8 A) \1 X* c
24.         }
    " z+ ]. w; k4 q) L7 N( y* o( i
25.         double sum = 0;
    # k5 Y, Q2 {! @( f' z
26.         while (!heap.isEmpty()) {
    % f* g0 n* H0 ~. H7 v
27.             Class c = heap.poll();
    
28.             sum += (double) c.pass / c.total;
    
29.         }
    0 T- T; l3 r; e) M0 f$ `
30.         return sum / classes.length;
    9 L! u( Z% d, L$ n* m3 R* o
31.     }
    
32. }

复制代码

* i; E8 ~% [" w1 X

No.4 好子数组的最大分数
8 k/ ^1 m' t+ k# {1 Q) @

解题思路

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

代码展示

1. class Solution {
   
2.     public int maximumScore(int[] nums, int k) {
   + n) i4 Z/ D2 D$ D/ p. x
3.         int[] heap = new int[nums.length + 5];
   / g; b4 C4 A# K& r+ ^# e
4.         int top = 0;
   * E2 n* W6 k& F' B
5.         int res = 0;
   0 Q+ S" c# k4 a# U
6.         for (int i = 0; i < nums.length; i++) {
   ! V& B: D$ \# R( p8 l
7.             while (top > 0 && nums[heap[top]] > nums[i]) {
   & J- l) a. a9 y9 G7 h& c4 B0 }# D
8.                 int right = i;
   + {7 L4 J5 d! V" I3 H
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.                 }
    6 z  ?% P3 K2 ]/ l- {- L
13.                 top--;
    
14.             }
    
15.             heap[++top] = i;
    / Q. Q9 _: E2 d. [
16.         }
    , g; B1 q" G9 s$ S! F/ O* H
17.         while (top > 0) {
    % \8 [  l, g! q% d- L* j, R
18.             int right = nums.length;
    
19.             int left = top > 1 ? heap[top - 1] : -1;
    
20.             if (left < k && right > k) {
    5 |* {. [% h1 X! J
21.                 res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    
22.             }
    . ^: l3 Q* l  r( K7 h4 p
23.             top--;
    # }  J3 \2 m% t
24.         }
    9 O" L' A6 u/ q! x) c* Y8 ^$ N
25.         return res;
    
26.     }
    # [* p3 `2 y" b. G
27. }

复制代码

联系上岸小助手年糕，参与免费带刷