上岸算法

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

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

No.1 二进制矩阵中的特殊位置

★ 解题思路

先统计每一行, 每一列有多少个 1

然后枚举每个位置, 若该位置是 1 且当前行和当前列中的 1 的数量都是 1, 则是特殊位置.

代码展示

class Solution {
   public int numSpecial(int[][] mat) {
       if (mat.length == 0)
           return 0;
       int[] row = new int[mat.length];
       int[] col = new int[mat[0].length];
       for (int i = 0; i < mat.length; i++) {
           for (int j = 0; j < mat[0].length; j++) {
               row[i] += mat[i][j];
               col[j] += mat[i][j];
           }
       }
       int res = 0;
       for (int i = 0; i < mat.length; i++) {
           for (int j = 0; j < mat[0].length; j++) {
               if (row[i] == 1 && col[j] == 1 && mat[i][j] == 1)
                   res++;
           }
       }
       return res;
   }
}

九月福利——BQ的不完全解答

活动开启倒计时~~

No.2 统计不开心的朋友

★

解题思路

枚举每一对 pair, 判断是否有人不开心即可.

代码展示

class Solution {
   public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
       // rank[i][j] 表示在 i 的喜欢列表里, j 的排名, 用于比较
       int[][] rank = new int[n][n];
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n - 1; j++) {
               rank[i][preferences[i][j]] = j;
           }
       }

       Set<Integer> set = new HashSet<>();
       for (int i = 0; i < pairs.length; i++) {
           for (int j = i + 1; j < pairs.length; j++) {
               // 一对 pair 最多造成 4 个人不开心 (为了避免重复计数, 使用 set)
               if (helper(pairs[i][0], pairs[i][1], pairs[j][0], pairs[j][1], rank))
                   set.add(pairs[i][0]);
               if (helper(pairs[i][1], pairs[i][0], pairs[j][0], pairs[j][1], rank))
                   set.add(pairs[i][1]);
               if (helper(pairs[j][0], pairs[j][1], pairs[i][0], pairs[i][1], rank))
                   set.add(pairs[j][0]);
               if (helper(pairs[j][1], pairs[j][0], pairs[i][0], pairs[i][1], rank))
                   set.add(pairs[j][1]);
           }
       }

       return set.size();
   }

   // 判断 x 是否不开心
   private boolean helper(int x, int y, int u, int v, int[][] rank) {
       return (rank[x][u] < rank[x][y] && rank[u][x] < rank[u][v])
               || (rank[x][v] < rank[x][y] && rank[v][x] < rank[v][u]);
   }
}

九月新课——上岸算法小班免费试听

No.3 连接所有点的最小费用

★ 解题思路

最小生成树问题. 使用 Kruskal 算法即可解决. (排序 + 并查集)

代码展示

class Solution {
   public int minCostConnectPoints(int[][] points) {
       // [from, to, length]
       List<int[]> edges = new ArrayList<>();
       for (int i = 0; i < points.length; i++) {
           for (int j = i + 1; j < points.length; j++) {
               edges.add(new int[]{i, j, distance(points[i], points[j])});
           }
       }

       edges.sort(Comparator.comparingLong(a -> a[2]));

       int res = 0;
       UnionFind uf = new UnionFind(points.length);
       for (int[] edge : edges) {
           if (uf.merge(edge[0], edge[1]))
               res += edge[2];
       }

       return res;
   }

   private int distance(int[] a, int[] b) {
       return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
   }
}

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]);
   }

   // 合并 a 和 b 所在集合, 若成功合并, 返回 true
   // 若 a 和 b 原本就属于同一集合, 返回 false
   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;
}

No.4 检查字符串是否可以通过排序子字符串得到另一个字符串

★解题思路

详解见代码备注。

代码展示

class Solution {
   public boolean isTransformable(String s, String t) {
       // 非法情况特判
       int[] cnt1 = new int[10];
       int[] cnt2 = new int[10];
       for (int i = 0; i < s.length(); i++) {
           cnt1[s.charAt(i) - '0']++;
           cnt2[t.charAt(i) - '0']++;
       }
       for (int i = 0; i < 10; i++) {
           if (cnt1[i] != cnt2[i])
               return false;
       }

       Arrays.fill(cnt1, 0);
       Arrays.fill(cnt2, 0);
       for (int i = 0; i < s.length(); i++) {
           cnt1[s.charAt(i) - '0']++;
           cnt2[t.charAt(i) - '0']++;
           // maxChar 表示 s 中最大的数量少于 t 的字符
           // minChar 表示 t 中最小的数量少于 s 的字符
           int maxChar = -1, minChar = -1;
           for (int j = 0; j <= 9; j++) {
               if (cnt1[j] < cnt2[j]) maxChar = j;
           }
           for (int j = 9; j >= 0; j--) {
               if (cnt2[j] < cnt1[j]) minChar = j;
           }
           // 若 maxChar > minChar 则无法排序
           if (maxChar != -1 && maxChar > minChar) {
               return false;
           }
       }
       return true;
   }
}

九月新课——项目实战小班免费试听

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

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