[数据结构与算法]leetcode之贪心算法刷题总结5

leetcode之贪心算法刷题总结5

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。贪心算法需要充分挖掘题目中条件，没有固定的模式，解决有贪心算法需要一定的直觉和经验。

贪心算法不是对所有问题都能得到整体最优解。能使用贪心算法解决的问题具有「贪心选择性质」。「贪心选择性质」严格意义上需要数学证明。能使用贪心算法解决的问题必须具备「无后效性」，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

1-使数组唯一的最小增量
题目链接：题目链接戳这里！！！

思路：对数组元素进行升序排序，对于每个元素，如果右侧相邻元素小于等于自己，则右侧相邻元素等于当前元素加1，同时记录增量。

class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums) ;
        int ans = 0 ;
        for(int i=0; i<nums.length-1; i++){
           if(nums[i+1]<=nums[i]){
               int temp = nums[i+1] ;
               nums[i+1] = nums[i] + 1 ;
               ans += nums[i+1] - temp ;
           }
        }
        return ans ;
    }
}

2-移除石子的最大得分
题目链接：题目链接戳这里！！！

思路：实时排序，每次让最大的，第二的分别减少1，直到第二的等于0。

class Solution {
    public int maximumScore(int a, int b, int c) {
        int [] nums = new int [] {a,b,c} ;
        Arrays.sort(nums) ;
        int ans = 0 ;
        //实时排序，每次让最大的，第二的分别减少1，直到第二的等于0
        while(nums[1]>0){
            nums[2] -- ;
            nums[1] -- ;
            ans ++ ;
            Arrays.sort(nums) ;
        }
        return ans ;
    }
}

思路2：数学法

class Solution {
    public int maximumScore(int a, int b, int c) {
        int [] nums = new int [] {a,b,c} ;
        Arrays.sort(nums) ;
   
        if(nums[0]+nums[1]<=nums[2]){
            return nums[0] + nums[1] ;
        }
        return (a+b+c) / 2 ;
    }
}

3-找出最有竞争力的子序列
题目链接：题目链接戳这里！！！

思路：维护一个单调栈，使得栈中的元素是最有竞争的子序列。保证栈空不出栈，同时保持栈顶元素尽量最小同时要保证栈中有k个数字。

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        //维护一个单调栈即可
        Stack<Integer> stack = new Stack<>() ;
        int len = nums.length ;

        for(int i=0; i<len; i++){
            while(!stack.isEmpty() && stack.peek()>nums[i] && len-i>=k-stack.size()+1){
                stack.pop() ;
            }
            if(k-stack.size()>0){
                stack.push(nums[i]) ;
            }
        }
        int [] ans = new int [k] ;
       
        while(k>0){
            ans[--k] = stack.pop() ;
        }
        return ans ;
    }
}

4-分割数组为连续子序列
题目链接：题目链接戳这里！！！

思路：用两个hash表做记录，第一个hash表count记录每个元素出现的次数，第二个hash表tail记录以nums[i]结尾的字符串个数。

具体思路可以参考这个链接：具体思路参考链接戳这里！！！

class Solution {
    public boolean isPossible(int[] nums) {
        //两个哈希表一个记录每个元素出现的次数，另一个记录以i结尾的子序列个数
        Map<Integer, Integer> count = new HashMap<>() ;
        Map<Integer, Integer> tail = new HashMap<>() ;

        for(int i=0; i<nums.length; i++){
            count.put(nums[i], count.getOrDefault(nums[i], 0) + 1) ;
        }

        for(int i=0; i<nums.length; i++){
            int cnt = count.getOrDefault(nums[i],0) ;
            if(cnt<=0){
                continue ;
            }else if(tail.getOrDefault(nums[i]-1, 0) > 0){
                count.put(nums[i], count.get(nums[i])-1) ;
                tail.put(nums[i]-1,tail.get(nums[i]-1)-1) ;
                tail.put(nums[i],tail.getOrDefault(nums[i],0)+1) ;
            }else if(count.getOrDefault(nums[i]+1, 0)>0 && count.getOrDefault(nums[i]+2, 0) > 0){
                count.put(nums[i], count.get(nums[i])-1) ;
                count.put(nums[i]+1, count.get(nums[i]+1)-1) ;
                count.put(nums[i]+2, count.get(nums[i]+2)-1) ;
                tail.put(nums[i]+2, tail.getOrDefault(nums[i]+2,0)+1) ;
            }else{
                return false ;
            }
        }
        return true ;
    }
}

