数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学将二进制字符串排序为升序所需移除的最小字符数
在计算机科学中，字符串操作是一个重要的主题，它涉及诸如连接、子串、反转等操作。与字符串操作相关的常见问题之一是从二进制字符串中删除所有0。在本文中，我们将讨论一种使用最小数量的非相邻对翻转来解决此问题的算法。
问题陈述
给定一个二进制字符串，我们必须使用最少的非相邻对翻转来删除字符串中的所有0。翻转定义为选择两个相邻字符并交换它们。换句话说，我们需要找到将字符串中所有0移动到字符串末尾所需的最小翻转次数。
方法
我们可以使用贪婪算法来解决这个问题。我们可以从字符串的左侧开始，并跟踪我们已将0翻转到末尾的最后一个索引。对于遇到的每个0，我们将其与最后一个翻转的0交换以将其移动到字符串的末尾。如果我们遇到1，我们只需移动到下一个索引。
让我们详细了解一下算法：
初始化两个变量，“lastFlipped”和“flipCount”，分别为-1和0。
从左到右遍历二进制字符串。
如果当前字符是'0'，则将其与索引“lastFlipped + 1”（即下一个需要交换的位置）处的字符交换，并将“lastFlipped”变量加1。
对于每次交换操作，将“flipCount”变量加1。
遍历完成后，所有0都将位于字符串的末尾，“flipCount”将包含删除所有0所需的最小翻转次数。
示例
以下是实现上述算法的代码：
#include <stdio.h>
#include <string.h>
int minNonAdjacentPairFlips(char* s) {
int lastFlipped = -1;
int flipCount = 0;
for (int i = 0; i < strlen(s); i++) {
if (s[i] == '0') {
char temp = s[i];
s[i] = s[lastFlipped + 1];
s[lastFlipped + 1] = temp;
lastFlipped++;
flipCount++;
}
}
return flipCount;
}
int main() {
char s[] = "100101000";
printf("Binary String: %s\n", s);
printf("Minimum Non-adjacent Pair Flips: %d\n", minNonAdjacentPairFlips(s));
return 0;
}
输出
Binary String: 100101000 Minimum Non-adjacent Pair Flips: 6
#include <iostream>
#include <string>
using namespace std;
int minNonAdjacentPairFlips(string s) {
int lastFlipped = -1;
int flipCount = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '0') {
swap(s[i], s[lastFlipped + 1]);
lastFlipped++;
flipCount++;
}
}
return flipCount;
}
int main() {
string s = "100101000";
cout << "Binary String: " << s << endl;
cout << "Minimum Non-adjacent Pair Flips: " << minNonAdjacentPairFlips(s) << endl;
return 0;
}
输出
Binary String: 100101000 Minimum Non-adjacent Pair Flips: 6
public class Main {
public static int minNonAdjacentPairFlips(String s) {
int lastFlipped = -1;
int flipCount = 0;
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '0') {
char temp = chars[i];
chars[i] = chars[lastFlipped + 1];
chars[lastFlipped + 1] = temp;
lastFlipped++;
flipCount++;
}
}
return flipCount;
}
public static void main(String[] args) {
String s = "100101000";
System.out.println("Binary String: " + s);
System.out.println("Minimum Non-adjacent Pair Flips: " + minNonAdjacentPairFlips(s));
}
}
输出
Binary String: 100101000 Minimum Non-adjacent Pair Flips: 6
def min_non_adjacent_pair_flips(s):
last_flipped = -1
flip_count = 0
for i in range(len(s)):
if s[i] == '0':
s_list = list(s)
s_list[i], s_list[last_flipped + 1] = s_list[last_flipped + 1], s_list[i]
s = ''.join(s_list)
last_flipped += 1
flip_count += 1
return flip_count
s = "100101000"
print("Binary String:", s)
print("Minimum Non-adjacent Pair Flips:", min_non_adjacent_pair_flips(s))
输出
Binary String: 100101000 Minimum Non-adjacent Pair Flips: 6
测试用例解释
让我们以二进制字符串“100101000”为例。我们必须使用最少的非相邻对翻转来删除此字符串中的所有0。
最初，“lastFlipped”和“flipCount”分别设置为-1和0。
我们从左到右开始遍历字符串。
在索引1处，我们遇到一个'0'。我们将它与索引“lastFlipped + 1”（即索引0）处的字符交换，并将“lastFlipped”递增到0。字符串变为“010101000”。“flipCount”递增到1。
在索引4处，我们遇到另一个'0'。我们将它与索引“lastFlipped + 1”（即索引1）处的字符交换，并将“lastFlipped”递增到1。字符串变为“011010000”。“flipCount”递增到2。
在索引5处，我们遇到一个'1'。我们只需移动到下一个索引。
结论
在本文中，我们讨论了一种使用最少的非相邻对翻转来从二进制字符串中删除所有0的算法。该算法中使用的方法是贪婪算法，这使得它高效且易于实现。
这个问题也可以使用动态规划来解决，但是贪婪算法提供了一个更简单、更快的解决方案。该算法的时间复杂度为O(n)，其中n是二进制字符串的长度。
总之，最小非相邻对翻转算法是字符串操作中一个有用的工具，可以应用于各种上下文中。
浏览量：152
