Bit Algorithms

X. O(32n) - bit counting
LeetCode 169 - Majority Element
LeetCode 229 - Majority Number II
- Boyer-Moore Majority Vote (not bit count)
Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array. Find it.

LeetCode 137 - Single Number II
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

LeetCode 477 - Total Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.

LintCode 196 - Find the Missing Number I
Given an array contains N numbers of 0 .. N, find which number doesn't exist in the array.
for (int i = 0; i < nums.length; i++) {
    result ^= i;
    result ^= nums[i];
}
result ^= nums.length;

X. Use bit to store info
LeetCode 187 -  Repeated DNA Sequences

LeetCode 318 - Maximum Product of Word Lengths
Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
private int getMask(String s){
    int mask = 0;
    for(char c: s.toCharArray()){
        mask |= 1 << (c - 'a');
    }
    return mask;
}

X. Bit String
LeetCode 320 - Generalized Abbreviation
Write a function to generate the generalized abbreviations of a word.
Example:
Given "word"
Return the following list (order does not matter):
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

X. Bit String
There exists a one to one mapping between abbreviation words and 2 based numbers.
Taking w2d for word as an example.
w2d--->0110
0110-->w11d-->w2d
So to get all the abbreviations for a word, first generate all the 2 based numbers within [0, 2^n -1] then maps each 2 based number to proper abbreviation string.

X. Bit String
public List generateAbbreviations(String word) {
    List result = new ArrayList();
    int maxLen = 1<for
(int i=0;ireturn result; } public String getString(int num,String word){ StringBuilder sb = new StringBuilder(); int count = 0for(int i=0;iint bit = (num>>i)&1if(bit==1){ if(count!=0){ sb.append(count); count = 0; } sb.append(word.charAt(i)); }else{ count+=1; } } if(count!=0) sb.append(count); return sb.toString(); }

X. DFS
public List generateAbbreviations(String word) {
    List res = new ArrayList<>();
    DFS(res, new StringBuilder(), word.toCharArray(), 0, 0);
    return res;
}

public void DFS(List res, StringBuilder sb, char[] c, int i, int num) {
    int len = sb.length();  
    if(i == c.length) {
        if(num != 0) sb.append(num);
        res.add(sb.toString());
    } else {
        DFS(res, sb, c, i + 1, num + 1);               // abbr c[i]

        if(num != 0) sb.append(num);                   // not abbr c[i]
        DFS(res, sb.append(c[i]), c, i + 1, 0);        
    }
    sb.setLength(len); 
}

X. Bit Trie
LeetCode 421 - Maximum XOR of Two Numbers in an Array
Given a list of numbers, a[0], a[1], a[2], … , a[N-1], where 0 <= a[i] < 2^32. Find the maximum result of a[i] XOR a[j].


Post a Comment

Labels

Java (159) Lucene-Solr (110) All (58) Interview (58) J2SE (53) Algorithm (43) Soft Skills (36) Eclipse (34) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (15) Defects (14) Text Mining (14) J2EE (13) Network (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Dynamic Languages (8) Http Client (8) Maven (8) Security (8) Trouble Shooting (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Problem Solving (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) IDE (5) Lesson Learned (5) Programmer Skills (5) System Design (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Python (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Troubleshooting (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts