一.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; } };
