红和绿

python两行

暴力枚举的，感觉不够优雅。

每个位置都试一遍，假设为红与绿的分界点，在这些结果里面找到最小值。

例如对于位置i，左边全部要染成红色，右边全部要染成绿色，则当前的值为s[:i].count('G') + s[i:].count('R')。

代码如下：

s = input()
print(min(map(lambda i: s[:i].count('G') + s[i:].count('R'), range(0, len(s) + 1))))

s=input()
res=[]
for i in range(len(s)):
    res.append(s[:i].count('G')+s[i:].count('R'))
print(min(res))

#include <bits/stdc++.h>
using namespace std;

int main(){
    int cnt=0, green=0;
    string s;
    cin>>s;
    for(auto &c: s){
        if(c=='G')
            green++;
        else
            cnt = min(cnt+1, green);
    }
    printf("%d\n", cnt);
    return 0;
}

//方法1：遍历一次数组，在当前位置为R时有可能两种情况，一种是把这个位置变成G，另一种是把前面的G全部变成R。
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        scan.close();
        int gCount = 0, count = 0;
        for(int i=0; i<str.length(); i++) {
            if(str.charAt(i)=='G') {
                gCount++;//记录G的个数
            }
            else {//如果当前字符是R
                count = Math.min(gCount, count+1);
            }//gCount表示把当前字符R前的所有G变成R,count表示当前字符R变成G
        }
        System.out.println(count);
    }
}

//方法2：用枚举，以每一个点为起点，左边的都是R，右边的都是G，记录每一次的次数，排序，得到最小的。
import java.util.Arrays;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        scan.close();
        int[] count = new int[str.length()];//记录每一次枚举染色的次数
        for(int i=0; i<str.length(); i++) {
            for(int j=0; j<i; j++) {
                if(str.charAt(j)=='G') {
                    count[i]++;//若左边的是G,记录变成R的次数
                }
            }
            for(int j=i+1; j<str.length(); j++) {
                if(str.charAt(j)=='R') {
                    count[i]++;//若右边的是R,记录变成G的次数
                }
            }
        }
        Arrays.sort(count);
        System.out.println(count[0]);
    }
}

1. 思路：G遍历涂的个数 和 （R总 - 已遍历的个数） 的最小和
2. 注意：左边全为G，右边全为R 的情况
3. 时间复杂度O(n)，空间复杂度O(1)

mystr = input()
mymin = Ry = Rcount = mystr.count('R')
GChangeCount = 0
for item in mystr:
    if item == 'G':
        GChangeCount +=1
    else:
        Rcount -=1
    if GChangeCount>=Ry and Ry == Rcount:
        mymin = Rcount
        break
    if Rcount+GChangeCount < mymin:
        mymin = Rcount+GChangeCount
    if Rcount == 0:
        break
print(mymin)

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int countR = count(s.begin(), s.end(), 'R');
    int countG = count(s.begin(), s.end(), 'G');
    int frontG = 0;
    int frontR = 0;
    int numColor = 0;
    int minColor = s.size() + 1;
    //遇到红且是最后一个连续红就试试前面改成红，后面改成绿
    for(int i = 0; i < s.size(); ){
        if(s[i] == 'R'){
            while(i < s.size() && s[i] == 'R'){
                frontR++;
                i++;
            }
            //前面的绿色（染红） + 后面的红色（染绿）
            numColor = frontG + (countR - frontR);
            minColor = min(minColor, numColor);
        }
        else{
            frontG++;
            i++;
        }
    }
    cout << min(minColor, min(countR, countG)) << endl;
    
}

#include<iostream>
#include<string>

using namespace std;

int main() {
    string s;
    cin >> s;
    int length = s.size();
    int ans = 50;
    for (int i = 0; i < length; i++) {
        int ans_temp = 0;
        for (int j = 0; j < length; j++) {
            if (s[j] == 'G' && j < i) ans_temp++;
            if (s[j] == 'R' && j >= i) ans_temp++;
        }
        if (ans_temp <= ans) ans = ans_temp;
    }
    cout << ans << endl;
   return 0;
}

AC率这么低，我以为什么题，结果做了以后发现是个小学阅读理解题(题意描述不明)。

import java.util.*;
public class Main {
    private static final int N_MAX = 55;
    private static final int INT_MAX= 0x3f3f3f3f;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] in = sc.next().toCharArray();
        int[] counts = new int[N_MAX];
        for (int i=1; i<=in.length; i++) {
            if (in[i-1] == 'R') {
                counts[i] = counts[i-1] + 1;
            }
            else {
                counts[i] = counts[i-1];
            }
        }
        int ans = INT_MAX;
        for (int i=0; i<=in.length; i++) {
            int left  = i - counts[i];
            int right = counts[in.length] - counts[i];
            ans = Math.min(left+right, ans);
        }
        System.out.println(ans);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            System.out.println(helper(in.nextLine()));
        }
    }
    public static int helper(String s){
        char[] a = s.toCharArray();
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < a.length;i++){
            int s1 = 0,e1 = i,s2 = i,e2 = a.length,count = 0;
            while(s1 < e1){
                if(a[s1] == 'G') count++;
                s1++;
            }
            while(s2 < e2){
                if(a[s2] == 'R') count++;
                s2++;
            }
            min = Math.min(count,min);
        }
        return min;
    }
}

#include<stdio.h>
#include<string.h>
#define min(a,b) a<b?a:b
int main(){
    char s[100];
    scanf("%s",s);
    int i,j,Min=1e8,n=strlen(s);
    for(i=0;i<n;i++){
        int cnt=0;
        for(j=0;j<i;j++) if(s[j]!='R') cnt++;
        for(j=i;j<n;j++) if(s[j]!='G') cnt++;
        Min=min(Min,cnt);
    }
    printf("%d\n",Min);
}

我觉得我的方法简单,看大家很多是遍历所有可能的分界点做的,说一下我的方法,只需要遍历一次数组,
在当前位置为R时有可能两种情况,一种是吧这个位置编程G,另一种是吧前面的G全部变成R.

时间复杂度O(n),空间复杂度O(1) 
#include<bits/stdc++.h>
using namespace std;

int main()
{
    std::ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int len = s.size();// 获取字符串长度
    int gCount = 0;// 字符串中G字母的个数
    int count = 0; // 最小涂色次数
    for(int i = 0; i < len;i++)
    {
        if(s[i] == 'G')
        {
            gCount++;
        }else
        {
            count = min(gCount, count + 1);
        }
            
    }
    cout << count << endl;
    return 0;
}

	

s = input()
dp = [0] * (len(s) + 1)
dp[0] = s.count('R')
for i in range(len(s)):
    if s[i] == 'G':
        dp[i+1] = dp[i] + 1
    else:
        dp[i+1] = dp[i] - 1
print(min(dp))