LeetCodeSwift in LeetCode高薪算法+计算机职称考试

LeetCode 1046. 最后一块石头的重量 Last St

2019-08-26  本文已影响0人  1江春水

【题目描述】
有一堆石头,每块石头的重量都是正整数。

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

1、1 <= stones.length <= 30
2、1 <= stones[i] <= 1000

【思路】
1、排序
2、按道理来讲排序的复杂度高,但貌似耗时不多
3、时间复杂度O(nlogn)
4、空间复杂度O(1)

Swift代码实现:

func lastStoneWeight(_ stones: [Int]) -> Int {
    if stones.count == 1 {
        return stones[0]
    }
    var tmp = stones.sorted()
    while tmp.count > 0 {
        let maxFir = tmp.removeLast()
        let maxSec = tmp[tmp.count-1]
        let cha = maxFir-maxSec
        if cha == 0 {
            tmp.removeLast()
        } else {
            tmp[tmp.count-1] = cha
            tmp.sort()
        }
        if tmp.count == 0 {
            return 0
        }
        if tmp.count == 1 {
            return tmp.first!
        }
    }
    return 0
}
上一篇下一篇

猜你喜欢

热点阅读