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
  1. Chapter3 Algorithm

Graph Search BFS 2

最短路径

找最短路径时,如果edge weight都是1,那么用BFS1就可以;如果edge weight不是1,用BFS2. Best First Search, Dijkstra's Algorithm。Dijkstra's Algorithm 找最短距离的限制条件是边的权重必须是正数。它不是点到一个点的算法,而是从出发点到所有点的最短路径的算法,而“两点间的距离”只是其中一个子产品。

和BFS1的区别是,BFS1把neighbor放在了FIFO的queue,而BFS2把每个点的最短距离放在了priority queue (min heap)。

generate的顺序不需要规定,expand才会控制min path

lazy deletion 如果删除或修改比较难,那么暂时先不改,先把新的照样放,直到不得不删除时删除。所以在generate一样的数时,完全可以把新的直接加进去,不管旧的。

  1. 一个Node只被expand一次

  2. 一个可以被generated多次 每次generate的路径递减

  3. 所有expand的node都是单调non-decreasing

  4. 棋盘格的 O(4logn*n) = nlogn 一般的O(ElogV)

  5. Termination Condition 可以是

    • 它要求的截止(when a conflict is found)

    • 找到了要求的node (target node is expanded, or kth element s expanded)

    • queue空了

kth smallest in 2D matrix

initial state: 从最小值开始,(0,0) expansion/generation rule: - expand input[i][j] generate比它大的最小 pop -- generate input[i][j+1] insert -- generate input[j+1][i] termination condition: - when the k-th element is expanded deduplication: - only generate each element once, can use a boolean array visited[][]; Extra Space O(n^2) - or use a Hash Table; Extra Space O(k)

Time: while loop k 轮,每轮净增1个(因为是出一个进两个),所以logk (heap operation, pop )

PreviousGraph Search BFSNextGraph Search DFS2

Last updated 5 years ago