5-使绳子变成彩色的最短时间
题目链接：题目链接戳这里！！！

思路：从前向后遍历所有气球的颜色，如果相邻的两个元素相同，则开始考虑删除气球，分为两种情况。
如果左侧的气球用时更少，则直接删除即可。
如果右侧的气球用时更少，除了删除气球，还需要将左侧气球的用时更新到下一个位置。

class Solution {
    public int minCost(String colors, int[] neededTime) {
        int ans = 0 ;
        for(int i=1; i<colors.length(); i++){
            if(colors.charAt(i)==colors.charAt(i-1)){
                if(neededTime[i]>=neededTime[i-1]){
                    ans += neededTime[i-1] ;
                }else{
                    ans += neededTime[i] ;
                    neededTime[i] = neededTime[i-1] ;
                }
            }
         
        }
           return ans ;
    }
}

6-乘积为正数的最大子数组的长度
题目链接：题目链接戳这里！！！

思路1：贪心策略
positive表示以当前下标i结尾乘积为正的子数组长度，negative表示以当前下标i结尾的乘积为负的子数组长度；对于每个数字，分为大于0，小于0，等于0三种情况讨论。

class Solution {
    public int getMaxLen(int[] nums) {
        //positive表示以当前下标i结尾乘积为正的子数组长度，negative表示乘积为负的子数组长度
        int positive = (nums[0] > 0 ? 1 : 0) ;
        int negative = (nums[0] < 0 ? 1 : 0) ;
        int maxLength = positive ;

        for(int i=1; i<nums.length; i++){
            if(nums[i]>0){
                positive ++ ;
                negative = (negative > 0 ? negative+1 : negative) ;
            }else if(nums[i]<0){
                int newNegative = positive + 1 ;
                int newPositive = (negative>0 ? negative+1 : 0) ;
                negative = newNegative ;
                positive = newPositive ;
            }else{
                positive = negative = 0 ;
            }
            maxLength = Math.max(maxLength, positive) ;
        }
        return maxLength ;
    }
}

思路2：动态规划
动态规划,positive[i]表示以i结尾的最长正数子数组长度，negative[i]表示以i结尾的最长负数子数组的长度.
我们很容易得到递推表达式。

class Solution {
    public int getMaxLen(int[] nums) {
       //动态规划,positive[i]表示以i结尾的最长正数子数组长度，negative[i]表示以i结尾的最长负数子数组的长度
       int [] positive = new int [nums.length] ;
       int [] negative = new int [nums.length] ;
       if(nums[0]>0){
           positive[0] = 1 ; 
       }else if(nums[0] < 0){
           negative[0] = 1 ;
       }
       int maxLength = positive[0] ;

       for(int i=1; i<nums.length; i++){
           if(nums[i]>0){
               positive[i] = positive[i-1] + 1 ;
               negative[i] = (negative[i-1] > 0 ? negative[i-1]+1 : 0) ;
           }else if(nums[i]<0){
               positive[i] = (negative[i-1]>0 ? negative[i-1] + 1 : 0) ;
               negative[i] = positive[i-1] + 1 ;
           }else{
               positive[i] = negative[i] = 0 ;
           }
           maxLength = Math.max(maxLength, positive[i]) ;
       }
       return maxLength ;
    }
}

7-峰与谷
题目链接：题目链接戳这里！！！

思路：从前向后遍历，保证奇数位置的大于偶数位置的，不满足条件就交换两个元素值。

