贪心算法刷题刷题

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这两个字母。他现在有一个只包含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: 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

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