【贪默算法3】
力扣1005.k次取反后最大化的数组和链接: link
思绪
既然要求最大和，那么不妨先给数组排个序，如果有负数，先处理惩罚负数从前往后给数组取反，如果负数处理惩罚完后k尚有次数，此时数组满是正数了，只必要对第一个元素取反即可，无非就是奇数次或者偶数次取反使用。最终求和即可。
方法1:
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
if (nums.length == 1)
return nums;
int ans = 0;
Arrays.sort(nums);
// 先处理负数
for (int i = 0; i < nums.length && k > 0; i++) {
if (nums < 0) {
nums = -nums;
k--;
}
}
// 如果k还有次数
if (k % 2 == 1) {
Arrays.sort(nums);
nums = -nums;
}
for (int num : nums) {
ans += num;
}
return ans;
}
}
相似题型
134.加油站
链接: link
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int start = 0;
int curSum = 0;
int totalSum = 0;
for (int i = 0; i < gas.length; i++) {
curSum += gas - cost;
totalSum += gas - cost;
// 如果出现汽油小于使用量
if (curSum < 0) {
start = i + 1;
curSum = 0;
}
}
// 总共gas < cost 一定不能跑完一圈
if (totalSum < 0) {
return -1;
}
return start;
}
}
135.分发糖果
链接: link
class Solution {
public int candy(int[] ratings) {
int res = 0;
int[] candyList = new int;
Arrays.fill(candyList, 1);
// 从左向右比较左孩子
for (int i = 1; i < ratings.length; i++) {
if (ratings > ratings) {
candyList = candyList + 1;
}
}
// 从右向左比较右孩子
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings > ratings) {
candyList = Math.max(candyList, candyList + 1);
}
}
for (int c : candyList) {
res += c;
}
return res;
}
}
860.柠檬水找零
链接: link
class Solution {
public boolean lemonadeChange(int[] bills) {
int m5 = 0, m10 = 0;
for (int i = 0; i < bills.length; i++) {
if (bills == 5) {
m5++;
} else if (bills == 10) {
m10++;
m5--;
} else if (bills == 20) {
if (m10 != 0) {
m10--;
m5--;
} else {
m5 -= 3;
}
}
if (m5 < 0 || m10 < 0) {
return false;
}
}
return true;
}
}
406.根据身高重建队列
链接: link
class Solution {
public int[][] reconstructQueue(int[][] people) {
// 对身高排序
Arrays.sort(people, (a, b) -> {
if (a == b)
return a - b; // a-b 是升序排列，按照k升序
return b - a;// 否则按照身高降序排列
});
List<int[]> que = new ArrayList<>();
for (int i = 0; i < people.length; i++) {
que.add(people, people);
}
return que.toArray(new int[]);
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]