class Solution {
    public void wiggleSort(int[] nums) {
      //从前向后遍历，保证奇数位置的大于偶数位置的
        for(int i=0; i<nums.length-1; i++){
            if(i%2==0){
                if(nums[i]<nums[i+1]){
                    swap(nums, i, i+1) ;
                }
            }else{
                if(nums[i]>nums[i+1]){
                    swap(nums, i, i+1) ;
                }
            }
        }
    }
    public void swap(int [] nums, int i, int j){
        int temp = nums[i] ;
        nums[i] = nums[j] ;
        nums[j] = temp ;
    }
}

8-不同字符的最小子序列
题目链接：题目链接戳这里！！！

思路：维护一个单调栈，如果栈顶元素在s的后面还有，并且当前字符栈顶元素大于当前s中的元素，则出栈，s中的元素进栈。如果当前元素已经在栈中了，则直接跳过。

class Solution {
    public String smallestSubsequence(String s) {
        //就是删除重复的字符，使得不同字符组成的字典序最小的字符串，维护一个单调栈就可以
        Stack<Character> stack = new Stack<>() ;
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i) ;
            if(stack.contains(c)){
                continue ;
            }
            while(!stack.isEmpty() && stack.peek()>c && s.indexOf(stack.peek(),i)!=-1){
                stack.pop() ;
            }
            stack.push(c) ;
        }
        String ans = "" ;
        for(int i=0; i<stack.size(); i++){
            ans += stack.get(i) ;
        }
        return ans ;
    }
}

9-有效的括号字符串
题目链接：题目链接戳这里！！！

思路：max与min分别表示未匹配的左括号的最大值和最小值
如果遇到左括号，则将最小值和最大值分别加 1；
如果遇到右括号，则将最小值和最大值分别减 1；
如果遇到星号，则将最小值减 1，将最大值加 1。

class Solution {
    public boolean checkValidString(String s) {
        //max与min分别表示未匹配的左括号的最大值和最小值
        int max = 0, min = 0 ;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '('){
                max ++ ;
                min ++ ;
            }else if(s.charAt(i)==')'){
               max -- ;
               min = Math.max(min-1, 0) ;
               if(max<0){
                   return false ;
               }
            }else{
                max ++ ;
                min = Math.max(min-1, 0) ;
            }
        }
        return min == 0 ;
    }
}

10-不含AAA或BBB的字符串
题目链接：题目链接戳这里！！！

思路：递归法
如果a>b,则使用aab
如果a<b,则使用bba
如果a=b，则使用ab

class Solution {
    public String strWithout3a3b(int a, int b) {
        //递归写法
        if(a==0){
            String s = "" ;
            for(int i=0; i<b; i++){
                s += 'b' ;
            }
            return s ;
        }
        if(b==0){
            String s = "" ;
            for(int i=0; i<a; i++){
                s += 'a' ;
            }
            return s ;
        }
        if(a==b){
            return "ab" + strWithout3a3b(a-1,b-1) ;
        }
        return a > b ? "aab" + strWithout3a3b(a-2,b-1) : "bba"+strWithout3a3b(a-1,b-2) ;
    }
}

11-打折买糖果的最小开销
题目链接：题目链接戳这里！！！
思路：升序排序，从后向前遍历数组，不停的累加每三个最大的中的两个最大的。

class Solution {
    public int minimumCost(int[] cost) {
        if(cost.length==1){
            return cost[0] ;
        }
        Arrays.sort(cost) ;
        int ans = 0 ;
        for(int i=cost.length-1; i>=0; i-=3){
            ans += cost[i] + (i-1 >= 0 ? cost[i-1] : 0) ;
        }
        return ans ;
    }
}

12-给定行和列的和求可行矩阵
题目链接：题目链接戳这里！！！

思路：贪心策略

class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int [][] ans = new int [rowSum.length][colSum.length] ;
        for(int i=0; i<rowSum.length; i++){
            for(int j=0; j<colSum.length; j++){
                ans[i][j] = Math.min(rowSum[i],colSum[j]) ;
                rowSum[i] -= ans[i][j] ;
                colSum[j] -= ans[i][j] ;
            }
        }
        return ans ;
    }
}

**

贪心告一段落了，明天最短路径，冲吧，少年慢慢不在年轻~

**