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

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

解题思路

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

代码展示

1. class Solution {
   5 }$ ]6 A) Q+ o$ H+ h% A
2.     public boolean areAlmostEqual(String s1, String s2) {
   - k. p& a& i# U& w% R
3.         List<Integer> differ = new ArrayList<>();
   0 ~& j- V. K+ j1 Q- s9 z* \: x6 u
4.         for (int i = 0; i < s1.length(); i++) {
     B6 e) ?* a. ?' p$ {" b; R
5.             if (s1.charAt(i) != s2.charAt(i)) {
   / u1 n& ]) d8 c9 f
6.                 differ.add(i);
   
7.             }
   + i6 V) R* e/ ^( w* t6 C) T# s
8.         }
     z: o! y$ p( X# T) [$ m3 A
9.         return differ.size() == 0 ||
   
10.                 (differ.size() == 2 &&
    9 L: ~% _' a# N" @( {9 K5 x  ~
11.                         s1.charAt(differ.get(0)) == s2.charAt(differ.get(1)) &&
    2 V. `3 H+ d; V# i
12.                         s1.charAt(differ.get(1)) == s2.charAt(differ.get(0))
    ! W) ?. A; g; b; i" @0 q3 E( w
13.                 );
    
14.     }
    
15. }

复制代码

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

解题思路

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

代码展示

1. class Solution {
   
2.     public int findCenter(int[][] edges) {
   6 m* k0 M( q4 O1 n0 D
3.         Set<Integer> set = new HashSet<>();
   ' y$ L8 n8 a7 N" m" @; L9 ~
4.         for (var edge : edges) {
   2 D/ D9 ]1 a% p" Y8 Z
5.             for (int e : edge) {
   % w! I0 F2 p* q3 \5 ~/ u0 h
6.                 if (set.contains(e)) {
   , C/ G2 ]1 c+ H$ G4 l
7.                     return e;
   
8.                 }
   - \% U% r$ ?8 H+ Z$ ~9 G6 X
9.                 set.add(e);
   
10.             }
    & G  Y* v! D' E! [
11.         }
    + ~7 O/ I* D3 @, J. W
12.         return -1;
    7 t! Q+ F" b1 R1 f. n, Q1 _1 a2 k
13.     }
    
14. }

复制代码

No.3 最大平均通过率

解题思路

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

代码展示

1. class Solution {
   
2.     static class Class {
   
3.         int pass;
   3 j+ [' ^& o4 I6 Z
4.         int total;
   $ y: d0 ?2 w# C+ b2 F0 ]5 h
5. 
   $ n- w7 J6 {8 A- \' T/ |
6.         public Class(int pass, int total) {
   ) X9 H) e+ o7 a2 t
7.             this.pass = pass;
   , ?$ D+ g. h% f
8.             this.total = total;
   % b0 P$ }. l! I- }0 K/ A4 r+ n
9.         }
   3 V8 }( ]7 q- q! w, u" C
10. 
    ; L+ h7 U$ N2 u1 f+ ~$ g
11.         double differ() {
    
12.             return (double) (pass + 1) / (total + 1) - (double) pass / total;
    8 P9 H3 x6 v- u7 g
13.         }
    
14.     }
    0 c8 E  L. E% v% e
15. 
    
16.     public double maxAverageRatio(int[][] classes, int extraStudents) {
    . ^! ?5 J4 l! \  _& N/ j
17.         PriorityQueue<Class> heap = new PriorityQueue<>((c1, c2) -> c1.differ() > c2.differ() ? -1 : 1);
    
18.         for (var c : classes) {
    ; I2 |, p. D% S, I
19.             heap.add(new Class(c[0], c[1]));
    
20.         }
    
21.         for (int i = 0; i < extraStudents; i++) {
    & |2 A% o$ f* k0 \4 v5 D
22.             Class c = heap.poll();
    
23.             heap.add(new Class(c.pass + 1, c.total + 1));
    ; M7 u+ C5 R/ i" G$ n+ H
24.         }
    
25.         double sum = 0;
    * }3 p% ~, J( B
26.         while (!heap.isEmpty()) {
    
27.             Class c = heap.poll();
    
28.             sum += (double) c.pass / c.total;
    
29.         }
    
30.         return sum / classes.length;
    3 V7 B8 f/ J- B; l  s! x
31.     }
      i( H! U# @6 `/ ^% c6 [' p7 n
32. }

复制代码

/ x, x; H0 Y& l( a8 @) i" D

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

解题思路

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

代码展示

1. class Solution {
   
2.     public int maximumScore(int[] nums, int k) {
   # o( \' z' l1 K9 L1 u* c, E4 r( x
3.         int[] heap = new int[nums.length + 5];
   8 s# f& X/ W1 G
4.         int top = 0;
   . c: O1 B- Y# k2 |! O( C: u
5.         int res = 0;
   ; e7 R3 j* \0 U, G' |1 s9 `. n/ D
6.         for (int i = 0; i < nums.length; i++) {
   
7.             while (top > 0 && nums[heap[top]] > nums[i]) {
   
8.                 int right = i;
   $ \) I! g9 H6 W3 g4 F
9.                 int left = top > 1 ? heap[top - 1] : -1;
   
10.                 if (left < k && right > k) {
    9 A) ~  ^; _/ _- [, g7 o
11.                     res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    7 V5 O; C( M9 s1 i2 a
12.                 }
    . {7 V  _" X+ F5 T# g
13.                 top--;
    
14.             }
    
15.             heap[++top] = i;
    
16.         }
    
17.         while (top > 0) {
    6 h" S  s7 i1 R
18.             int right = nums.length;
    6 q+ b' C- T2 o5 }$ Y
19.             int left = top > 1 ? heap[top - 1] : -1;
    ( k) r2 e: S: ~" K0 `+ Y
20.             if (left < k && right > k) {
    
21.                 res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    3 k  f* h: o% ?" {
22.             }
    " u8 E/ ^9 p' Q: p5 a4 k* X/ j
23.             top--;
    - Z. l$ h5 H  J+ g- Z8 U: w
24.         }
    
25.         return res;
    
26.     }
    
27. }

复制代码

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