01串修改__牛客网

爱萝莉

熟悉的dp问题，但是要两个dp数组。转移方程：当str[i] == '1'时，dp0[i] = min(dp0[i-1],dp0[i-2])+1;dp1[i] = dp1[i-1]。

意思就是当第i位不为0时，dp0[i]的值要么是对前两位进行变换，要么是对前一位进行变化，然后取最小+1；

而对于dp1[i]来说，因为str[i]就是‘1’所以值可以与前一位相同不需要变换。反之等于'0'的情况亦然。

最后返回值为dp0[n-1],dp1[n-1]的较小值。

注意初始条件哦。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    int minOperations(string str) {
        // write code here
        int n = str.size();
        if(n == 0 || n == 1)return 0;
        if(n == 2)return str[0] == str[1]?0:1;
        
        vector<int>dp0(n,0);
        vector<int>dp1(n,0);
        
        if(str[0] == str[1]){
            if(str[0] == '0'){
                dp1[0]= 1;
                dp1[1]= 1;
            }
            else{
                dp0[0]=1;
                dp0[1]=1;
            }
        }
        else{
            if(str[0] == '0'){
                dp0[1]=1;
                dp1[0]=1;
                dp1[1]=1;
            }else{
                dp1[1]=1;
                dp0[0]=1;
                dp0[1]=1;
            }
        }
        
        for(int i =2;i<n;++i){
            if(str[i] == '0'){
                dp1[i] = min(dp1[i-1],dp1[i-2])+1;
                dp0[i] = dp0[i-1];
            }else{
                dp0[i] = min(dp0[i-1],dp0[i-2])+1;
                dp1[i] = dp1[i-1];
            }
        }
        
        return min(dp0[n-1],dp1[n-1]);
    }
};

发表于 2022-10-18 11:27:47 回复(0)

zzzood

模拟，分别统计，遇到0，看修改0->1得需要多少步；遇到1，看修改1->0得需要多少步。

遍历一遍，能得到修改0的最少次数，和修改1的最少次数，返回最小的即可。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    int minOperations(string str) {
        // write code here
        int do0=0, do1=0;
        int i=0;
        while(i<str.size()){
            int st = i;
            if(str[i]=='0'){
                while(i<str.size() && str[i]=='0'){
                    ++i;
                }
                do0 += (i-st)/2;
                do0 += (i-st)%2;
            }
            else{
                while(i<str.size() && str[i]=='1'){
                    ++i;
                }
                do1 += (i-st)/2;
                do1 += (i-st)%2;
            }
        }
        return min(do0, do1);
    }
};

编辑于 2022-10-30 21:32:41 回复(1)

灯火烛天

分别操作变为‘0’和变为‘1’，字符串转数组遍历，判断不需要改变下移1位，判断需要改变下移2位，返回较小次数

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    public int minOperations (String str) {
        int[] arr = new int[str.length()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.valueOf(String.valueOf(str.charAt(i)));
        }
        int d0 = 0;
        for (int i = 0; i < arr.length;) {
            if (arr[i] == 0) {
                i++;
            } else {
                d0++;
                i += 2;
            }
        }
        int d1 = 0;
        for (int i = 0; i < arr.length;) {
            if (arr[i] == 1) {
                i++;
            } else {
                d1++;
                i += 2;
            }
        }
        return Math.min(d0, d1);
    }
}

发表于 2022-10-31 14:25:27 回复(0)

感性的肖恩在做核酸

没学过dp 这里使用模拟的方法，转成1需要多少步转成0需要多少步。返回最小值即可

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return int整型
     */
    public int minOperations (String str) {
        // write code here
        int count0 = findMinCount(str, '0');
        int count1 = findMinCount(str, '1');

        return Math.min(count0, count1);
    }
    private int findMinCount(String str, char num) {
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) != num) {
                if (i + 1 < str.length() && str.charAt(i + 1) != num) {
                    count++;
                    i++; // 两个都不是0 只需要一次操作 所以i++跳过后面的字符
                } else if (i + 1 < str.length() && str.charAt(i + 1) == num) {
                    count++;
                } else if (i +1 == str.length()) {
                    count++;
                }
            }

        }

        return count;
    }
}

