首页 > 试题广场 >

偏爱字母

[编程题]偏爱字母
  • 热度指数：3779 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

小美喜欢字母E，讨厌字母F。在小美生日时，小团送了小美一个仅包含字母E和F的字符串，小美想从中选出一个包含字母E数量与字母F数量之差最大的子串。

*子串：从字符串前面连续删去若干个字符，从后面连续删去若干个字符剩下的字符串（也可以一个都不删），例如abcab是fabcab的子串，而不是abcad的子串。我们将空串看作所有字符串的子串。


输入描述:
第一行一个正整数n表示字符串的长度。
第二行长度为n，且仅包含大写字母’E’,’F’的字符串（不含引号）
 


输出描述:
输出一个整数，表示最大的差值
示例1

输入

5
EFEEF

输出

2

说明

选择子串EE,此时有2个E，0个F,有最大差值2-0=2
另外，选择子串EFEE也可以达到最大差值。

备注:
对于30%的数据，n<=300
对于60%的数据，n<=3000
对于100%的数据，n<=300000
算法知识视频讲解
添加回答
kangjinci头像 kangjinci 
//贪心，像PAT的最大子列和那题，我的算法启蒙，浙大数据结构的第一讲
#include<iostream>
#include<string>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt[2] = {0};
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        cnt[s[i] - 'E']++;
        if (cnt[0] < cnt[1]) {
            cnt[0] = 0;
            cnt[1] = 0;
        }
        ans = max(ans, cnt[0] - cnt[1]);
    }
    cout << ans << endl;

    return 0;
}
发表于 2021-03-15 21:37:08 回复(0)
牛客304000217号头像 牛客304000217号
go 动态规划，和前一套一道题特别像，所以很快做出来了，只是最后有个逻辑错误，最后一个用例没通过··· 
package main
import "fmt"
func EF() {
	var N int
	var str string
	fmt.Scan(&N,&str)
	cur,max:=0,0
	for i:=0;i<N;i++{
		if str[i]=='E' {
			cur++
            if i==N-1&&cur>max{
                max=cur
            }
		}else {
			if cur>max{
				max=cur
			}
			cur--
            if cur<0{
			cur=0
		    }
		}
		
	}
	fmt.Println(max)
}

func main(){
    EF()
}


发表于 2022-05-24 16:24:56 回复(0)
许愿给我来一个offer呀头像 许愿给我来一个offer呀
一维数组动态规划
importjava.util.*;
publicclassMain{
    publicstaticvoidmain(String[]args){
        Scanner sc =newScanner(System.in);
        intn = sc.nextInt();
        String s = sc.next();
        intindex =0;
        while(s.charAt(index)!='E'){
            index++;
        }
        int[] dp =newint[n];
        dp[index]=1;
        intmax =1;
        for(inti =index+1;i<n;i++){
            if(s.charAt(i)=='E'){
                dp[i]=Math.max(1,dp[i-1]+1);
            }else{
                dp[i] = Math.max(0,dp[i-1]-1);
            }
            if(dp[i]>max){
                max = dp[i];
            }
        }
        System.out.print(max);
    }
}
发表于 2021-05-07 10:36:18 回复(0)
牛客默克尔号头像 牛客默克尔号
收到之前动态规划求连续列表的启发，使用dp：E是1，F是-1 
n=int(input())
l=input()
ll=[]
def trans(a):
    d={'E':1,'F':-1}
    return d[a]
def solve(n,l):
    p=[0]
    for i in range(n):
        p.append(max(p[i]+l[i],l[i]))
    return max(p)
ll=[trans(i) for i in l]
print(solve(n,ll))


发表于 2021-04-14 15:34:47 回复(0)
一个大番茄z头像 一个大番茄z
cpp 简单dp 
#include <iostream>
using namespace std;
int main(){
    int n;
    string s;
    cin>>n>>s;
    int _max= s[0]=='E' ? 1 : -1, pre=_max;
    for(int i=1;i<n;i++){
        int t = s[i]=='E' ? 1 : -1;
        pre=max(pre + t , t);
        _max=max(_max,pre);
    }
    cout<<_max<<endl;;
}
发表于 2021-04-07 19:22:48 回复(0)
Python
梦飞翔201909251511348头像 梦飞翔201909251511348
n=int(input())
L=input()
count=0
res=0
for i,num in enumerate(L):
    count+=1 if num=="E" else -1
    if count<0:count=0
    res=max(res,count)
print(res)
#简短的python解法
发表于 2021-04-03 17:13:01 回复(0)
pein531头像 pein531
把E看成1，F看成-1。遍历数组，遇到E就+1，遇到F就-1，如果所有的E都被F平衡完了，就从0开始重新计算，即从当前位置重新开启一段子数组计算E和F的个数差值。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        char[] str = br.readLine().trim().toCharArray();
        int maxSum = 0, sum = 0;
        for(int i = 0; i < n; i++){
            if(str[i] == 'E') sum ++;
            if(str[i] == 'F') sum --;
            maxSum = Math.max(maxSum, sum);
            sum = Math.max(sum, 0);
        }
        System.out.println(maxSum);
    }
}


