Leetcode1167 Minimum Cost to Connect Sticks

题目地址

变式原文地址

领扣地址 本题在Leetcode上是会员题,对应Lintcode-1872

有若干长度为正整数的棍子,每连接两个棍子X和Y需要X+Y的代价,求问将所有棍子连接成一个的最小代价

因为连接两个棍子需要的代价是他们的长度和,合为一个之后又会再与其他棍子连接,相当于他们被重复计算了多次,为了减少代价,重复的长度必须要尽量小,所以很明显,每次取最小的两个棍子。

使用优先队列就迎刃而解了。

本题代码

1
2
3
4
5
6
7
8
9
10
11
public int MinimumCost(List<Integer> sticks) {
PriorityQueue<Integer> pq = new PriorityQueue<>(sticks);
int ans = 0;
while (pq.size() > 1) {
int top = pq.poll();
int top2 = pq.poll();
ans += (top + top2);
pq.offer(top + top2);
}
return ans;
}

注意点

C++中STL优先队列默认是大顶堆,队首是最大值

C++

1
2
3
4
5
// 小顶堆
priority_queue <int,vector<int>,greater<int> > q;
// 大顶堆(默认)
priority_queue <int,vector<int>,less<int> >q;
priority_queue<int> q;

Java中的优先队列默认是小顶堆,队首是最小值

Java若要实现大顶堆,重写Comparator函数

1
2
3
4
5
6
7
private static final int DEFAULT_INITIAL_CAPACITY = 11;
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(DEFAULT_INITIAL_CAPACITY, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
× thanks~
打赏二维码