Showing posts with label Binary Search. Show all posts
Showing posts with label Binary Search. Show all posts

Monday, March 13, 2017

Leetcode -- 129. Sum Root to Leaf Numbers(dfs)

129. Sum Root to Leaf Numbers(dfs)
medium
https://leetcode.com/problems/sum-root-to-leaf-numbers/#/description

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
    1
   / \
  2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

思路: - Using dfs, add left path & right path to current node for getting number till reach the leaf.
           Calculate by sum = root.val + sum*10;
           - Since we calculate left & right with same previous sum(parent node), so we do
            recursive call: helper(root.left, sum) + helper(root.right, sum);

Complexity: Time O(n) Space O(h)


public class Solution {
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }
    public int helper(TreeNode root, int sum){
        if(root == null) return 0;
        if(root.left == null && root.right == null)
            return root.val + sum*10;
        sum = root.val + sum*10;
        return helper(root.left, sum) + helper(root.right, sum);
    }
}




Friday, February 10, 2017

Leetcode/各大家 -- 33. Search in Rotated Sorted Array(Binary Search)

33. Search in Rotated Sorted Array(Binary Search)
Medium
https://leetcode.com/problems/search-in-rotated-sorted-array/
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

思路:* Know that rotated array is 1st reversed all, 2nd divided by 2 parts, each part do reverse order.
           So the rotated array here is in 2 parts in ascending order. [(...pivot)(pivot+1...)]
           * Use binary search to find answers in one part of the ascending subarray.
Complexity: Time O(N) Space O(1)

public class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0)return -1;
        //find pivot - nums[p] is max
        int p = 0;
        while(p < nums.length - 1){
            if(nums[p+1] >= nums[p])p++;
            else break;
        }
        if(target > nums[p]) return -1;
        if(target >= nums[0]){
            return search(nums, target, 0, p);
        }
        return search(nums, target, p + 1, nums.length - 1);
    }
    //search in sorted array
    public int search(int[] nums, int target, int start, int end){
        while(start <= end){
            int mid = start + (end - start)/2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] <= target)
                start = mid + 1;
            else
                end = mid - 1;
        }
        return -1;
    }
}

Sunday, January 8, 2017

Leetcode/各大家 -- 270. Closest Binary Search Tree Value

270. Closest Binary Search Tree Value

https://leetcode.com/problems/closest-binary-search-tree-value/
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.


1. recursion
Complexity: 时间 O(logN) 空间 O(H)

思路

根据二叉树的性质,我们知道当遍历到某个根节点时,最近的那个节点要么是在子树里面,要么就是根节点本身。所以我们根据这个递归,返回子树中最近的节点,和根节点中更近的那个就行了。
public class Solution {
    public int closestValue(TreeNode root, double target) {
        // 选出子树的根节点
        TreeNode kid = target < root.val ? root.left : root.right;
        // 如果没有子树,也就是递归到底时,直接返回当前节点值
        if(kid == null) return root.val;
        // 找出子树中最近的那个节点
        int closest = closestValue(kid, target);
        // 返回根节点和子树最近节点中,更近的那个节点
        return Math.abs(root.val - target) < Math.abs(closest - target) ? root.val : closest;
    }
}

2.Iterative
We the node is in tree so traveling the BST and keep a value closet to target

Complexity: O(lgN)

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        while(root!=null){
            //if current root.val is closer, update closest 
            closest = Math.abs(closest-target)<Math.abs(root.val-target)?closest:root.val;
            //do binary search
            root = target<root.val?root.left:root.right;
        }
        return closest;
    }
}
 

Tuesday, December 13, 2016

Leetcode/各大家 -- 50.pow(double x,int n) Binay Search

Pow(x, n) - Binary Search
  • Difficulty: Medium
Implement pow(x, n).
Ex: 9^-3  = 1/27
2^-2 = 1/4 // -2%2 = 0
2^-3 = 1/8 // -3%2 = 1
company: LinkedIn, Google, Bloomberg, Facebook
https://leetcode.com/problems/powx-n/

思路:每次将指数n/2,然后 n分三种情况: 
1.等于1,则x*res*res 2.等于0 则res*res 3.负数,则res*res/x
关键词: Divide and Conquer (Recurrsion)
Time & Space complexity: O(log n) O(1)


