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

3 e; g) y; Q9 R
9 Q, f) J) G; c6 A3 ~

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

解题思路

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

代码展示

1. class Solution {
   
2.     public boolean areAlmostEqual(String s1, String s2) {
   4 d9 V* X$ o5 S& ^5 y( w/ k
3.         List<Integer> differ = new ArrayList<>();
   
4.         for (int i = 0; i < s1.length(); i++) {
     c, g& n1 P( ^8 b+ x( r7 t. Z4 d
5.             if (s1.charAt(i) != s2.charAt(i)) {
   
6.                 differ.add(i);
   6 u, ]) Y4 A; R: q( V. g9 Q0 [2 M
7.             }
   
8.         }
   
9.         return differ.size() == 0 ||
   # G1 Y9 k5 p- C
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))
    8 K& t6 G/ S# E& }
13.                 );
    2 c' o' O2 D# [/ B# d: ?
14.     }
    
15. }

复制代码

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

解题思路

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

代码展示

1. class Solution {
   
2.     public int findCenter(int[][] edges) {
   0 N% w+ ~$ l  h3 W  k& K/ t
3.         Set<Integer> set = new HashSet<>();
   
4.         for (var edge : edges) {
   
5.             for (int e : edge) {
   
6.                 if (set.contains(e)) {
   
7.                     return e;
   
8.                 }
   ( s; k/ {3 u: M! i- B  d
9.                 set.add(e);
   
10.             }
    
11.         }
    7 V5 z6 Y: z3 @8 V1 w% i( h
12.         return -1;
    
13.     }
    % S8 U, f% o/ y/ m3 R
14. }

复制代码

No.3 最大平均通过率

解题思路

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

代码展示

1. class Solution {
   " E3 c5 c9 j' b! |
2.     static class Class {
   
3.         int pass;
   # ^( p7 B2 P3 C0 \0 n
4.         int total;
   0 F8 ]3 }0 T1 U3 `6 `; n  M
5. 
   6 s4 E+ p% ?( K0 q( i9 Q+ o
6.         public Class(int pass, int total) {
   # O0 J- R8 A2 A9 e) W  ~* z
7.             this.pass = pass;
   
8.             this.total = total;
   
9.         }
   
10. 
    
11.         double differ() {
    
12.             return (double) (pass + 1) / (total + 1) - (double) pass / total;
    
13.         }
    3 \" V! ~2 ^) ]$ w( v
14.     }
    
15. 
    
16.     public double maxAverageRatio(int[][] classes, int extraStudents) {
    ; v9 U, ~$ b$ S4 v3 L- d1 ?
17.         PriorityQueue<Class> heap = new PriorityQueue<>((c1, c2) -> c1.differ() > c2.differ() ? -1 : 1);
    + k( `6 d' ]! d8 U% S* V4 g6 o
18.         for (var c : classes) {
    
19.             heap.add(new Class(c[0], c[1]));
    
20.         }
    5 i% W! x- Q0 S1 A
21.         for (int i = 0; i < extraStudents; i++) {
    5 o$ t7 s! Z6 q& q
22.             Class c = heap.poll();
    8 }" `7 F% B1 L; v, W
23.             heap.add(new Class(c.pass + 1, c.total + 1));
    
24.         }
    
25.         double sum = 0;
    
26.         while (!heap.isEmpty()) {
    : G* z, \4 d; o( c) E& b0 e
27.             Class c = heap.poll();
    % T. v& T6 v" j. L* a# z0 J6 w
28.             sum += (double) c.pass / c.total;
    
29.         }
    " O6 T% J+ d# ~& P
30.         return sum / classes.length;
    
31.     }
    
32. }

复制代码

( o; j7 }- {: M7 W

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

解题思路

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

代码展示

1. class Solution {
   " q8 B) `$ a+ k! ^" T# S
2.     public int maximumScore(int[] nums, int k) {
   
3.         int[] heap = new int[nums.length + 5];
   
4.         int top = 0;
   
5.         int res = 0;
   4 R( d# z; o4 [) ~
6.         for (int i = 0; i < nums.length; i++) {
   
7.             while (top > 0 && nums[heap[top]] > nums[i]) {
   
8.                 int right = i;
   
9.                 int left = top > 1 ? heap[top - 1] : -1;
   - X0 K- y  I1 ?8 p  B, ^2 N
10.                 if (left < k && right > k) {
      v* }& n: g) x2 t
11.                     res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    
12.                 }
    
13.                 top--;
    
14.             }
    
15.             heap[++top] = i;
    
16.         }
    - J6 V: g! N- _
17.         while (top > 0) {
    % Z4 F9 x& k. L& `* m: M/ a
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]]);
    ! f6 W2 i6 H8 b: ]
22.             }
    . l! J+ p) m: ]' R8 }* ?4 G- D' \$ y
23.             top--;
    ( K# a) C% f3 D6 A+ n
24.         }
    * l3 E( }' P6 R
25.         return res;
    9 y% v7 h  v' q! V/ Z$ p
26.     }
    
27. }

复制代码

联系上岸小助手年糕，参与免费带刷
( Z6 {* p( P( l4 c+ D