搜索
首页后端开发C++使字符串成为由一串0后面跟着一串1组成的最小移除次数

使字符串成为由一串0后面跟着一串1组成的最小移除次数

Sep 07, 2023 pm 10:57 PM
字符串移除 最小次数 和

使字符串成为由一串0后面跟着一串1组成的最小移除次数

问题“进行 0 子字符串的字符串连接的最小删除量”涉及操作字符串的工作。提供 0 和 1 的字符串作为输入,结果是一个整数,反映为了生成连续 0 的子串而必须消除的 0 的最小数量。

换句话说,问题可以重新表述为:给定一个由0和1组成的字符串,为了使剩下的字符串中包含一段连续的0,需要消除多少个0。

算法

第一步:变量初始化

  • 定义一个计数变量来记录当前零序列的长度。

  • 定义一个 max_count 变量来跟踪迄今为止遇到的最长的零序列。

  • 将两个变量都设置为0。

第二步:字符串遍历

使用循环遍历字符串中的每个字符。

第三步:零检测

如果当前字符为零,则增加计数变量。

第 4 步:一次检测

  • 如果当前字符是 1,则将 count 变量与 max_count 变量进行比较。

  • 如果计数变量高于 max_count 变量,则将 max_count 变量设置为等于计数变量。

  • 将计数变量重置为0。

第 5 步:循环完成

重复这个过程,直到字符串中的所有字符都被处理完。

步骤6:最小删除计算

删除所有零以使剩余的不被任何零分隔所需的最小删除次数可以通过从字符串长度中减去 max_count 来计算。

第7步:结果输出

将结果打印到控制台。

遵循的方法

  • 动态方法

  • 迭代方法

方法一:动态方法

动态规划可以用来高效地解决这个问题。为了创建连续0的子字符串,我们可以创建一个数组dp[],其中dp[i]表示从子字符串s[0...i]中需要消除的最小数量的0。从空子字符串中消除的最小数量的0是0,因此我们可以将dp[0]初始化为0。

然后,我们可以迭代字符串s并将dp[i]更新为−

  • 如果 s[i] 为“0”,则 dp[i] = dp[i-1],因为我们可以将 s[i] 包含在连续 0 的子串中或将其删除。

  • 当 s[i] 为“1”时,我们必须获得距离 i 最接近的索引 j,其中包含连续 0 的子串。这可以通过从 i-1 迭代到 0 并查看子字符串 s[j...i] 是否包含连续的 0 来完成。如果找到索引 j,则 dp[i] = dp[j-1] + (i-j+1),其中 dp[j-1] 表示必须从子串 s[ 中消除的 0 的最小数量0...j-1]和(i-j+1)是为了获得连续0的子串s[j...i]而必须消除的1的总数。如果没有发现这样的索引 j,则 dp[i] = dp[i-1],因为我们不能将 s[i] 包含在连续 0 的子串中。

    最后,为了获得连续 0 的子串,需要从整个字符串 s 中删除的 0 的最小数量由 dp[n-1] 给出,其中 n 是字符串 s 的长度。

示例 1

下面的程序使用我们上面讨论的方法,首先从标准输入读取输入字符串,然后识别所有 0 的子字符串。然后计算最长的 0 子串的长度以及通过连接每个 0 子串生成的字符串的长度。为了确定所需消除的最少次数,它最终从所有 0 子串的总和中减去最长 0 子串的长度,并将结果显示到标准输出。

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

int main() {
   string s = "100100011000110"; // constant input string

   vector<pair<int, int>> substrings; // vector to store start and end indices of each substring of 0s

   int start = -1;
   for (int i = 0; i < s.length(); i++) {
      if (s[i] == '0') {
         if (start == -1) {
         start = i;
         }
      } else {
         if (start != -1) {
         substrings.push_back(make_pair(start, i - 1));
         start = -1;
         }
      }
   }
   if (start != -1) {
      substrings.push_back(make_pair(start, s.length() - 1));
   }

   int totalLength = 0;
   for (auto& p : substrings) {
      totalLength += p.second - p.first + 1;
   }

   int maxLength = 0;
   for (auto& p : substrings) {
      int len = p.second - p.first + 1;
      if (len > maxLength) {
         maxLength = len;
      }
   }

   int removals = totalLength - maxLength;
   cout << "Input string: " << s << endl;
   cout << "Minimum removals: " << removals << endl;

   return 0;
}

输出

Input string: 100100011000110
Minimum removals: 6

方法2:迭代方法

这种方法使用一种直接的迭代方法,逐个字符地遍历给定的字符串,同时更新两个变量count和max_count的值。该方法根据当前字符是0还是1来更新count和max_count变量的值。然后,它提供了max_count和最长的0子字符串的长度之间的差异。

Example 2

的中文翻译为:

示例2

该代码是一个 C++ 软件,它计算从二进制字符串中删除所有零所需的最小消除次数,以便其余的不被任何零分隔。 min_deletions 函数将二进制字符串作为输入,并使用循环来遍历字符串中的每个字符。该循环每次遇到零时都会增加计数变量,并在遇到一时将其重置为零。 count变量的最大值保存在max_count中,最后从max_count中减去字符串的长度以获得所需的最小删除次数。然后将结果显示给用户。

