上岸算法

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

我们直击上岸

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

No.1 解码异或后的数组

★ 解题思路

a ^ b = c 则有 a ^ b ^ a = c ^ a 即 b = a ^ c

代码展示

class Solution {
   public int[] decode(int[] encoded, int first) {
       int[] res = new int[encoded.length + 1];
       res[0] = first;
       for (int i = 0; i < encoded.length; i++) {
           // res[i] ^ res[i+1] = encoded[i]
           res[i + 1] = encoded[i] ^ res[i];
       }
       return res;
   }
}

No.2 交换链表中的节点

★解题思路

比较朴素的实现，封装了一个函数，遍历三次链表。

代码展示

class Solution {
   public ListNode swapNodes(ListNode head, int k) {
       int n = 0;
       for (ListNode cur = head; cur != null; cur = cur.next) {
           n++;
       }
       ListNode a = getKthNode(head, k);
       ListNode b = getKthNode(head, n - k + 1);
       int tmp = a.val;
       a.val = b.val;
       b.val = tmp;
       return head;
   }

   ListNode getKthNode(ListNode head, int k) {
       ListNode cur = head;
       for (int i = 0; cur != null; i++, cur = cur.next) {
           if (i == k - 1) {
               return cur;
           }
       }
       return null;
   }
}

No.3 执行交换操作后的最小汉明距离

★解题思路

使用并查集维护集合 —— 一个位置的数字与其他哪些位置的数字可交换。

然后贪心法计数即可。

代码展示

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

class Solution {
   public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
       UnionFind uf = new UnionFind(source.length);
       for (int[] a : allowedSwaps) {
           uf.merge(a[0], a[1]);
       }
       // map[i] 是一个 counter
       // map[i][j] > 0 表示 source[i] 可以通过交换变成 j
       // 使用 map<int,map> 而不是 map<int,set> 的原因是避免 source 有重复数字
       Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
       for (int i = 0; i < source.length; i++) {
           int fi = uf.find(i);
           if (!map.containsKey(fi)) {
               map.put(fi, new HashMap<>());
           }
           Map<Integer, Integer> cnt = map.get(fi);
           cnt.put(source[i], cnt.getOrDefault(source[i], 0) + 1);
           map.put(i, cnt);
       }
       int res = target.length;
       for (int i = 0; i < target.length; i++) {
           Map<Integer, Integer> cnt = map.get(i);
           if (cnt.getOrDefault(target[i], 0) > 0) {
               res--;
               cnt.put(target[i], cnt.get(target[i]) - 1);
           }
       }
       return res;
   }
}

No.4 完成所有工作的最短时间

★解题思路

二分 + 枚举

代码展示

class Solution {
   public int minimumTimeRequired(int[] jobs, int k) {
       // 使用 long 以避免 (l + r) 溢出
       long l = Arrays.stream(jobs).min().getAsInt();
       long r = Arrays.stream(jobs).sum();
       while (l + 1 < r) {
           long mid = (l + r) / 2;
           if (check(jobs, k, mid)) {
               r = mid;
           } else {
               l = mid;
           }
       }
       return (int) (check(jobs, k, l) ? l : r);
   }

   boolean check(int[] jobs, int k, long limit) {
       // 判断 k 个工人能否在 limit 的时限下完成任务
       return dfs(jobs, 0, new int[k], limit);
   }

   // 枚举每个任务分配给哪个工人
   // sum[i] 表示当前 i 工人得到的任务的总工时
   boolean dfs(int[] jobs, int curJob, int[] sum, long limit) {
       if (curJob == jobs.length) {
           return true;
       }
       for (int i = 0; i < sum.length; i++) {
           if (sum[i] + jobs[curJob] <= limit) {
               sum[i] += jobs[curJob];
               if (dfs(jobs, curJob + 1, sum, limit)) {
                   return true;
               }
               sum[i] -= jobs[curJob];
               // 一个很重要的优化
               // sum[i] = 0 表示 curJob 被分给一个新的工人
               // 如果未能在上方 return true, 换一个新工人也不可能达标
               if (sum[i] == 0) {
                   break;
               }
           }
       }
       return false;
   }
}

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

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