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;} elsereturn 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;elseright = 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];elsea = 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;}
}