Leetcode每日一题:1046.last-stone-weight(最后一块石头的重量)

Leetcode每日一题:1046.last-stone-weight(最后一块石头的重量)
题意:每次选择数组中两个最大的元素进行比较:

  • 若相等,两个都消除;
  • 若不相等,消除两个,留下它们的差;
    重复以上操作,求最后数组中剩下的元素;
    思路:因为本题中数组最多有30个元素,那么先用sort排序毫无压力,然后从后向前遍历,先对当前元素和前一个元素作比较,如果相等则i-=2,否则i-=1 and insert(二者之差);如果最后遍历到i==1stones[i]==stones[i-1]直接return 0,否则return stones[0]
    Leetcode每日一题:1046.last-stone-weight(最后一块石头的重量)
    Leetcode每日一题:1046.last-stone-weight(最后一块石头的重量)
static bool cmp(int a, int b)
{
    return a < b;
}

void Insert(vector<int> &stones, int tar, int len)
{
    if (len == 1)
    {
        stones[0] = tar;
        return;
    }
    for (int i = len - 2; i >= 0; i--)
    {
        if (stones[i] > tar)
        {
            stones[i + 1] = stones[i];
            continue;
        }
        else
        {
            stones[i + 1] = tar;
            return;
        }
    }
    stones[0] = tar;
}

int lastStoneWeight(vector<int> &stones)
{
    int len = stones.size();
    if (len == 1)
        return stones[0];
    if (len == 2)
        return abs(stones[1] - stones[0]);
    // 排序
    sort(stones.begin(), stones.end(), cmp);
    for (int i = len - 1; i > 0; i--)
    {
        // 如果二者相等,则消除
        if (stones[i] == stones[i - 1])
        {
            if (i == 1)
                return 0;
            i -= 1;
            continue;
        }
        // 否则消除后插入二者差值
        Insert(stones, abs(stones[i] - stones[i - 1]), i);
    }
    return stones[0];
}

上一篇:LeetCode------(Java第1046)最后一块石头的重量题


下一篇:leetcode 1046 最后一块石头的重量