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;elsetarget += 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;elseleft = 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);elsereturn 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);}
}