上岸算法

死磕100%上岸率的精品小班课

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

No.1 Slowest Key

★解题思路

一次循环即可统计出答案.

代码展示

class Solution { 
   public char slowestKey(int[] releaseTimes, String keysPressed) { 
       char res = 'a'; 
       int len = 0; 
       int prev = 0; 
       for (int i = 0; i < releaseTimes.length; i++) { 
           if (len < releaseTimes[i] - prev || 
                   (len == releaseTimes[i] - prev && keysPressed.charAt(i) > res)) { 
               len = releaseTimes[i] - prev; 
               res = keysPressed.charAt(i); 
           } 
           prev = releaseTimes[i]; 
       } 
       return res; 
   } 
}

No.2 Ariarithmetic Subarrays

★ 解题思路

数据范围较小, 可以直接暴力地每次都取出子树组, 排序, 校验.

代码展示

class Solution { 
   public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) { 
       int m = l.length; 
       List<Boolean> res = new ArrayList<>(); 
       for (int i = 0; i < m; i++) { 
           int[] arr = Arrays.copyOfRange(nums, l[i], r[i] + 1); 
           Arrays.sort(arr); 
           boolean tmp = true; 
           for (int j = 2; j < arr.length; j++) { 
               if (arr[j] - arr[j - 1] != arr[j - 1] - arr[j - 2]) { 
                   tmp = false; 
                   break; 
               } 
           } 
           res.add(tmp); 
       } 
       return res; 
   } 
} 

No.3 Path With Minimum Effort

★解题思路

二分答案

代码展示

class Solution { 
   public int minimumEffortPath(int[][] heights) { 
       // [l, r] 表示当前答案存在的区间 
       int l = 0, r = 1000000; 
       while (l + 1 < r) { 
           int mid = (l + r) / 2; 
           // 校验在不超过 mid 的体力下, 能否到达终点 
           if (check(heights, mid)) { 
               r = mid; 
           } else { 
               l = mid; 
           } 
       } 
       return check(heights, l) ? l : r; 
   } 

   private boolean check(int[][] heights, int limit) { 
       // dfs 判断能否到达终点 
       boolean[][] vis = new boolean[heights.length][heights[0].length]; 
       dfs(0, 0, heights, vis, limit); 
       return vis[heights.length - 1][heights[0].length - 1]; 
   } 

   private void dfs(int x, int y, int[][] heights, boolean[][] vis, int limit) { 
       vis[x][y] = true; 
       int[] dx = {0, 0, 1, -1}; 
       int[] dy = {1, -1, 0, 0}; 
       for (int i = 0; i < 4; i++) { 
           int nx = dx[i] + x; 
           int ny = dy[i] + y; 
           if (nx >= 0 && ny >= 0 && heights.length > nx && heights[0].length > ny  
                   && !vis[nx][ny] && limit >= Math.abs(heights[nx][ny] - heights[x][y])) { 
               dfs(nx, ny, heights, vis, limit); 
           } 
       } 
   } 
}

No.4 Rank Transform of a Matrix

★ 解题思路

并查集求联通分量的概念，去求同属于相同level的组，然后依次去更新每一个组的level。详细见题解注释

代码展示

class Solution { 
   public int[][] matrixRankTransform(int[][] matrix) { 
       int n = matrix.length; 
       int m = matrix[0].length; 
       int[][] result = new int[n][m]; 

       // 记录value => [(x, y), (x1, y1) .....] 
       Map<Integer, List<int[]>> map = new TreeMap<>(); 
       for(int i = 0; i < n; i++){ 
           for(int j = 0; j < m; j++){ 
               int[] point = {i,j}; 
               int value = matrix[i][j]; 
               map.computeIfAbsent(value, k -> new ArrayList<>()); 
               map.get(value).add(point); 
           } 
       } 

       // 初始化当前行和当前列的排名都为 1 
       Map<Integer, Integer> minRow = new HashMap<>(); 
       Map<Integer, Integer> minColumn = new HashMap<>(); 
       for(int i = 0; i < n; i++) { 
           minRow.put(i, 1); 
       } 
        for(int j = 0; j < m; j++){ 
           minColumn.put(j, 1); 
       } 

       for(Integer key : map.keySet()){ 
           List<int[]> points = map.get(key); 
           int pointsSize = points.size(); 
           int[] father = new int[pointsSize]; 
           // 初始化并查集所有点的father关系 
           for(int i = 0; i < pointsSize; i++) { 
               father[i] = i; 
           } 
           // 将至相同的点，并且属于同一行或者同一列的归属在同一个“联通分量”，一样的level 
           for(int i = 0; i < pointsSize; i++){ 
               for(int j = i+1; j < pointsSize; j++){ 
                   int[] a = points.get(i); 
                   int[] b = points.get(j); 
                   if(a[0] ==  b[0] || a[1] == b[1]) { 
                       union(i, j, father); 
                   } 
               } 
           } 
           // 记录 value ==> 同属于一个“联通分量”的所有坐标点 
           HashMap<Integer, List<int[]>> group = new HashMap<>(); 
           for(int i = 0; i < pointsSize; i++){ 
               int p = find(i, father); 
               group.computeIfAbsent(p, k -> new ArrayList<>()); 
               group.get(p).add(points.get(i)); 
           } 

           // 给每一个”联通分量“设置答案 
           for(Integer gKey : group.keySet()){ 
               int max = 0; 
               List<int[]> sublist = group.get(gKey); 
               // 计算得出当前这个"联通分量"(组)的所属等级 
               for(int[] p : sublist){ 
                   int x = p[0]; 
                   int y = p[1]; 
                   max = Math.max(max, Math.max(minRow.get(x), minColumn.get(y))); 
               } 

               // 更新属于这个组内所有的元素的等级，并且将当前row and column最大level + 1 
               for(int[] point : sublist){ 
                   int x = point[0]; 
                   int y = point[1]; 
                   result[x][y] = max; 
                   minRow.put(x, max+1); 
                   minColumn.put(y, max+1); 
               } 
           } 
       } 
       return result; 
   } 

   // 并查集 
   void union(int a, int b, int[] father){ 
       int fatherA = find(a, father); 
       int fatherB = find(b, father); 
       father[fatherB] = fatherA; 
   } 
   // find函数 
   int find(int x, int[] father){ 
       if (x == father[x]) { 
           return x; 
       } 
       int fatherX = father[x]; 
       return father[x] = find(fatherX, father); 
   } 
}

    杭州上岸算法网络科技有限公司

上岸算法网络科技有限公司是一家致力于用高质量，高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量，高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟，用最高效，经济，合理的方式帮助更多学生快速找到梦寐以求的工作。