上岸算法

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

我们直击上岸

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

No.1 卡车上的最大单元数

★解题思路

优先使用容量大的箱子即可。

代码展示

class Solution {
   public int maximumUnits(int[][] boxTypes, int truckSize) {
       Arrays.sort(boxTypes, (a, b) -> (b[1] - a[1]));
       int res = 0;
       for (var box : boxTypes) {
           int cnt = Math.min(truckSize, box[0]);
           res += cnt * box[1];
           truckSize -= cnt;
       }
       return res;
   }
}

上岸全栈项目小班

教学特色：

2021春招版,新增项目,手把手带大家完成个性化项目

5人小班化教学,理论课+实践课双管齐下,吃透项目细节

一个月内全面了解全栈开发核心概念和流程

结课后一对一能力背景分析,了解自身求职进程

No.2 大餐计数

★解题思路

枚举即可。使用一个 Map 记录每种美味度对应的菜品数量。

代码展示

class Solution {
   public int countPairs(int[] deliciousness) {
       int res = 0, mod = 1000000007, max = 2 * (1 << 20);
       Map<Integer, Integer> map = new HashMap<>();
       for (int d : deliciousness) {
           for (int sum = 1; sum <= max; sum *= 2) {
               res = (res + map.getOrDefault(sum - d, 0)) % mod;
           }
           map.put(d, map.getOrDefault(d, 0) + 1);
       }
       return res;
   }
}

No.3 将数组分成三个子数组的方案数

★解题思路

二分查找。分成三段 left mid 和 right，有两个分界点，当我们确定左侧的分界点之后，可以二分查找右侧的分界点的最大值和最小值，在此范围内都是成立的。

代码展示

class Solution {
   public int waysToSplit(int[] nums) {
       int sum = Arrays.stream(nums).sum();
       int mod = 1000000007;
       int cur = nums[0];
       int ans = 0;
       int preSum[] = new int[nums.length];
       preSum[0] = nums[0];
       for (int i = 1; i < nums.length - 1; i++) {
           cur += nums[i];
           preSum[i] = nums[i] + preSum[i - 1];
           // 最大值
           int lr = findRight(preSum, cur, i);
           // 最小值
           int ll = findLeft(preSum, cur, sum - cur, lr);
           if (ll == -1 || lr == -1 || ll > lr) {
               continue;
           }
           ans += (lr - ll + 1);
           ans %= mod;
       }
       return ans;
   }

   int findRight(int[] preSum, int sum, int r) {
       // 左边部分的和小于等于右边
       int l = 1;
       int ret = -1;
       while (l <= r) {
           int m = (l + r) / 2;
           // 0 ~ m-1
           int lsum = preSum[m - 1];
           // m ~ 右界
           int rsum = sum - preSum[m - 1];
           if (lsum <= rsum) {
               ret = m;
               l = m + 1;
           } else {
               r = m - 1;
           }
       }
       return ret;
   }

   int findLeft(int[] preSum, int sum, int rSum, int r) {
       int l = 1;
       int ret = -1;
       while (l <= r) {
           int m = (l + r) / 2;
           int midSum = sum - preSum[m - 1];
           if (midSum <= rSum) {
               ret = m;
               r = m - 1;
           } else {
               l = m + 1;
           }
       }
       return ret;
   }
}

No.4

得到子序列的最少操作次数

★

解题思路

LCS，需要使用 o(NlogN) 的算法。

代码展示

class Solution {
   public int minOperations(int[] target, int[] arr) {
       Map<Integer, Integer> map = new HashMap<>();
       for (int i = 0; i < target.length; i++) {
           map.put(target[i], i);
       }
       List<Integer> list = new ArrayList<>();
       for (int num : arr) {
           if (map.containsKey(num)) {
               list.add(map.get(num));
           }
       }

       List<Integer> list2 = new ArrayList<>();
       for (int num : list) {
           if (list2.size() == 0 || list2.get(list2.size() - 1) < num) {
               list2.add(num);
               continue;
           }
           int l = 0, r = list2.size() - 1;
           while (l + 1 < r) {
               int mid = (l + r) / 2;
               if (list2.get(mid) < num) {
                   l = mid;
               } else {
                   r = mid;
               }
           }
           int idx = list2.get(l) >= num ? l : r;
           list2.set(idx, num);
       }
       return target.length - list2.size();
   }
}

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

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