34.贪心算法1
0.贪心算法
1.柠檬水找零（easy）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int x : bills) {
if (x == 5) // 5 元：直接收下
{
five++;
} else if (x == 10) // 10 元：找零 5 元
{
if (five == 0)
return false;
five--;
ten++;
} else // 20 元：分情况讨论
{
if (five != 0 && ten != 0) // 贪⼼
{
five--;
ten--;
} else if (five >= 3) {
five -= 3;
} else
return false;
}
}
return true;
}
}2.将数组和减半的最少操作次数
2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int halveArray(int[] nums) {
// 创建⼀个⼤根堆
PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
double sum = 0.0;
for (int x : nums) // 把元素都丢进堆中，并求出累加和
{
heap.offer((double) x);
sum += x;
}
sum /= 2.0; // 先算出⽬标和
int count = 0;
while (sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下
{
double t = heap.poll() / 2.0;
sum -= t;
count++;
heap.offer(t);
}
return count;
}
}3.最大数
179. 最大数 - 力扣（LeetCode）
题目解析
算法原理
---全序性
代码
class Solution {
public String largestNumber(int[] nums) {
// 优化：把所有的数转化成字符串
int n = nums.length;
String[] strs = new String[n];
for (int i = 0; i < n; i++)
strs[i] = "" + nums[i];
// 排序
Arrays.sort(strs, (a, b) -> {
return (b + a).compareTo(a + b);
});
// 提取结果
StringBuffer ret = new StringBuffer();
for (String s : strs)
ret.append(s);
if (ret.charAt(0) == '0')
return "0";
return ret.toString();
}
}4.摆动序列（medium）
376. 摆动序列 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n < 2)
return n;
int ret = 0, left = 0;
for (int i = 0; i < n - 1; i++) {
int right = nums[i + 1] - nums[i]; // 计算接下来的趋势
if (right == 0)
continue; // 如果⽔平，直接跳过
if (left * right <= 0)
ret++; // 累加波峰或者波⾕
left = right;
}
return ret + 1;
}
}5.最长递增子序列（medium）
300. 最长递增子序列 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int lengthOfLIS(int[] nums) {
ArrayList<Integer> ret = new ArrayList<>();
int n = nums.length;
ret.add(nums[0]);
for (int i = 1; i < n; i++) {
if (nums[i] > ret.get(ret.size() - 1)) // 如果能接在最后⼀个元素后⾯，直接放
{
ret.add(nums[i]);
} else {
// ⼆分插⼊位置
int left = 0, right = ret.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (ret.get(mid) < nums[i])
left = mid + 1;
else
right = mid;
}
ret.set(left, nums[i]); // 放在 left 位置上
}
}
return ret.size();
}
}6.递增的三元子序列（medium）
334. 递增的三元子序列 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public boolean increasingTriplet(int[] nums) {
int a = nums[0], b = Integer.MAX_VALUE;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > b)
return true;
else if (nums[i] > a)
b = nums[i];
else
a = nums[i];
}
return false;
}
}7.最长连续递增序列
674. 最长连续递增序列 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int findLengthOfLCIS(int[] nums) {
int ret = 0, n = nums.length;
for (int i = 0; i < n;) {
int j = i + 1;
// 找到递增区间的末端
while (j < n && nums[j] > nums[j - 1])
j++;
ret = Math.max(ret, j - i);
i = j; // 循环内部直接更新下⼀个位置的起点 - 贪⼼
}
return ret;
}
}8.买卖股票的最佳时机（easy）
121. 买卖股票的最佳时机 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int maxProfit(int[] prices) {
int ret = 0; // 记录最终结果
for (int i = 0, prevMin = Integer.MAX_VALUE; i < prices.length; i++) {
ret = Math.max(ret, prices[i] - prevMin); // 先更新结果
prevMin = Math.min(prevMin, prices[i]); // 再更新最⼩值
}
return ret;
}
}9.买卖股票的最佳时机 Ⅱ（medium）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int maxProfit(int[] prices)
{
// 实现⽅式⼀：双指针
int ret = 0, n = prices.length;
for(int i = 0; i < n; i++)
{
int j = i;
while(j + 1 < n && prices[j] < prices[j + 1]) j++; // 向后寻找上升的末端
ret += prices[j] - prices[i];
i = j;
}
return ret;
}
}
class Solution {
public int maxProfit(int[] prices) {
// 实现⽅式⼆：拆分成⼀天⼀天的形式
int ret = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
ret += prices[i] - prices[i - 1];
}
}
return ret;
}
}
10.K 次取反后最大化的数组和（easy）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
int m = 0, minElem = Integer.MAX_VALUE, n = nums.length;
for (int x : nums) {
if (x < 0)
m++;
minElem = Math.min(minElem, Math.abs(x));
}
// 分类讨论
int ret = 0;
if (m > k) {
Arrays.sort(nums);
for (int i = 0; i < k; i++) // 前 k ⼩个负数，变成正数
{
ret += -nums[i];
}
for (int i = k; i < n; i++) // 后⾯的数不变
{
ret += nums[i];
}
} else {
// 把负数全部变成正数
for (int x : nums)
ret += Math.abs(x);
if ((k - m) % 2 != 0) // 判断是否处理最⼩的正数
{
ret -= minElem * 2;
}
}
return ret;
}
}