代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
你的初始 能量 为 power
,初始 分数 为 0
,只有一包令牌 tokens
。其中 tokens[i]
是第 i
个令牌的值(下标从 0 开始)。
令牌可能的两种使用方法如下:
token[i]
点 能量 ,可以将令牌 i
置为正面朝上,失去 token[i]
点 能量 ,并得到 1
分 。1
分 ,可以将令牌 i
置为反面朝上,获得 token[i]
点 能量 ,并失去 1
分 。每个令牌 最多 只能使用一次,使用 顺序不限 ,不需 使用所有令牌。
在使用任意数量的令牌后,返回我们可以得到的最大 分数 。
示例 1:
输入:tokens = [100], power = 50 输出:0 解释:无法使用唯一的令牌,因为能量和分数都太少了。
示例 2:
输入:tokens = [100,200], power = 150 输出:1 解释:令牌 0 正面朝上,能量变为 50,分数变为 1 。 不必使用令牌 1 ,因为你无法使用它来提高分数。
示例 3:
输入:tokens = [100,200,300,400], power = 200 输出:2 解释:按下面顺序使用令牌可以得到 2 分: 1. 令牌 0 正面朝上,能量变为 100 ,分数变为 1 2. 令牌 3 正面朝下,能量变为 500 ,分数变为 0 3. 令牌 1 正面朝上,能量变为 300 ,分数变为 1 4. 令牌 2 正面朝上,能量变为 0 ,分数变为 2
提示:
0 <= tokens.length <= 1000
0 <= tokens[i], power < 104
令牌的使用方法有两种,一种是消耗能量得到分数,一种是消耗分数得到能量。显然,我们应该消耗尽可能少的能量来得到尽可能多的分数。
因此,我们可以将令牌按照消耗能量的多少进行排序,然后使用双指针,一个指针从左向右遍历,一个指针从右向左遍历,每次遍历都尽可能地消耗能量得到分数,然后更新最大分数。如果当前能量不足以消耗当前令牌,那么我们就尝试使用分数来消耗当前令牌,如果分数不足以消耗当前令牌,那么我们就停止遍历。
时间复杂度 $O(n\log n)$,空间复杂度 $O(n)$。其中 $n$ 为令牌的数量。
class Solution:
def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
tokens.sort()
i, j = 0, len(tokens) - 1
ans = t = 0
while i <= j:
if power >= tokens[i]:
power -= tokens[i]
i, t = i + 1, t + 1
ans = max(ans, t)
elif t:
power += tokens[j]
j, t = j - 1, t - 1
else:
break
return ans
class Solution {
public int bagOfTokensScore(int[] tokens, int power) {
Arrays.sort(tokens);
int i = 0, j = tokens.length - 1;
int ans = 0, t = 0;
while (i <= j) {
if (power >= tokens[i]) {
power -= tokens[i++];
++t;
ans = Math.max(ans, t);
} else if (t > 0) {
power += tokens[j--];
--t;
} else {
break;
}
}
return ans;
}
}
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int power) {
sort(tokens.begin(), tokens.end());
int i = 0, j = tokens.size() - 1;
int ans = 0, t = 0;
while (i <= j) {
if (power >= tokens[i]) {
power -= tokens[i++];
ans = max(ans, ++t);
} else if (t) {
power += tokens[j--];
--t;
} else {
break;
}
}
return ans;
}
};
func bagOfTokensScore(tokens []int, power int) int {
sort.Ints(tokens)
i, j := 0, len(tokens)-1
ans, t := 0, 0
for i <= j {
if power >= tokens[i] {
power -= tokens[i]
i, t = i+1, t+1
ans = max(ans, t)
} else if t > 0 {
power += tokens[j]
j, t = j-1, t-1
} else {
break
}
}
return ans
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。