发表于 2021-03-06 12:46:49 回复(5)
牛客997588876号头像 牛客997588876号
我觉得有歧义。就包含E与F之差最大的子串而言，那么给定字符串EFFF，到底是答案是1还是3呢，如果是1，是因为小美喜欢E这个信息么？
发表于 2021-03-12 19:11:30 回复(6)
南笙无梦头像 南笙无梦
将输入的字符串转换为一个数字数组，这题就变成了求最大子序和
使用动态规划就可以写出来了 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String gift = sc.next();
        // 将字符串转换为数字数组
        int[] giftNum = new int[gift.length()];
        for (int i = 0; i < gift.length(); i++) {
            // E转换为数字1，F转换为数字-1
            giftNum[i] = gift.charAt(i) == 'E' ? 1 : -1;
        }
        method(giftNum, n);
    }

    // 转换为数字数组之后，这题就相当于求最大子序和了
    public static void method(int[] gift, int n) {
        // 初始化dp数组
        int[] dp = new int[n];
        dp[0] = Math.max(gift[0], 0);
        int max = dp[0];
        // 遍历，根据递推求最大子串和
        for (int i = 1; i < dp.length; i++) {
            // 每次到达一个新的数字，考虑是加上当前数组总和大还是重头开始总和大
            dp[i] = Math.max(dp[i - 1] + gift[i], gift[i]);
            // 不断更新最大值
            max = Math.max(dp[i], max);
        }
        System.out.println(max);
    }
}


发表于 2023-05-12 22:13:31 回复(0)
罗啰萝头像 罗啰萝 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        String str = sc.next();
        int[] dp = new int[len];
        if (str.charAt(0)=='E') dp[0] = 1;
        else dp[0] = 0;
        for (int i = 1; i < len; i++) {
            if (str.charAt(i) == 'E') {
                dp[i] = dp[i-1] + 1;
            } else {
                dp[i] = Math.max(dp[i-1] - 1, 0);
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

发表于 2022-08-05 21:35:47 回复(0)
卷笔刀坏了头像 卷笔刀坏了
题意其实是求 E的数量减去F的数量，不是绝对值，不过都是滑动窗口的思想
如果只是求E的数量减去F的数量的最大值：
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] chs = sc.next().toCharArray();
        //eNum表示E的数量减去F的数量，如果小于0，重新开始计数，也就是滑动窗口的左端点移至当前下标
        int res = 1, eNum = 0;
        for (int i = 0; i < n; i++) {
            if (chs[i] == 'E') eNum++;
            else if (--eNum < 0) eNum = 0;
            res = Math.max(res, eNum);
        }
        System.out.println(res);
    }
}
如果是绝对值，多加一个变量，同样的思想： 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] chs = sc.next().toCharArray();
        //eNum表示E的数量减去F的数量，如果小于0，重新开始计数，也就是滑动窗口的左端点移至当前下标
        //fNum表示F的数量减去E的数量，如果小于0，重新开始计数
        int res = 1, eNum = 0, fNUm = 0;
        for (int i = 0; i < n; i++) {
            if (chs[i] == 'E') {
                eNum++;
                if (--fNUm < 0) fNUm = 0;
            } else {
                fNUm++;
                if (--eNum < 0) eNum = 0;
            }
            res = Math.max(res, Math.max(eNum, fNUm));
        }
        System.out.println(res);
    }
}
编辑于 2022-08-25 22:04:07 回复(1)
RogerL头像 RogerL
动态规划，遇到E差就+1，遇到F差就-1 
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        int[] dp = new int[n];
 
        int flag = 0;
        if (s.charAt(0) == 'E') {
            dp[0] = 1;
        } else {
            dp[0] = -1;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == 'E') {
                flag = 1;
            } else {
                flag = -1;
            }
            dp[i] = Math.max(flag,dp[i - 1] + flag);
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        System.out.println(max);
    }
}


发表于 2022-08-18 16:26:43 回复(0)
牛客914333777号头像 牛客914333777号
c++动态规划 
using namespace std;
#include<iostream>
#include<string>
#include<vector>
int main(){
    int n ;
    cin >> n;
    string str;
    cin >> str;
    vector<int> dp(n,0);//dp[i] :包括第i位置之前的“E和F”的差值
    if(str[0] == 'E'){//初始化，判断第一个字母是什么
        dp[0] = 1;
    }
    else{
        dp[0] = -1;
    }
    int ans = 0;
    for(int i = 1; i < n; i++){
        if(str[i] == 'E'){//如果当前位置的字母为E，肯定选取当前位置，在前一个位置的基础上+1;
            dp[i] = dp[i-1]+1;
        }
        else{//如果当前位置的字母是F，判断要不要当前位置，如果要，因为是F所以-1；如果不要重新计数，重置为0；
            dp[i] = max(dp[i-1]-1,0);
        }
        ans = max(ans,dp[i]);//选取一个最大值
    }
    cout << ans <<'\n';
}


