Notes by Louisa
Notes by Louisa
Notes by Louisa
  • Introduction
  • Chapter1 Python Cheatsheet
    • Reference, Deep Copy and Shallow Copy
    • Iterators
    • List Comprehensions
    • Numpy
    • Pandas
    • Data Visualization
    • DateTime
    • Python Good to knows
  • Chapter2 Java Cheatsheet
    • Fundamentals to Java
    • Interface, Abstract Class, Access Modifier, Exceptions
    • Linked List and Java List
    • Java Queue, Stack and Deque
    • Binary Tree
    • Heap in Java
    • Map/Set/Hash
    • OOD
  • Chapter3 Algorithm
    • Fundamental Knowledge
    • Binary Search
    • Basic Sorting
    • Advanced Sorting
    • Linked List
    • Recursion 1
    • HashTable
    • Queue
    • Sliding Window
    • Stack
    • Binary Tree
    • Binary Search Tree
    • Heap
    • String
    • Graph Search DFS1 (Back Tracking)
    • Recursion II and Memoization
    • Dynamic Programming
    • Complete Binary Tree, Segment Tree, Trie Tree
    • Graph Search BFS
    • Graph Search BFS 2
    • Graph Search DFS2
    • Problems from 'JianZhi Offer'
    • Problems Categorized
    • Bit Operations
  • Chapter4 Model
    • Linear Regression
    • Logistic Regression
    • Regularization and Feature Selection
    • Model Evaluation
    • Nonlinear Models
    • PCA
    • Unsupervised Learning
    • Gradient Descent and Gradient Boosting
    • XG Boost and Light GBD
    • Deep Learning
    • Tensorflow/Keras
    • RNN
  • Chapter5 Statistics and A/B Testing
    • Inference about independence
    • Probability, Sampling and Randomization with Python
    • A/B Testing
    • Stats Interview Review
    • Statistics Glossary
  • Chapter6 SQL
    • Student Scores Query
    • Order Query
    • Movie Rating Query
    • Social-Network Query
    • LeetCode SQL题目总结
    • Spark SQL
  • Chapter7 Big Data and Spark
    • Introduction to Pyspark
    • Data Cleaning with Apache Spark
    • Feature Engineering with Pyspark
    • Building Recommendation Engines with Pyspark
    • Building Data Engineering Pipelines in Python
    • Hadoop MapReduce
    • Big Data Related Paper
  • Chapter8 Code Walk-Throughs
    • Python
    • R
    • Shell
  • Chapter9 Special Topics
    • Anomaly Detection
    • E Commerce
    • Supply Chain
    • Social Network Analysis
    • NLP intro
    • Time Series
    • Challenge Prophet with LSTM models
  • Project: The Winning Recipes to an Oscar Award
  • Project: A Crime Analysis of the Last Decade NYC
  • Project: Predict User Type Based on Citibike Data
  • GeoSpark/GeoSparkVis for Geospatial Big Data
  • Single Scattering Albedo
  • Sea Ice Albedo Retrievals
  • Lidar Project
Powered by GitBook
On this page
  • Classic Version
  • 2D Version
  • Find Closest Element
  • First Occurrence
  • Last Occurrence
  • K Closest to Sorted Array
  • Smallest Element that is Larger than Target
  • Sqrt()
  • Find Peak Element
  • Search In Shifted Sorted Array I
  • First Bug Version
  • 新题: 虚拟数组
  • 高等难度
  • K-th smallest in Two Sorted Arrays
  • Closest k Element
  • Search In Unknown Sized Sorted Array
  • 实际工作中的binary search
  • 面试时:
  1. Chapter3 Algorithm

Binary Search

普通版、2D版、万金油版、有重复元素版

Classic Version

每次缩小一半的查找范围,和中间值比较。大于中间值往左,小于中间值往右。通过L=mid+1 or R=mid-1改变LR边界值。

def binary_search(nums, target):
 if not nums:
  return None
 left, right = 0, len(nums)-1
 while left<=right: #小于还是小于等于?可以用1个元素debug,循环都进不去,所以这里一定要小于等于
  mid=(left+right)/2
  if nums[mid]<target:
   left=mid+1 #必须+1, 因为还是用1个元素debug,如果数组里是5,找的是7,循环出不去
  elif nums[mid]>target:
   right=mid-1
  else 
   return mid
 return None 
//package 一般是一个名词,而且全小写、用点
//class 名词,首字母大写, upper CammelCase
//interface 名词,upper CammelCase
//method 动词, lower cammelCase
//method里的变量名, lower cammelCase