发表于 2023-11-17 16:36:27 回复(0)

Python

pein531

分别求一下改为全零串和全一串的代价，返回两者中的较小值即可。由于是对称的，以改为全一串为例：分割字符串得到所有连续零的子串，然后挨个将每个零串改成全一串即可。对于一个长度为 $n$ 的全零串，要将它改为全一串，需要进行的操作次数为 $\frac{n+1}{2}$ ，所有次数累加起来就得到了总的操作次数。

落单的零是没有关系的，如果剩下一个0，它必然和一个1是相邻的，我们只要进行一次操作将01改成11即可。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @return int整型
#
class Solution:
    def minOperations(self , s: str) -> int:
        # write code here
        return min(self.getop(s, '1'), self.getop(s, '0'))

    def getop(self, s: str, delimter: str):
        terms = [term for term in s.split(delimter) if term]
        cnt = 0
        for term in terms:
            cnt += (len(term) + 1) >> 1
        return cnt

发表于 2023-02-01 17:58:04 回复(0)

枫凡

想法是去掉重复的 00 和 11 变为 0 和 1比较最终的字符串中0 1 的最小总和

class Solution {
public:
    int minOperations(string str) {
        // 把连续 00 11 变成 0 1 再判断 0 1 总的最小个数
        for(int i=0; i<str.size()-1;++i)
        {
            if(str[i]=='0'){
                if(str[i+1]=='0')
                    str[i+1]=' ';
            }
            if(str[i]=='1'){
                if(str[i+1]=='1')
                    str[i+1]=' ';
            }
        }
        int n = str.size();int num0=0, num1=0;
        if(str[str.size()-1] == str[str.size()-2])n--;
        for(int i=0; i<=n-1; ++i)
        {
            if(str[i]=='0')
                num0++;
            if(str[i]=='1')
                num1++;
        }
        return num0<=num1?num0:num1;
    }
};

发表于 2023-06-07 16:11:44 回复(0)

已注销

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    public int minOperations (String str) {
        // write code here
        int n = str.length();
        /*
            从最后一个字符往前加字符，
            dp[i][0]代表为[i,n-1]范围的字符串全部转为字符'0'的最少操作次数，
            dp[i][1]代表为[i,n-1]范围的字符串全部转为字符'1'的最少操作次数。
            因为一次可以选2个字符，use[i]代表i和i+1字符相同，而且被用于同时改变。
            当往前加的str[i]为'0':
                那么全部转换为'0'不用操作，dp[i][0]=dp[i+1][0]；
                全部转换为'1'分两种情况:
                    1、如果后面的str[i+1]也是为'0'，而且没有被用于组合，那么str[i]可以和str[i+1]组合一起变为'1'，
                        那么跟后面str[i+1]全部变为'1'的最少操作数一样，dp[i][1]=dp[i+1][1]；
                    2、不是第1种情况，那么自己就要单独变为'1'，最少操作数+1，dp[i][1]=dp[i+1][1]+1。
            当往前加的str[i]为'1'：
                跟'0'的情况一样的逻辑。
            另一个数可以用+1取模2获得。
        */
        int[][] dp = new int[n][2];
        dp[n-1][(str.charAt(n-1) - '0' + 1)%2] = 1;

        boolean[] use = new boolean[n];

        for(int i=n-2;i>=0;i--){
            int num = str.charAt(i) - '0';
            dp[i][num] = dp[i+1][num];
            int anotherNum = (num + 1) % 2;
            if(str.charAt(i) == str.charAt(i+1) && use[i+1] == false){
                dp[i][anotherNum] = dp[i+1][anotherNum]; 
                use[i] = true;    
            }else{
                dp[i][anotherNum] = dp[i+1][anotherNum] + 1;
            }
            
        }

        return Math.min(dp[0][0],dp[0][1]); 

    }
}

