上岸算法

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

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

No.1 数组异或操作

★解题思路

比较简单, 一次循环就可以计算出结果.

代码展示

class Solution { 
   public int xorOperation(int n, int start) { 
       int res = 0; 
       for (int i = 0; i < n; i++) { 
           res ^= start + 2 * i; 
       } 
       return res; 
   } 
}

No.2 保证文件名唯一

★ 解题思路

使用一个 Map记录某个文件名的编号即可. 不过需要注意 ["name", "name(1)", "name"] 这种手动创建了 "name(1)"的情况.

代码展示

class Solution { 
   public String[] getFolderNames(String[] names) { 
       Map<String, Integer> cnt = new HashMap<>(); 
       String[] res = new String[names.length]; 
       for (int i = 0; i < names.length; i++) { 
           res[i] = names[i]; 
           int j = 0; 
           if (cnt.containsKey(names[i])) { // 包含, 说明重名, 加编号 
               // 编号不断增加, 直到不重名 (针对上面所说的手动创建 name(1) 的情况) 
               for (j = cnt.get(names[i]); ;j++) { 
                   res[i] = names[i] + "(" + j + ")"; 
                   if (!cnt.containsKey(res[i])) break;  
               } 
           } 
           cnt.put(names[i], j + 1); // names[i] 的编号 
           cnt.put(res[i], 1); // res[i] 的编号 
       } 
       return res; 
   } 
}

No.3 避免洪水泛滥

★解题思路

贪心法, 在当前已经有水的湖泊中, 抽取距离下一次下雨时间最近的湖泊的水. 使用优先队列即可完成这个排序.

由于 LeetCode 不支持 AbstractMap.SimpleEntry, 所以需要自行实现 Map.Entry.

代码展示

class MyEntry<K, V> implements Map.Entry<K, V> { 

   K k; 
   V v; 

   public MyEntry(K rain, V integers) { 
       k = rain; 
       v = integers; 
   } 

   @Override 
   public K getKey() { 
       return k; 
   } 

   @Override 
   public V getValue() { 
       return v; 
   } 

   @Override 
   public V setValue(V value) { 
       v = value; 
       return v; 
   } 
} 

class Solution { 
   public int[] avoidFlood(int[] rains) { 
       // rainTimes[i] 表示湖泊 i 的下雨时间列表 
       Map<Integer,List<Integer>> rainTimes = new HashMap<>(); 
       for (int i = 0; i < rains.length; i++) { 
           if (!rainTimes.containsKey(rains[i])) { 
               rainTimes.put(rains[i], new LinkedList<>()); 
           } 
           rainTimes.get(rains[i]).add(i); 
       } 
       for (int k : rainTimes.keySet()) { 
           rainTimes.get(k).add(0x3f3f3f3f); // 避免优先队列中 get(0) 异常 
       } 
       // 优先队列, 保存当前已经有水的湖泊, 按照下一次下雨的时间排序 
       PriorityQueue<Map.Entry<Integer,List<Integer>>> heap = new PriorityQueue<>((a, b)->a.getValue().get(0) - b.getValue().get(0)); 
       // 集合, 保存当前已经有水的湖泊 
       Set<Integer> hasWater = new HashSet<>(); 
       int[] res = new int[rains.length]; 
       for (int i = 0; i < rains.length; i++) { 
           if (rains[i] > 0) { 
               if (hasWater.contains(rains[i])) { 
                   return new int[]{}; 
               } 
               res[i] = -1; 
               hasWater.add(rains[i]); 
               rainTimes.get(rains[i]).remove(0); // 下过一次雨 
               heap.add(new MyEntry<Integer,List<Integer>>(rains[i], rainTimes.get(rains[i]))); 
           } else { 
               var lake = heap.poll(); 
               if (lake != null) { 
                   res[i] = lake.getKey(); 
                   hasWater.remove(res[i]); 
               } else { 
                   res[i] = 1; // heap 为空说明所有湖泊都没有水, 随便抽一个 
               } 
           } 
       } 
       return res; 
   } 
}

No.4 找到最小生成树里的关键边和伪关键边

★解题思路

如果我们不使用一条边, 最小生成树变大, 那么它就是关键的.

如果我们使用了一条边, 最小生成树不变, 并且它不是关键的, 那么它就是伪关键的.

代码展示

class Edge { 
   int id, a, b, v; 

   public Edge(int id, int a, int b, int v) { 
       this.id = id; 
       this.a = a; 
       this.b = b; 
       this.v = v; 
   } 
} 

class UnionFind { 
   int[] fa; 

   public UnionFind(int n) { 
       fa = new int[n]; 
       Arrays.fill(fa, -1); 
   } 

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

   public void merge(int a, int b) { 
       int Fa = find(a); 
       int Fb = find(b); 
       fa[Fa] = Fb; 
   } 
} 

class Solution { 

   public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) { 
       List<Edge> edgeList = new ArrayList<>(); 
       for (int i = 0; i < edges.length; i++) { 
           int[] e = edges[i]; 
           edgeList.add(new Edge(i, e[0], e[1], e[2])); 
       } 
       edgeList.sort((a, b)->a.v-b.v); 
       int mst = calcMST(n, edgeList, -1, -1); // 真正的最小生成树 
       List<List<Integer>> res = new ArrayList<>(); 
       res.add(new ArrayList<>()); 
       res.add(new ArrayList<>()); 
       for (int i = 0; i < edges.length; i++) { 
           int t1 = calcMST(n, edgeList, i, -1); // 不使用 i 构造最小生成树 
           int t2 = calcMST(n, edgeList, -1, i); // 必使用 i 构造最小生成树 
           if (t1 != mst) { // 不使用, MST变大, 关键边 
               res.get(0).add(i); 
           } else if (t2 == mst) { // 使用, MST不变, 且不是关键边, 则是伪关键边 
               res.get(1).add(i); 
           } 
       } 
       return res; 
   } 

   private int calcMST(int n, List<Edge> edgeList, int forbidden, int must) { 
       // 不使用 forbidden, 而必须使用 must 构造最小生成树 
       UnionFind uf = new UnionFind(n); 
       int res = 0; 
       int cnt = 0; 
       if (must >= 0) { 
           cnt++; 
           for (var e : edgeList) { 
               if (e.id == must) { 
                   res += e.v; 
                   uf.merge(e.a, e.b); 
                   break; 
               } 
           } 
       } 
       for (var e : edgeList) { 
           if (e.id == forbidden || e.id == must) { 
               continue; 
           } 
           int fa = uf.find(e.a); 
           int fb = uf.find(e.b); 
           if (fa != fb) { 
               uf.merge(fa, fb); 
               cnt++; 
               res += e.v; 

           } 
           if (cnt == n - 1) return res; 
       } 
       return 0x3f3f3f3f; 
   } 
}

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

上岸科技，一家位于西雅图致力于帮助北美小伙伴们上岸的团体。

团队主要由一群怀揣情怀于美国高校毕业的一线IT公司工程师构成。我们坚持采用小班课形式，并结合大量”面试式“和”白板“的教学和交流形式，最终帮助大家提升求职成功概率同时大大减少刷题的痛苦。

正如我们的信仰：我们教的是如何上岸而不仅是算法。