给定一个只包含’0’和’1’两种字符的字符串,每次操作可以选择相邻的两个字符,将它们同时变成’0’或者同时变成’1’。 请问最少多少次操作后,所有的字符都相同? 字符串长度不超过1000。

区块链毕设网qklbishe.com为您提供问题的解答

给定一个只包含’0’和’1’两种字符的字符串,每次操作可以选择相邻的两个字符,将它们同时变成’0’或者同时变成’1’。

请问最少多少次操作后,所有的字符都相同?
字符串长度不超过1000。
熟悉的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]);     } };

27:47

以上就是关于问题给定一个只包含’0’和’1’两种字符的字符串,每次操作可以选择相邻的两个字符,将它们同时变成’0’或者同时变成’1’。
请问最少多少次操作后,所有的字符都相同?
字符串长度不超过1000。的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码,定制。

区块链NFT链游项目方科学家脚本开发培训

承接区块链项目定制开发

微信:btc9767

QQ :1330797917

TELEGRAM: BTCOK9

承接区块链项目定制开发


qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 给定一个只包含’0’和’1’两种字符的字符串,每次操作可以选择相邻的两个字符,将它们同时变成’0’或者同时变成’1’。 请问最少多少次操作后,所有的字符都相同? 字符串长度不超过1000。

发表回复