ניתן מספר נ המשימה היא למצוא את האורך של הארוך ביותר ברציפות 1 שניות סדרה בייצוג הבינארי שלה.
דוגמאות:
קֶלֶט: n = 14
תְפוּקָה: 3
הֶסבֵּר: הייצוג הבינארי של 14 הוא 111 0.
קֶלֶט: n = 222
תְפוּקָה: 4
הֶסבֵּר: הייצוג הבינארי של 222 הוא 110 1111 0.
תוכן עניינים
- [גישה נאיבית] זמן איטרטיבי O(1) ומרחב O(1)
- [גישה יעילה] שימוש במניפולציה של סיביות O(1) זמן ו-O(1) מרחב
- [גישה נוספת] באמצעות המרת מחרוזת
[גישה נאיבית] זמן איטרטיבי O(1) ומרחב O(1)
C++#include using namespace std; int maxConsecutiveOne(int n ){ int count = 0 ; int maxi = 0 ; // traverse and check if bit set increment the count for (int i = 0 ; i < 32 ; i++){ if (n & (1 << i)){ count++; } else { maxi = max (maxi count); count = 0 ; } } return maxi; } int main() { int n = 14 ; cout << maxConsecutiveOne(n) <<'n'; return 0; }
Java public class GFG { static int maxConsecutiveOne(int n) { int count = 0; int maxi = 0; // traverse and check if bit set increment the count for (int i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) { count++; } else { maxi = Math.max(maxi count); count = 0; } } return maxi; } public static void main(String[] args) { int n = 14; System.out.println(maxConsecutiveOne(n)); } }
Python def maxConsecutiveOne(n): count = 0 maxi = 0 # traverse and check if bit set increment the count for i in range(32): if n & (1 << i): count += 1 else: maxi = max(maxi count) count = 0 return maxi if __name__ == '__main__': n = 14 print(maxConsecutiveOne(n))
C# using System; class GFG { static int MaxConsecutiveOne(int n) { int count = 0; int maxi = 0; // traverse and check if bit set increment the count for (int i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) { count++; } else { maxi = Math.Max(maxi count); count = 0; } } return maxi; } static void Main() { int n = 14; Console.WriteLine(MaxConsecutiveOne(n)); } }
JavaScript function maxConsecutiveOne(n) { let count = 0; let maxi = 0; // traverse and check if bit set increment the count for (let i = 0; i < 32; i++) { if (n & (1 << i)) { count++; } else { maxi = Math.max(maxi count); count = 0; } } return maxi; } // Driver code let n = 14; console.log(maxConsecutiveOne(n));
תְפוּקָה
3
[גישה יעילה] שימוש במניפולציה של סיביות O(1) זמן ו-O(1) מרחב
הרעיון מבוסס על התפיסה שה- ו של רצף סיביות עם a שמאלה מוזז ב-1 גרסה של עצמה מסירה ביעילות את הנגרר 1 מכל רצף של רצופות 1 שניות .
אז המבצע נ = (n & (n<< 1)) מקטין את האורך של כל רצף של 1 שניות על ידי אחד בייצוג בינארי של נ . אם נמשיך לעשות את הפעולה הזו בלולאה, בסופו של דבר נ = 0. מספר האיטרציות הנדרשות כדי להגיע הוא למעשה אורך הרצף הארוך ביותר ברציפות של 1 שניות .
אִיוּר:
בצע את השלבים הבאים כדי ליישם את הגישה לעיל:
- צור ספירת משתנים עם ערך .
- הפעל לולאת זמן עד נ אינו 0.
- בכל איטרציה בצע את הפעולה נ = (n & (n<< 1))
- הגדל את הספירה באחד.
- ספירת החזרות
#include using namespace std; int maxConsecutiveOnes(int x) { // Initialize result int count = 0; // Count the number of iterations to // reach x = 0. while (x!=0) { // This operation reduces length // of every sequence of 1s by one. x = (x & (x << 1)); count++; } return count; } int main() { // Function Call cout << maxConsecutiveOnes(14) << endl; return 0; }
Java class GFG { private static int maxConsecutiveOnes(int x) { // Initialize result int count = 0; // Count the number of iterations to // reach x = 0. while (x!=0) { // This operation reduces length // of every sequence of 1s by one. x = (x & (x << 1)); count++; } return count; } public static void main(String strings[]) { System.out.println(maxConsecutiveOnes(14)); } }
Python def maxConsecutiveOnes(x): # Initialize result count = 0 # Count the number of iterations to # reach x = 0. while (x!=0): # This operation reduces length # of every sequence of 1s by one. x = (x & (x << 1)) count=count+1 return count if __name__ == '__main__': print(maxConsecutiveOnes(14)) # by Anant Agarwal.
C# using System; class GFG { // Function to find length of the // longest consecutive 1s in binary // representation of a number private static int maxConsecutiveOnes(int x) { // Initialize result int count = 0; // Count the number of iterations // to reach x = 0. while (x != 0) { // This operation reduces length // of every sequence of 1s by one. x = (x & (x << 1)); count++; } return count; } // Driver code public static void Main() { Console.WriteLine(maxConsecutiveOnes(14)); } } // This code is contributed by Nitin Mittal.
JavaScript function maxConsecutiveOnes(x) { // Initialize result let count = 0; // Count the number of iterations to reach x = 0 while (x !== 0) { // This operation reduces length of // every sequence of 1s by one x = (x & (x << 1)); count++; } return count; } // Driver code console.log(maxConsecutiveOnes(14));
PHP // PHP program to find length function maxConsecutiveOnes($n) { // Initialize result $count = 0; // Count the number of // iterations to reach x = 0. while ($n != 0) { // This operation reduces // length of every sequence // of 1s by one. $n = ($n & ($n << 1)); $count++; } return $count; } echo maxConsecutiveOnes(14) 'n'; ?> תְפוּקָה
3
מורכבות זמן: O(1)
מרחב עזר: O(1)
[גישה נוספת] באמצעות המרת מחרוזת
אנו מאתחלים שני משתנים max_len ו-cur_len ל-0. לאחר מכן אנו חוזרים על כל סיביות של המספר השלם n. אם הסיביות הכי פחות משמעותיות (LSB) היא 1, נגדיל את cur_len כדי לספור את הריצה הנוכחית של 1 רצופות. אם ה-LSB הוא 0 הוא שובר את הרצף הנוכחי אז אנו מעדכנים את max_len אם cur_len גדול יותר ומאפסים את cur_len ל-0. לאחר בדיקת כל סיביות נעביר את n ימינה ב-1 כדי לעבור לסיביות הבאות. לבסוף לאחר סיום הלולאה אנו מבצעים עדכון אחרון של max_len אם cur_len הסופי גדול יותר ומחזירים max_len כאורך הרצף הארוך ביותר של 1s עוקבות.
C++#include #include #include using namespace std; int maxConsecutiveOnes(int n){ string binary = bitset<32>(n).to_string(); int count = 0; int maxCount = 0; // Loop through the binary string to // find the longest consecutive 1s for (int i = 0; i < binary.size(); i++) { if (binary[i] == '1') { count++; if (count > maxCount) { maxCount = count; } } else { count = 0; } } // Print the result return maxCount ; } int main() { int n = 14; cout << maxConsecutiveOnes(n) <<'n'; return 0; }
Java import java.util.*; public class Main { static int maxConsecutiveOnes(int n) { String binary = String.format('%32s' Integer.toBinaryString(n)).replace(' ' '0'); int count = 0; int maxCount = 0; // Loop through the binary string to // find the longest consecutive 1s for (int i = 0; i < binary.length(); i++) { if (binary.charAt(i) == '1') { count++; if (count > maxCount) { maxCount = count; } } else { count = 0; } } // Return the result return maxCount; } public static void main(String[] args) { int n = 14; System.out.println(maxConsecutiveOnes(n)); } }
Python def maxConsecutiveOnes(n): binary = format(n '032b') count = 0 maxCount = 0 # Loop through the binary string to # find the longest consecutive 1s for bit in binary: if bit == '1': count += 1 if count > maxCount: maxCount = count else: count = 0 # Return the result return maxCount if __name__ == '__main__': n = 14 print(maxConsecutiveOnes(n))
C# using System; class GFG { static int MaxConsecutiveOnes(int n) { string binary = Convert.ToString(n 2).PadLeft(32 '0'); int count = 0; int maxCount = 0; // Loop through the binary string to // find the longest consecutive 1s foreach (char bit in binary) { if (bit == '1') { count++; if (count > maxCount) maxCount = count; } else { count = 0; } } // Return the result return maxCount; } static void Main() { int n = 14; Console.WriteLine(MaxConsecutiveOnes(n)); } }
JavaScript function maxConsecutiveOnes(n) { let binary = n.toString(2).padStart(32 '0'); let count = 0; let maxCount = 0; // Loop through the binary string to // find the longest consecutive 1s for (let i = 0; i < binary.length; i++) { if (binary[i] === '1') { count++; if (count > maxCount) { maxCount = count; } } else { count = 0; } } // Return the result return maxCount; } // Driver code let n = 14; console.log(maxConsecutiveOnes(n));
תְפוּקָה
3