上岸算法

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

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

No.1 好数对的数目

★解题思路

题目数据范围较小, 直接使用 for 循环求解即可通过. 时间复杂度 o(n^2), 空间复杂度 o(1).

代码展示

class Solution {
   public int numIdenticalPairs(int[] nums) {
       int n = nums.length;
       int res = 0;
       for (int i = 0; i < n; i++) {
           for (int j = i + 1; j < n; j++) {
               res += nums[i] == nums[j] ? 1 : 0;
           }
       }
       return res;
   }
}

还可以借助 HashMap 实现时空复杂度均为 o(n) 的解法.

No.2 仅含1的子串数

★解题思路

注意子串的概念: 下标必须是连续的.

我们找到每一段最长的连续的 1, 假设长度为 n. 这一段连续的 1 的子串数量即: n * (n + 1) / 2

代码展示

class Solution {
   public int numSub(String s) {
       final long mod = 1000000007L;
       long res = 0;
       int i = 0;
       while (true) {
           while (i < s.length() && s.charAt(i) != '1') i++;
           if (i >= s.length()) {
               break;
           }
           int j = i;
           while (j < s.length() && s.charAt(j) == '1') j++;
           // [i, j) 是一段连续的 1, 且 s[i-1] 和 s[j] 是 0 (或者边界)
           res += (long)(j - i + 1) * (j - i) / 2;
           res %= mod;
           i = j + 1;
       }
       return (int)res;
   }
}

No.3 概率最大的路径

★解题思路

最短路问题, 把边长改成了概率而已. 使用 Dijkstra 算法即可通过.

代码展示

class Node {
   public int id;
   public double prob;

   public Node(int id, double prob) {
       this.id = id;
       this.prob = prob;
   }
}

class Solution {
   public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
       Map<Integer, List<Node>> neighbors = new HashMap<>();
       for (int i = 0; i < n; i++) {
           neighbors.put(i, new ArrayList<>());
       }
       for (int i = 0; i < edges.length; i++) {
           int a = edges[i][0], b = edges[i][1];
           double p = succProb[i];
           neighbors.get(a).add(new Node(b, p));
           neighbors.get(b).add(new Node(a, p));
       }

       Map<Integer, Double> res = new HashMap<>();
       Set<Integer> calculated = new HashSet<>();
       PriorityQueue<Node> heap = new PriorityQueue<>((n1, n2) -> Double.compare(n2.prob, n1.prob));
       heap.add(new Node(start, 1.0));
       while (!heap.isEmpty()) {
           Node cur = heap.poll();
           if (calculated.contains(cur.id)) {
               continue;
           }
           res.put(cur.id, cur.prob);
           calculated.add(cur.id);
           for (Node nxt : neighbors.get(cur.id)) {
               double newProb = cur.prob * nxt.prob;
               if (newProb > res.getOrDefault(nxt.id, 0.0)) {
                   res.put(nxt.id, newProb);
                   heap.add(new Node(nxt.id, newProb));
               }
           }
       }
       return res.getOrDefault(end, 0.0);
   }
}

No.4 服务中心的最佳位置

★解题思路

Geometric median, 使用 Weiszfeld's algorithm 迭代计算即可.

代码展示

class Solution {
   final int iter = 1000;

   public double getMinDistSum(int[][] positions) {
       double x = 0, y = 0;
       int n = positions.length;
       if (n == 1) {
           return 0;
       }
       for (var pos : positions) {
           x += pos[0];
           y += pos[1];
       }
       x /= n;
       y /= n;

       double nx = x + 1, ny = y + 1;
       for (int i = 0; i < iter; i++) {
           nx = ny = 0;
           double frac = 0;
           for (var pos : positions) {
               double d = Math.sqrt(Math.pow(pos[0] - x, 2.0) + Math.pow(pos[1] - y, 2.0));
               if (d == 0) continue;
               nx += pos[0] / d;
               ny += pos[1] / d;
               frac += 1 / d;
           }
           if (frac == 0) return 0; // 说明所有点都在相同的位置
           nx /= frac;
           ny /= frac;
           x = nx;
           y = ny;
       }

       double res = 0;
       for (var pos : positions) {
           double dx = pos[0] - x, dy = pos[1] - y;
           res += Math.sqrt(dx * dx + dy * dy);
       }
       return res;
   }
}

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

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

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

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