上岸算法

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

我们直击上岸

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

No.1 设计Goal解析器

★解题思路

详情见下方代码注解。

代码展示

class Solution {
   public String interpret(String command) {
       command = command.replaceAll("\\(\\)", "o");
       command = command.replaceAll("\\(al\\)", "al");
       return command;
   }
}

No.2 K和数对的最大数目

★解题思路

使用 Map 统计每个数值的出现次数, 然后匹配即可. 为了避免重复, Map 中储存大于 k/2 的, 而之后枚举的是小于 k/2 的.

代码展示

class Solution {
   public int maxOperations(int[] nums, int k) {
       Map<Integer, Integer> count = new HashMap<>();
       int halfk = 0;
       for (int num : nums) {
           if (num * 2 > k) {
               count.put(num, count.getOrDefault(num, 0) + 1);
           } else if (num * 2 == k) {
               halfk++;
           }
       }
       Arrays.sort(nums);
       int res = halfk / 2;
       for (int num : nums) {
           if (num * 2 > k) {
               break;
           }
           if (count.getOrDefault(k - num, 0) > 0) {
               res++;
               count.put(k - num, count.get(k - num) - 1);
           }
       }
       return res;
   }
}

No.3 连接连续二进制数字

★解题思路

从 n 到 1 逐个拼接计算加和即可. 往一个数字 i 的二进制前拼接一个 0 不影响大小, 拼接一个 1 相当于加上一个 2 的幂.

代码展示

class Solution {
   final int mod = 1000000007;

   public int concatenatedBinary(int n) {
       int res = 0;
       int pow2 = 1;
       for (int i = n; i >= 1; i--) {
           for (int j = i; j > 0; j >>= 1) {
               if ((j & 1) == 1) {
                   res = (res + pow2) % mod;
               }
               pow2 = (pow2 << 1) % mod;
           }
       }
       return res;
   }
}

No.4 最小不兼容性

★解题思路

解决该题目的通用方法就是深度优先搜索. 分别枚举每个数字要放到哪个组中.

但是需要加一些优化, 否则会超时.

代码展示

class Solution {
   int res, k, cnt;
   int[] idx, latest, first, nums;

   public int minimumIncompatibility(int[] nums, int k) {
       if (nums.length == k) {
           return 0;
       }
       // 判断无解
       int[] numCnt = new int[17];
       for (int num : nums) {
           if ((++numCnt[num]) > k) {
               return -1;
           }
       }
       Arrays.sort(nums);
       this.k = k;
       this.nums = nums;
       cnt = nums.length / k;
       res = Integer.MAX_VALUE;
       idx = new int[k];
       latest = new int[k];
       first = new int[k];
       dfs(0, 0);
       return res;
   }

   private void dfs(int used, int sum) {
       if (used == nums.length) {
           res = Math.min(res, sum);
           return;
       }
       // 优化点
       if (sum >= res) {
           return;
       }
       // 枚举 nums[used] 放到哪一组中
       for (int i = 0; i < k; i++) {
           if (idx[i] < cnt && (idx[i] == 0 || latest[i] != nums[used])) {
               int newSum = sum;
               if (idx[i] == 0) {
                   first[i] = nums[used];
               } else {
                   newSum -= latest[i] - first[i];
                   newSum += nums[used] - first[i];
               }
               idx[i]++;
               int bak = latest[i];
               latest[i] = nums[used];
               dfs(used + 1, newSum);
               idx[i]--;
               latest[i] = bak;
               // 优化点: 第一个数值, 没有必要继续枚举
               if (idx[i] == 0) {
                   break;
               }
           }
       }
   }
}

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

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