1 या 0

Question

की लगातार बिट स्ट्रिंग ढूँढना लगातार सबसे लंबे बिट स्ट्रिंग (या तो 1 या 0) की लंबाई कैसे प्राप्त करें?

00000000 11110000 00000000 00000000 -> यदि यह 0 है तो लंबाई हो जाएगा 20

11111111 11110000 11110111 11111111 -> यदि यह 1 है तो लंबाई हो जाएगा 12

Answer 1

एक सरल तरीका है बस पाश होगा बिट्स पर, और एक पंक्ति में बिट्स की संख्या का ट्रैक रखें, जिसकी कीमत समान है, और अधिकतम जो यह मान पहुंच गया है।

int num_conseq_matching_bits(int n) { 
    int i, max, cur, b, prevb; 
    prevb = n & 1; /* 0th bit */ 
    cur = 1; 
    max = 1; 
    for(i=1; i<32; i++) { 
     b = (n >> i) & 1; /* get the i'th bit's value */ 
     if(b == prevb) { 
      cur += 1; 
      if(cur > max) 
       max = cur; 
     } 
     else { 
      cur = 1; /* count self */ 
      prevb = b; 
     } 
    } 
    return max; 
} 

Answer 2

आप एक को देखने तालिका फार्म कर सकते हैं आप के लिए जल्दी से यह करने के लिए:

यहाँ एक सरल सी समारोह जो सिर्फ इस करता है। तालिका जितनी बड़ी होगी, उतनी तेज़ी से लुकअप होगी। 2x256 एंट्री टेबल थोड़ी सी झुकाव के साथ एक समय में 8 बिट्स कर सकते हैं। तालिका का 1 एस संस्करण जोड़ें और प्रविष्टियां जोड़ने शुरू करें। शायद यह है कि मैं इसके बारे में कैसे जाऊंगा।

Answer 3

मैं टेबल विचार से सहमत नहीं हूं, क्योंकि मैं इसे आजमा रहा था और महसूस किया कि एएससीआईआई में "बीए" में 'बी' के लिए लगातार 5 0 और 'ए' के ​​लिए लगातार 5 0 होंगे, वे नहीं होंगे लगातार 10 के लिए एक साथ जोड़ें। वास्तव में, लगातार 5 0 अधिकतम होगा। (यह एक साधारण के संदर्भ में था क्रिस डोड है क्योंकि पर स्वेच्छाचार कैसे एक मेज सही ढंग से इस्तेमाल किया जा सकता "एक मेज विचार में गिनती बिट्स।"।)

मैं इस तरह एक एल्गोरिथ्म का प्रयोग करेंगे:

#include <iostream> 
#include <algorithm> 

using namespace std; 

// Assumes Little Endian architecture 
int mostConsecutiveBits(char str[], int length) { 
    int currentConsecutiveBits=0; 
    int maxConsecutiveBits=0; 
    char currentBit; 
    char lastBit=0; 
    char currentChar=str[0]; 
    int charCtr,bitCtr; 

    for (charCtr=length-1; charCtr>=0; charCtr--) { 

     currentChar=str[charCtr]; 

     for (bitCtr=0; bitCtr<8; bitCtr++) { 
      currentBit=currentChar & 1; 

      if (currentBit!=lastBit) { 
       maxConsecutiveBits=max(maxConsecutiveBits,currentConsecutiveBits); 
       currentConsecutiveBits=1; 
       lastBit=currentBit; 
      } 
      else { 
       currentConsecutiveBits++; 
      } 

      currentChar=currentChar>>1; 

     } 
     maxConsecutiveBits=max(maxConsecutiveBits,currentConsecutiveBits); 
    } 

    return maxConsecutiveBits; 
} 


int main (int argc, char * const argv[]) { 
    cout << mostConsecutiveBits("AB",2); 
    return 0; 
} 

इस एल्गोरिदम में, मुझे लगता है कि बिटस्ट्रीम को 8-बिट वर्णों के रूप में दर्शाया गया है। प्रत्येक चरित्र के लिए, मैं थोड़ी सी बिट के साथ आखिरी बिट को देखता हूं और। यदि यह आखिरी बिट जैसा ही है, तो मैं लगातार बिट गिनती करता हूं, अन्यथा, मैं गिनती को रीसेट करता हूं क्योंकि बिट्स लगातार नहीं होते हैं। मैं फिर अवलोकन के लिए वर्ण में अगले बिट को स्थानांतरित करने के लिए थोड़ा सा शिफ्ट ऑपरेशन का उपयोग करता हूं। उम्मीद है की यह मदद करेगा!

मेरा उत्तर प्रभावी ढंग से डेविड अंडरहिल के उत्तर का डुप्लिकेट है। :)

Answer 4

तालिका विचार का उपयोग करने के लिए, आप की तरह

static struct { 
    int lead; /* leading 0 bits */ 
    int max; /* maximum 0 bits */ 
    int trail; /* trailing 0 bits */ 
} table[256] = { ....data.... }; 

int mostConsecutiveBits(unsigned char *str, int length, bool count_ones) { 
    int max = 0; /* max seen so far */ 
    int trail = 0; /* trailing 0s from previous bytes */ 
    while (length-- > 0) { 
     int byte = *str++; 
     if (count_ones) 
      byte ^= 0xff; 
     if (table[byte].max > max) 
      max = table[byte].max; 
     if (trail + table[byte].lead > max) 
      max = trail + table[byte].lead; 
     if (byte) 
      trail = table[byte].trail; 
     else 
      trail += 8; 
    } 
    return max; 
} 

