上岸算法

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

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

No.1 Largest Substring Between Two Equal Characters

★ 解题思路

记录每种字符第一次出现的位置即可.

代码展示

class Solution {
   public int maxLengthBetweenEqualCharacters(String s) {
       int[] firstPos = new int[26];
       Arrays.fill(firstPos, -1);
       int res = -1;
       for (int i = 0; i < s.length(); i++) {
           int c = s.charAt(i) - 'a';
           if (firstPos[c] >= 0) {
               // 只要 c 再次出现, 与第一次出现的位置相减即可得到一个字符串
               res = Math.max(res, i - firstPos[c] - 1);
           } else {
               // 记录字符 c 第一次出现的位置
               firstPos[c] = i;
           }
       }
       return res;
   }
}

10月好课备春招——上岸算法小班

No.2 Lexicographically Smallest String After Applying Operations

★ 解题思路

用 BFS 或 DFS 遍历所有情况即可. 然后拿出最小的字符串.

代码展示

class Solution {
   public String findLexSmallestString(String s, int a, int b) {
       // 所有可能的变换情况, 存放于 set
       TreeSet<String> set = new TreeSet<>();
       // dfs 获取所有的变换
       dfs(s, a, b % s.length(), set);
       // 返回字典序最小的
       return set.first();
   }

   private void dfs(String s, int a, int b, TreeSet<String> set) {
       if (set.contains(s)) {
           return;
       }
       set.add(s);

       // 对于 s 有两种变换
       // 1\. 轮转
       dfs(s.substring(s.length() - b) + s.substring(0, s.length() - b), a, b, set);
       // 2\. 累加
       StringBuilder sb = new StringBuilder(s);
       for (int i = 1; i < sb.length(); i += 2) {
           int d = sb.charAt(i) - '0';
           sb.setCharAt(i, (char) ('0' + ((d + a) % 10)));
       }
       dfs(sb.toString(), a, b, set);
   }
}

10月公益带刷活动

No.3 Best Team With No Conflicts

★ 解题思路

排序后使用动态规划, 类似于 LIS 问题.

代码展示

class Solution {
   static class P {
       int score, age;
       public P(int score, int age) {
           this.score = score;
           this.age = age;
       }
   }

   public int bestTeamScore(int[] scores, int[] ages) {
       P[] p = new P[scores.length];
       for (int i = 0; i < p.length; i++) {
           p[i] = new P(scores[i], ages[i]);
       }

       int res = 0;
       // 按照 age 升序排序
       Arrays.sort(p, (a, b) -> (a.age == b.age ? a.score - b.score : a.age - b.age));
       // 动态规划: f[i] 表示选用球员 i 时, 0 ~ i 的球员的最高分数
       // 状态转移: f[i] = f[j] + p[i].score 要求 j < i 且 p[j].score <= p[i].score
       int[] f = new int[scores.length];
       for (int i = 0; i < scores.length; i++) {
           f[i] = p[i].score;
           for (int j = 0; j < i; j++) {
               if (p[j].score <= p[i].score) {
                   f[i] = Math.max(f[i], f[j] + p[i].score);
               }
           }
           res = Math.max(res, f[i]);
       }
       return res;
   }
}

No.4 Graph Connectivity With Threshold

★ 解题思路

如果事先知道所有边, 那么我们就可以使用并查集完成连通性查询了.

所以该问题的重点在于如何获取所有边.

枚举 + 优化.

代码展示

class Solution {
   public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
       UnionFind uf = new UnionFind(n + 1);
       // 枚举公因数 z 和倍数来得到所有的边
       // 小优化: 如果公因数 z 的所有倍数已经被枚举过了
       // 那么不必再枚举 z * 2, z * 3 ... 的公因数
       boolean[] vis = new boolean[n + 1];
       for (int i = threshold + 1; i * 2 <= n; i++) {
           if (vis[i]) {
               continue;
           }
           for (int j = 1; j * i <= n; j++) {
               vis[j * i] = true;
               for (int k = j + 1; k * i <= n; k++) {
                   uf.merge(i * j, i * k);
               }
           }
       }
       // 已经构建好并查集, 查询即可
       List<Boolean> res = new ArrayList<>();
       for (int[] query : queries) {
           res.add(uf.find(query[0]) == uf.find(query[1]));
       }
       return res;
   }
}
class UnionFind {
   public UnionFind(int size) {
       f = new int[size];
       Arrays.fill(f, -1);
   }

   public int find(int x) {
       if (f[x] < 0)
           return x;
       return f[x] = find(f[x]);
   }

   public boolean merge(int a, int b) {
       int fa = find(a);
       int fb = find(b);
       if (fa == fb)
           return false;
       f[fa] = fb;
       return true;
   }

   private int[] f;
}

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

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