首页 > 试题广场 >

小美的01串翻转

[编程题]小美的01串翻转

热度指数：1488 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美定义一个 01 串的权值为：每次操作选择一位取反，使得相邻字符都不相等的最小操作次数。
例如，"10001"的权值是 1，因为只需要修改一次：对第三个字符取反即可。
现在小美拿到了一个 01 串，她希望你求出所有非空连续子串的权值之和，你能帮帮她吗？

输入描述:

一个仅包含'0'和'1'的字符串，长度不超过 2000。

输出描述:

所有非空子串的权值和。

示例1

输入

输出

说明

长度为 2 的子串中，有 2 个"00"的权值是 1。
长度为 3 的 3 个子串权值都是 1。
长度为 4 的 2 个子串权值都是 1。
长度为 5 的 1 个子串权值是 1。
总权值之和为 2+3+2+1=8

算法知识视频讲解

Java

烤串不吃串

dp[i][j] 表示如果把子字符串 [i,j] 奇数位填0，偶数位填1需要修改的数量。那么把[i,j] 变为01串需要的操作就是 min(j-i+1-dp[i][j], dp[i][j]）.

那么直接通过矩阵递推填满整个矩阵即可。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String st = in.nextLine();
        char[] ss = st.toCharArray();
        int n = ss.length;
        // "1": 1; "0": 0
        // ss[i][j], [i, j]
        int[][] weight = new int[n][n];
        for (int i = 0; i < n; i++) {
            if (i % 2 == 1) {
                weight[i][i] = ss[i]=='1' ? 1: 0;
            } else {
                weight[i][i] = ss[i]=='0' ? 1: 0;
            }
        }
        int res = 0;
        for (int i = 2; i  <= n; i ++) {
            for (int j = 0; j + i - 1 < n; j++) {
                weight[j][j+i-1] = weight[j][i+j-2] + weight[j+i-1][j+i-1];
                res += Math.min( i-weight[j][j+i-1], weight[j][j+i-1]);
            }
        }
        System.out.println(res);
    }
}

编辑于 2023-12-26 18:53:42 回复(0)

Java

十默

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

String s = in.next();

char[] array = s.toCharArray();

int n = s.length();

int[][][] dp = new int[n][n][2];

int sum =0;

for(int i=n-1;i>=0;i--)

{

for(int j=i;j<n;j++){

if(i==j){

if(array[i]=='0'){

dp[i][i][1]=1;

}else{

dp[i][i][0]=1;

}

}else{

int a = array[j]=='0'? 0:1;

dp[i][j][0]=dp[i][j-1][1]+a;

dp[i][j][1]=dp[i][j-1][0]+1-a;

}

sum+=Math.min(dp[i][j][0],dp[i][j][1]);

}

System.out.println(sum);

}

发表于 2023-09-08 15:15:21 回复(0)

Java

cylms

import java.util.*;

public class Main {
    static boolean isAchieved;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] chars = sc.next().toCharArray();
        int n = chars.length;
        int[][][] dp = new int[n][n][2];
        int res = 0;
        dp[0][0][chars[0] - '0'] = 0;
        dp[0][0][1 - chars[0] + '0'] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == 0 && j == 0) continue;
                int bit = chars[j] - '0';
                dp[i][j][bit] = dp[i][j - 1][1 - bit];
                dp[i][j][1 - bit] = dp[i][j - 1][bit] + 1;
                res += Math.min(dp[i][j][bit], dp[i][j][1 - bit]);
            }
        }
        System.out.println(res);
    }
}

发表于 2023-08-25 14:20:35 回复(0)

提交观点

问题信息

来自：2023年美团秋招编程...

难度：

3条回答 79收藏 3851浏览

小美的01串翻转

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题