检查二进制字符串是否在1s之间有0 |集1（一般方法）-yiteyi-C++库

给定一个0和1的字符串，我们需要检查给定的字符串是否有效。当1之间不存在零时，给定字符串有效。例如，1111、000011110、1111000是有效字符串，但01010011、01010、101不是。这里讨论了解决这个问题的一种方法，给出了使用正则表达式的另一种方法第二组 例如：

null

Input : 100Output : VALIDInput : 1110001Output : NOT VALIDThere is 0 between 1sInput : 00011Output : VALID

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

Algorithm:

查找字符串中第一个出现的1。让它成为第一。
查找字符串中最后出现的1。让它成为最后一个。
从第一个循环到最后一个循环，如果存在0，则返回false。如果未找到0，则返回true。

Explanation:Suppose we have a string:  01111011110000 Now take two variables say A and B. run a loop for 0 to length of the string and point Ato the first occurrence of 1, after that again run a loop from length of the string to 0and point second variable to the last occurrence of 1.So A = 1 (Position of first '1' is the string) and B = 9 (last occurrence of '1').Now run a loop from A to B and check that '0' is present between 1 or not, if "YES" than set flag to 1 and break the loop, else set flag  to 0.In this case flag will set to 1 as the given string is not valid and print "NOT VALID".

