上岸算法 ,任何只教知识的课程都是耍流氓

我们直击上岸，关注我们，第一时间获得大厂面试真题讲解

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

解题思路

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

代码展示

**classSolution** {
    **public** boolean **areAlmostEqual**(String s1, String s2) {
        List<Integer> differ = **new** ArrayList<>();
        **for** (**int** i = 0; i < s1.length(); i++) {
            **if** (s1.charAt(i) != s2.charAt(i)) {
                differ.**add**(i);
            }
        }
        **return** differ.size() == 0 ||
                (differ.size() == 2 &&
                        s1.charAt(differ.**get**(0)) == s2.charAt(differ.**get**(1)) &&
                        s1.charAt(differ.**get**(1)) == s2.charAt(differ.**get**(0))
                );
    }
}

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

解题思路

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

代码展示

**classSolution** {
    **publicintfindCenter**(**int**[][] edges) {
        Set<Integer> **set** = **new** HashSet<>();
        **for** (**var** edge : edges) {
            **for** (**int** e : edge) {
                **if** (**set**.contains(e)) {
                    **return** e;
                }
                **set**.**add**(e);
            }
        }
        **return**-1;
    }
}

No.3最大平均通过率

解题思路

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

代码展示

class Solution { 
   static class Class { 
       int pass; 
       int total; 

       public Class(int pass, int total) { 
           this.pass = pass; 
           this.total = total; 
       } 

       double differ() { 
           return (double) (pass + 1) / (total + 1) - (double) pass / total; 
       } 
   } 

   public double maxAverageRatio(int[][] classes, int extraStudents) { 
       PriorityQueue<Class> heap = new PriorityQueue<>((c1, c2) -> c1.differ() > c2.differ() ? -1 : 1); 
       for (var c : classes) { 
           heap.add(new Class(c[0], c[1])); 
       } 
       for (int i = 0; i < extraStudents; i++) { 
           Class c = heap.poll(); 
           heap.add(new Class(c.pass + 1, c.total + 1)); 
       } 
       double sum = 0; 
       while (!heap.isEmpty()) { 
           Class c = heap.poll(); 
           sum += (double) c.pass / c.total; 
       } 
       return sum / classes.length; 
   } 
}

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

解题思路

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

代码展示

class Solution { 
   public int maximumScore(int[] nums, int k) { 
       int[] heap = new int[nums.length + 5]; 
       int top = 0; 
       int res = 0; 
       for (int i = 0; i < nums.length; i++) { 
           while (top > 0 && nums[heap[top]] > nums[i]) { 
               int right = i; 
               int left = top > 1 ? heap[top - 1] : -1; 
               if (left < k && right > k) { 
                   res = Math.max(res, (right - left - 1) * nums[heap[top]]); 
               } 
               top--; 
           } 
           heap[++top] = i; 
       } 
       while (top > 0) { 
           int right = nums.length; 
           int left = top > 1 ? heap[top - 1] : -1; 
           if (left < k && right > k) { 
               res = Math.max(res, (right - left - 1) * nums[heap[top]]); 
           } 
           top--; 
       } 
       return res; 
   } 
}