首页 > 试题广场 >

分割字符串的最大得分

[编程题]分割字符串的最大得分
  • 热度指数:1600 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给你一个由若干 0 和 1 组成的字符串s,请你计算并返回将该字符串分割成两个子字符串(即左子字符串和右子字符串, 子字符串允许为空)所能获得的最大得分。
已知分割字符串的得分规则如下:
左子字符串中:0得2分,1得1分
右子字符串中:1得2分,0得1分 
子字符串为空则得0分

输入描述:
一行包括一个由0和1组成的字符串s


输出描述:
一行一个整数表示答案。
示例1

输入

011101

输出

11

说明

当左子字符串 = "0" 且 右子字符串 = "11101",得分最大= 2+ 9 = 11 
示例2

输入

00111

输出

10

说明

当左子字符串 = "00" 且右子字符串 = "111" 时,得分最大 = 4 + 6 = 10
s = input()
d = (len(s) + 1) * [0]
for ch in s:
    if ch=='0':
        d[0] += 1
    else:
        d[0] += 2
for i in range(len(s)):
    if s[i] == '0':
        d[i + 1] = d[i] + 1
    else:
        d[i + 1] = d[i] - 1
print(max(d))

发表于 2021-01-11 17:26:28 回复(1)
#include<iostream>
#include<string>
 
using namespace std;
 
int maxScore(string s){
    int maxres=0;
    int maxnum=0;
    for(int i=0;i<s.size();i++){    //右字串总和
        if(s[i]=='0')    maxnum++;
        else    maxnum+=2;
    }
    maxres=max(maxnum,maxres);
    for(int i=0;i<s.size();i++){    //滑动窗口
        if(s[i]=='0')    maxnum++;
        else    maxnum--;
        maxres=max(maxnum,maxres);
    }
    return maxres;
}
 
int main(){
    string s;
    cin>>s;
    cout<<maxScore(s)<<endl;
}

发表于 2021-02-04 18:33:27 回复(0)
为什么用暴力法也能过😂
s = input().strip()
n = len(s)
max_score = 0
for i in range(n + 1):
    max_score = max(max_score, s[:i].count('0')*2 + s[:i].count('1') + s[i:].count('0') + s[i:].count('1')*2)
print(max_score)


发表于 2021-01-19 11:28:50 回复(0)
#include <iostream>
#include <string>
using namespace std;

long long  leftSocore( char ch ){
    if( ch == '0') return 2;
    if( ch == '1') return 1;
    return 0;
}

long long  rightSocore( char ch ){
    if( ch == '0') return 1;
    if( ch == '1') return 2;
    return 0;
}

int main( ){
    string str;
    getline(cin,str);
    if( str.size() == 0 ) return 0;
    long long  left_score = 0;
    long long  right_score = 0;
    long long max_score = 0;
    
    for( int i = 0; i < str.size(); i++ ){
        right_score += rightSocore( str[i] );
    }
    max_score = right_score;
    for( int i = 0; i < str.size(); i++ ){
        left_score += leftSocore( str[i] );
        right_score -= rightSocore( str[i] );
        if( left_score + right_score > max_score ){
            max_score = left_score + right_score;
        }
    }
    cout<<max_score;
    return 0;
}


编辑于 2022-07-28 14:50:02 回复(0)
#include <iostream>
using namespace std;

int main() 
{
    string s;
    cin >> s;
    int cur = 0;
    for(char c : s)
    {
        if(c == '0')
        {
            cur += 1;
        }
        else
        {
            cur += 2;
        }
    }

    int result = cur;
    for(char c : s)
    {
        if(c == '0')
        {
            cur++;
        }
        else
        {
            cur--;
        }
        result = max(result,cur);
    }
    cout << result;
    return 0;
}

发表于 2023-04-12 14:10:27 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string str;
    cin >> str;
    // 双向遍历
    vector<int> l_val(str.size()), r_val(str.size());
    for(int i = 0; i < str.size(); ++i){
        if(i == 0){
            l_val[i] = (str[i] == '0' ? 2 : 1);
        }else{
            if(str[i] == '0'){
                l_val[i] = l_val[i - 1] + 2;
            }else{
                l_val[i] = l_val[i - 1] + 1;
            }
        }
    }
    
    for(int i = str.size() - 1; i >= 0; --i){
        if(i == str.size() - 1){
            r_val[i] = (str[i] == '1' ? 2 : 1);
        }else{
            if(str[i] == '0'){
                r_val[i] = r_val[i + 1] + 1;
            }else{
                r_val[i] = r_val[i + 1] + 2;
            }
        }
    }
    int ans = r_val[0];
    for(int i = 0; i < str.size(); ++i){
        ans = max(l_val[i] + (i + 1 == str.size() ? 0 : r_val[i + 1]), ans);
    }
    ans = max(ans, l_val[str.size() - 1]);
    cout << ans << endl;
    
    return 0;
}

