Skip to content

Instantly share code, notes, and snippets.

Avatar

Ray liyunrui

View GitHub Profile
View LogisticRegression.py
class LogisticRegression:
def __init__(self, lr=0.001, n_iters= 1000):
self.lr = lr
self.n_iters = n_iters
self.weights = None
self.bias = None
def fit(self, X, y):
"""
X: input vector with shape of [B, D]
@liyunrui
liyunrui / 207. Course Schedule.py
Last active Jan 19, 2021
leetcode-directed graph
View 207. Course Schedule.py
class Solution:
"""
Thought Process:
The problem come down to find whether directed graphs is cyclic or not.
DFS:
step1:
step2:
do dfs on graph to ..
The difference between find cycle in undirected graph is we require 3 states of node instead of 2
0: not visited yet
View 305. Number of Islands II.py
class UnionFindSet(object):
def __init__(self):
"""
This is version, we don't know how many nodes we'll cope with in the begining.
So, we use dict to store _parents and _rank instead of array.
Also, we would know nb of connected components dynamically.
"""
self._parents = {}
self._ranks = {}
self.count = 0 # nb of connected components
View kmeans.py
def eucliean_distance(x1, x2):
return np.sqrt(np.sum((x1-x2)**2))
class Kmeans:
def __init__(self, K=3, max_iters=100):
"""It's an iterative unsupervised algorithm.
Basically, We'd like to cluster a dataset into k non-overlapping clusters such that total
within-cluster variance summed over all k cluster is as small as possible.
In the end, each sample in dataset will be assigned to the cluster with the nearest centroid.
"""
View 721. Accounts Merge.py
class UnionFindSet:
def __init__(self, n):
#Initially, all elements are single element subsets.
self._parents = [node for node in range(n)]
# it's like height of tree but it's not always equal to height because path compression technique.
self._ranks = [1 for i in range(n)]
def find(self, u):
"""
The find method with path compression, return root of node u.
View 684. Redundant Connection.py
class UnionFindSet:
def __init__(self, n):
#Initially, all elements are single element subsets.
self._parents = [node for node in range(n)]
# it's like height of tree but it's not always equal to height because path compression technique.
self._ranks = [1 for i in range(n)]
def find(self, u):
"""
The find method with path compression, return root of node u.
View 200. Number of Islands.py
class UnionFindSet:
def __init__(self, n):
self._parents = [node for node in range(n)]
self._ranks = [1 for _ in range(n)]
def find(self, u):
while u != self._parents[u]:
self._parents[u] = self._parents[self._parents[u]]
u = self._parents[u]
return u
View 277. Find the Celebrity.py
# The knows API is already defined for you.
# return a bool, whether a knows b
# def knows(a: int, b: int) -> bool:
class Solution:
"""
Problem Clarification:
Definition of celibrity:
everbody knows him but he does not know anybody
Thought Process:
View 323. Number of Connected Components in an Undirected Graph.py
class Solution:
"""
PC:
Can I assume that no duplicate edges will appear in edges
"""
def countComponents(self, n: int, edges: List[List[int]]) -> int:
"""
Given n nodes and edge list of undirected graph, to find number of connected components.
Note:
View 323. Number of Connected Components in an Undirected Graph.py
class UnionFindSet:
def __init__(self, n):
self._parents = [node for node in range(n)]
self._ranks = [1 for _ in range(n)]
def find(self, u):
while u != self._parents[u]:
self._parents[u] = self._parents[self._parents[u]]
u = self._parents[u]
return u
You can’t perform that action at this time.