तालिका आरंभ कुछ चाहिए सीधी-सपाट है, लेकिन अपने बिट और बाइट आदेश (थोड़ा endian या बड़े endian) पर निर्भर करता है।

Answer 5

के बाद से आप ने लिखा नहीं था बिट श्रृंखला (नियमित पूर्णांक, बाइट सरणी या चार स्ट्रिंग मैं मान लिया गया है कि यह चार सरणी

iPhone से

int maxConsBits(char *pStr,char cChar) 
{ 
    char curChar; 
    int curMax = 0; 
    int max = 0; 
    while (pStr) 
    { 
     if (*pStr == cChar) 
     { 
      curMax++; 
      if (curMax > max) 
      { 
      max = curMax; 
      } 
     } 
     else 
     {   
      curMax = 0; 
     } 
     pStr++; 
    } 
    return max; 
} 

Answer 6

पोस्टिंग उंगलियों withbig क्या है।

वाले हैं , फिर उलटा।

लीडज़ फ़ंक्शन का उपयोग करके इनपुट पर लूप करें। प्रत्येक पुनरावृत्ति के लिए, इनपुट को बाईं ओर स्थानांतरित करें। जब तक आप इनपुट के अंत तक नहीं पहुंच जाते। ध्यान दें कि आपको मूल इनपुट लंबाई की तुलना करने की आवश्यकता है संचयी लीडज़ गणना

इसके अलावा, एक अनुकूलन के रूप में, आप प्रारंभिक रूप से निरस्त कर सकते हैं जब शेष इनपुट लंबाई आपके द्वारा देखी गई सबसे बड़ी लीडज़ से कम है।

ऑनलाइन कई तेज लीडज़ एल्गोरिदम ऑनलाइन हैं।शून्य की गिनती, बस पहले बिटवाइज़ पूरक लेने के लिए

int CountConsecutiveOnes(unsigned long n) 
{ 
    unsigned long m = n; 
    int k = 0; 

    while (m) 
    { 
     ++k; 
     n >>= 1; 
     m &= n; 
    } 

    return k; 
} 

:

Answer 7

आप सिर्फ चार बाइट्स की एक बाइट स्ट्रिंग के लिए देख रहे हैं, तो आप इन एक unsigned long में पैक और इस तरह एक एल्गोरिथ्म का उपयोग कर सकते हैं।

आप चार से अधिक समय बाइट तार गिनती करने के लिए की जरूरत है, तो आप सिर्फ संचालन x >>= 1 और x & y या तो सीधे बाइट तार पर लागू कर सकते हैं या इसे और अधिक x >>= 1 के कार्यान्वयन पर unsigned long तो चेकों कैरी के तार का उपयोग करने के कुशल हो सकता है बहुत महंगा नहीं हैं।

Answer 8

निम्नलिखित अवधारणा पर आधारित है कि यदि आप AND स्वयं के एक स्थानांतरित संस्करण के साथ थोड़ा अनुक्रम है, तो आप लगातार 1 की पंक्ति से पिछली 1 को हटा रहे हैं।

 11101111 (x) 
    & 11011110 (x << 1) 
    ---------- 
     11001110 (x & (x << 1)) 
     ^^
     | | 
    trailing 1 removed 

दोहरा इस N बार 0x00 करने के लिए N लगातार 1 के साथ किसी भी क्रम कम हो जाएगा।

int count_consecutive_ones(int in) { 
    int count = 0; 
    while (in) { 
    in = (in & (in << 1)); 
    count++; 
    } 
    return count; 
} 

की लगातार 0 के संख्या की गणना के लिए, बस को उलटने के लिए और एक ही दिनचर्या:

तो, लगातार 1 की यह गिन सकते हैं। अवधारणा के

int count_consecutive_zeros(int in) { 
    return count_consecutive_ones(~in); 
} 

---

सबूत: http://ideone.com/Z1l0D

int main(void) { 
    printf("%d has %d consecutive 1's\n", 0, count_consecutive_ones(0)); 
    printf("%d has %d consecutive 0's\n", 0, count_consecutive_zeros(0)); 

    /* 00000000 11110000 00000000 00000000 -> If it is 0 then length will be 20 */ 
    printf("%x has %d consecutive 0's\n", 0x00F00000, count_consecutive_zeros(0x00F00000)); 

    /* 11111111 11110000 11110111 11111111 -> If it is 1 then length will be 12 */ 
    printf("%x has %d consecutive 1's\n", 0xFFF0F7FF, count_consecutive_ones(0xFFF0F7FF)); 
} 

आउटपुट:

0 has 0 consecutive 1's 
0 has 32 consecutive 0's 
f00000 has 20 consecutive 0's 
fff0f7ff has 12 consecutive 1's 

Answer 9

यह आपकी मदद कर सकता है .... सबसे पहले अपने द्विआधारी संख्या स्ट्रिंग के लिए कनवर्ट बिट्स का कहना है। यह आप लगातार 1 के की अधिकतम संख्या (जावा में) दे देंगे

String[] split = bits.split("0"); 
Arrays.sort(split); 
int maxLength = split[split.length - 1].length(); 

Answer 10

public static int maxConsecutiveOneInBinaryNumber(int number) { 
int count = 0; 
int max = 0; 
while (number != 0) { 
    if ((number & 1) == 1) { 
    count++; 
    } else { 
    max = Math.max(count, max); 
    count = 0; 
    } 
    number = number >> 1; 
} 
return Math.max(count, max); 
} 

आप यहाँ इस कोड को कर सकते हैं: https://github.com/VishalSKumar/DSFiddle/blob/master/src/main/java/com/vishalskumar/hackerrank/MaxConsecutiveOneInBinary.java