思路是自左向右求一遍以当前字符为分界的左边字符串的得分,再自右向左求一边,然后去对于每个字符将左边和右边的之加起来取最大即可。
发表于 2022-08-16 16:41:13 回复(0)
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author asdf
 */
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String next = scanner.next();
		if (next.length() == 0) {
			System.out.println(0);
			return;
		}
		String left = "";
		String right = "";
		int sum = 0;
		int[] arr = new int[next.length() + 1];
		for (int i = 1; i < next.length(); i ++) {
			left = next.substring(0, i);
			right = next.substring(i);
			for (char c : left.toCharArray()) {
				if ('0' == c) {
					sum += 2;
				} else if ('1' == c){
					sum += 1;
				} else {
					sum += 0;
				}
			}
			for (char c : right.toCharArray()) {
				if ('0' == c) {
					sum += 1;
				} else if ('1' == c){
					sum += 2;
				} else {
					sum += 0;
				}
			}
			arr[i - 1] = sum;
			sum = 0;
		}
		for (char c : next.toCharArray()) {
			if ('0' == c) {
				sum += 2;
			} else if ('1' == c){
				sum += 1;
			} else {
				sum += 0;
			}
		}
		arr[arr.length - 2] = sum;
		sum = 0;
		for (char c : next.toCharArray()) {
			if ('0' == c) {
				sum += 1;
			} else if ('1' == c){
				sum += 2;
			} else {
				sum += 0;
			}
		}
		arr[arr.length - 1] = sum;
		Arrays.sort(arr);
		System.out.println(arr[arr.length - 1]);
	}
    
}

发表于 2022-06-09 21:04:21 回复(1)
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int len=s.length();
        int[]d=new int[len+1];
        for(int i=0;i<len;i++) {
        	if(s.charAt(i)=='0') {
        		d[0]+=1;
        	}
        	else {
        		d[0]+=2;
        	}
        }
        for(int i=0;i<len;i++) {
        	if(s.charAt(i)=='0') {
        		d[i+1]=d[i]+1;
        	}
        	else {
        		d[i+1]=d[i]-1;
        	}
        }
        Arrays.sort(d);
        System.out.print(d[len]);
	}
	

}
根据第一个python回答改的java版本
发表于 2022-03-24 20:00:30 回复(0)
s=input()
n=len(s)
left=[0 for _ in  range(n)]
right=[0 for _ in  range(n)]

for i in range(n):
    if s[i]=='0':
        left[i]+=2
    else:
        left[i]+=1
    if i>=1:left[i]+=left[i-1]

for i in range(n-1,-1,-1):
    if s[i]=='0':
        right[i]+=1
    else:
        right[i]+=2
    if i<=n-2:right[i]+=right[i+1]

ret=0
for i in range(n-1):
    ret=max(ret,left[i]+right[i+1])
ret=max(ret,left[-1],right[0])
print(ret)

不得不说有很多题都是从前往后遍历一次,再从后往前遍历一次,保存点什么,最后再遍历一次,就能做
发表于 2022-03-06 22:29:38 回复(0)
ss=input().strip()
if len(ss)==1:   #特例
    print(2)
else:
    maxC=0
    i=1
    for i in range(len(ss)+1):  #i为左子串的长度
        L=[]
        R=[]
        j=0
        k=i
        while(j<i):             #左字串
            L.append(ss[j])
            j=j+1
        while(k<len(ss)):       #右字串
            R.append(ss[k])
            k=k+1
        c=0
        c=L.count('0')*2+L.count('1')
        c=c+R.count('1')*2+R.count('0')
        maxC=max(maxC,c)
    print(maxC)

发表于 2021-05-18 20:50:43 回复(0)
行吧, 无情的暴力解法选手
#include<iostream>
usingnamespacestd;
 
intmain()
{
    string str;
    while(cin>>str);
    intret=0, sum=0;
    for(auto j :str)    {if(j=='1')    {ret+=2;}    else{ret+=1;}}
    for(inti=0;i<str.size();i++)
    {
        intcur=0, sum=0;
        while(cur<=i)   
        {
            if(str[cur++]=='0')    {sum+=2;}    else{sum+=1;}
        }
        cur = i+1;
        while(cur<str.size())
        {
            if(str[cur++]=='1')    {sum+=2;}    else   {sum+=1;}
        }
        if(sum>ret)    {ret = sum;}
    }
     
    cout<<ret;
    return0;
}
发表于 2021-01-05 20:58:00 回复(0)