class Solution(object):
    public int binarySearch(int[] array, int target) {
        if (array==null) { //如果是0其实没关系 因为进不去循环,返回-1
        return -1;
        }
        int l = 0;
        int r = array.length-1;
        while (l<=r) {
            int mid = l+(r-l)/2; //int越过32位的overflow 可能会变成负数,可能是一个奇怪的数,不会自动变成long
            if (array[mid]==target) {
            return mid;
            }
            elif (array[mid]<target) {
            left = mid+1;
            }
            else {
            right = mid-1;
            }
        }
      return -1;
    } 

Time: O(logn)

2D Version

一个二维坐标可以和一维坐标联系,4*4的matrix,(2,2)代表2*4+2个元素比它小。index=row_index*m+col_index.(m: number of cols).

所以,row_index=index/m; col_index=index%m.

第一个index是0,最后一个index是n*m-1。所以初始化的left=0, right=n*m-1.

class Solution(object):
  def search(self, matrix, target):
    """
    input: int[][] matrix, int target
    return: int[]
    """
    # write your solution here
    if not matrix or len(matrix)==0:
      return [-1,-1]

    m, n = len(matrix), len(matrix[0])
    left, right= 0, m*n-1

    while left<=right:
      mid = (left+right)//2
      row = mid//n
      column = mid%n

      if matrix[row][column]==target:
        return [row, column]
      
      elif matrix[row][column]<target:
        left = mid+1
      
      else:
        right = mid-1
    
    return [-1,-1]

Time: O(log(n*m))

  1. 每次搜索都比上次少一半<------>所以我们必须保证每一次的搜索范围都在减小

  2. 终止时剩下1~2个元素,才能确认target是否在这两个元素之中<---->淘汰元素时要保证target不会被淘汰

Find Closest Element

eg [1,2,5,9] target=3, index=1, number=2

错误示范

因为如果(0,1),剩两个数或者剩下一个数,都会在这里做死循环;违反了上面中的原则1,搜索空间并没有减小,因为line5的mid永远都是一个值。

不能让left和right之间没有元素,不然会让left和right来回传值, 所以while的条件必须要在left和right之中隔一个值

def binary_search (nums, target):
    left=0
    right=len(nums)-1
    while left<=right:
        mid=(left+right)/2
        if nums[mid]>target:
            right=mid
        elif nums[mid]<target:
            left=mid
        else:
            return mid
return None
  1. 本质是提前一步退出

    搜索空间只剩下两个元素,target和谁更近就是谁

  2. Post-processing 最后剩下LR还没有比较

正确做法

class Solution(object):
  def closest(self, array, target):
    """
    input: int[] array, int target
    return: int
    """
    # write your solution here
    if not array or len(array)==0:
      return -1
    
    left, right = 0, len(array)-1

    while left<right-1:
      mid = (left+right)//2
      if array[mid]==target:
        return mid
      elif array[mid]<target:
        left = mid #不可以+1
      else:
        right = mid #不可以-1
    
    return left if (array[right]-target>target-array[left]) else right

#上面这种写法虽然没有+1-1 但是肯定不会有死循环,因为while循环条件不同了,循环内一定是三个元素,
#所以不会在两个数之间来回传值
class Solution (object):
    public int findClosest (int[] array, int target){
    if (array==null||array.length==0){
    return -1;
    }
    
    int l = 0;
    int r = array.length-1;
    
    while (l<r-1) {
        int mid = l+(r-l)/2; //int越过32位的overflow 可能会变成负数,可能是一个奇怪的数,不会自动变成long
        
        if (array[mid]==target) {
            return mid;
        }
        
        elif (array[mid]<target) {
            left = mid;
        }
        
        else {
            right = mid;
        }
    }
  return (array[right]-target<target-array[left])? right : left; //ternary operator
} 

Time: O(logn)

First Occurrence

如果找不到,return-1 (面试时,注意和面试官沟通,回复-1还是None)

  1. num[mid]<target, 左半边不要了,一定在右边,可以+1(left=mid+1)

  2. num[mid]>target, 右半边不要了,一定在左边,但是含mid(right=mid)

  3. num[mid]=target, 虽然找到了,但也有可能不是第一个,所以right=mid

