36.贪心算法3
1.坏了的计算器（medium）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int brokenCalc(int startValue, int target) {
// 正难则反 + 贪⼼
int ret = 0;
while (target > startValue) {
if (target % 2 == 0)
target /= 2;
else
target += 1;
ret++;
}
return ret + startValue - target;
}
}2.合并区间（medium）
56. 合并区间 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int[][] merge(int[][] intervals) {
// 1. 按照左端点排序
Arrays.sort(intervals, (v1, v2) -> {
return v1[0] - v2[0];
});
// 2. 合并区间 - 求并集
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(right, b);
} else // 不能合并
{
ret.add(new int[] { left, right });
left = a;
right = b;
}
}
// 别忘了最后⼀个区间
ret.add(new int[] { left, right });
return ret.toArray(new int[0][]);
}
}
3.无重叠区间（medium）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
// 1. 按照左端点排序
Arrays.sort(intervals, (v1, v2) -> {
return v1[0] - v2[0];
});
// 2. 移除区间
int ret = 0;
int left = intervals[0][0], right = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
int a = intervals[i][0], b = intervals[i][1];
if (a < right) // 有重叠区间
{
ret++;
right = Math.min(right, b); // 贪⼼：删除右端点较⼤的区间
} else // 没有重叠区间
{
right = b;
}
}
return ret;
}
}
4.⽤最少数量的箭引爆⽓球（medium）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int findMinArrowShots(int[][] points) {
// 1. 按照左端点排序
Arrays.sort(points, (v1, v2) -> {
return v1[0] > v2[0] ? 1 : -1;
});
// 2. 求出互相重叠的区间的数量
int right = points[0][1];
int ret = 1;
for (int i = 1; i < points.length; i++) {
int a = points[i][0], b = points[i][1];
if (a <= right) // 有重叠
{
right = Math.min(right, b);
} else // 没有重叠
{
ret++;
right = b;
}
}
return ret;
}
}5.整数替换（medium）
397. 整数替换 - 力扣（LeetCode）
题目解析
算法原理
代码
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;
} else if (n % 4 == 1) {
n = n / 2;
ret += 2;
} else {
n = n / 2 + 1;
ret += 2;
}
}
}
return ret;
}
}6.俄罗斯套娃信封问题（hard）
. - 力扣（LeetCode）
题目解析
算法原理
代码
解法⼀：Java 算法代码：
class Solution {
public int maxEnvelopes(int[][] e) {
// 解法⼀：动态规划
Arrays.sort(e, (v1, v2) -> {
return v1[0] - v2[0];
});
int n = e.length;
int[] dp = new int[n];
int ret = 1;
for (int i = 0; i < n; i++) {
dp[i] = 1; // 初始化
for (int j = 0; j < i; j++) {
if (e[i][0] > e[j][0] && e[i][1] > e[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ret = Math.max(ret, dp[i]);
}
return ret;
}
}解法⼆（重写排序 + 贪⼼ + ⼆分）：
当我们把整个信封按照「下⾯的规则」排序之后： i. 左端点不同的时候：按照「左端点从⼩到⼤」排序； ii. 左端点相同的时候：按照「右端点从⼤到⼩」排序 我们发现，问题就变成了仅考虑信封的「右端点」，完完全全的变成的「最⻓上升⼦序列」的模 型。那么我们就可以⽤「贪⼼ + ⼆分」优化我们的算法。
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(mid) >= b)
right = mid;
else
left = mid + 1;
}
ret.set(left, b);
}
}
return ret.size();
}
}7.可被三整除的最⼤和（medium）
. - 力扣（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);
}
}8.距离相等的条形码（medium）
. - 力扣（LeetCode）
题目解析
算法原理
代码
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)) {
maxVal = x;
maxCount = hash.get(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;
}
}9.矩阵中的最长递增路径
767. 重构字符串 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public String reorganizeString(String s) {
int[] hash = new int[26];
char maxChar = ' ';
int maxCount = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (maxCount < ++hash[ch - 'a']) {
maxChar = ch;
maxCount = hash[ch - 'a'];
}
}
int n = s.length();
// 先判断
if (maxCount > (n + 1) / 2)
return "";
char[] ret = new char[n];
int index = 0;
// 先处理次数最多的字符
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);
}
}