博客

从今天起记录一些题目加强理解

1046. 最后一块石头的重量
      
      有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

简单解法

int Cmp(const void* a, const void* b)
{
    return *(int*)b - *(int*)a;
}
int lastStoneWeight(int* stones, int stonesSize)
{
    int time = stonesSize - 1;
    int buf[30] = {0};
    memcpy(buf, stones, stonesSize * sizeof(int));
    while (time > 0) {
        qsort(buf, 30, sizeof(int), Cmp);
        buf[0] -= buf[1];
        buf[1] = 0;
        time--;
    }
    return buf[0];
}

作者：dog_egg
链接：https://leetcode-cn.com/problems/last-stone-weight/solution/wo-hao-sao-a-wo-zen-yao-xiang-chu-lai-zhe-chong-sa/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

官方解法（与上种方法类似，个人觉得写起来过于麻烦）：

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b, *b = tmp;
}

void push(int *heap, int *heapSize, int x) {
    heap[++(*heapSize)] = x;
    for (int i = (*heapSize); i > 1 && heap[i] > heap[i >> 1]; i >>= 1) {
        swap(&heap[i], &heap[i >> 1]);
    }
}

void pop(int *heap, int *heapSize) {
    int tmp = heap[1] = heap[(*heapSize)--];
    int i = 1, j = 2;
    while (j <= (*heapSize)) {
        if (j != (*heapSize) && heap[j + 1] > heap[j]) ++j;
        if (heap[j] > tmp) {
            heap[i] = heap[j];
            i = j;
            j = i << 1;
        } else {
            break;
        }
    }
    heap[i] = tmp;
}

int top(int *heap) {
    return heap[1];
}

int lastStoneWeight(int *stones, int stonesSize) {
    if (stonesSize == 1) {
        return stones[0];
    }
    if (stonesSize == 2) {
        return fabs(stones[0] - stones[1]);
    }
    int heap[stonesSize + 2], heapSize = 0;
    for (int i = 0; i < stonesSize; i++) {
        push(heap, &heapSize, stones[i]);
    }

    while (heapSize > 1) {
        int a = top(heap);
        pop(heap, &heapSize);
        int b = top(heap);
        pop(heap, &heapSize);
        if (a > b) {
            push(heap, &heapSize, a - b);
        }
    }
    return heapSize ? top(heap) : 0;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/last-stone-weight/solution/zui-hou-yi-kuai-shi-tou-de-zhong-liang-b-xgsx/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。