[LeetCode][python3]Day12. Last Stone Weight (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.13

1. My Solution

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones=sorted(stones)
        left=self.smash(stones)
        #print(left)
        return left
    
    def smash(self,stones):
        if not stones:
            return 0
        elif len(stones)==1:
            return stones[0]
        else:
            stones[-2]=stones[-1]-stones[-2]
            stones.pop()
            if stones[-1]==0:
                stones.pop()
                return self.smash(stones)
            for i in range(len(stones)):
                if stones[-1]<=stones[i]:
                    if i!=0:
                        #print(stones[:i]+[stones[-1]]+stones[i:-1])
                        return self.smash(stones[:i]+[stones[-1]]+stones[i:-1])
                    else:
                        #print([stones[-1]]+stones[i:-1])
                        return self.smash([stones[-1]]+stones[i:-1])

Explanation:

It is the code version of the description of this problem. First I though this is a Knapsack Problem and trying to find a smallest diff when separating stones into two subset, then I was wrong when the test case came to [4,3,4,3,2]. A smart smasher will smash the stones to none of them left, but it will left 2 when you follow the rules from this problem.

2. A better Solution:

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones.sort(reverse=True)
        while len(stones) > 1:
            arr = stones[2:]
            y = stones[0]
            x = stones[1]
            if x != y:
                arr.append(y-x)
            stones = sorted(arr,reverse=True)
        if stones:
            return stones[0]
        return 0

Explanation:

This is in the same logic but a cleaner script. Besides, it use while loop instead of recursive function.