目录
贪心算法
贪心算法：
策略极多。
贪心策略：局部最优->全局最优
1. 把解决问题的过程分为若干个部分
2. 解决每一步的时候，都选择当前看起来最优的解法
3. “希望”得到全局最优解
贪心算法的特点：
1. 贪心策略的提出是没有标准以及模板的
2. 可能每一道题的贪心策略都是不同的
有的时候，贪心策略是一个错误的方法。正确的贪心策略，我们是需要“证明的”
学习方法：
1. 前期学习的时候，把重点放在贪心的策略上，把这个策略当成经验吸收
2. 如何去证明
柠檬水找零
解法：贪心 分情况讨论：
5->收下；
10->找5，收10；
20->找10+5或者5+5+5
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;// 统计5、10的数量
for (int x : bills) {
if (x == 5)
five++;// 不用找钱
else if (x == 10) {
ten++;
if (five < 1)
return false;
else
five--;
} else {// 付20
if (ten >= 1 && five >= 1) {
ten--;
five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
}将数组和减半的最少操作次数
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;
heap.offer(t);
sum -= t;
count++;
}
return count;
}
}最大数
解法：
正常的排序本质（升序）：确定元素的先后顺序，谁在前，谁在后
排序规则：
a>b -> a前，b后
a=b -> 无所谓
a<b -> b前，a后
本题的排序（优化）：把数转化成字符串，然后拼接字符串，比较字典序
排序规则：
ab>ba -> a前，b后
ab=ba -> 无所谓
ab<ba -> b前，a后
class Solution {
public String largestNumber(int[] nums) {
int n = nums.length;
String[] s = new String[n];
for (int i = 0; i < n; i++) {
s[i] = "" + nums[i];// 将整数数组转为字符串数组
}
Arrays.sort(s, (a, b) -> {// 重写排序
return (b + a).compareTo(a + b);// 返回最大数
});
StringBuffer ret = new StringBuffer();
for (String ss : s) {
ret.append(ss);// 对字符串数组中元素进行拼接（最大数）
}
if (ret.charAt(0) == '0')
return "0";
return ret.toString();
}
}摆动序列
解法：贪心
估计出所有的波峰以及波谷的个数（左右两边相减后符号不同）
核心思路：
right=nums[ i+1 ]-nums[ i ]
if(right==0) continue;
if(left*right<=0) ret++;
left=right;
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length, ret = 0, left = 0;
if (n < 2)
return 1;
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;
}
}⭐最长递增子序列
解法：动态规划+二分（优化）
1. dp解法：
- 状态表示：dp[i]表示，以i位置的元素为结尾的所有子序列中，最长递增子序列的长度
- 状态转移方程：dp[i]=max(dp[j]+1)(j<i&&nums[j]<nums[i])
在考虑最长递增子序列的“长度”的时候，不需要关心这个序列是什么样子，仅需关心“最后一个元素”是谁。
2. 贪心优化：
- 存什么：所有长度为x的递增子序列中，最后一个元素的最小值
- 存哪里：所有大于等于nums[i]的最小值的位置
3. 利用二分优化
class Solution {
public int lengthOfLIS(int[] nums) {
ArrayList<Integer> ret = new ArrayList<>();
int n = nums.length;
ret.add(nums[0]);// 先把nums中第一个数放进去
for (int i = 0; i < n; i++) {
if (nums[i] > ret.get(ret.size() - 1)) {// 下一个数>ret中最后一个数
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]);
}
}
return ret.size();
}
}递增的三元子序列
解法一：动态规划 - 利用dp找到数组中最长递增子序列的长度，判断是否大于等于3即可
解法二：贪心 - >O(n)
class Solution {
public boolean increasingTriplet(int[] nums) {
ArrayList<Integer> ret = new ArrayList<>();
ret.add(nums[0]);
int n = nums.length;
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]);
}
}
return ret.size() >= 3 ? true : false;
}
}优化：
class Solution {
public boolean increasingTriplet(int[] nums) {
int a = nums[0], b = Integer.MAX_VALUE;
int n = nums.length;
for (int i = 1; i < n; i++) {
if (nums[i] > b)
return true;
else if (nums[i] > a)
b = nums[i];
else
a = nums[i];
}
return false;
}
}最长连续递增序列
解法：贪心+双指针
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;
}
}买卖股票的最佳时机
解法一：暴力解法，两层for循环的暴力枚举 O(
)
解法二：贪心 + 一个变量标记“前缀最小值”prevMin O(n)
class Solution {
public int maxProfit(int[] prices) {
int ret = 0, prevmin = Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++) {
ret = Math.max(ret, prices[i] - prevmin);// 更新结果
prevmin = Math.min(prevmin, prices[i]);// 更新最小值
}
return ret;
}
}买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II - 力扣（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;
}
}K 次取反后最大化的数组和
1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
解法一：每次排序后，一直将最小数取反
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
int x = 0;
while (x < k) {
Arrays.sort(nums);
nums[0] = (-nums[0]);
x++;
}
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
return sum;
}
}解法二：贪心——>分情况讨论：
按身高排序
解法一：创建二元组
- 创建一个新的数组 pair<int,string>;
- 对新的数组排序；
- 按照顺序把名字提取出来即可；
解法二：利用哈希表存下映射关系（缺陷：身高相同时比较麻烦）
- 先用哈希表存下映射关系：<身高，名字>；
- 对身高数组排序；
- 根据排序后的结果，往哈希表里面找名字即可；
解法三：对下标排序（常用）
- 创建一个下标数组；
- 仅对下标数组排序；
- 根据下标数组排序后的结果，找到原数组的信息
class Solution {
public String[] sortPeople(String[] names, int[] heights) {
// 创建一个下标数组
int n = names.length;
Integer[] index = new Integer[n];
for (int i = 0; i < n; i++)
index[i] = i; // index={0,1,2,3,4,···};
// 对下标数组排序
Arrays.sort(index, (i, j) -> {
return heights[j] - heights[i];
});
// 提取结果
String[] ret = new String[n];
for (int i = 0; i < n; i++) {
ret[i] = names[index[i]];
}
return ret;
}
}优势洗牌
解法：田忌赛马-废物利用最大化
排序：
- 如果比不过，就去拖累对方最强的那个
- 如果能比过，就直接比
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
// 1. 排序
Arrays.sort(nums1);
Integer[] index2 = new Integer[n];
for (int i = 0; i < n; i++)
index2[i] = i;
Arrays.sort(index2, (i, j) -> {
return nums2[i] - nums2[j];
});
// 2. 田忌赛马
int[] ret = new int[n];
int left = 0, right = n - 1;
for (int x : nums1) {
if (x > nums2[index2[left]])
ret[index2[left++]] = x;
else
ret[index2[right--]] = x;// 废物利用最大化
}
return ret;
}
}最长回文串
class Solution {
public int longestPalindrome(String s) {
// 1. 计数 - 用数组模拟哈希表
int[] count = new int[128]; // 覆盖所有ASCII字符
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
count[c]++;
}
// 2. 统计结果
int sum = 0;
boolean hasOdd = false;
for (int c : count) {
sum += c / 2 * 2; // 取最大偶数次
if (c % 2 != 0) {
hasOdd = true;
}
}
return hasOdd ? sum + 1 : sum;
}
}增减字符串匹配
解法：贪心
- 当遇到“ I ”：选择当前最小的那个数
- 当遇到“ D ”：选择当前最大的那个数
class Solution {
public int[] diStringMatch(String s) {
int n = s.length();
int[] ret = new int[n + 1];
int left = 0, right = n, i = 0;
while (left < right) {
if (s.charAt(i) == 'I') {
ret[i++] = left++;
} else {
ret[i++] = right--;
}
}
ret[n] = left; // 把最后一个数放进去
return ret;
}
}分发饼干
解法：贪心策略：
排序，针对当前胃口最小的孩子，挑选饼干：
- 能满足，直接喂
- 不能满足，删掉这个饼干
class Solution {
public int findContentChildren(int[] g, int[] s) {
int ret = 0, i = 0, j = 0;
Arrays.sort(g);
Arrays.sort(s);
while (i < g.length && j < s.length) {
if (g[i] <= s[j]) {
ret++;
i++;
j++;
} else {
j++;
}
}
return ret;
}
}最优除法
解法一：暴力解法->递归->记忆化搜索->动态规划（麻烦）
解法二：贪心
除了前两个数以外，其余的数全放在分子上即可
class Solution {
public String optimalDivision(int[] nums) {
int n = nums.length;
StringBuffer ret = new StringBuffer();
if (n == 1) {
return ret.append(nums[0]).toString();
} else if (n == 2) {
return ret.append(nums[0]).append("/").append(nums[1]).toString();
} else {
ret.append(nums[0]).append("/(");
int i = 1;
while (i < n - 1) {
ret.append(nums[i++]).append("/");
}
ret.append(nums[n - 1]).append(")");
}
return ret.toString();
}
}跳跃游戏 II
解法一：贪心（×）
解法二：动态规划
dp[ i ]表示：从0位置开始，到达 i 位置时的最小跳跃次数
解法三：类似层序遍历的过程
class Solution {
public int jump(int[] nums) {
int left = 0, right = 0, ret = 0, maxpos = 0, n = nums.length;
while (left <= right) {
if (maxpos >= n - 1)
return ret;
for (int i = left; i <= right; i++) {
maxpos = Math.max(maxpos, nums[i] + i);
}
left = right + 1;
right = maxpos;
ret++;
}
return -1;
}
}跳跃游戏
解法同上
class Solution {
public boolean canJump(int[] nums) {
int left = 0, right = 0, maxpos = 0, n = nums.length;
while (left <= right) {
if (maxpos >= n - 1)
return true;
for (int i = left; i <= right; i++) {
maxpos = Math.max(maxpos, nums[i] + i);
}
left = right + 1;
right = maxpos;
}
return false;
}
}加油站
解法一：暴力枚举（超时）O(
净收益：diff = [-2，-2，-2，3，3]
- 依次枚举所有的起点
- 从起点开始，模拟一遍加油的流程即可
解法二：贪心 O(n)
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int curgas = 0, tank = 0, n = gas.length, begin = 0;
int[] diff = new int[n];
for (int i = 0; i < n; i++) {
curgas += gas[i] - cost[i];
tank += gas[i] - cost[i];
if (tank < 0) {
begin = i + 1;
tank = 0;
}
}
return curgas >= 0 ? begin : -1;
}
}单调递增的数字
解法一：暴力枚举
- 从大到小的顺序，枚举[n，0]区间内的数字
- 判断数字是否是“单调递增的”
- 数字->字符串
- 模10，除以10
解法二：贪心（找规律）
- 如果高位单增，则不修改
- 从左往右，找到第一个递减的位置（从这个位置向前推，推到相同区域的最左端），使其减小1，后面的数全部修改为9
class Solution {
public int monotoneIncreasingDigits(int n) {
// 把数字转化为字符数组
char[] s = Integer.toString(n).toCharArray();
int i = 0, m = s.length;
// 找到第一个递减的位置
while (i + 1 < m && s[i] <= s[i + 1])
i++;
if (i == m - 1)
return n;// 特殊情况
// 回退
while (i - 1 >= 0 && s[i] == s[i - 1])
i--;
s[i]--;
for (int j = i + 1; j < m; j++)
s[j] = '9';
return Integer.parseInt(new String(s));// 将字符数组转化为整型
}
}坏了的计算器
解法一：正向推导（难）
解法二：正难则反
class Solution {
public int brokenCalc(int start, int target) {
// 正难则反+贪心
int ret = 0;
while (target > start) {
if (target % 2 == 0)
target /= 2;
else
target += 1;
ret++;
}
return ret + start - target;
}
}【区间问题】
- 排序——按照左端点或右端点
- 根据排序后结果总结规律，进而得出解决问题的策略
合并区间
解法：排序（左端点）+贪心策略
- 先按照左端点排序——性质：能够合并的区间都是连续的-只需遍历数组一次
- 如何合并——求并集
class Solution {
public int[][] merge(int[][] intervals) {
// 按照左端点排序
Arrays.sort(intervals, (v1, v2) -> {
return v1[0] - v2[0];
});
// 合并区间-求并集
int left = intervals[0][0], right = intervals[0][1];
List<int[]> ret = new ArrayList<>();
for (int i = 1; i < intervals.length; i++) {
int a = intervals[i][0], b = intervals[i][1];
if (a <= right) {// 有重叠部分-合并
right = Math.max(b, right);
} else {// 不能合并
ret.add(new int[] { left, right });// 把结果加入数组中
left = a;
right = b;
}
}
// 最后一个区间
ret.add(new int[] { left, right });
return ret.toArray(new int[0][]);// 不限行不限列
}
}无重叠区间
解法：排序（左端点）+贪心策略
- 按照左端点排序
- 移除区间（移除最少的区间，保留更多的区间）
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
// 按左端点进行排序
Arrays.sort(intervals, (v1, v2) -> {
return v1[0] - v2[0];
});
// 贪心
int left = intervals[0][0], right = intervals[0][1];
int count = 0;
for (int i = 1; i < intervals.length; i++) {
int a = intervals[i][0], b = intervals[i][1];
if (a < right) {// 有重叠部分
right = Math.min(b, right);
count++;
} else {// 没有重叠部分
left = a;
right = b;
}
}
return count;
}
}用最少数量的箭引爆气球
452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
解法：排序（左端点）+贪心策略
- 按照左端点排序
- 性质：按照左端点排序之后，互相重叠的区间是连续的
- 提出贪心策略
- 最少的弓箭数量->一支箭应该引爆更多的气球->将互相重叠的所有区间都拿出来引爆
class Solution {
public int findMinArrowShots(int[][] points) {
// 按左端点排序
Arrays.sort(points, (v1, v2) ->
// return v1[0] - v2[0];
Integer.compare(v1[0], v2[0])// 防溢出
);
// 贪心
int ret = 0;
int left = points[0][0], right = points[0][1];
for (int i = 1; i < points.length; i++) {
int a = points[i][0], b = points[i][1];
if (a <= right) {
ret++;
right = Math.min(b, right);
} else {
left = a;
right = b;
}
}
return points.length - ret;
}
}整数替换
解法一：模拟 - 递归（暴力）
class Solution {
public int integerReplacement(int n) {
return dfs((long) n);
}
public int dfs(long n) {
if (n == 1)
return 0;
if (n % 2 == 0)
return 1 + dfs(n / 2);
else {
return 1 + Math.min(dfs(n + 1), dfs(n - 1));// 最小值
}
}
}加上备忘录（记忆化搜索）：
class Solution {
// 加上备忘录
Map<Long, Integer> hash;
public int integerReplacement(int n) {
hash = new HashMap<>();
return dfs((long) n);
}
public int dfs(long n) {
if (hash.containsKey(n))
return hash.get(n);
if (n == 1) {
hash.put(n, 0);
return hash.get(n);
}
if (n % 2 == 0) {
hash.put(n, 1 + dfs(n / 2));
return hash.get(n);
} else {
hash.put(n, 1 + Math.min(dfs(n + 1), dfs(n - 1)));// 最小值存入备忘录
return hash.get(n);
}
}
}解法二：贪心+分类讨论（不好想）
补充：二进制
- 偶数：二进制表示中最后一位为0
- 奇数：二进制表示中最后一位为1
- ÷2操作：二进制表示中右移一位
class Solution {
public int integerReplacement(int n) {
int ret = 0;
while (n > 1) {
// 分类讨论
if (n % 2 == 0) {// 偶数
n /= 2;
ret++;
} else {// 奇数
if (n == 3) {
ret += 2;// 需要两步
n = 1;// 将n置为1
} else if (n % 4 == 1) {
n = (n - 1) / 2;
ret += 2;// 需要两步
} else {
n = n / 2 + 1;// (同n=(n+1)/2);
ret += 2;
}
}
}
return ret;
}
}俄罗斯套娃信封问题
解法一：常规解法->动态规划+贪心+二分
乱序 -> 有序 -> 按照左端点排序 -> 最长递增子序列
- 状态表示 dp[i] 表示：以 i 位置的信封为结尾的所有套娃序列中，最长的套娃序列的长度
- 状态转移方程 dp[i]=max(dp[j]+1) -> 0<=j<i;e[ i ][ 0 ]>e[ j ][ 0 ];e[ i ][ 1 ]>e[ j ][ 1 ]
- 初始化
- 填表顺序
- 返回值
解法二：重写排序（左端点从小到大）+贪心+二分（找到规律）
重写排序：-> 最长递增子序列
- 左端点不同
- 左端点从小到大排序
- 左端点相同
- 右端点从大到小排序
class Solution {
public int maxEnvelopes(int[][] e) {
// 重写排序
Arrays.sort(e, (v1, v2) -> {
return v1[0] != v2[0] ? v1[0] - v2[0] : v2[1] - v1[1];
});
// 贪心+二分
ArrayList<Integer> ret = new ArrayList<>();
ret.add(e[0][1]);
for (int i = 1; i < e.length; i++) {
int b = e[i][1];
if (b > ret.get(ret.size() - 1))
ret.add(b);
else {
int left = 0, right = ret.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (ret.get(ret.size() - 1) >= b)
right = mid;
else
left = mid + 1;
}
ret.set(left, b);
}
}
return ret.size();
}
}可被三整除的最大和
1262. 可被三整除的最大和 - 力扣（LeetCode）
解法：正难则反+贪心+分类讨论
先把所有的数累加在一起->根据累加和，删除一些数
class Solution {
public int maxSumDivThree(int[] nums) {
int INF = 0x3f3f3f3f;
int sum = 0, x1 = INF, x2 = INF, y1 = INF, y2 = INF;
for (int x : nums) {
sum += x;
// 找最小值和次小值
if (x % 3 == 1) {
if (x < x1) {
x2 = x1;
x1 = x;
} else if (x < x2) {
x2 = x;
}
} else if (x % 3 == 2) {
if (x < y1) {
y2 = y1;
y1 = x;
} else if (x < y2) {
y2 = x;
}
}
}
// 分类讨论
if (sum % 3 == 0)
return sum;
else if (sum % 3 == 1)
return Math.max(sum - x1, sum - y1 - y2);
else
return Math.max(sum - y1, sum - x1 - x2);
}
}解法二：动态规划
距离相等的条形码
解法：贪心+模拟+哈希表
每次处理一批相同的数，摆放的时候每次隔一个格子（先处理出现次数最多的数，剩下的数的处理顺序无所谓）
class Solution {
public int[] rearrangeBarcodes(int[] b) {
Map<Integer, Integer> hash = new HashMap<>();
int maxval = 0, maxcount = 0;
for (int x : b) {
hash.put(x, hash.getOrDefault(x, 0) + 1);
if (maxcount < hash.get(x)) {
maxcount = hash.get(x);
maxval = x;
}
}
int n = b.length;
int[] ret = new int[n];
int index = 0;
// 先处理出现次数最多的数
for (int i = 0; i < maxcount; i++) {
ret[index] = maxval;
index += 2;
}
hash.remove(maxval);
for (int x : hash.keySet()) {
for (int i = 0; i < hash.get(x); i++) {
if (index >= n)
index = 1;
ret[index] = x;
index += 2;
}
}
return ret;
}
}重构字符串
解法：贪心+模拟
- 每次处理一批相同的字符
- 摆放的时候，隔一个位置放一个字符
- 优先处理出现次数最多的字符
class Solution {
public String reorganizeString(String s) {
// 先统计个数
int n = s.length();
int[] hash = new int[26];
int maxcount = 0;
char maxchar = ' ';
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (maxcount < ++hash[ch - 'a']) {
maxchar = ch;
maxcount = hash[ch - 'a'];
}
}
int index = 0;
char[] ret = new char[n];
// 先判断
if (maxcount > (n + 1) / 2)
return "";
// 先处理出现次数最多的数
for (int i = 0; i < maxcount; i++) {
ret[index] = maxchar;
index += 2;
}
hash[maxchar - 'a'] = 0;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < hash[i]; j++) {
if (index >= n)
index = 1;
ret[index] = (char) (i + 'a');
index += 2;
}
}
return new String(ret);
}
}