class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int power) {
}
};
948. 令牌放置
你的初始 能量 为 P，初始 分数 为 0，只有一包令牌 tokens 。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。
令牌可能的两种使用方法如下：
token[i] 点 能量 ，可以将令牌 i 置为正面朝上，失去 token[i] 点 能量 ，并得到 1 分 。1 分 ，可以将令牌 i 置为反面朝上，获得 token[i] 点 能量 ，并失去 1 分 。每个令牌 最多 只能使用一次，使用 顺序不限 ，不需 使用所有令牌。
在使用任意数量的令牌后，返回我们可以得到的最大 分数 。
示例 1：
输入：tokens = [100], P = 50 输出：0 解释：无法使用唯一的令牌，因为能量和分数都太少了。
示例 2：
输入：tokens = [100,200], P = 150 输出：1 解释：令牌 0 正面朝上，能量变为 50，分数变为 1 。不必使用令牌 1 ，因为你无法使用它来提高分数。
示例 3：
输入：tokens = [100,200,300,400], P = 200 输出：2 解释：按下面顺序使用令牌可以得到 2 分： 1. 令牌 0 正面朝上，能量变为 100 ，分数变为 1 2. 令牌 3 正面朝下，能量变为 500 ，分数变为 0 3. 令牌 1 正面朝上，能量变为 300 ，分数变为 1 4. 令牌 2 正面朝上，能量变为 0 ，分数变为 2
提示：
0 <= tokens.length <= 10000 <= tokens[i], P < 104原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.8 MB, 提交时间: 2023-09-20 11:16:27
func bagOfTokensScore(tokens []int, power int) int {
sort.Ints(tokens)
max_scores, cur_scores := 0, 0
l, r := 0, len(tokens) - 1
for l <= r {
if power >= tokens[l] {
cur_scores++
power -= tokens[l]
l++
max_scores = max(max_scores, cur_scores)
} else if cur_scores > 0 {
cur_scores--
power += tokens[r]
r--
} else {
break
}
}
return max_scores
}
func max(a, b int) int { if a > b { return a }; return b }
php 解法, 执行用时: 12 ms, 内存消耗: 19 MB, 提交时间: 2023-09-20 11:15:08
class Solution {
/**
* @param Integer[] $tokens
* @param Integer $power
* @return Integer
*/
function bagOfTokensScore($tokens, $power) {
$n = count($tokens);
sort($tokens);
$left = 0;
$right = $n - 1;
$score = 0;
$maxScore = 0;
while ($left <= $right) {
if ($power >= $tokens[$left]) {
$power -= $tokens[$left];
$left++;
$score++;
$maxScore = max($maxScore, $score);
} else {
if ($score > 0) {
$power += $tokens[$right];
$right--;
$score--;
} else {
break;
}
}
}
return $maxScore;
}
}
rust 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-09-20 11:14:33
impl Solution {
pub fn bag_of_tokens_score(tokens: Vec<i32>, p: i32) -> i32 {
if tokens.len() == 0 {
return 0;
}
let mut tokens = tokens;
let mut p = p;
let mut i = 0;
let mut j = tokens.len() - 1;
let mut score = 0;
let mut ret = 0;
tokens.sort_unstable();
while i <= j {
if p >= tokens[i] {
p -= tokens[i];
score += 1;
ret = ret.max(score);
i += 1;
} else if score > 0 {
p += tokens[j];
score -= 1;
j -= 1;
} else {
break;
}
}
ret
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 10.6 MB, 提交时间: 2023-09-20 11:10:20
class Solution {
public:
//入手最便宜的分，将分换最贵的能量，来得到更大的能量潜力
//能买就买，不能买，去用分兑换更大的，再来买
int bagOfTokensScore(vector<int>& tokens, int power) {
sort(begin(tokens),end(tokens));
int max_scores = 0,cur_scores = 0;
int l = 0,r = tokens.size()-1;
while(l <= r){
if(power >= tokens[l]){
cur_scores ++;
power -= tokens[l++];
max_scores = max(max_scores,cur_scores);
}else if(cur_scores > 0){
cur_scores --;
power += tokens[r--];
}else break;
}
return max_scores;
}
};
python3 解法, 执行用时: 48 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-20 11:10:03
class Solution:
def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
tokens.sort()
deque = collections.deque(tokens)
ans = bns = 0
while deque and (power >= deque[0] or bns):
while deque and power >= deque[0]:
power -= deque.popleft()
bns += 1
ans = max(ans, bns)
if deque and bns:
power += deque.pop()
bns -= 1
return ans
java 解法, 执行用时: 2 ms, 内存消耗: 40.4 MB, 提交时间: 2023-09-20 11:08:55
/**
* 贪心，在让令牌正面朝上的时候，肯定要去找能量最小的令牌。
* 同样的，在让令牌反面朝上的时候，肯定要去找能量最大的令牌。
*/
class Solution {
public int bagOfTokensScore(int[] tokens, int P) {
Arrays.sort(tokens);
int lo = 0, hi = tokens.length - 1;
int points = 0, ans = 0;
while (lo <= hi && (P >= tokens[lo] || points > 0)) {
while (lo <= hi && P >= tokens[lo]) {
P -= tokens[lo++];
points++;
}
ans = Math.max(ans, points);
if (lo <= hi && points > 0) {
P += tokens[hi--];
points--;
}
}
return ans;
}
}