贪心算法3
目录
【贪心算法3】
力扣1005.k次取反后最大化的数组和
链接:
思路
既然要求最大和，那么不妨先给数组排个序，如果有负数，先处理负数从前往后给数组取反，如果负数处理完后k还有次数，此时数组全是正数了，只需要对第一个元素取反即可，无非就是奇数次或者偶数次取反操作。最终求和即可。
方法1:
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
if (nums.length == 1)
return nums[0];
int ans = 0;
Arrays.sort(nums);
// 先处理负数
for (int i = 0; i < nums.length && k > 0; i++) {
if (nums[i] < 0) {
nums[i] = -nums[i];
k--;
}
}
// 如果k还有次数
if (k % 2 == 1) {
Arrays.sort(nums);
nums[0] = -nums[0];
}
for (int num : nums) {
ans += num;
}
return ans;
}
}相似题型
134.加油站
链接:
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[i] - cost[i];
totalSum += gas[i] - cost[i];
// 如果出现汽油小于使用量
if (curSum < 0) {
start = i + 1;
curSum = 0;
}
}
// 总共gas < cost 一定不能跑完一圈
if (totalSum < 0) {
return -1;
}
return start;
}
}135.分发糖果
链接:
class Solution {
public int candy(int[] ratings) {
int res = 0;
int[] candyList = new int[ratings.length];
Arrays.fill(candyList, 1);
// 从左向右比较左孩子
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candyList[i] = candyList[i - 1] + 1;
}
}
// 从右向左比较右孩子
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyList[i] = Math.max(candyList[i], candyList[i + 1] + 1);
}
}
for (int c : candyList) {
res += c;
}
return res;
}
}860.柠檬水找零
链接:
class Solution {
public boolean lemonadeChange(int[] bills) {
int m5 = 0, m10 = 0;
for (int i = 0; i < bills.length; i++) {
if (bills[i] == 5) {
m5++;
} else if (bills[i] == 10) {
m10++;
m5--;
} else if (bills[i] == 20) {
if (m10 != 0) {
m10--;
m5--;
} else {
m5 -= 3;
}
}
if (m5 < 0 || m10 < 0) {
return false;
}
}
return true;
}
}406.根据身高重建队列
链接:
class Solution {
public int[][] reconstructQueue(int[][] people) {
// 对身高排序
Arrays.sort(people, (a, b) -> {
if (a[0] == b[0])
return a[1] - b[1]; // a-b 是升序排列，按照k升序
return b[0] - a[0];// 否则按照身高降序排列
});
List<int[]> que = new ArrayList<>();
for (int i = 0; i < people.length; i++) {
que.add(people[i][1], people[i]);
}
return que.toArray(new int[people.length][]);
}
}