#include <iostream> 
#include <string> 
using namespace std; 
 
int min_deletions(string str) { 
   int count = 0, max_count = 0; 
   for (char c : str) { 
      if (c == '0') { 
         count++; 
      } else { 
         max_count = max(max_count, count); 
         count = 0; 
      } 
   } 
    return str.length() - max_count; 
} 
 
int main() { 
   string str = "100010011000110"; 
   int deletions = min_deletions(str); 
   cout << "Minimum deletions needed: " << deletions << endl; 
   return 0; 
} 

输出

Minimum deletion needed: 12 

结论

确定所有 0 的子串、计算连接每个 0 的子串所产生的字符串的长度以及确定最长 0 的子串的长度是解决给定问题的三个步骤。然后可以从所有 0 子串的总和中减去最大 0 子串的长度,以获得所需的最少删除次数。

我们用来获得答案的方法简单有效,并且以线性时间运行,因此适合大输入。但它可以通过应用更复杂的方法(例如动态规划)来进一步增强。

以上是使字符串成为由一串0后面跟着一串1组成的最小移除次数的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:tutorialspoint。如有侵权,请联系admin@php.cn删除
C#vs. C:学习曲线和开发人员的经验C#vs. C:学习曲线和开发人员的经验Apr 18, 2025 am 12:13 AM

C#和C 的学习曲线和开发者体验有显着差异。 1)C#的学习曲线较平缓,适合快速开发和企业级应用。 2)C 的学习曲线较陡峭,适用于高性能和低级控制的场景。

C#vs. C:面向对象的编程和功能C#vs. C:面向对象的编程和功能Apr 17, 2025 am 12:02 AM

C#和C 在面向对象编程(OOP)中的实现方式和特性上有显着差异。 1)C#的类定义和语法更为简洁,支持如LINQ等高级特性。 2)C 提供更细粒度的控制,适用于系统编程和高性能需求。两者各有优势,选择应基于具体应用场景。

从XML到C:数据转换和操纵从XML到C:数据转换和操纵Apr 16, 2025 am 12:08 AM

从XML转换到C 并进行数据操作可以通过以下步骤实现:1)使用tinyxml2库解析XML文件,2)将数据映射到C 的数据结构中,3)使用C 标准库如std::vector进行数据操作。通过这些步骤,可以高效地处理和操作从XML转换过来的数据。

C#vs. C:内存管理和垃圾收集C#vs. C:内存管理和垃圾收集Apr 15, 2025 am 12:16 AM

C#使用自动垃圾回收机制,而C 采用手动内存管理。1.C#的垃圾回收器自动管理内存,减少内存泄漏风险,但可能导致性能下降。2.C 提供灵活的内存控制,适合需要精细管理的应用,但需谨慎处理以避免内存泄漏。

超越炒作:评估当今C的相关性超越炒作:评估当今C的相关性Apr 14, 2025 am 12:01 AM

C 在现代编程中仍然具有重要相关性。1)高性能和硬件直接操作能力使其在游戏开发、嵌入式系统和高性能计算等领域占据首选地位。2)丰富的编程范式和现代特性如智能指针和模板编程增强了其灵活性和效率,尽管学习曲线陡峭,但其强大功能使其在今天的编程生态中依然重要。

C社区:资源,支持和发展C社区:资源,支持和发展Apr 13, 2025 am 12:01 AM

C 学习者和开发者可以从StackOverflow、Reddit的r/cpp社区、Coursera和edX的课程、GitHub上的开源项目、专业咨询服务以及CppCon等会议中获得资源和支持。1.StackOverflow提供技术问题的解答;2.Reddit的r/cpp社区分享最新资讯;3.Coursera和edX提供正式的C 课程;4.GitHub上的开源项目如LLVM和Boost提升技能;5.专业咨询服务如JetBrains和Perforce提供技术支持;6.CppCon等会议有助于职业

c#vs. c:每种语言都擅长c#vs. c:每种语言都擅长Apr 12, 2025 am 12:08 AM

C#适合需要高开发效率和跨平台支持的项目,而C 适用于需要高性能和底层控制的应用。1)C#简化开发,提供垃圾回收和丰富类库,适合企业级应用。2)C 允许直接内存操作,适用于游戏开发和高性能计算。

继续使用C:耐力的原因继续使用C:耐力的原因Apr 11, 2025 am 12:02 AM

C 持续使用的理由包括其高性能、广泛应用和不断演进的特性。1)高效性能:通过直接操作内存和硬件,C 在系统编程和高性能计算中表现出色。2)广泛应用:在游戏开发、嵌入式系统等领域大放异彩。3)不断演进:自1983年发布以来,C 持续增加新特性,保持其竞争力。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 个月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
1 个月前By尊渡假赌尊渡假赌尊渡假赌
威尔R.E.P.O.有交叉游戏吗?
1 个月前By尊渡假赌尊渡假赌尊渡假赌

热工具

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

将Eclipse与SAP NetWeaver应用服务器集成。

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )专业的PHP集成开发工具