上岸算法

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

我们直击上岸

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

No.1 统计匹配检索规则的物品数量

解题思路

枚举、统计。

代码展示

class Solution { 
   public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) { 
       int index = 0; 
       if (ruleKey.equals("color")) { 
           index = 1; 
       } else if (ruleKey.equals("name")) { 
           index = 2; 
       } 
       int count = 0; 
       for (var item : items) { 
           if (item.get(index).equals(ruleValue)) { 
               count++; 
           } 
       } 
       return count; 
   } 
}

No.2 最接近目标价格的甜点成本

解题思路

递归搜索即可，把所有的配比方案都枚举一遍。

代码展示

class Solution { 
   int answer; 

   public int closestCost(int[] baseCosts, int[] toppingCosts, int target) { 
       answer = 0x3f3f3f3f; // INF 
       for (int base : baseCosts) { 
           dfs(base, 0, toppingCosts, target); 
       } 
       return answer; 
   } 

   private void dfs(int sum, int idx, int[] toppingCosts, int target) { 
       if (sum - target > Math.abs(answer - target)) { 
           return; 
       } 
       if (idx == toppingCosts.length) { 
           int cur = Math.abs(sum - target); 
           int min = Math.abs(answer - target); 
           if (cur < min || (cur == min && sum < answer)) { 
               answer = sum; 
           } 
           return; 
       } 
       for (int i = 0; i < 3; i++) { 
           dfs(sum + toppingCosts[idx] * i, idx + 1, toppingCosts, target); 
       } 
   } 
}

No.3 通过最少操作次数使数组的和相等

解题思路

贪心，每次挑跨度最大的数字操作。

代码展示

class Solution { 
   public int minOperations(int[] nums1, int[] nums2) { 
       // 无解情况判断 
       if (nums1.length > nums2.length * 6 || nums2.length > nums1.length * 6) { 
           return -1; 
       } 
       // 保证 nums1.sum > nums2.sum 
       if (Arrays.stream(nums1).sum() < Arrays.stream(nums2).sum()) { 
           int[] tmp = nums1; 
           nums1 = nums2; 
           nums2 = tmp; 
       } 
       int sum1 = Arrays.stream(nums1).sum(); 
       int sum2 = Arrays.stream(nums2).sum(); 
       int[] count1 = count(nums1); 
       int[] count2 = count(nums2); 
       int operationCount = 0; 
       // 将 nums1 中的数字变小，nums2 中的数字变大 
       while (sum1 > sum2) { 
           int i1 = lastNonZero(count1) + 1; 
           int i2 = firstNonZero(count2) + 1; 
           // 挑跨度大的那个数字进行操作 
           if (i1 - 1 > 6 - i2) { 
               int target = Math.max(1, i1 - (sum1 - sum2)); 
               count1[i1 - 1]--; 
               count1[target - 1]++; 
               sum1 -= i1 - target; 
           } else { 
               int target = Math.min(6, i2 + (sum1 - sum2)); 
               count2[i2 - 1]--; 
               count2[target - 1]++; 
               sum2 += target - i2; 
           } 
           operationCount++; 
       } 
       return operationCount; 
   } 

   private int lastNonZero(int[] arr) { 
       for (int i = arr.length - 1; i >= 0; i--) { 
           if (arr[i] != 0) { 
               return i; 
           } 
       } 
       return -1; 
   } 

   private int firstNonZero(int[] arr) { 
       for (int i = 0; i < arr.length; i++) { 
           if (arr[i] != 0) { 
               return i; 
           } 
       } 
       return -1; 
   } 

   private int[] count(int[] nums) { 
       int[] counts = new int[6]; 
       for (int n : nums) { 
           counts[n - 1]++; 
       } 
       return counts; 
   } 
} 

No.4 车队 II

解题思路

单调栈，详见注释。

代码展示

class Solution { 
   public double[] getCollisionTimes(int[][] cars) { 
       // 若 answer[i] > 0, 则 car i 必然会与后面的某辆车相遇 
       // 一辆车前面的车不会影响它的速度，即使相遇了，所以考虑从后往前遍历 
       double[] answer = new double[cars.length]; 
       // 单调栈，车速是单调递增的 
       LinkedList<Integer> stack = new LinkedList<>(); 
       for (int i = cars.length - 1; i >= 0; i--) { 
           while (!stack.isEmpty()) { 
               if (cars[stack.getLast()][1] >= cars[i][1]) { 
                   // 栈顶更快，追不上，弹出 
                   stack.pollLast(); 
               } else { 
                   if (answer[stack.peekLast()] < 0) { 
                       break; 
                   } 
                   double d = answer[stack.peekLast()] * (cars[i][1] - cars[stack.peekLast()][1]); 
                   if (d > cars[stack.peekLast()][0] - cars[i][0]) { 
                       break; 
                   } else { 
                       // 在追上前，前车已经和它之前的车相遇，弹出 
                       stack.pollLast(); 
                   } 
               } 
           } 
           if (stack.isEmpty()) { 
               answer[i] = -1; 
           } else { 
               answer[i] = (double) (cars[stack.peekLast()][0] - cars[i][0]) / (cars[i][1] - cars[stack.peekLast()][1]); 
           } 
           stack.addLast(i); 
       } 
       return answer; 
   } 
}