public class Solution {
    public double myPow(double x, int n) {
        if (x == 0)return 0;
        if (n == 0)return 1;// base case: x^0 = 1
        double res = myPow(x, n/2);
        if(n%2 == 0){//-2%2=0
            return res*res;
        }else if(n%2 == 1){
            return res*res*x;
        }else {//-1 here, -3%2=-1
            return res*res/x;
        }
    }
}

Leetcode - Binary Search解法


Binary Search (T(n) = T(n/2) + O(1). =>O(lgN))
适用于sorted array,mid = start + (end-start)/2; //!!!avoid limit error big integer

EX:
Two sum- sorted array
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
O(nlgn).
外面for loop h或者 low,high
里面start,mid,end 根据index搜

for(int k=0;k<nums.length-1;k++){
            int start=k+1,end=nums.length-1, gap=target-nums[k];
            while(start<=end){//是个范围
                        mid = start + (end-start)/2; //!!!avoid limit error
                        start = mid+1, end = mid-1;

278. Find first bad version F家
--返回是start: end 会落在 non bad的最后一个里面,下一个start落在第一个bad的位置
https://leetcode.com/problems/first-bad-version/
public int firstBadVersion(int n) {
        int start = 1, end = n;
        while(start <= end){
            int mid = start + (end - start)/2;
            if(isBadVersion(mid)){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
        return start;
    }


 Search for range
 https://leetcode.com/submissions/detail/86564241/
--Another approach : find first appearance vs find last appearance(return mid)
if(nums[mid] >= target){//first appearance
            end = mid - 1;
        }
  if(nums[mid] <= target){//last appearance
            start = mid + 1;
        } 

https://leetcode.com/problems/search-for-a-range/

Search insert position
https://leetcode.com/problems/search-insert-position/
 --有时候 return start (low)
» 33. Search in Rotated Sorted Array
http://rainykat.blogspot.com/2017/02/leetcode-33-search-in-rotated-sorted.html 
» 69.367. sqrt(x) F家 /valid perfect square LinkedIn
根据 mid= (left+right)/2来和x/mid比较
http://rainykat.blogspot.com/2016/12/leetcode-sqrtx.html

Leetcode/F家,LinkedIn-69.sqrt(x) 和 367.valid perfect square(Binary Search)

69.Sqrt(x) - Binary Search
  • Difficulty: Medium
https://leetcode.com/problems/sqrtx/
Implement int sqrt(int x).
Compute and return the square root of x.

sqrt(9)=3

Company: Bloomberg Apple Facebook
思路:用binary search找中间满足条件的数,满足条件的情况特别注意 ,总会在loop里return
            - always use x/mid to compare
            - return case: x/mid >= mid && x/(mid+1) < (mid+1)//eg: 5/2 >2; 5/3<3
Complexity: Time O(logN) Space O(1)

public class Solution {
    public int mySqrt(int x) {
        if(x==0){ return 0;}
        if(x==1){ return 1;}
        int start = 1,end = x;
        while(start<=end){
            int mid = start + (end-start)/2;
            if (mid <= x / mid && (mid + 1) > x / (mid + 1))// 特别注意满足条件,不止是等于
       return mid; 
      else if (x / mid < mid)//mid太大
       end = mid-1;
      else
       start = mid + 1;
        }
        return start;//什么都行。。。。
    }
}


延展题
367.Valid Perfect Square LinkedIn
  • Difficulty: Medium
 https://leetcode.com/problems/valid-perfect-square/ 
1.做法1: 1+3+5+7+...
2.bitwise
3.double cast


public class Solution {
    public boolean isPerfectSquare(int num) {
        if(num==0||num==1){ return true;}
        int start = 1, end =num;
        while(start<=end){
            int mid = start+(end-start)/2;
            if(mid<=num/mid&&(mid+1)>num/(mid+1)){
                if((double)num/mid - mid==0.0 ){//和上题一样,加多一个判定条件
                    return true;
                }
                return false;
            }else if(mid>num/mid){
                end = mid - 1;
            }else{
                start = mid+1;
            }
        }
        return false;
    }
}