0948._Bag_of_Tokens.md

948. Bag of Tokens

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/bag-of-tokens/

内容描述

You have an initial power P, an initial score of 0 points, and a bag of tokens.

Each token can be used at most once, has a value token[i], and has potentially two ways to use it.

If we have at least token[i] power, we may play the token face up, losing token[i] power, and gaining 1 point.
If we have at least 1 point, we may play the token face down, gaining token[i] power, and losing 1 point.
Return the largest number of points we can have after playing any number of tokens.

 

Example 1:

Input: tokens = [100], P = 50
Output: 0
Example 2:

Input: tokens = [100,200], P = 150
Output: 1
Example 3:

Input: tokens = [100,200,300,400], P = 200
Output: 2
 

Note:

tokens.length <= 1000
0 <= tokens[i] < 10000
0 <= P < 10000

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

贪心

先把tokens按照power排序，然后我们一定会先使用最少的power去换取point，然后当power不够用的时候，就用一个point去换取最多的power，注意一下边界就可以

因为tokens = tokens[1:]是O(N)的，所以总时间复杂度为)(N^2)，60ms，beats 100%

class Solution:
    def bagOfTokensScore(self, tokens, P):
        """
        :type tokens: List[int]
        :type P: int
        :rtype: int
        """
        if not tokens or len(tokens) == 0 or P == 0:
            return 0

        tokens.sort()
        score = 0
        while tokens:
            if P >= tokens[0]:
                P -= tokens[0]
                tokens = tokens[1:]
                score += 1
            else:
                if len(tokens) == 1 or score < 1:
                    return score
                else:
                    score -= 1
                    P += tokens[-1]
                    tokens = tokens[:-1]
        return score

思路 2 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******

用一个deque来缩减时间，40ms，beats 100%

class Solution:
    def bagOfTokensScore(self, tokens, P):
        """
        :type tokens: List[int]
        :type P: int
        :rtype: int
        """
        if not tokens or len(tokens) == 0 or P == 0:
            return 0

        tokens = collections.deque(sorted(tokens))
        score = 0
        while tokens:
            if P >= tokens[0]:
                P -= tokens[0]
                tokens.popleft()
                score += 1
            else:
                if len(tokens) == 1 or score < 1:
                    return score
                else:
                    score -= 1
                    P += tokens[-1]
                    tokens.pop()
        return score