leetcode之贪心算法刷题总结4
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。贪心算法需要充分挖掘题目中条件，没有固定的模式，解决有贪心算法需要一定的直觉和经验。
贪心算法不是对所有问题都能得到整体最优解。能使用贪心算法解决的问题具有「贪心选择性质」。「贪心选择性质」严格意义上需要数学证明。能使用贪心算法解决的问题必须具备「无后效性」，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
1-最长快乐字符串
题目链接：题目链接戳这里！！！
思路：构造数组，按照每个字符的个数由多到少实时排序，定义StringBuilder对象sb，如果sb的最后两位是数量最多的字符，则此时需要使用数量次多的字符，如果sb最后两位不是数量最多的字符，则在sb后追加数量最多的字符。
class Solution {
public String longestDiverseString(int a, int b, int c) {
//构造数组，按每个字符的个数实时排序
int [][] arr = {{'a',a},{'b',b},{'c',c}} ;
StringBuilder sb = new StringBuilder() ;
while(true){
Arrays.sort(arr, (x, y) -> y[1] - x[1]);
if(arr[0][1]==0){
break ;
}
int n = sb.length() ;
if(n>=2 && sb.charAt(n-1) == arr[0][0] && sb.charAt(n-2)==arr[0][0]){
if(arr[1][1]==0){
break ;
}
sb.append((char)arr[1][0]) ;
arr[1][1] -- ;
}else{
sb.append((char)arr[0][0]) ;
arr[0][1] -- ;
}
}
return sb.toString() ;
}
}
2-交换一次的先前排列
题目链接：题目链接戳这里！！！
思路：一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大可能排列。从后向前找逆序，找到逆序后与右面最大的一个值交换即可,如果最大的有多个，交换最前面的最大的。
class Solution {
public int[] prevPermOpt1(int[] arr) {
//从后向前找逆序，找到逆序后与右面最大的一个值交换即可,如果最大的有多个，交换最前面的最大的
for(int i=arr.length-1; i>0; i--){
if(arr[i] < arr[i-1]){
for(int j=arr.length-1; j>=i; j--){
if(arr[i-1]>arr[j] && arr[j] != arr[j-1]){
int temp = arr[i-1] ;
arr[i-1] = arr[j] ;
arr[j] = temp ;
return arr ;
}
}
}
}
return arr ;
}
}
3-数组大小减半
题目链接：题目链接戳这里！！！
思路：map统计所有数字出现的次数，同时map的键存入优先队列，同时优先队列按照值降序排序，每次累加值，如果sum大于数组长度的一半，则结束循环。
class Solution {
public int minSetSize(int[] arr) {
int ans = 0, sum = 0 , n = arr.length ;
Map<Integer, Integer> map = new HashMap<>() ;
for(int num : arr){
map.put(num, map.getOrDefault(num, 0) + 1) ;
}
//优先队列，按照值降序排序
PriorityQueue<Integer> heap = new PriorityQueue<>((o1,o2)->map.get(o2)-map.get(o1));
heap.addAll(map.keySet()) ; //队列中存入键，按照值排序
while(sum < n / 2){
sum += map.get(heap.poll()) ;
ans ++ ;
}
return ans ;
}
}
这样写也是可以的，哈哈哈，思路一样，换成数组模拟,效率更高。用cnt记录每个数字出现的次数，然后对cnt升序排序，然后从后向前遍历cnt，判断数组是否减半即可。
class Solution {
public int minSetSize(int[] arr) {
int ans = 0, sum = 0 , n = arr.length ;
int [] cnt = new int [100001] ;
for(int num : arr){
cnt[num] ++ ;
}
Arrays.sort(cnt) ;
for(int i=cnt.length-1; i>=0; i--){
if(sum >= n / 2){
break ;
}
sum += cnt[i] ;
ans ++ ;
}
return ans ;
}
}
4-和为K的最少斐波那契数字数目
题目链接：题目链接戳这里！！！
思路：每一次从前向后找那个小于k的最大斐波那契数字，然后用k减取它，直至k等于0.
class Solution {
public int findMinFibonacciNumbers(int k) {
int ans = 0, f1 = 1, f2 = 1 ;
while(k!=0){
f1 = f2 = 1 ;
while(f2<=k){
f2 += f1 ;
f1 = f2-f1 ;
}
k -= f1 ;
ans ++ ;
}
return ans ;
}
}
5-构造K个回文字符串
题目链接：题目链接戳这里！！！
思路：这题技巧性很强，不太容易想到哦，判断能否将字符串构建成k个回文字符串，如果能构成需要满足两个条件。
第一：s的长度大于等于k
第二：s中奇数字符串的长度小于等于k
class Solution {
public boolean canConstruct(String s, int k) {
//s的长度大于等于k且s中奇数字符的个数小于等于k
int [] cnt = new int [26] ;
int n = s.length() ;
for(int i=0; i<n; i++){ //统计每个字符出现的次数
cnt[s.charAt(i)-'a'] ++ ;
}
int odd = 0 ;
for(int i=0; i<26; i++){
if(cnt[i] % 2 == 1){
odd ++ ;
}
}
return odd<=k && n>=k ;
}
}
6-检查一个字符串是否可以打破另一个字符串
题目链接：题目链接戳这里！！！
思路：对两个字符串分别进行升序排序，然后分别比较是否满足条件即可。
对于所有c1[i]>=c2[i] 或者 对于所有的c1[i]<=c2[i]都是满足条件的。
class Solution {
public boolean checkIfCanBreak(String s1, String s2) {
char [] c1 = s1.toCharArray() ;
char [] c2 = s2.toCharArray() ;
Arrays.sort(c1) ;
Arrays.sort(c2) ;
return f(c1,c2) || f(c2,c1) ;
}
public boolean f(char [] c1, char [] c2){
for(int i=0; i<c1.length; i++){
if(c1[i]<c2[i]){
return false ;
}
}
return true ;
}
}
7-不同整数的最少数目
题目链接：题目链接戳这里！！！
思路：这题很好想，不太好实现，因为删除k次，使得不同的数字的数目变的最少，所以每次删除数字中出现次数最少的数。用map存储每个数字的出现次数，建立优先队列，按照map中值的由小到大排序，只有当map中的值为0时候，ans才累加。
class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> map = new HashMap<>() ;
for(int num : arr){ //记录每个数字出现的个数
map.put(num, map.getOrDefault(num, 0) + 1) ;
}
int ans = 0 ;
int n = map.keySet().size() ;
boolean flag = true ;
PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->map.get(o1)-map.get(o2));
queue.addAll(map.keySet()) ;
while(k>0){
int value = map.get(queue.element()) ;
k -- ;
value -= 1 ;
if(value==0){
map.remove(queue.element()) ;
queue.poll() ;
flag = true ;
}else{
map.put(queue.peek(), value) ;
flag = false ;
}
if(flag){
ans ++ ;
}
}
return n-ans ;
}
}
8-非递增顺序的最小子序列
题目链接：题目链接戳这里！！！
思路：前缀和+贪心
对数组元素升序，然后先求出所有元素的前缀和，避免后面重复求和，从后向前遍历数组元素，累加当前元素，如果当前元素和，大于前面则结束循环。
class Solution {
public List<Integer> minSubsequence(int[] nums) {
Arrays.sort(nums) ;
int [] sums = new int [nums.length+1] ;
for(int i=1; i<sums.length; i++){
sums[i] = nums[i-1] + sums[i-1] ;
}
List<Integer> ans = new ArrayList<>() ;
int sum = 0 ;
for(int i=nums.length-1; i>=0; i--){
sum += nums[i] ;
ans.add(nums[i]) ;
if(sum>sums[i]){
break ;
}
}
return ans ;
}
}
9-最少的后缀翻转次数
题目链接：题目链接戳这里！！！
思路：每次相邻的不一样，则需要向后翻转一次，首先要记录第一位是否需要翻转。
class Solution {
public int minFlips(String target) {
int ans = 0 ;
if(target.charAt(0)=='1'){ //判断第一位是否需要翻转
ans ++ ;
}
for(int i=0; i<target.length()-1; i++){
if(target.charAt(i) != target.charAt(i+1)){
ans ++ ;
}
}
return ans ;
}
}
10-三次操作后最大值与最小值得最小差
题目链接：题目链接戳这里！！！
思路：这个操作过程其实就是删除过程，三次操作，保证最大值和最小值得差最小，那么每次都对数组中得最大值或者最小值进行操作是最优得选择，故三次操作分为四种情况：
四种情况：删除三个最大，删除三个最小，删除两个最大一个最小，删除一个最大两个最小
class Solution {
public int minDifference(int[] nums) {
if(nums.length<=4){
return 0 ;
}
Arrays.sort(nums) ;
//三次操作，四种情况，删除三个最大，删除三个最小，删除两个最大一个最小，删除一个最大两个最小
int a = Math.min(nums[nums.length-4] - nums[0], nums[nums.length-1]-nums[3]);
int b = Math.min(nums[nums.length-3] - nums[1], nums[nums.length-2] - nums[2]) ;
return Math.min(a,b) ;
}
}
11-你可以获得的最大硬币数目
题目链接：题目链接戳这里！！！
思路：保证你可以获得最大硬币数额，那就要先对数组进行升序排序，然后每次取出两个最大和一个最小，这样最后可以保证你拿到的硬币数额最大。
class Solution {
public int maxCoins(int[] piles) {
Arrays.sort(piles) ;
int ans = 0 ;
//两个人最大配一个最小
int j = 0 ;
for(int i=piles.length-2; i>=j; i-=2){
ans += piles[i] ;
j ++ ;
}
return ans ;
}
}
12-字符频次唯一的最小删除次数
题目链接：题目链接戳这里！！！
思路：count数组记录每个字符出现的频次，对于每个字符，如果频次之前没有出现过，则不需要管，如果之前出现过，则需要将当前频次减1，直至频次没有出现。
class Solution {
public int minDeletions(String s) {
int [] count = new int [26] ;
for(int i=0; i<s.length(); i++){ //记录每个字符出现的次数
count[s.charAt(i)-'a'] ++ ;
}
Set<Integer> set = new HashSet<>() ;
int ans = 0 ;
for(int i=0; i<26; i++){
int fre = count[i] ;
while(fre>0 && !set.add(fre)){ //频次之前出现过，需要删除一个元素
fre -- ;
ans ++ ;
}
set.add(fre) ;
}
return ans ;
}
}
13-验证回文字符串II
题目链接：题目链接戳这里！！！‘
思路：从两端开始判断，如果两端元素相等，继续向中间遍历，如果不想等，则分两种情况，删除第low个是否是回文，或者第high个是否是回文。
class Solution {
public boolean validPalindrome(String s) {
//从两端开始判断，如果两端元素相等，继续向中间遍历，如果不想等，则分两种情况
int low = 0, high = s.length() - 1 ;
while(low < high){
if(s.charAt(low)==s.charAt(high)){
low ++ ;
high -- ;
}else{
return f(s,low) || f(s,high) ;
}
}
return true ;
}
public boolean f(String s, int index){
StringBuilder s1 = new StringBuilder(s) ;
String s2 = s1.deleteCharAt(index).toString() ;
String s3 = new StringBuilder(s2).reverse().toString() ;
return s2.equals(s3) ;
}
}
14-改变一个整数能得到的最大差值
题目链接：题目链接戳这里！！！
思路：枚举法
无非就是0-9之间的替换，枚举所有情况，找出最大值和最小值，同时剔除0和首位是0的。
class Solution {
public int maxDiff(int num) {
//枚举法
int max = Integer.MIN_VALUE ;
int min = Integer.MAX_VALUE ;
int n = String.valueOf(num).length() ;
for(int i=0; i<=9; i++){
for(int j=0; j<=9; j++){
int ans = swap(num, i, j) ;
if(ans != 0 && ans>=Math.pow(10,n-1)){
max = Math.max(max, ans) ;
min = Math.min(min, ans) ;
}
}
}
return max - min ;
}
public int swap(int num, int x, int y){
String s = String.valueOf(num) ;
StringBuffer s1 = new StringBuffer(s) ;
for(int i=0; i<s.length(); i++){
if(s.charAt(i)==(char)(x + '0')){
s1.setCharAt(i, (char)(y + '0')) ;
}
}
return Integer.parseInt(s1.toString()) ;
}
}
思路2：贪心策略
对于num，如果想替换一个数位，使得num的值变为最大，需要从高位到低位遍历，遇到第一个不为9的，将所有的该数字替换为9.
如果想替换一个数位，使得num变成最小，需要从前向后遍历num各位，遇到第一个不为0的，将所有该数字替换为0，不过需要注意的是0不能在首位。
class Solution {
public int maxDiff(int num) {
//贪心策略
StringBuffer max = new StringBuffer(String.valueOf(num)) ;
StringBuffer min = new StringBuffer(String.valueOf(num)) ;
for(int i=0; i<max.length(); i++){
if(max.charAt(i) != '9'){
replace(max, max.charAt(i), '9') ;
break ;
}
}
for(int i=0; i<min.length(); i++){
if(i==0 && min.charAt(i)!='1'){
replace(min,min.charAt(i), '1') ;
break ;
}
if(min.charAt(i) != '0' && i!=0 && min.charAt(i) != min.charAt(0)){
replace(min, min.charAt(i), '0') ;
break ;
}
if(i==min.length()-1){
replace(min, min.charAt(0), '1') ;
}
}
return Integer.parseInt(max.toString()) - Integer.parseInt(min.toString()) ;
}
public void replace(StringBuffer s, char x, char y){
for(int i=0; i<s.length(); i++){
if(s.charAt(i)==x){
s.setCharAt(i, y) ;
}
}
}
}
15- 得到目标数组的最少函数调用次数
题目链接：题目链接戳这里！！！
思路：贪心策略，逆向思维
让序列中某个数加 1；
让序列中所有数全体乘以 2。
询问你需要操作多少次，才能得到目标数组。
我们可以采用逆向思维，从目标数组转化为初始数组，支持两种操作：
让序列中某个数减 1；
让序列中所有数全体除以 2（要求序列中所有数均为偶数）。
记录每个元素减取1的所有操作和除以2的最多操作。
class Solution {
public int minOperations(int[] nums) {
int max = 0, odd=0 ;
for(int num : nums){
int even = 0 ;
while(num > 0){
if(num%2==1){
odd ++ ;
num -- ;
}else{
even ++ ;
num /= 2 ;
}
}
max = Math.max(max, even) ;
}
return max + odd ;
}
}
**
好好努力，好好吃饭，好好锻炼，让我们一起健健康康为祖国工作50年！！！
**