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