上岸算法

任何只教知识的课程都是耍流氓

我们直击上岸

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

No.1 重新格式化电话号码

★

解题思路

预处理两种特殊符号之后的字符串根据长度 len 分一下三种情况

len % 3 == 0: 直接拼接

len % 3 == 1: 保留最后四位特殊拼接

len % 3 == 2: 保留最后两位特殊拼接

代码展示

class Solution {
   public String reformatNumber(String number) {
       if (number == null || number.length() == 0) {
           return "";
       }
       int n = number.length();
       StringBuilder tempString = new StringBuilder();
       for (int i = 0; i < n; i++) {
           char c = number.charAt(i);
           if (c == '-' || c == ' ') {
               continue;
           }
           tempString.append(c);
       }
       int tmpSize = tempString.length();
       StringBuilder resString = new StringBuilder();
       if (tmpSize % 3 == 0) {
           for (int i = 0; i < tmpSize; i += 3) {
               resString.append(tempString.charAt(i))
                       .append(tempString.charAt(i + 1))
                       .append(tempString.charAt(i + 2));
               if (i != tmpSize - 3) {
                   resString.append('-');
               }
           }
           return resString.toString();
       }
       else if (tmpSize % 3 == 1) {
           int tmpL = tmpSize - 4;
           for (int i = 0; i < tmpL; i += 3) {
               resString.append(tempString.charAt(i))
                       .append(tempString.charAt(i + 1))
                       .append(tempString.charAt(i + 2))
                       .append('-');
           }
           resString.append(tempString.charAt(tmpL))
                   .append(tempString.charAt(tmpL + 1))
                   .append('-')
                   .append(tempString.charAt(tmpL + 2))
                   .append(tempString.charAt(tmpL + 3));
           return resString.toString();
       }
       else {
           int tmpL = tmpSize - 2;
           for (int i = 0; i < tmpL; i += 3) {
               resString.append(tempString.charAt(i))
                       .append(tempString.charAt(i + 1))
                       .append(tempString.charAt(i + 2))
                       .append('-');
           }
           resString.append(tempString.charAt(tmpL))
                   .append(tempString.charAt(tmpL + 1));
           return resString.toString();
       }
   }
}

No.2 删除子数组的最大得分

★解题思路

同向双指针经典应用

left 指针枚举起点

right指针不断的扩大sunArray的范围

当不满足条件时，移动left指针使得满足条件

代码展示

public int maximumUniqueSubarray(int[] nums) {
       if (nums == null || nums.length == 0) {
           return 0;
       }
       int n = nums.length;
       int res = 0;
       int tmpSum = 0;
       // two point
       // 枚举左端点left，右端点right，记录left ~ right 之间重复字符个数
       int left = 0, right = 0;
       int []counts = new int[10001];
       while (left < n && right < n) {
           int num = nums[right];
           counts[num] += 1;
           tmpSum += num;
           // subArray 存在重复数字，从left开始移除，直到满足条件
           while (left < n && counts[num] > 1) {
               tmpSum -= nums[left];
               counts[nums[left]] -= 1;
               left++;
           }
           res = Math.max(res, tmpSum);
           right++;
       }
       return res;
   }

No.3 跳跃游戏 VI

★解题思路

动态规划加优先队列

数据结构Pair，当前位置的结果值value，当前位置的index

优先队列的堆首是已经到达过位置结果值最大的

判断队首的位置能否调达至当前位置i

代码展示

class Solution {
   static class Pair {
       int value;
       int index;
       Pair(int value, int index) {
           this.value = value;
           this.index = index;
       }
   }
   public int maxResult(int[] nums, int k) {
       if (nums == null || nums.length == 0) {
           return 0;
       }
       int n = nums.length;
       // 单调队列【优先队列】
       PriorityQueue<Pair> queue = new PriorityQueue<>((o1, o2) -> o2.value - o1.value);
       queue.offer(new Pair(nums[0], 0));
       int res = nums[0];

       for (int i = 1; i < n; i++) {
           // 选择一个可到达的目的地中最大的那个跳跃，不满足则出队列
           while (!queue.isEmpty() && i - queue.peek().index > k) {
               queue.poll();
           }
           if (!queue.isEmpty()) {
               res = queue.peek().value + nums[i];
           }
           queue.offer(new Pair(res, i));
       }
       return res;
   }
}

No.4 检查边长度限制的路径是否存在

★解题思路

查询按照距离限制排序，记录在TreeMap，query => index

边集合根据边权重排序

针对每一个查询

代码展示

// 并查集模板
static class UnionFind {
   int[] father;

   UnionFind(int n) {
       father = new int[n];
       for (int i = 0; i < n; i++) {
           father[i] = i;
       }
   }

   public int find(int x) {
       if (x == father[x]) {
           return x;
       }
       return father[x] = find(father[x]);
   }

   public void union(int a, int b) {
       int fatherA = find(a);
       int fatherB = find(b);
       if (fatherA != fatherB) {
           father[fatherA] = fatherB;
       }
   }
}

public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
   // key：query[start, end, limit] value: index
   // 按照距离远近排序，距离从小到大
   TreeMap<int[], Integer> map = new TreeMap<>((o1, o2) -> o1[2] != o2[2] ? o1[2] - o2[2] : 1);
   for (int i = 0; i < queries.length; i++) {
       map.put(queries[i], i);
   }
   // 图的边集合也根据边的权重排序
   Arrays.sort(edgeList, Comparator.comparingInt(o -> o[2]));
   boolean[] res = new boolean[queries.length];
   UnionFind unionFind = new UnionFind(n);
   int index = 0;
   while (!map.isEmpty()) {
       Map.Entry<int[], Integer> curr = map.pollFirstEntry();
       int[] query = curr.getKey();
       int currIn = curr.getValue();
       // 只连接比limit更小的那些边
       while (index < edgeList.length && edgeList[index][2] < query[2]) {
           unionFind.union(edgeList[index][0], edgeList[index][1]);
           index++;
       }
       // 查询两端点是否连通
       res[currIn] = (unionFind.find(query[0]) == unionFind.find(query[1]));
   }
   return res;
}

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

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