C++

                         // C++ program to check if a string is valid or not.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function returns 1 when string is valid                       
                         // else returns 0                       
                         bool                                     checkString(string s)                       
                         {                       
                                                 int                                     len = s.length();                       
           
                                                 // Find first occurrence of 1 in s[]                       
                                                 int                                     first = s.size() + 1;                       
                                                 for                                     (                                     int                                     i = 0; i < len; i++) {                       
                                                 if                                     (s[i] ==                                     '1'                                     ) {                       
                                                 first = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Find last occurrence of 1 in s[]                       
                                                 int                                     last = 0;                       
                                                 for                                     (                                     int                                     i = len - 1; i >= 0; i--) {                       
                                                 if                                     (s[i] ==                                     '1'                                     ) {                       
                                                 last = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Check if there is any 0 in range                       
                                                 for                                     (                                     int                                     i = first; i <= last; i++)                       
                                                 if                                     (s[i] ==                                     '0'                                     )                       
                                                 return                                     false                                     ;                       
           
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string s =                                     "00011111111100000"                                     ;                       
                                                 checkString(s) ? cout <<                                     "VALID"                                     : cout <<                                     "NOT VALID"                                     ;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to check if a string is valid or not.                       
           
                         class                                     Test {                       
                                                 // Method returns 1 when string is valid                       
                                                 // else returns 0                       
                                                 static                                     boolean                                     checkString(String s)                       
                                                 {                       
                                                 int                                     len = s.length();                       
           
                                                 // Find first occurrence of 1 in s[]                       
                                                 int                                     first =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < len; i++) {                       
                                                 if                                     (s.charAt(i) ==                                     '1'                                     ) {                       
                                                 first = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Find last occurrence of 1 in s[]                       
                                                 int                                     last =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i = len -                                     1                                     ; i >=                                     0                                     ; i--) {                       
                                                 if                                     (s.charAt(i) ==                                     '1'                                     ) {                       
                                                 last = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Check if there is any 0 in range                       
                                                 for                                     (                                     int                                     i = first; i <= last; i++)                       
                                                 if                                     (s.charAt(i) ==                                     '0'                                     )                       
                                                 return                                     false                                     ;                       
           
                                                 return                                     true                                     ;                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 String s =                                     "00011111111100000"                                     ;                       
                                                 System.out.println(checkString(s) ?                                     "VALID"                                     :                                     "NOT VALID"                                     );                       
                                                 }                       
                         }                       

python

                         # Python3 program to check if                       
                         # a string is valid or not.                       
           
                         # Function returns 1 when                       
                         # string is valid else                       
                         # returns 0                       
                         def                                     checkString(s):                       
                                   
                                                 Len                                     =                                     len                                     (s)                       
                                   
                                                 # Find first occurrence                       
                                                 # of 1 in s[]                       
                                                 first                                     =                                     len                                     (s)                                     +                                     1                       
           
                                                 for                                     i                                     in                                     range                                     (                                     Len                                     ):                       
                                                 if                                     (s[i]                                     =                                     =                                     '1'                                     ):                       
                                                 first                                     =                                     i                       
                                                 break                       
           
                                                 # Find last occurrence                       
                                                 # of 1 in s[]                       
                                                 last                                     =                                     0                       
           
                                                 for                                     i                                     in                                     range                                     (                                     Len                                     -                                     1                                     ,                       
                                                 -                                     1                                     ,                                     -                                     1                                     ):                       
                                                 if                                     (s[i]                                     =                                     =                                     '1'                                     ):                       
                                                 last                                     =                                     i                       
                                                 break                       
           
                                                 # Check if there is any                       
                                                 # 0 in range                       
                                                 for                                     i                                     in                                     range                                     (first,                       
                                                 last                                     +                                     1                                     ):                       
                                                 if                                     (s[i]                                     =                                     =                                     '0'                                     ):                       
                                                 return                                     False                       
                                                 return                                     True                       
           
                         # Driver code                       
                         s                                     =                                     "00011111111100000"                       
                         if                                     (checkString(s)):                       
                                                 print                                     (                                     "VALID"                                     )                       
                         else                                     :                       
                                                 print                                     (                                     "NOT VALID"                                     )                       
           
                         # This code is contributed by avanitrachhadiya2155                       

C#

                         // C# program to check if a                       
                         // string is valid or not.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Method returns 1 when string is valid                       
                                                 // else returns 0                       
                                                 static                                     bool                                     checkString(String s)                       
                                                 {                       
                                                 int                                     len = s.Length;                       
           
                                                 // Find first occurrence of 1 in s[]                       
                                                 int                                     first = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < len; i++) {                       
                                                 if                                     (s[i] ==                                     '1'                                     ) {                       
                                                 first = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Find last occurrence of 1 in s[]                       
                                                 int                                     last = 0;                       
                                                 for                                     (                                     int                                     i = len - 1; i >= 0; i--) {                       
                                                 if                                     (s[i] ==                                     '1'                                     ) {                       
                                                 last = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Check if there is any 0 in range                       
                                                 for                                     (                                     int                                     i = first; i <= last; i++)                       
                                                 if                                     (s[i] ==                                     '0'                                     )                       
                                                 return                                     false                                     ;                       
           
                                                 return                                     true                                     ;                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 string                                     s =                                     "00011111111100000"                                     ;                       
                                                 Console.WriteLine(checkString(s) ?                       
                                                 "VALID"                                     :                                     "NOT VALID"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

Javascript

                         <script>                       
           
                                                 // JavaScript program to check                       
                                                 // if a string is valid or not.                       
                                   
                                                 // Method returns 1 when string is valid                       
                                                 // else returns 0                       
                                                 function                                     checkString(s)                       
                                                 {                       
                                                 let len = s.length;                       
                                   
                                                 // Find first occurrence of 1 in s[]                       
                                                 let first = 0;                       
                                                 for                                     (let i = 0; i < len; i++) {                       
                                                 if                                     (s[i] ==                                     '1'                                     ) {                       
                                                 first = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Find last occurrence of 1 in s[]                       
                                                 let last = 0;                       
                                                 for                                     (let i = len - 1; i >= 0; i--) {                       
                                                 if                                     (s[i] ==                                     '1'                                     ) {                       
                                                 last = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Check if there is any 0 in range                       
                                                 for                                     (let i = first; i <= last; i++)                       
                                                 if                                     (s[i] ==                                     '0'                                     )                       
                                                 return                                     false                                     ;                       
                                   
                                                 return                                     true                                     ;                       
                                                 }                       
                                   
                                                 let s =                                     "00011111111100000"                                     ;                       
                                                 document.write(checkString(s) ?                       
                                                 "VALID"                                     :                                     "NOT VALID"                                     );                       
                                   
                         </script>                       

输出：

VALID

时间复杂性： O（n）

本文由 萨希尔·拉吉普特 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章