美团笔试0819第三题

样例：10001 输出8

java选手帮忙看看为啥0%啊，我这已经纯暴力了，列举了所有的连续子串，各自计算子串的权值再相加。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static HashMap<String, Integer> map = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int n = str.length();
        long ans = getAns(str);
        System.out.println(ans);
    }

    private static long getAns(String input) {
        long sum = 0;
        int n = input.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
				//获取连续子串
                String s = input.substring(i, j + 1);
			 	//获取子串的权值：最小修改次数，使得字符串01交替出现
                int count = getCount(s);
                sum += count;
            }
        }
        return sum;
    }

    private static int getCount(String str) {
        if (map.containsKey(str)) {
            return map.get(str);
        }
        int flips = 0;
        int n = str.length();
        int ans1 = 0, ans2 = 0;
        int pre = str.charAt(0);
	  	//暴力法
	  	//前后两个一样时，讨论修改“后面的”和修改“前面的”两种情况
        for (int i = 1; i < n; i++) {
            char cur = str.charAt(i);
            if (pre == cur) {
                ans1++;
                cur = cur == '0' ? '1' : '0';
                pre = cur;
            } else {
                pre = cur;
            }
        }
        pre = str.charAt(0);
        for (int i = 1; i < n; i++) {
            char cur = str.charAt(i);
            if (pre == cur) {
                ans2++;
                pre = pre == '0' ? '1' : '0';
                pre = cur;
            } else {
                pre = cur;
            }
        }
        flips = Math.min(ans1, ans2);
        map.put(str, flips);
        return flips;
    }
}