发表于 2023-05-06 09:16:46 回复(0)

Phantom2022

class Solution {
public:
    int minOperations(string str) {
        int zeros = 0;
        int ones = 0;
        for(int i = 0; i < str.size(); ++i){
            if(str[i] == '0')
                zeros++;
            else
                ones++;
            if(i < str.size() && str[i + 1] == str[i])
                ++i;
        }
        return min(zeros, ones);
    }
};

发表于 2023-03-26 15:41:16 回复(0)

勇敢的90后复盘中

import java.util.*;


public class Solution {

    public int minOperations (String str) {
        int res0 = 0, res1 = 0;

        // 全变为1的情况
        char[] tmp = str.toCharArray();
        for (int i = 0; i < tmp.length; i++) {
            if (tmp[i] != '1') {
                res1++;
                i++;
            }
        }
        // 全变为0的情况
        for (int i = 0; i < tmp.length; i++) {
            if (tmp[i] != '0') {
                res0++;
                i++;
            }
        }
        return Math.min(res0, res1);
    }
}

发表于 2023-03-22 20:04:46 回复(0)

tsrj

    package _12月在家重刷.题目;

import java.util.Arrays;

/**
 * @author qxm
 * @create 2023-02-21 19:37
 **/
/* 
    思路:全变成0，全变成1取二者较小。
    如何计算需要的最小次数?
    以1001101为例：
        全变成0，把1去掉，[00,0],需要ceil("00".length/2)+ceil("0".length/2)
        全变成1，把0去掉，[1,11,1],需要ceil("1".length/2)+ceil("11".length/2)+ceil("1".length/2)
        二者取较小者
 */
public class _T13_01串修改 {
    public static void main(String[] args) {
        int res = new _T13_01串修改().minOperations("1001101");
        System.out.println(res);
    }

    public int minOperations(String str) {
        //全为0
        int ans0 = 0;
        String[] split0 = str.split("[0]+");
        //System.out.println(Arrays.toString(split0));
        for (int i = 0; i < split0.length; i++) {
            if (split0[i].length() % 2 == 0) {
                ans0 += split0[i].length() / 2;
            } else {
                ans0 += split0[i].length() / 2 + 1;
            }
        }
        //System.out.println(ans0);

        //全为1
        int ans1 = 0;
        String[] split1 = str.split("[1]+");
        //System.out.println(Arrays.toString(split1));
        for (int i = 0; i < split1.length; i++) {
            if (split1[i].length() % 2 == 0) {
                ans1 += split1[i].length() / 2;
            } else {
                ans1 += split1[i].length() / 2 + 1;
            }
        }
        //System.out.println(ans1);

        return Math.min(ans0, ans1);
    }
}

发表于 2023-02-22 13:55:23 回复(0)

肥嘟嘟左卫门也想拿offer

func minOperations( str string ) int {
    r1, r2 := 0, 0
    pre := 0
    // 模拟结果为全1，需要的操作次数
    for i := range str {
        if str[i] == '1' {
            pre = 0
        } else {
            // 如果有连续不为0, 注意连续的两可以变成一个操作
            // 例如 1 0 0 0 1 -> 1 1 1 1 1 
            // 当 i = 1 时， pre = 1
            //    i = 2 时， pre = 0
            //    i = 3 时， pre = 1
            pre = (pre + 1) % 2
            r1 += pre
        }
    }
    // 模拟结果为全0，需要的操作次数, 与上诉类似
    for i := range str {
        if str[i] == '0' {
            pre = 0
        } else {
            pre = (pre + 1) % 2
            r2 += pre
        }
    }
    // 返回两种结果中较小的那个
    return min(r1, r2)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

发表于 2023-02-17 20:01:07 回复(0)

Magina_

1

发表于 2022-10-19 23:39:00 回复(0)

01串修改

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题