贪心算法刷题

快来打我* 2023-07-16 09:59 23阅读 0赞

# 1.递增数组 #

### 题目链接：[递增数组][Link 1] ###

### 题目介绍： ###

> 牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？

### 思路： ###

严格递增，我们应该让某个数字后面的一个比他小的连续区间都进行加1操作，然后遍历整个数组(除最后一个数字)。其实我们不需要真正的对数组进行加1操作，只需要求出ai与ai+1的差，再加上1,就是需要加1的次数，不需要真正进行加1,因为如果ai+n比a\[i\]大，那这个加1操作与a\[i+n\]无关，如果比a\[i\]小，则也会相应加1,与a\[i+1\]的差并不会改变，当a\[i+1\]被当作前面的数时，求的依然是两者的差值，故不进行加1操作也不会影响最后的次数。

### 代码 ###

class Solution:
        def IncreasingArray(self , array):
            cnt=0
            for i in range(len(array)-1):
                cnt+=max(0,array[i]-array[i+1]+1)
            return cnt

# 2.牛牛的AC #

### 题目链接：[牛牛的AC][AC] ###

### 题目介绍 ###

> 一年一度的春招就要到来了，牛牛为了备战春招，在家刷了很多道题，所以牛牛非常喜欢AC这两个字母。他现在有一个只包含A和C的字符串，你可以任意修改最多k个字符，让A变成C，或者C变成A。请问修改完之后，最长连续相同字符的长度是多少。

### 思路 ###

跟上面的那道题类似，也是对列表进行操作，但实际上又不用真正的去操作。依然使用贪心的"想当然"策略。想要最长连续相同字符串，又最多改变k个字符，那我们就在字串里找，这个字串中有k个字符与剩下的字符不同，这都是我们可以容忍的，记录下在能容忍的情况下，字串的最长大小就是最后的结果。  
主要是用什么方法来记录一个字串，我尝试的是two points的方法，设置左右两个游标来限定为一个字符串。该问题还有一个点就是怎么计算是否超过限定的k，我刚开始使用.count()的方法，超时了。后面参考别人的代码，应该使用变量来记录下这个子串中的某个字符的数量，这样就没有必要每次去再遍历子串了。  
那我们需要A2C，C2A进行两次，然后求最大值嘛？这个是不需要的，题目中只要求返回长度，那我们在记录数量时，A和C的数量都记录下来，然后当两个都不能容忍k时，再让左端游标移动，这个有点与非的意思。

### 代码 ###

class Solution:
        def Solve(self , k , s ):
            right,left=0,0
            max_len=0
            s_length=len(s)
            A_cnt,C_cnt=0,0
            while right<s_length:
                if(s[right]=='A'):A_cnt+=1
                if(s[right]=='C'):C_cnt+=1
                right+=1
                while (A_cnt>k and C_cnt>k):
                    if(s[left]=='A'):A_cnt-=1
                    if(s[left]=='C'):C_cnt-=1
                    left+=1
                max_len=max(right-left,max_len)
            return max_len

欢迎关注公众号，一起进步

![公众号二维码.jpg][.jpg]

[Link 1]: https://www.nowcoder.com/practice/d0907f3982874b489edde5071c96754a
[AC]: https://www.nowcoder.com/practice/6309d58571b94aff96951f6a7ee84e7b
[.jpg]: /images/20230528/400b52d49efb4eb1993479ecf969d0f1.png