題目鏈接
題目:你的初始能量為 P,初始分數為 0,只有一包令牌。
令牌的值為 token[i],每個令牌最多只能使用一次,可能的兩種使用方法如下:
leetcode 518?如果你至少有 token[i] 點能量,可以將令牌置為正面朝上,失去 token[i] 點能量,并得到 1 分。
如果我們至少有 1 分,可以將令牌置為反面朝上,獲得 token[i] 點能量,并失去 1 分。
在使用任意數量的令牌后,返回我們可以得到的最大分數。
示例:
示例 1:
輸入:tokens = [100], P = 50
輸出:0
示例 2:
輸入:tokens = [100,200], P = 150
輸出:1
示例 3:
leetcode121、輸入:tokens = [100,200,300,400], P = 200
輸出:2
別人思路:先對tokens進行排序,然后從前面較小能量的值換分數,然后用分數換后面較大的能量,在從前面較小的能量值換分數,貪心算法。
class Solution {public int bagOfTokensScore(int[] tokens, int P) {int left = 0;int right = tokens.length - 1;int res = 0;int points = 0;Arrays.sort(tokens);while(left <= right){if(P >= tokens[left]){P -= tokens[left];left++;points++;res = Math.max(points, res);}else if(points > 0){P += tokens[right];right--;points--;}else{break;}}return res;}
}
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态