【Day 86 】2021-12-04 - 1046.最后一块石头的重量 #105
Comments
思路:读完题, 发现是 top K问题的变形, 于是可以使用堆(优先队列) 求解。 首先特判一下, 如果原数组的size == 1, 可以直接取出数组的第一个元素返回即可。 否则, 将数组中的数都放进一个大顶堆pq中, 使用一个while循环, 只要pq的size >= 2, 就每次从top位置取出两个数 firstBig 和 secondBig:
如果循环结束时, pq为空则返回0, 否则pq的顶部元素即为所求。 代码:实现语言: C++ class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
if (stones.size() == 1) return stones.front();
priority_queue<int> pq;
for (auto& s : stones)
pq.push(s);
while (pq.size() >= 2) /* 别漏了==的情况 */
{
int firstBig = pq.top();
pq.pop();
int secondBig = pq.top();
pq.pop();
if (firstBig != secondBig)
pq.push(firstBig - secondBig);
}
return pq.empty() ? 0 : pq.top();
}
};复杂度分析
|
思路使用堆的方法 先构建一个最大堆 每次如果堆中元素多于两个, 那么取出堆顶的两个元素, 并计算 remain, 如果 remain 不为 0, 将 remain 加入堆中继续循环 最后返回 堆顶元素如果 h 中还有元素 (代表还有一个元素), 否则返回 0, 代表没有元素剩余 import heapq
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
h = [-x for x in stones]
heapq.heapify(h)
while len(h) >= 2:
s1 = heapq.heappop(h)
s2 = heapq.heappop(h)
remain = -s1 - (-s2)
if remain != 0:
heapq.heappush(h, -remain)
return 0 if not h else -h[0]复杂度时间复杂度: O(nlogn) 每次从堆中取出元素需要 O(logn) 的时间, 一共需要进行 O(n) 次 空间复杂度: O(n) 堆的空间复杂度 |
解题思路堆。模拟整个流程。建立大顶堆，将所有石头放入堆中，如果堆中石头多于2个，则拿出最大的两个进行粉碎，直到最后剩小于2个石头为止。 代码class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
// put stones into max-heap
for (int stone : stones) {
heap.offer(stone);
}
// simulate the smash process
while (heap.size() >= 2) {
int y = heap.poll();
int x = heap.poll();
if (x != y) {
heap.offer(y - x);
}
}
return heap.size() == 0 ? 0 : heap.poll();
}
}复杂度分析
|
def lastStoneWeight(self, stones: List[int]) -> int:
q = [-stone for stone in stones]
heapq.heapify(q)
while (len(q)) > 1:
heapq.heappush(q, heapq.heappop(q) - heapq.heappop(q))
return -q[0] |
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap = [-stone for stone in stones]
heapq.heapify(heap)
while len(heap) > 1:
x,y = heapq.heappop(heap),heapq.heappop(heap)
if x != y:
heapq.heappush(heap,x-y)
if heap: return -heap[0]
return 0
|
Problemhttps://leetcode.com/problems/last-stone-weight/ Note
Solutionclass Solution {
public int lastStoneWeight(int[] stones) {
if(stones == null || stones.length == 0){
return 0;
}
int n = stones.length;
PriorityQueue<Integer> q = new PriorityQueue<>(n, Collections.reverseOrder());
for(int i = 0; i < stones.length; i++){
q.offer(stones[i]);
}
while(q.size() > 1){
int s1 = q.poll();
int s2 = q.poll();
if(s1 != s2){
q.offer(s1 - s2);
}
}
return q.isEmpty()? 0: q.poll();
}
}Complexity
|
思路
关键点代码
C++ Code: class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int, vector<int>> pq;
for(int i=0; i< stones.size(); i++)
{
pq.push(stones[i]);
}
while(pq.size()>1)
{
int topNode1 = pq.top();
pq.pop();
int topNode2 = pq.top();
pq.pop();
if(topNode1-topNode2>0)
pq.push(topNode1-topNode2);
}
return pq.size()? pq.top(): 0;
}
};
|
思路
Java Code public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> (b - a));
for (int n : stones) {
pq.add(n);
}
while (pq.size() > 1) {
int stone1 = pq.poll();
int stone2 = pq.poll();
if (stone1 != stone2) {
pq.add(Math.abs(stone1 - stone2));
}
}
return pq.isEmpty() ? 0 : pq.poll();
}时间&空间
|
# use min heap
# time: O(NlogN)
# space: O(N)
import heapq
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
if len(stones) == 1:
return stones[0]
# min heap
heap = []
for stone in stones:
heapq.heappush(heap, -stone)
while len(heap) > 1:
candidate1 = -heapq.heappop(heap)
candidate2 = -heapq.heappop(heap)
if candidate1 == candidate2:
if not heap: return 0
continue
left = abs(candidate1 - candidate2)
heapq.heappush(heap, -left)
return -heapq.heappop(heap) |
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones.sort()
while len(stones)> 1:
a = stones.pop()
b = stones.pop()
stones.append(abs(a-b))
stones.sort()
if stones:
return stones[0]
else:
return 0
|
思路堆。 代码(C++)class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> q;
for (int s: stones) q.push(s);
while (q.size() > 1) {
int a = q.top();
q.pop();
int b = q.top();
q.pop();
if (a > b) q.push(a - b);
}
return q.empty() ? 0 : q.top();
}
};复杂度分析
|
代码class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
for (int stone : stones) {
pq.offer(stone);
}
while (pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
if (a > b) {
pq.offer(a - b);
}
}
return pq.isEmpty() ? 0 : pq.poll();
}
}复杂度时间复杂度：O(NLogN) |
|
class Solution { |
type hp []int
func (h hp) Len() int{return len(h)}
func (h hp) Less(i,j int) bool{return h[i]>h[j]}
func (h hp) Swap(i,j int) {h[i],h[j] = h[j],h[i]}
func (h *hp) Push(x interface{}){
*h = append(*h, x.(int))
}
func (h *hp) Pop() interface{}{
out := *h
x := out[len(out)-1]
*h = out[:len(out)-1]
return x
}
func lastStoneWeight(stones []int) int {
h := &hp{}
for i:=0;i<len(stones);i++{
heap.Push(h,stones[i])
}
for h.Len() > 1{
x := heap.Pop(h).(int)
y := heap.Pop(h).(int)
if x > y{
heap.Push(h,x-y)
}
}
if h.Len()>0{
return heap.Pop(h).(int)
}
return 0
} |
IdeaHeap Codeclass Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap = []
for i in stones:
heapq.heappush(heap, -i)
while len(heap) > 2:
i, j = -heapq.heappop(heap), -heapq.heappop(heap)
if i - j != 0:
heapq.heappush(heap,-abs(i-j))
if len(heap) > 1:
return abs(heapq.heappop(heap) - heapq.heappop(heap))
elif len(heap) == 1:
return abs(heapq.heappop(heap))
else:
return 0Complexity:Time: O(N log N). Heap pop and heap push is O(log N). We need to go through all arrays for each simulation. |
link:https://leetcode.com/problems/last-stone-weight/ 代码 Javascriptfunction PriorityQueue() {
this.heap = [null];
this.insert = function (value) {
this.heap.push(value);
let currentNodeIdx = this.heap.length - 1;
let currentNodeParentIdx = Math.floor(currentNodeIdx / 2);
while (
this.heap[currentNodeParentIdx] &&
value > this.heap[currentNodeParentIdx]
) {
let parent = this.heap[currentNodeParentIdx];
this.heap[currentNodeParentIdx] = value;
this.heap[currentNodeIdx] = parent;
currentNodeIdx = currentNodeParentIdx;
currentNodeParentIdx = Math.floor(currentNodeIdx / 2);
}
};
this.remove = function () {
if (this.heap.length < 3) {
const toReturn = this.heap.pop();
this.heap[0] = null;
return toReturn;
}
const toRemove = this.heap[1];
this.heap[1] = this.heap.pop();
let currentIdx = 1;
let [left, right] = [2 * currentIdx, 2 * currentIdx + 1];
let currentChildIdx =
this.heap[right] && this.heap[right] >= this.heap[left] ? right : left;
while (
this.heap[currentChildIdx] &&
this.heap[currentIdx] < this.heap[currentChildIdx]
) {
let currentNode = this.heap[currentIdx];
let currentChildNode = this.heap[currentChildIdx];
this.heap[currentChildIdx] = currentNode;
this.heap[currentIdx] = currentChildNode;
currentIdx = currentChildIdx;
[left, right] = [2 * currentIdx, 2 * currentIdx + 1];
currentChildIdx =
this.heap[right] && this.heap[right] >= this.heap[left] ? right : left;
}
return toRemove;
};
}
const lastStoneWeight = function (stones) {
const pq = new PriorityQueue();
for (let i = 0; i < stones.length; i++) {
pq.insert(stones[i]);
}
while (pq.heap.length > 2) {
let x = pq.remove();
let y = pq.remove();
if (x != y) {
let max = Math.max(x, y);
let min = Math.min(x, y);
let z = max - min;
pq.insert(z);
}
}
return pq.remove();
}; |
|
var lastStoneWeight = function(stones) {
while(stones.length > 1) {
stones.sort((a, b) => a - b);
let a = stones.pop();
let b = stones.pop();
if(a !== b) stones.push(a - b);
}
return stones[0] || 0
}; |
题目https://leetcode-cn.com/problems/last-stone-weight/ 思路Heap python3class heapq:
def __init__(self, descend = False):
self.heap = []
self.descend = descend
def _swap(self, idx1, idx2):
self.heap[idx1], self.heap[idx2] = self.heap[idx2], self.heap[idx1]
def _smaller(self, lst, rst):
return lst > rst if self.descend else lst < rst
def _size(self):
return len(self.heap)
def _top(self):
if self.heap:
return self.heap[0]
return None
def _push(self, x):
self.heap.append(x)
self._sift_up(self._size() - 1)
def _pop(self):
tmp = self.heap[0]
self._swap(0, self._size() - 1)
self.heap.pop()
self._sift_down(0)
return tmp
def _sift_up(self, idx):
while (idx != 0):
parentIdx = (idx - 1) // 2
if (self._smaller(self.heap[parentIdx], self.heap[idx])):
break
self._swap(parentIdx, idx)
idx = parentIdx
def _sift_down(self, idx):
while (idx*2+1 < self._size()):
smallestIdx = idx
leftIdx = idx*2+1
rightIdx = idx*2+2
if (self._smaller(self.heap[leftIdx], self.heap[idx])):
smallestIdx = leftIdx
if (rightIdx < self._size() and self._smaller(self.heap[rightIdx], self.heap[smallestIdx])):
smallestIdx = rightIdx
if (smallestIdx == idx):
break
self._swap(smallestIdx, idx)
idx = smallestIdx
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap = heapq(descend = True)
for s in stones:
heap._push(s)
while(heap._size() > 1):
y = heap._pop()
x = heap._pop()
if y != x:
heap._push(y - x)
if heap._size() >= 1:
return heap._top()
return 0
复杂度分析
相关题目
|
idea由每次取出最重的石头比较，想到需要排序。 codecomplexitytime：O(NlogN) |
思路heap 代码使用语言：Python3 import heapq
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
for i in range(len(stones)):
stones[i] *= -1
heapq.heapify(stones)
while len(stones) > 1:
stone_1 = heapq.heappop(stones)
stone_2 = heapq.heappop(stones)
if stone_1 != stone_2:
heapq.heappush(stones, stone_1 - stone_2)
return -heapq.heappop(stones) if stones else 0复杂度分析 |
1046. Last Stone WeightIntuition
Code/**
* @param {number[]} stones
* @return {number}
*/
const lastStoneWeight = function(stones) {
const maxHeap = new BinaryHeap((c, p) => c < p);
stones.forEach((stone) => maxHeap.push(stone));
while (maxHeap.size() > 1) {
const diff = maxHeap.pop() - maxHeap.pop();
if (diff > 0) {
maxHeap.push(diff);
}
}
return maxHeap.size() ? maxHeap.pop() : 0;
};Complexity Analysis
|
代码class Solution {
public int lastStoneWeight(int[] stones) {
Queue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
for(int i = 0; i < stones.length; i++) {
queue.offer(stones[i]);
}
while(queue.size() > 1) {
int x = queue.poll();
int y = queue.poll();
int diff = Math.abs(x - y);
if(diff != 0) {
queue.offer(diff);
}
}
if(queue.isEmpty()) return 0;
return queue.peek();
}
}复杂度分析时间复杂度O(nlogn) 空间复杂度O(n) |
思路优先队列 代码class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> q;
for(int s:stones){
q.push(s);
}
while(q.size()>1){
int a=q.top();
q.pop();
int b=q.top();
q.pop();
if(a>b){
q.push(a-b);
}
}
return q.empty()?0:q.top();
}
};
复杂度分析
|
1046. Last Stone Weighthttps://leetcode.com/problems/last-stone-weight/ Topics-Heap 思路Heap 代码 Pythonclass Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
q = [-e for e in stones]
heapq.heapify(q)
while len(q) > 1:
x = heapq.heappop(q)
y = heapq.heappop(q)
heapq.heappush(q, -1 * abs(x-y))
return -1 * q[0] if len(q) == 1 else 0复杂度分析时间复杂度： O(N*Log(N)) |
|
class Solution { |
思路设置一个大顶堆，所有数字入堆，然后从堆内取出最大的两个数字，把它们的差再放入堆中，直到堆内剩下的数字少于2个。最后如果堆不为空就返回堆顶，否则返回0。 代码class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> heap = new PriorityQueue<>((e1, e2) -> e2 - e1);
for (int stone : stones) {
heap.offer(stone);
}
while (heap.size() > 1) {
int stone1 = heap.poll();
int stone2 = heap.poll();
if (stone1 != stone2) {
heap.offer(stone1 - stone2);
}
}
return heap.isEmpty() ? 0 : heap.peek();
}
}TC: O(nlogn) |
thoughtsheap 把stones数组的值取反加入heap 然后pop 出两两比较 知道最后元素个数<=1 codeimport heapq
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap = []
for stone in stones:
heapq.heappush(heap, -stone)
while len(heap) > 1:
x, y = heapq.heappop(heap), heapq.heappop(heap)
if x == y:
continue
else:
heapq.heappush(heap, x-y)
return -heap[0] if heap else 0complexityTime O(nlgn) Space O(n) |
代码class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
new_stones=[-1*stone for stone in stones]
heapq.heapify(new_stones)
while len(new_stones) >1:
y=heapq.heappop(new_stones)
x=heapq.heappop(new_stones)
if y !=x:
heapq.heappush(new_stones,y-x)
if new_stones:
return -new_stones[0]
else:
return 0复杂度Time: O(nlogn) Space: O(n) |
|
class Solution { |
|
/**
|
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap = [-stone for stone in stones]
heapq.heapify(heap)
while len(heap) > 1:
x, y = heapq.heappop(heap), heapq.heappop(heap)
if x != y:
heapq.heappush(heap, x - y)
if heap: return -heap[0]
return 0 |
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
h = [-stone for stone in stones]
heapq.heapify(h)
while len(h) > 1:
a, b = heapq.heappop(h), heapq.heappop(h)
if a != b:
heapq.heappush(h, a - b)
return -h[0] if h else 0 |
【Day 86】1046.最后一块石头的重量代码class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> q;
for (int s: stones) {
q.push(s);
}
while (q.size() > 1) {
int a = q.top();
q.pop();
int b = q.top();
q.pop();
if (a > b) {
q.push(a - b);
}
}
return q.empty() ? 0 : q.top();
}
};复杂度时间复杂度：O(NLogN) 空间复杂度：O(N) |
Codesvar lastStoneWeight = function(stones) {
stones.sort((a, b) => a - b);
if (stones.length < 2) {
return stones[0];
}
while (stones.length) {
let len = stones.length;
let a = stones[len - 1], b = stones[len - 2];
stones.pop();
stones.pop();
if (a !== b) {
let j = 1;
if (!stones.length) {
return a - b;
}
while (j <= stones.length) {
if (a - b <= stones[0]) {
stones.unshift(a - b);
break;
}
if (a - b >= stones[stones.length - 1]) {
stones.push(a - b);
break;
}
if (a - b >= stones[j - 1] && a - b <= stones[j]) {
stones.splice(j, 0, a - b);
break;
}
j++;
}
}
if (stones.length === 1) {
return stones[0];
}
}
return 0;
}; |
JAVA版本思路：直接使用堆来完成的，【扩展可以自己手动构建堆。。。】
时间复杂度：O(nlogn) 空间复杂度：O(n) |
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> q(stones.begin(), stones.end());
while (q.size() > 1){
int stone1 = q.top();
q.pop();
int stone2 = q.top();
q.pop();
if (stone1 != stone2){
q.push(stone1 - stone2);
}
}
if (q.size() == 1){
return q.top();
}
else{
return 0;
}
} |
func lastStoneWeight(stones []int) int {
var l int
l = len(stones)
if l == 0 {
return 0
}
for ; l > 1; l = len(stones) {
sort.Ints(stones)
x := stones[l-2]
y := stones[l-1]
if x == y {
stones = stones[0:l-2]
} else {
stones = append(stones[0:l-2], y-x)
}
}
result := 0
if len(stones) > 0 {
result = stones[0]
}
return result
} |
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> q;
for (int s: stones) {
q.push(s);
}
while (q.size() > 1) {
int a = q.top();
q.pop();
int b = q.top();
q.pop();
if (a > b) {
q.push(a - b);
}
}
return q.empty() ? 0 : q.top();
}
}; |
class Solution {
public int lastStoneWeight(int[] stones) {
MaxHeap maxHeap = new MaxHeap(stones);
while(maxHeap.size() > 1) {
int y = maxHeap.poll();
int x = maxHeap.poll();
if(y > x) {
maxHeap.push(y - x);
}
}
return maxHeap.size() == 1 ? maxHeap.poll() : 0;
}
private class MaxHeap{
final int[] data;
int tail;
public MaxHeap(int[] data) {
this.data = data;
this.tail = data.length - 1;
buildHeap();
}
private void heapify(int i) {
int r = (i + 1) << 1;
int l = r - 1;
int max = i;
if(r <= tail && data[max] < data[r]) max = r;
if(l <= tail && data[max] < data[l]) max = l;
if(max == i) return;
swap(max, i);
heapify(max);
}
private void buildHeap() {
for(int i = ((this.tail + 1) >> 1) - 1; i >= 0; i--){
heapify(i);
}
}
private void swap(int p, int q) {
int temp = data[p];
data[p] = data[q];
data[q] = temp;
}
public void push(int i) {
data[++tail] = i;
buildHeap();
}
public int poll() {
int root = data[0];
data[0] = data[tail--];
heapify(0);
return root;
}
public int size() {
return tail + 1;
}
}
} |
|
class Solution { |
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
for (int stone : stones) {
pq.offer(stone);
}
while (pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
if (a > b) {
pq.offer(a - b);
}
}
return pq.isEmpty() ? 0 : pq.poll();
}
} |
时间复杂度：O(NlogN) |
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap_max = []
for stone in stones:
heapq.heappush(heap_max, -stone)
while len(heap_max) > 1:
top1 = heapq.heappop(heap_max)
top2 = heapq.heappop(heap_max)
left = abs(top1-top2)
if left > 0:
heapq.heappush(heap_max, -left)
if len(heap_max) > 0:
return -heapq.heappop(heap_max)
return 0
|
堆时间复杂度：O(NlogN) |
思路堆 代码JavaScript Code var lastStoneWeight = function (stones) {
const pq = new MaxPriorityQueue();
for (const stone of stones) {
pq.enqueue("x", stone);
}
while (pq.size() > 1) {
const a = pq.dequeue()["priority"];
const b = pq.dequeue()["priority"];
if (a > b) {
pq.enqueue("x", a - b);
}
}
return pq.isEmpty() ? 0 : pq.dequeue()["priority"];
};复杂度 令石头个数为 N
|
代码class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
for (int stone : stones) {
pq.offer(stone);
}
while (pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
if (a > b) {
pq.offer(a - b);
}
}
return pq.isEmpty() ? 0 : pq.poll();
}
}复杂度
|
思路直接模拟 Python代码class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones.sort()
while len(stones)>0:
if len(stones)==1:
return stones[0]
elif stones[-1]==stones[-2]:
stones.pop()
stones.pop()
else:
y=stones.pop()
x=stones.pop()
stones.append(y-x)
stones.sort()
return 0 |
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
for (int stone : stones) {
pq.offer(stone);
}
while (pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
if (a > b) {
pq.offer(a - b);
}
}
return pq.isEmpty() ? 0 : pq.poll();
}
} |
|
class Solution { } |
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
for (int stone : stones) {
pq.offer(stone);
}
while (pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
if (a > b) {
pq.offer(a - b);
}
}
return pq.isEmpty() ? 0 : pq.poll();
}
} |
|
class Solution: |
代码
C++ Code: class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> q;
for(int i=0;i<stones.size();++i)
q.push(stones[i]);
int a, b;
while(q.size()>1)
{
a = q.top();
q.pop();
b = q.top();
q.pop();
q.push(a-b);
}
return q.top();
}
};
|
思路
代码javascript /*
* @lc app=leetcode.cn id=1046 lang=javascript
*
* [1046] 最后一块石头的重量
*/
// @lc code=start
/**
* @param {number[]} stones
* @return {number}
*/
var lastStoneWeight = function(stones) {
let curr = stones.length - 1
while (curr > 0) {
stones.sort((a, b) => a - b)
stones[curr - 1] = stones[curr] - stones[curr - 1]
curr--
}
return stones[0]
};
// @lc code=end复杂度分析
|
Note优先队列，大顶堆 Codeclass Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> q = new PriorityQueue<>((a, b) ->
((Integer)b - (Integer)a));
int n = stones.length;
for (int i = 0; i < n; i++) {
q.add(stones[i]);
}
while (q.size() > 1) {
int x = q.remove();
if (q.size() < 1) {
break;
}
int y = q.remove();
if (x > y) {
q.add(x - y);
} else if (x < y) {
q.add(y - x);
}
}
if (q.size() == 0) {
return 0;
}
return q.peek();
}
}Complexity
|
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
h = []
for item in stones:
heapq.heappush(h, -item)
while(len(h) > 1):
item1 = -heapq.heappop(h)
item2 = -heapq.heappop(h)
remaining = item1 - item2
if remaining > 0:
heapq.heappush(h, -remaining)
if len(h) == 1:
return -h[0]
else:
return 0 |
Title:1046. Last Stone WeightQuestion Reference LeetCodeSolutionCodeclass Solution {
public:
void swap(int& x, int& y) {
if (x != y) {
x ^= y;
y ^= x;
x ^= y;
}
}
int getMaxChildIndex(vector<int>& heap, int index) {
int l = index * 2;
int r = index * 2 + 1;
if (r > heap[0] || heap[l] > heap[r])
return l;
return r;
}
void bottom_up(vector<int>& heap, int index) {
while (index > 1 && heap[index] > heap[index / 2]) {
swap(heap[index], heap[index / 2]);
index = index / 2;
}
}
void top_down(vector<int>& heap, int index) {
int n = heap[0];
while (index <= n/2) {
int mc = getMaxChildIndex(heap, index);
if (heap[index] >= heap[mc])
break;
swap(heap[index], heap[mc]);
index = mc;
}
}
void heapify(vector<int>& heap) {
int n = heap[0];
for (int i = n / 2; i >= 1; i--) {
top_down(heap, i);
}
}
int heap_pop(vector<int>& heap) {
int max_val = heap[1];
int n = heap[0];
swap(heap[1], heap[n]);
heap[0]--;
top_down(heap, 1);
return max_val;
}
void heap_push(vector<int>& heap, int v) {
int n = heap[0];
heap[n + 1] = v;
heap[0]++;
bottom_up(heap, n + 1);
}
int lastStoneWeight(vector<int>& stones) {
vector<int> heap(stones.size() + 1, 0);
heap[0] = stones.size();
for (int i = 0; i < stones.size(); i++)
heap[i + 1] = stones[i];
heapify(heap);
while(heap[0] > 1) {
int y = heap_pop(heap);
int x = heap_pop(heap);
if (x != y) {
heap_push(heap, y - x);
}
}
return heap[0] == 0? 0 : heap[1];
}
};
ComplexityTime Complexity and ExplanationO(n*logn) Space Complexity and ExplanationO(n) |
Note
Solutionclass Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap = []
for s in stones:
heapq.heappush(heap, -s)
while len(heap) > 1:
tmp = -heapq.heappop(heap) + heapq.heappop(heap)
if tmp:
heapq.heappush(heap, -tmp)
return -heap[0] if heap else 0Time complexity: O(NlogN) Space complexity: O(N) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
1046.最后一块石头的重量
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/last-stone-weight/
前置知识
题目描述
The text was updated successfully, but these errors were encountered: