Количество переворотов для чередования двоичных строк | Комплект 1
Данная двоичная строка содержит только нули и единицы. Нам нужно сделать эту строку последовательностью альтернативных символов, перевернув некоторые биты, наша цель - минимизировать количество битов, которые нужно перевернуть.
Примеры :
Ввод: str = «001» Выход: 1 Минимальное необходимое количество переворачиваний = 1 Мы можем перевернуть 1-й бит с 0 на 1 Ввод: str = «0001010111» Выход: 2 Минимальное необходимое количество переворачиваний = 2. Мы можем перевернуть 2-й бит с 0 на 1 и 9-й. бит от 1 до 0, чтобы сделать чередование строка «0101010101».
Ожидаемая временная сложность: O (n), где n - длина входной строки.
We can solve this problem by considering all possible results, As we are supposed to get alternate string, there are only 2 possibilities, alternate string starting with 0 and alternate string starting with 1. We will try both cases and choose the string which will require minimum number of flips as our final answer.
Trying a case requires O(n) time in which we will loop over all characters of given string, if current character is expected character according to alternation then we will do nothing otherwise we will increase flip count by 1. After trying strings starting with 0 and starting with 1, we will choose the string with minimum flip count.
Total time complexity of solution will be O(n)
C++
// C/C++ program to find minimum number of // flip to make binary string alternate #include <bits/stdc++.h> using namespace std; // Utility method to flip a character char flip( char ch) { return (ch == "0" ) ? "1" : "0" ; } // Utility method to get minimum flips when // alternate string starts with expected char int getFlipWithStartingCharcter(string str, char expected) { int flipCount = 0; for ( int i = 0; i < str.length(); i++) { // if current character is not expected, // increase flip count if (str[i] != expected) flipCount++; // flip expected character each time expected = flip(expected); } return flipCount; } // method return minimum flip to make binary // string alternate int minFlipToMakeStringAlternate(string str) { // return minimum of following two // 1) flips when alternate strign starts with 0 // 2) flips when alternate strign starts with 1 return min(getFlipWithStartingCharcter(str, "0" ), getFlipWithStartingCharcter(str, "1" )); } // Driver code to test above method int main() { string str = "0001010111" ; cout << minFlipToMakeStringAlternate(str); return 0; } |
Java
// Java program to find minimum number of // flip to make binary string alternate class GFG { // Utility method to flip a character public static char flip( char ch) { return (ch == "0" ) ? "1" : "0" ; } // Utility method to get minimum flips when // alternate string starts with expected char public static int getFlipWithStartingCharcter(String str, char expected) { int flipCount = 0 ; for ( int i = 0 ; i < str.length(); i++) { // if current character is not expected, // increase flip count if (str.charAt(i) != expected) flipCount++; // flip expected character each time expected = flip(expected); } return flipCount; } // method return minimum flip to make binary // string alternate public static int minFlipToMakeStringAlternate(String str) { // return minimum of following two // 1) flips when alternate string starts with 0 // 2) flips when alternate string starts with 1 return Math.min(getFlipWithStartingCharcter(str, "0" ), getFlipWithStartingCharcter(str, "1" )); } // Driver code to test above method public static void main(String args[]) { String str = "0001010111" ; System.out.println(minFlipToMakeStringAlternate(str)); } } // This code is contributed by Sumit Ghosh |
Python 3
# Python 3 program to find minimum number of # flip to make binary string alternate # Utility method to flip a character def flip( ch): return "1" if (ch = = "0" ) else "0" # Utility method to get minimum flips when # alternate string starts with expected char def getFlipWithStartingCharcter( str , expected): flipCount = 0 for i in range ( len ( str )): # if current character is not expected, # increase flip count if ( str [i] ! = expected): flipCount + = 1 # flip expected character each time expected = flip(expected) return flipCount # method return minimum flip to make binary # string alternate def minFlipToMakeStringAlternate( str ): # return minimum of following two # 1) flips when alternate strign starts with 0 # 2) flips when alternate strign starts with 1 return min (getFlipWithStartingCharcter( str , "0" ), getFlipWithStartingCharcter( str , "1" )) # Driver code to test above method if __name__ = = "__main__" : str = "0001010111" print (minFlipToMakeStringAlternate( str )) |
C#
// C# program to find minimum number of // flip to make binary string alternate using System; class GFG { // Utility method to // flip a character public static char flip( char ch) { return (ch == "0" ) ? "1" : "0" ; } // Utility method to get minimum flips // when alternate string starts with // expected char public static int getFlipWithStartingCharcter(String str, char expected) { int flipCount = 0; for ( int i = 0; i < str.Length; i++) { // if current character is not // expected, increase flip count if (str[i] != expected) flipCount++; // flip expected character each time expected = flip(expected); } return flipCount; } // method return minimum flip to // make binary string alternate public static int minFlipToMakeStringAlternate( string str) { // return minimum of following two // 1) flips when alternate string starts with 0 // 2) flips when alternate string starts with 1 return Math.Min(getFlipWithStartingCharcter(str, "0" ), getFlipWithStartingCharcter(str, "1" )); } // Driver Code public static void Main() { string str = "0001010111" ; Console.Write(minFlipToMakeStringAlternate(str)); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find minimum number of // flip to make binary string alternate // Utility method to flip a character function flip( $ch ) { return ( $ch == "0" ) ? "1" : "0" ; } // Utility method to get minimum flips when // alternate string starts with expected char function getFlipWithStartingCharcter( $str , $expected ) { $flipCount = 0; for ( $i = 0; $i < strlen ( $str ); $i ++) { // if current character is not expected, // increase flip count if ( $str [ $i ] != $expected ) $flipCount ++; // flip expected character each time $expected = flip( $expected ); } return $flipCount ; } // method return minimum flip to make binary // string alternate function minFlipToMakeStringAlternate( $str ) { // return minimum of following two // 1) flips when alternate strign starts with 0 // 2) flips when alternate strign starts with 1 return min(getFlipWithStartingCharcter( $str , "0" ), getFlipWithStartingCharcter( $str , "1" )); } // Driver code to test above method $str = "0001010111" ; echo minFlipToMakeStringAlternate( $str ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find minimum number of // flip to make binary string alternate // Utility method to flip a character function flip(ch) { return (ch == "0" ) ? "1" : "0" ; } // Utility method to get minimum flips when // alternate string starts with expected char function getFlipWithStartingCharcter(str,expected) { let flipCount = 0; for (let i = 0; i < str.length; i++) { // if current character is not expected, // increase flip count if (str.charAt(i) != expected) flipCount++; // flip expected character each time expected = flip(expected); } return flipCount; } // method return minimum flip to make binary // string alternate function minFlipToMakeStringAlternate(str) { // return minimum of following two // 1) flips when alternate string starts with 0 // 2) flips when alternate string starts with 1 return Math.min(getFlipWithStartingCharcter(str, "0" ), getFlipWithStartingCharcter(str, "1" )); } // Driver code to test above method let str = "0001010111" ; document.write(minFlipToMakeStringAlternate(str)); // This code is contributed by avanitrachhadiya2155 </script> |
Выход :
2
Минимальное количество замен для чередования двоичной строки | Комплект 2
Эта статья предоставлена Уткаршем Триведи. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.