发表于 2022-04-20 22:00:32 回复(0)
牛客444127117号头像 牛客444127117号
将E看成1，F看成-1的最大子数组和
发表于 2022-03-17 11:01:31 回复(0)
BinWatson头像 BinWatson 

#include <bits/stdc++.h>

using namespace std;
int main()
{    
    int n;
    cin >> n;
    string str;
    cin >> str;
    vector<int> prefixCt(n + 1, 0);
    
    for (int i = 1; i <= n; ++i) {
        prefixCt[i] = (str[i] == 'E' ? 1 : -1) + prefixCt[i - 1];
    }
    
    int minCt = 0;
    int result = 0;
    for (int i = 1; i <= n; ++i) {
        result = max(prefixCt[i] - minCt, result);
        minCt = min(prefixCt[i], minCt);
    }
    cout << result;
}

发表于 2022-03-16 20:37:55 回复(0)
JavaScript
牛客68020592号头像 牛客68020592号

看到“最大“的字样想到动态规划
先将EF字符串转换为1,-1的数组nums
然后明确dp，dp[i]代表以nums[i]结尾的子串的最大和
明确dp方程，dp[i]由前一项和nums[i]决定，如果前一项小于0，则去掉前面的项

得出dp方程，即dp[i] = Math.max(dp[i-1], 0) + nums[i]
初始化dp，由方程已知，初始化dp[0]即可，得出dp[0] = nums[0]
把每次得到的最大和进行对比，求出最大和max 
// 动态规划
let n = ~~readline()
let str = readline().split('')
let dp = []
// 将EF替换为1，-1
let nums = str.map(item => item == 'E' ? 1 : -1)
// 初始化dp数组
dp[0] = nums[0]
// 初始化最大差值
let max = nums[0]
for(let i = 1 ;i<n;i++){
    dp[i] = Math.max(dp[i-1], 0) + nums[i]
    max = Math.max(dp[i] ,max)
}
// 依据题意，差值最小时为全F的情况，输出0
print(max >= 0 ? max : 0)
编辑于 2022-03-12 11:54:22 回复(0)
爱看电影的小男孩头像 爱看电影的小男孩



/*
这道题 说到底就是动态规化  首先将数组中的连续E F的个数存入到一个数组中  然后对数据进行动态规化 寻找最大值
*/
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n =  sc.nextLine();
        String str = sc.nextLine();
        char[] c = str.toCharArray();
        List<Integer> list = new ArrayList<Integer>();
        int e = 0;
        int f = 0;
       for(int i=0;i<c.length;i++){
            if(c[i]=='E'){
                if(f!=0)
                    list.add(f);
                e++;
                f = 0;
            }
            if(c[i]=='F'){
                if(e!=0)
                    list.add(e);
                f--;
                e=0;
            }
        }
     if(e==0){
            list.add(f);
        }else
            list.add(e);
     int sum = 0;
        int max = 0;
        int dmax = 0;

        for(int i=0;i<list.size();i++){
            dmax = Math.max(list.get(i)+dmax, list.get(i));
            max = Math.max(max,dmax);
        }
        System.out.println(max);
    }
}

发表于 2021-09-21 10:03:45 回复(0)
看星星呐头像 看星星呐
与美团2021第9场第3题思路一样 
n = int(input())
c = list(input())
def tran(x):
    if x=='E':return 1
    else: return -1
a = list(map(tran, c))
def dp(n,a):
    pre = [0]
    for i in range(n):
        maxsum = max(a[i],pre[i]+a[i])
        pre.append(maxsum)
    return max(pre)
print(dp(n, a))

发表于 2021-09-01 09:56:18 回复(0)
yosoro25252头像 yosoro25252 
n = int(input())
s = input()
res = 0
cur = 0
curMin = 0
for i in range(n):
    if s[i] == 'E':
        v = 1
    else:
        v = -1
    cur += v
    curMin = min(curMin, cur)
    res = max(res, cur - curMin)
print(res)

发表于 2021-08-14 23:54:06 回复(0)
牛客133059086号头像 牛客133059086号
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        if(s.length()==0){
            System.out.println(0);
        }
        int[] a = new int[n];
        a[0] = s.charAt(0)=='E'?1:-1;
        int max = a[0];
        for(int i=1;i<n;i++){
            if(s.charAt(i)=='E'){
                a[i] = Math.max(1,a[i-1]+1);
            }else{
                a[i] = Math.max(-1,a[i-1]-1);
            }
            max = Math.max(max,a[i]);
        }
        if(max>0){
            System.out.println(max);
        }else{
            System.out.println(0);
        }
    }
}
发表于 2021-08-05 21:35:28 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 美团 前端工程师 算法工程师 2021 大数据开发工程师 Java工程师
上传者：小小
难度：
28条回答 4707浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号