class Solution(object):
  def firstOccur(self, array, target):
    """
    input: int[] array, int target
    return: int
    """
    # write your solution here
    if not array or len(array)==0:
        return -1
    
    left, right = 0, len(array)-1
    
    while left<right-1:
      
      mid = (left+right)//2
      
      if array[mid]==target:
        right=mid
      elif array[mid]<target:
        left=mid+1
      elif array[mid]>target:
        right=mid-1
    
    if array[left]==target:
      return left
    if array[right]==target:
      return right

    return -1  

Last Occurrence

和First Occurrence的区别在

1. mid=target时往左还是往右: 右

2. Post-Processing的顺序先后:先检查右边

class Solution(object):
  def lastOccur(self, array, target):
    """
    input: int[] array, int target
    return: int
    """
    # write your solution here
    if not array or len(array)==0:
        return -1
        
    left, right = 0, len(array)-1
    
    while left<right-1:
      
      mid = (left+right)//2
      
      if array[mid]==target:
        left = mid
      elif array[mid]<target:
        left = mid+1
      elif array[mid]>target:
        right = mid-1
    
    if array[right]==target:
        return right
    if array[left]==target:
        return left
    
    return -1

K Closest to Sorted Array

log(n)+k

line 35其实根本不用abs 因为既然sorted了也就知道谁大谁小了

class Solution(object):
  def kClosest(self, array, target, k):
    """
    input: int[] array, int target, int k
    return: int[]
    """
    # write your solution here
    res=[]
    if len(array)==0 or k==0:
      return res
    index=self.getIndex(array, target)
    l,r=index-1, index+1
    res.append(array[index])
    while len(res)<k and (l>=0 or r<len(array)):
      if r<len(array) and (l<0 or abs(array[l]-target)>abs(array[r]-target)):
        res.append(array[r])
        r+=1
      elif l>=0:
        res.append(array[l])
        l-=1
    return res
    
  

  def getIndex(self, array, target):
    left, right = 0,len(array)-1
    while left<right-1:
      mid=(left+right)//2
      if array[mid]==target:
        return mid
      elif array[mid]<target:
        left=mid
      else:
        right=mid
    return left if abs(array[left]-target)<abs(array[right]-target) else right
class Solution(object):
  def kClosest(self, array, target, k):
    """
    input: int[] array, int target, int k
    return: int[]
    """
    # write your solution here
    if not array or len(array)==0 or k<0:
      return -1
    
    index = self.binarySearch(array, target)
    result = []
    if k>0:
      result.append(array[index])
    
    i,j= index-1, index+1
    
    while len(result)<k and (i>=0 or j<=len(array)-1):
      if i>=0 and (j>len(array)-1 or target-array[i]<array[j]-target):
        result.append(array[i])
        i-=1
      else:
        result.append(array[j])
        j+=1
    return result

  def binarySearch(self, array, target):
    left, right = 0, len(array)-1

    while left<right-1:
      mid = (left+right)//2
      if array[mid]==target:
        return mid
      elif array[mid]<target:
        left = mid
      else:
        right = mid
    
    return left if (array[right]-target>target-array[left]) else right

在上面这种写法里,要先把数字自己放进去,left, number, right 三个数字这样的顺序出现在数组里,然后left、right依次左、右expand。 左边expand的条件是, - 首先左边还没过界并且result里的值还有的剩 - 其次满足接下来两个条件二选一 (1)右边到界了左边还没到 (2)左边的距离比右边的距离更小 相似的,右边expand的条件是, - 首先右边还没过界并且result里的值还有的剩 - 其次满足接下来两个条件二选一 (1)左边到界了右边还没到 (2)右边的距离比左边的距离更小

要特别注意两个点

1)先append 再移动 2)while循环里if和elif的判断的先后条件,因为很容易list index out of range

还可以这么写 看起来简单点

class Solution(object):
  def kClosest(self, array, target, k):
    """
    input: int[] array, int target, int k
    return: int[]
    """
    # write your solution here
    if not array or len(array)==0 or k<0:
      return -1
    
    index = self.binarySearch(array, target)
    l,r=index,index+1
    result=[]
    for i in range(0,k):
      if l>=0 and (r>len(array)-1 or array[r]-target>target-array[l]):
        result.append(array[l])
        l-=1
      else:
        result.append(array[r])
        r+=1
    return result

  def binarySearch(self, array, target):
    left, right = 0, len(array)-1

    while left<right-1:
      mid = (left+right)//2
      if array[mid]==target:
        return mid
      elif array[mid]<target:
        left = mid
      else:
        right = mid
    
    return left if (array[right]-target>target-array[left]) else right
