代码随想录——双指针与滑动窗口(四)

一.1423. 可获得的最大点数

题目详情

解题思路

这里我们每次只能取最左或最右边的卡牌,第一反应其实是使用双指针，通过局部贪心来解决，但是如果两边相等的话用局部贪心无法来判断到底取哪一边，那我们不妨换一个思路：

我们首先任选一边维持一个长度为k的子数组，计算出子数组的和，记录下来为当前最大值，然后定义左右指针，删去左指针指向的值，加上右指针指向的值，不断更新当前最大值，当左指针的位置到-1，当前最大值就是目标值。

解题代码：

• Go

func max(a,b int)int{
    if a>b{
        return a
    }else{
        return b
    }
}

func maxScore(cardPoints []int, k int) int {
    if k==0{
        return 0
    }
    n:=len(cardPoints)
    l,r:=0,n-1
    res:=0
    for l<k{
        res+=cardPoints[l]
        l++
    }
    l=k-1
    maxvalue:=res
    for l>=0{
        res-=cardPoints[l]
        res+=cardPoints[r]
        l--
        r--
        maxvalue=max(maxvalue,res)
    }
    return maxvalue
}

• Cpp

class Solution {
public:
    int max(int a, int b) {
        return a > b ? a : b;
    }

    int maxScore(std::vector<int>& cardPoints, int k) {
        if (k == 0) {
            return 0;
        }
        int n = cardPoints.size();
        int l = 0, r = n - 1;
        int res = 0;
        for (l = 0; l < k; l++) {
            res += cardPoints[l];
        }
        l = k - 1;
        int maxvalue = res;
        while (l >= 0) {
            res -= cardPoints[l];
            res += cardPoints[r];
            l--;
            r--;
            maxvalue = max(maxvalue, res);
        }
        return maxvalue;
    }
};

二.1456. 定长子串中元音的最大数目

题目详情

解题思路

这道题属于一个比较典型的滑动窗口题目了，我们维护一个定长的滑动窗口，记录里面的元音字母数即可。

代码

• Go

func in (s rune) bool{
    if s=='a'||s=='o'||s=='e'||s=='i'||s=='u'{
        return true
    }else{
        return false
    }
}

func max(a,b int)int{
    if a>b{
        return a
    }else{
        return b
    }
}

func maxVowels(s string, k int) int {
   n:=len(s)
   l:=0
   maxvalue:=0
   sum:=0
   for r:=0;r<n;r++{
    if in(rune(s[r])){
        sum++
    }
    if r-l+1>k{
        if in(rune(s[l])){
            sum--
        }
        l++
    }
    maxvalue=max(maxvalue,sum)
   }
   return maxvalue
    
}

• Cpp

class VowelCounter {
public:
    bool isVowel(char s) {
        if (s == 'a' || s == 'o' || s == 'e' || s == 'i' || s == 'u') {
            return true;
        }
        return false;
    }

    int max(int a, int b) {
        return a > b ? a : b;
    }

    int maxVowels(std::string s, int k) {
        int n = s.length();
        int l = 0;
        int maxvalue = 0;
        int sum = 0;
        for (int r = 0; r < n; r++) {
            if (isVowel(s[r])) {
                sum++;
            }
            if (r - l + 1 > k) {
                if (isVowel(s[l])) {
                    sum--;
                }
                l++;
            }
            maxvalue = max(maxvalue, sum);
        }
        return maxvalue;
    }
};

三.