百度网站收录查询,昆山网站网站建设,wordpress博客搭建,重庆蒲公英网站建设公司怎么样整体思想#xff1a;在满足可用资金的情况下#xff0c;选择其中利润最大的业务#xff0c;直到选到k个业务为止#xff0c;注意k可能比n大。
每次选择完一个业务#xff0c;可用资金都会变动#xff0c;这是可选择的业务也会变化#xff0c;因此每次将可选择的业务放在…整体思想在满足可用资金的情况下选择其中利润最大的业务直到选到k个业务为止注意k可能比n大。
每次选择完一个业务可用资金都会变动这是可选择的业务也会变化因此每次将可选择的业务放在一个优先队列大顶堆中堆顶元素就是目标业务。
优先队列堆的实现方式优先队列自定义比较器。
另外注意将业务根据所需资金capacity进行升序排列达到一种剪枝的目的。
class Solution {public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {int n profits.length;Listint[] list new ArrayList();for (int i 0; i n; i) {list.add(new int[] {capital[i], profits[i]});}Collections.sort(list, (a, b) - a[0] - b[0]);PriorityQueueInteger q new PriorityQueue((a, b) - b - a);int i 0;while (k-- 0) {while (i n list.get(i)[0] w) q.add(list.get(i)[1]);if (q.isEmpty()) break;w q.poll();}return w;}
}拓展 优先队列 在Java中优先队列PriorityQueue是一种特殊的队列它可以确保队列中元素的顺序是按照它们的优先级进行排列的数据结构。在优先队列中具有较高优先级的元素会先被处理而具有较低优先级的元素会被放置在队列的尾部。 优先队列可以用于许多应用比如任务调度、事件模拟等。在Java中优先队列通常是基于堆Heap实现的这意味着它可以高效地支持插入和删除具有最高或最低优先级的元素。 import java.util.PriorityQueue; public class Main { public static void main(String[] args) { // 创建一个优先队列 PriorityQueueInteger priorityQueue new PriorityQueue(); // 向优先队列中添加元素 priorityQueue.add(3); priorityQueue.add(1); priorityQueue.add(2); // 输出队列中的元素按照优先级顺序 while (!priorityQueue.isEmpty()) { System.out.println(priorityQueue.poll()); } }
} 需要注意的是当元素被添加到优先队列中时它们会根据其自然顺序或者根据提供的比较器进行排序。默认情况下优先队列会按照元素的自然顺序进行排序但也可以通过提供自定义的比较器来改变排序规则。 比较器 在Java中Collections.sort 方法用于对集合进行排序。它可以接受一个比较器Comparator作为第二个参数以便根据指定的比较规则对集合中的元素进行排序。 比较器是一个接口它定义了用于比较两个对象顺序的规则。在Collections.sort中当传入比较器时它将根据比较器所定义的规则对集合中的元素进行排序。 具体来说比较器的定义如下 public interface ComparatorT {int compare(T o1, T o2);
}这个接口中的 compare 方法接受两个参数 o1 和 o2分别代表要比较的两个对象。在这个方法中需要定义比较规则返回一个负整数、零或者正整数分别表示第一个参数小于、等于或大于第二个参数。 在实际使用中可以通过创建实现了Comparator接口的类或者使用Lambda表达式来定义比较器。比如 ListInteger numbers Arrays.asList(3, 1, 2);
Collections.sort(numbers, (a, b) - a - b);在这个例子中(a, b) - a - b 就是一个比较器它定义了对整数列表进行升序排序的规则。具体来说它告诉Collections.sort方法按照元素的大小进行排序。 总之比较器允许我们根据特定的规则对集合中的元素进行排序从而满足不同的排序需求。
