Binary Search (Tree) + Bisection - Algorithm

Binary search
- Prefer [], start=0, end=len-1
- int mid = left + (right - left) / 2;
- if low

  1. public int searchRightIndex(int[] nums, int left, int right, int target) {  
  2.     while (left <= right) {  
  3.         int mid = (left + right) / 2;  
  4.         if (nums[mid] > target) right = mid - 1;  
  5.         else left = mid + 1;  
  6.     }  
  7.     return right;  
  8. }  
  9. public int searchLeftIndex(int[] nums, int left, int right, int target) {  
  10.     while (left <= right) {  
  11.         int mid = (left + right) / 2;  
  12.         if (nums[mid] < target) left = mid + 1;  
  13.         else right = mid - 1;  
  14.     }  
  15.     return left;  
  16. }  

LeetCode 35 - Search Insert Position
LeetCode 34 - Search for a Range
find the starting and ending position of a given target value.
start = Solution.firstGreaterEqual(A, target);
end = firstGreaterEqual(A, target + 1) - 1;

LeetCode 278 - First Bad Version
http://www.cnblogs.com/anne-vista/p/4848945.html

LeetCode 374 - Guess Number Higher or Lower
https://leetcode.com/articles/guess-number-higher-or-lower/

X. Search in rotated sort array
LeetCode 153 - Find the minimum element in a sorted and rotated array

LeetCode 33 - Searching an Element in a Rotated Sorted Array
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end){
            int mid = (start + end) / 2;
            if (nums[mid] == target)
                return mid;
        
            if (nums[start] <= nums[mid]){// can be just < as no duplicate
                 if (target < nums[mid] && target >= nums[start]) 
                    end = mid - 1;
                 else
                    start = mid + 1;
            } 
        
            if (nums[mid] <= nums[end]){//<
                if (target > nums[mid] && target <= nums[end])
                    start = mid + 1;
                 else
                    end = mid - 1;
            }
        }
        return -1;
    }
LeetCode 81 - Search in Rotated Sorted Array II


Bisection
- Suppose we know the answer, it's easier to determine whether the answer is true/possible
- isPossible(**, int curValue)

LeetCode 287 - Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive),
- Constant space, don't modify the array
- Bisection (1, nums.length-1)
- 32(n)
public int findDuplicate(int[] nums) {
    int n = nums.length-1, res = 0;
    for (int p = 0; p < 32; ++ p) {
        int bit = (1 << p), a = 0, b = 0;
        for (int i = 0; i <= n; ++ i) {
            if (i > 0 && (i & bit) > 0) ++a;
            if ((nums[i] & bit) > 0) ++b;
        }
        if (b > a) res += bit;
    }
    return res;
}
- O(n) find cycle in LinkedList


find the contiguous subarray whose length is greater than or equal to k that has the maximum average value.
        for (int n: nums) {
            max_val = Math.max(max_val, n);
            min_val = Math.min(min_val, n);
        }
        double prev_mid = max_val, error = Integer.MAX_VALUE;
        while (error > 0.00001) {
            double mid = (max_val + min_val) * 0.5;
            if (check(nums, mid, k))
                min_val = mid;
            else
                max_val = mid;
            error = Math.abs(prev_mid - mid);
            prev_mid = mid;
        }

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given n, find the total number of full staircase rows that can be formed.

LeetCode 410 - Split Array Largest Sum
you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
- TODO DP

LintCode - Copy Books
Return the number of smallest minutes need to copy all the books.
- DP
- Bisection O(nlg(sum/k)), (max, total)

- sizeIsDoable (1, Math.min(height, width))
            while (minSize <= maxSize) {
                // The font size that will be attempted
                int currentTargetSize = (minSize + maxSize) / 2;

                // See if the given font size fits
                if (sizeIsDoable(currentTargetSize, width, height, message)) {
                    // It fits, save as largest so far and try even larger
                    minSize = currentTargetSize + 1;
                    bestSize = currentTargetSize;
                } else {
                    // Doesn't fit, try smaller sizes
                    maxSize = currentTargetSize - 1;
                }
            }

Compute the integer/real square root

LeetCode 367 - Valid Perfect Square
- O(nlogn) Bisection (1, num/2)

Codeforces Round #318 - Bear and Elections

POJ 3104 -- Drying
Poj 3258 - River Hopscotch
POJ 3273 -- Monthly Expense
POJ 3122 - Pie

X. Binary Search tree/TreeMap/TreeSet
- [lower, upper bound]
- In order traversal, prev node
- Binary search tree: TreeSet, window size k
- Use TreeSet or TreeMap directly
- Or can't when need store extra info in node such as sameCount, leftCount

LeetCode 530 - Minimum Absolute Difference in BST
- In order traversal, prevNode
- [lower, upper bound]

LeetCode - 220 Contains Duplicate III
find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
- Bucket sort
- Binary search tree: TreeSet, window size k O(nlogk)

LeetCode 352 - Data Stream as Disjoint Intervals
- TreeMap intervals to merge interval based on start
- TreeSet

LeetCode 436 - Find Right Interval
- Use TreeMap to store intervals
- Use TreeMap> to handle duplicate start
- Sort Intervals based on start + binary search

LeetCode 493 - Reverse Pairs
we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].
- Build the Binary Search Tree from right to left
- Merge Sort

LeetCode 414 - Third Maximum Number
Use PriorityQueue with HashSet to check duplicate
https://discuss.leetcode.com/topic/63086/java-priorityqueue-o-n-o-1
TreeSet (not PQ as need call contains)
set.add(num);
if(set.size() > 3) {set.remove(set.first());}
Maitain state: first, second, third

Post a Comment

Labels

Java (159) Lucene-Solr (112) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (38) Eclipse (33) Code Example (31) Linux (25) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) Problem Solving (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Shell (7) ANT (6) Coding Skills (6) Database (6) Lesson Learned (6) Programmer Skills (6) Scala (6) Tips (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) System Design (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) 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) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (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) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts