上岸算法

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

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

No.1 获取生成数组中的最大值

★ 解题思路

数据范围很小, 直接模拟生成这个数组, 维护最大值即可.

代码展示

class Solution { 
   public int getMaximumGenerated(int n) { 
       if (n <= 1) { 
           return n; 
       } 
       int[] nums = new int[n + 1]; 
       nums[1] = 1; 
       int res = 1; 
       for (int i = 0; i <= n; i++) { 
           if (2 <= i * 2 && i * 2 <= n) { 
               nums[i * 2] = nums[i]; 
               res = Math.max(res, nums[i * 2]); 
           } 
           if (2 <= i * 2 + 1 && i * 2 + 1 <= n) { 
               nums[2 * i + 1] = nums[i] + nums[i + 1]; 
               res = Math.max(res, nums[i * 2 + 1]); 
           } 
       } 
       return res; 
   } 
}

No.2字符频次唯一的最小删除次数

★解题思路

从出现次数多的字符开始删除即可, 详见注释.

代码展示

class Solution { 
   public int minDeletions(String s) { 
       // 统计每种字符的出现次数 
       int[] count = new int[26]; 
       for (int i = 0; i < s.length(); i++) { 
           count[s.charAt(i) - 'a']++; 
       } 
       // 将出现次数倒序放到堆中 (大顶堆) 
       int res = 0; 
       PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); 
       for (int i = 0; i < 26; i++) { 
           if (count[i] > 0) { 
               maxHeap.add(count[i]); 
           } 
       } 
       // 每次循环取出堆顶 (当前出现次数最多的字符出现的次数) 
       // 将相同的出现次数减小 (删除字符) 
       while (maxHeap.size() > 1) { 
           int largest = maxHeap.poll(); 
           // 统计多少个字符出现次数相同 
           int num = 0; 
           while (!maxHeap.isEmpty() && largest == maxHeap.peek()) { 
               num++; 
               maxHeap.poll(); 
           } 
           // 删除字符后剩下的次数 
           for (int i = 1; i <= num; i++) { 
               if (largest > i) { 
                   maxHeap.add(largest - i); 
                   res += i; 
               } else { 
                   res += largest; 
               } 
           } 
       } 
       return res; 
   } 
}

No.3 销售价值减少的颜色球

★解题思路

贪心, 每次销售数量最多的即可.

代码展示

class Solution { 
   public int maxProfit(int[] inventory, int orders) { 
       TreeMap<Integer, Integer> map = new TreeMap<>(); 
       for (int i : inventory) { 
           map.put(i, map.getOrDefault(i, 0) + 1); 
       } 
       map.put(0, 0);  // 避免 entry2 为 null 
       int res = 0; 
       while (orders > 0) { 
           // entry 为数量最多的颜色球以及种数 
           // entry2 是第二多的 
           // 要将 entry.val 种颜色的球的数量销售到 entry2.key 个 
           var entry = map.lastEntry(); 
           map.remove(entry.getKey()); 
           var entry2 = map.lastEntry(); 
           long maxNum = (long) (entry.getKey() - entry2.getKey()) * entry.getValue(); 
           if (maxNum >= orders) { 
               long avg = orders / entry.getValue(); 
               res += (avg * entry.getValue() * (entry.getKey() * 2 - avg + 1) / 2) % 1000000007L; 
               res %= 1000000007; 
               orders -= avg * entry.getValue(); 
               res += (orders * (entry.getKey() - avg)) % 1000000007L; 
               res %= 1000000007; 
               break; 
           } 
           res += ((long) (entry.getKey() - entry2.getKey()) * entry.getValue() * (entry.getKey() + entry2.getKey() + 1) / 2) % 1000000007L; 
           res %= 1000000007; 
           map.put(entry2.getKey(), entry2.getValue() + entry.getValue()); 
           orders -= maxNum; 
       } 
       return res; 
   } 
}

No.4

通过指令创建有序数组

★

解题思路

因为是固定顺序插入, 所以使用树状数组或者线段树可以很容易解决这个问题 (统计比自己大的元素数量和比自己小的元素数量).

代码展示

class Solution { 
   public int createSortedArray(int[] instructions) { 
       BinaryIndexedTree tree = new BinaryIndexedTree(100005); 
       int res = 0; 
       for (int i : instructions) { 
           int smaller = tree.sum(i - 1); 
           int greater = tree.sum(100000) - tree.sum(i); 
           res = (res + Math.min(smaller, greater)) % 1000000007; 
           tree.add(i, 1); 
       } 
       return res; 
   } 
} 

class BinaryIndexedTree { 
   private final int[] a; 

   public BinaryIndexedTree(int size) { 
       a = new int[size + 1]; 
   } 

   // pos: 1-indexed 
   public void add(int pos, int delta) { 
       for (; pos < a.length; pos += lowbit(pos)) { 
           a[pos] += delta; 
       } 
   } 

   // pos: 1-indexed 
   public int sum(int pos) { 
       int res = 0; 
       for (; pos > 0; pos -= lowbit(pos)) { 
           res += a[pos]; 
       } 
       return res; 
   } 

   private static int lowbit(int x) { 
       return x & (-x); 
   } 
}

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

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