int[] findKClosest(int[] array, int target, int K){
    
    int[] res = new int[K];
    int closestIdx = findClosest(array, int target);
    int l = closestIdx-1;
    int r = closestIdx+1;
    res[0] = array[closestIdx];
    
    for (i=0, i<K, i++){
        if (r>array.length || l>=0 && Math.abs()<Math.abs() ){  //l有可能一上来就是-1 如果一上来k的range已经有了confinement,就不会两边同时出界
        
        } 
        else{ // r < A.length && l < 0 || Math.abs()
        
        }
    

}

Smallest Element that is Larger than Target

input = ssss eeee bbbb (smaller, equal, bigger) 本质是在找bigger里面的第一个

case1: if input[m]<target('s') -> l=m or l=m+1 both ok case2: if input[m]==target('e') -> l=m or l=m+1 both ok case3: if input[m]>target('b') -> r=m 不可以-1

post-processing:先左后右

class Solution(object):
  def smallestElementLargerThanTarget(self, array, target):
    """
    input: int[] array, int target
    return: int
    """
    # write your solution here
    if not array or len(array)==0:
      return -1
    
    left, right = 0, len(array)-1
    
    while left<right-1:
      mid=(left+right)//2
      if array[mid]==target:
        left=mid #+1 OK
      elif array[mid]>target:
        right=mid #cannot -1
      else:
        left=mid #+1 OK
    
    if array[left]>target:
      return left
    elif array[right]>target:
      return right
    
    return -1

Sqrt()

找一个最接近于平方根的整数, floor

方法一:试

def sqrt(n):
    val = 1
    while val*val<=n
        val+=1
    return val-1

Time O( (n)\sqrt(n)(​n) )

Space O(1)

方法二:binary search

if mid*mid<n: go right [mid, right]

if mid*mid>n: go left [left, mid]

if mid*mid==n: return mid

class Solution(object):
  def sqrt(self, x):
    """
    input: int x
    return: int
    """
    # write your solution here
    if x<=1:
      return x

    left, right = 1, x//2
    while left<right-1:
      mid = (left+right)//2
      if mid*mid==x:
        return mid
      elif mid*mid>x:
        right=mid-1
      else:
        left=mid
    if right*right<=x:
      return right
    else:
      return left
class Solution(object):
  def sqrt(self, x):
    """
    input: int x
    return: int
    """
    # write your solution here
    if x<=1:
      return x
    left = 1
    right = x//2
    
    while True:
      mid = (left+right)//2
      if mid>x//mid:
        right=mid-1
      elif mid<=x//mid and mid+1>x//(mid+1):
        return mid
      else:
        left = mid+1

Find Peak Element

class Solution(object):
    def findPeak(self, array):
    """
    input: int[] array
    return: int
    """
        left, right = 0, len(array)-1
        while left<right-1:
            mid = (left+right)//2
            if array[mid]>array[mid-1] and array[mid]>array[mid+1]:
                return mid
            elif array[mid]<array[mid+1]:
                left=mid+1
            elif array[mid]>array[mid-1]:
                right=mid-1
        return left if array[left]>array[right] else right

Search In Shifted Sorted Array I

class Solution(object):
  def search(self, array, target):
    """
    input: int[] array, int target
    return: int
    """
    # write your solution here
    
    if not array or len(array)==0:
      return -1
    
    left, right = 0, len(array)-1

    while left<right-1:
      mid=(left+right)//2
      if array[mid]==target:
        return mid
      if array[left]<=array[mid]:
        if target<array[mid] and target>=array[left]:
          right=mid-1
        else:
          left=mid+1
      else:
        if target<=array[right] and target>array[mid]:
          left=mid+1
        else:
          right=mid-1
    
    if array[left]==target:
      return left
    elif array[right]==target:
      return right

    return -1

First Bug Version

Pull Request有很多个版本,如果有一个version有bug,在version7发现了,快速找到这个有bug的version的第一个version

Java那个版本的答案需要注意:因为一开始先找到n/2和n这个范围,如果bad version是第一个,那么在while除的时候有可能就直接让n=0了,这样left和right都是0,not valid. 所以要在while前面先判断n还没有到1

class Solution:
  def findFirstBadVersion(n): 
    # write your solution here
    left, right = 1, n
    while left<right-1:
      mid = (left+right)//2
      if isBadVersion(mid):
        right=mid
      else:
        left=mid+1
    return left if isBadVersion(left) else right
class Solution extends VersionControl {
  public int findFirstBadVersion(int n) {
    // write your solution here
    while ((n!=1) & (isBadVersion(n))){
      n/=2;
    }
    int left = n; 
    int right = n*2;

    while (left<right-1){
      int mid = (right+left)/2;
      if (isBadVersion(mid)){
        right=mid;
      }else{
        left=mid+1;
      }
    }
    return isBadVersion(left)? left:right;
  }
}

新题: 虚拟数组

给一个已排好序的正整数数组,在首尾之间,不连续的部分可以看成是漏掉了一些数。这些漏掉的数可以组成一个虚拟的数组,要求给出一个序号k,返回虚拟数组的第k个数。 比如给定原数组:[2,4,7,8,9,15],漏掉的数组成这样一个虚拟数组:[3,5,6,10,11,12,13,14]。若k=2,返回虚拟数组的第二个数“5”。

每次取数组中间位置mid的元素a[mid],跟数组最右边的元素a[right]比较,求出k=(a[right]-a[mid])-(right-mid) 这个k值就代表从mid到right之间有多少个hole。比较k和n的大小,如果k<n就说明第n个hole在数组左半边,那么让n=n-k然后继续搜索左半边;否则的话第n个hole在数组右半边,就继续搜索右半边。直到最后left+1==right,直接返回a[right]-n就是最终要求的值

def kth_missing_num(nums, k):
     
    missed = num_missing(nums)
    if missed < k: 
        raise ValueError("not that many missing numbers")
     
    start, end = 0, len(nums)-1
    while start + 1 != end:
        mid = (start+end)//2
        missed = num_missing(nums, start, mid)
        if missed >= k:
            end = mid
        else:
            start = mid 
            k = k - missed 
    return nums[start] + k
     
def num_missing(nums, start = 0, end = None):
    if end is None:
        end = len(nums) - 1
     
    return nums[end] - nums[start] - (end - start)
 
class TestMissingNumber(unittest.TestCase):
 
    def setUp(self):
        self.nums = [2,4,7,8,9,15]
        self.missings = [3,5,6,10,11,12,13,14]
    def tearDown(self):
        pass
    def testMissingNumber(self):
        for i, missed in enumerate(self.missings):
            self.assertEqual(kth_missing_num(self.nums, i+1), missed)
        with self.assertRaises(ValueError):
            kth_missing_num(self.nums, len(self.missings)+1)

高等难度

K-th smallest in Two Sorted Arrays

1.1: 两个sorted array的median 两个array凑在一起的

1.2: 两个sorted array的第k小或者前k小的元素 方法一:可以2-pointers的方法,谁小移谁,用O(k)的时间 方法二:Binary Search 谁小删除谁 每一次搜索范围都是当前的k/2个元素 O(logk)

Closest k Element

用上面的方法来接着做 1. Binary Search to find L and R log(n) 2. 此时有了两个array,left及left的左边都可以通过当前element和target的距离,这就是所谓的array A,同理,right及right的右边都是arrayB。就成了上面的这个题 log(k)就可以搞定

Search In Unknown Sized Sorted Array

  1. Find the end 倍增法

  2. Binary Search

class Solution(object):
  def search(self, dic, target):
    """
    input: Dictionary dic, int target
    return: int
    """
    # write your solution here
    start = 1
    while dic.get(start) and dic.get(start)<target:
      start*=2
  
    left, right = start//2, start
    while left<=right:
      mid = (left+right)//2
      if dic.get(mid) is None or dic.get(mid)>target:
        right = mid-1
      elif dic.get(mid)<target:
        left = mid+1
      else:
        return mid
    return -1

Time: O(log 2(first_bug_version))

实际工作中的binary search

任何object都可以被sorted,但是我们需要一个比较策略,比如口红可以用色号、RGB色度、16进制的数字、品牌的首字母、喜爱程度... 这些都是comparable

Generics: 范形 就像是外形看不出来色号的口红

面试时:

  1. Clarification: - sorted? ascending?descending? - how you define your colors

  2. Examples:过一个example

  3. Solutions: Assumptions - xx的时候返回xx (比如不存在的时候返回-1还是null) - 如果遇到multiple该return哪个?(都可以) Input、Output: - input:int array, int target - output:int index Corner Case: - null: 没有array - empty: 有array但没元素 Algorithm: - Binary Search, 时间空间复杂度 call stack+ new出来的

  4. Coding

  5. 回头验证space & time complexity

  6. Test Case

要讲清楚:

退出循环的时候l和r在哪里(classic里是错开,提前一步时是)

PreviousFundamental KnowledgeNextBasic Sorting

Last updated 5 years ago