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

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

解题思路

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

代码展示

1. class Solution {
   . j5 R: v. J1 f9 d9 Z$ h, w# _! ?, I
2.     public boolean areAlmostEqual(String s1, String s2) {
   
3.         List<Integer> differ = new ArrayList<>();
   ) l7 j( G1 _1 y; Y% v1 X0 o  m1 ]- l
4.         for (int i = 0; i < s1.length(); i++) {
   
5.             if (s1.charAt(i) != s2.charAt(i)) {
   : w( Y  Q4 F9 x2 H2 H0 o
6.                 differ.add(i);
   
7.             }
   
8.         }
   
9.         return differ.size() == 0 ||
   
10.                 (differ.size() == 2 &&
    4 e  X2 j: F, i5 N
11.                         s1.charAt(differ.get(0)) == s2.charAt(differ.get(1)) &&
    $ i% J2 n. D1 b( H* k0 p
12.                         s1.charAt(differ.get(1)) == s2.charAt(differ.get(0))
    ; X' A8 Q. q1 B
13.                 );
    9 H% n8 z0 p+ o7 }( Q
14.     }
    
15. }

复制代码

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

解题思路

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

代码展示

1. class Solution {
   * s  U) S; ?; m' D7 i+ |6 S. n7 C
2.     public int findCenter(int[][] edges) {
   & Z: i, l0 e: t" |( I
3.         Set<Integer> set = new HashSet<>();
   / e* [2 {# G0 i- z4 z; c" h
4.         for (var edge : edges) {
   
5.             for (int e : edge) {
   6 H* @9 [3 m, m0 o
6.                 if (set.contains(e)) {
   ! v3 W% h$ n5 D5 A  n4 Y
7.                     return e;
   ; `; M. ?, S' e1 U0 S
8.                 }
   
9.                 set.add(e);
   
10.             }
    
11.         }
    8 e$ P" }3 ?1 G+ E( V
12.         return -1;
    
13.     }
    
14. }

复制代码

1 }& w' g. g- w# o

No.3 最大平均通过率

解题思路

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

代码展示

1. class Solution {
   ' z! O5 E& U* |$ C
2.     static class Class {
   
3.         int pass;
   
4.         int total;
   0 i" W& g4 T% j, u8 W4 r
5. 
   + f+ e- n3 ^' f  Y& f
6.         public Class(int pass, int total) {
   
7.             this.pass = pass;
   5 E3 e  A* |4 `: U6 A# X. v
8.             this.total = total;
   
9.         }
   
10. 
    ( }" `& M; N2 W4 t6 I
11.         double differ() {
    . ]9 e$ I) }( W& F
12.             return (double) (pass + 1) / (total + 1) - (double) pass / total;
    
13.         }
    * B7 `6 k: G% r' r
14.     }
    
15. 
    + h: L4 i& D, g) n, K
16.     public double maxAverageRatio(int[][] classes, int extraStudents) {
    3 n5 s! F  J; H1 P
17.         PriorityQueue<Class> heap = new PriorityQueue<>((c1, c2) -> c1.differ() > c2.differ() ? -1 : 1);
    $ J1 c! ^- H' c9 A2 f: s
18.         for (var c : classes) {
    7 ]5 x7 K$ R, r+ E1 S
19.             heap.add(new Class(c[0], c[1]));
    
20.         }
    
21.         for (int i = 0; i < extraStudents; i++) {
    
22.             Class c = heap.poll();
    
23.             heap.add(new Class(c.pass + 1, c.total + 1));
    
24.         }
    
25.         double sum = 0;
    ( S- W# ]2 m( L8 y6 e, E' g( g7 y" D
26.         while (!heap.isEmpty()) {
    ' d- M9 z- M- ?+ ~) o% V9 N
27.             Class c = heap.poll();
    : c) u/ Y, Q' Y' j  q
28.             sum += (double) c.pass / c.total;
    
29.         }
    % ~2 u, |6 _+ w3 P1 H$ g* [( Q" e
30.         return sum / classes.length;
    1 [' Y2 y1 {4 v! \
31.     }
    
32. }

复制代码

No.4 好子数组的最大分数
7 c" Q/ ]" J) `

解题思路

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

代码展示

1. class Solution {
   
2.     public int maximumScore(int[] nums, int k) {
   6 J: \- Q: T" w
3.         int[] heap = new int[nums.length + 5];
   
4.         int top = 0;
   
5.         int res = 0;
   
6.         for (int i = 0; i < nums.length; i++) {
   
7.             while (top > 0 && nums[heap[top]] > nums[i]) {
   3 g( q: k4 @% N( M8 H. ~6 S3 `( z
8.                 int right = i;
   
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]]);
    7 H8 L% _. r! |3 P
12.                 }
    ) r7 X6 j3 K( H, C+ g& |
13.                 top--;
    
14.             }
    ' D5 O. ~9 I6 W9 l9 ]. W
15.             heap[++top] = i;
    
16.         }
    
17.         while (top > 0) {
    % E( N9 x, s, w7 F" e  A
18.             int right = nums.length;
    
19.             int left = top > 1 ? heap[top - 1] : -1;
    
20.             if (left < k && right > k) {
      E8 e! F5 v* s2 H
21.                 res = Math.max(res, (right - left - 1) * nums[heap[top]]);
    ! q1 k* H; J& M$ X/ ~. F* k+ X
22.             }
    
23.             top--;
    
24.         }
    9 G0 B* \+ V9 o; N! o
25.         return res;
    
26.     }
    # h% x' I& {; O% T; e! x* G
27. }

复制代码

联系上岸小助手年糕，参与免费带刷
' J* h# Q" k1 v$ @( B6 f