from graphlib import TopologicalSorter, CycleError
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
ts = TopologicalSorter()
for pre in prerequisites:
ts.add(pre[0], pre[1])
try:
tuple(ts.static_order())
except CycleError:
return False
return True
function canFinish(n: number, p: number[][]): boolean {
const graph: number[][] = new Array(n).fill(0).map(e => e = []);
const unvisited = 0, beingVisited = -1, hasBeenVisited = 1
const visited = new Array(n).fill(unvisited);
for (const [x, y] of p) {
graph[x].push(y)
}
const go = (i: number) => {
if (visited[i] === beingVisited) return false;
if (visited[i] === hasBeenVisited) return true;
visited[i] = beingVisited;
for (const j of graph[i]) {
if (!go(j)) return false;
}
visited[i] = hasBeenVisited;
return true;
}
for (let i = 0; i < n; i++) {
if (!go(i)) return false;
}
return true;
};
VL Python nó còn implement sẵn mấy cái này nữa hả fence
Cái topo sort là 1 trong những vấn đề cơ bản của graph mà.VL Python nó còn implement sẵn mấy cái này nữa hả fence
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
child = defaultdict(list)
d = defaultdict(int)
for u, v in prerequisites:
child[u].append(v)
d[v] += 1
d[u] += 0
q = deque([u for u, du in d.items() if du == 0])
while q:
u = q.popleft()
for v in child[u]:
d[v] -= 1
if d[v] == 0:
q.append(v)
del d[v]
return sum(d.values()) == 0
toi mới tự implement lại, fack meVL Python nó còn implement sẵn mấy cái này nữa hả fence
use std::collections::VecDeque;
impl Solution {
pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
let num_courses = num_courses as usize;
let mut adj = vec![Vec::new(); num_courses];
let mut indegress = vec![0; num_courses];
prerequisites.iter().for_each(|e| {
adj[e[0] as usize].push(e[1] as usize);
indegress[e[1] as usize] += 1;
});
let mut zeros = VecDeque::from(
indegress
.iter()
.enumerate()
.filter_map(|(i, &val)| if val == 0 { Some(i) } else { None })
.collect::<Vec<_>>(),
);
let mut count = 0;
while let Some(e) = zeros.pop_front() {
adj[e].iter().for_each(|&v| {
indegress[v] -= 1;
if indegress[v] == 0 {
zeros.push_back(v);
}
});
count += 1;
}
count == num_courses
}
}
enum class Color{white, gray, black};
struct State
{
State() = default;
int pre_count{};
Color color{Color::white};
};
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
std::vector<std::vector<int>> adj_map(numCourses);
std::vector<State> c_state(numCourses);
for (const auto& ls : prerequisites)
{
adj_map[ls[1]].emplace_back(ls[0]);
c_state[ls[0]].pre_count += 1;
}
for (int i = 0; i < numCourses; ++i)
{
if (c_state[i].pre_count == 0 && c_state[i].color == Color::white)
{
dfs_visit(adj_map, c_state, i);
}
}
if(m_order.size() == numCourses)
return true;
return false;
}
private:
std::vector<int> m_order;
void dfs_visit(const std::vector<std::vector<int>>& adj_map, std::vector<State>& c_state, int course)
{
if (c_state[course].pre_count > 0)
return;
c_state[course].color = Color::gray;
m_order.emplace_back(course);
for (int next_course : adj_map[course])
{
c_state[next_course].pre_count -= 1;
if (c_state[next_course].pre_count == 0)
{
dfs_visit(adj_map, c_state, next_course);
}
}
c_state[course].color = Color::black;
}
};
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
for course_a, course_b in prerequisites:
graph[course_a].append(course_b)
NOT_TAKE = 0
IN_PROGRESS = 1
IS_TAKEN = 2
status = [NOT_TAKE for course in range(numCourses)]
def take_course(start_course):
nonlocal status
if status[start_course] == IN_PROGRESS:
return False
if status[start_course] == IS_TAKEN:
return True
status[start_course] = IN_PROGRESS
for prerequisite_coures in graph[start_course]:
if not take_course(prerequisite_coures):
return False
status[start_course] = IS_TAKEN
return True
for course in range(numCourses):
if not take_course(course):
return False
return True
var canFinish = function(numCourses, prerequisites) {
const VISITED = 1;
const HOT = 2;
const states = {};
const deps = {};
const dfs = node => {
if (states[node] === HOT) {
return false;
}
if (states[node] === VISITED) {
return true;
}
states[node] = HOT;
if (Array.isArray(deps[node])) {
for (let d of deps[node]) {
if (!dfs(d)) {
return false;
}
}
}
states[node] = VISITED;
return true;
};
for (let [a, b] of prerequisites) {
deps[a] ||= [];
deps[a].push(b);
}
for (let i = 0; i < numCourses; i++) {
if (!states[i] && !dfs(i)) {
return false;
}
}
return true;
};
cày bao lâu được 6k point vậy thímĐủ point redeem áo Leetcode rồi, mừng quá
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
degree = [0] * numCourses
adj = defaultdict(list)
for e in prerequisites:
u, v = e[0], e[1]
degree[u] += 1
adj[v].append(u)
q = []
for u in range(numCourses):
if degree[u] == 0:
q.append(u)
n = 0
while len(q):
u = q.pop(0)
n += 1
for v in adj[u]:
degree[v] -= 1
if degree[v] == 0:
q.append(v)
return n == numCourses
function longestSubsequence(arr: number[], d: number): number {
const dp = new Map();
let res = 1;
for (const k of arr) {
const prev = dp.get(k - d) ?? 0;
dp.set(k, prev + 1);
res = Math.max(res, dp.get(k))
}
return res;
};
class Solution {
public:
const int MX = 1e4;
int longestSubsequence(vector<int>& arr, int dif) {
int n = arr.size(), ans = 1;
map<int,int> dp;
for (int i = 0; i < n; i++){
int x = arr[i] + MX; // make sure every number non negative
if (x - dif < 0 || x - dif >= 2 * MX + 1){
// out of constraint
dp[x] = 1; // subsequence contain only 1 element
}
dp[x] = dp[x - dif] + 1; // update max length
ans = max(ans,dp[x]);
}
return ans;
}
};
public class Solution {
public int LongestSubsequence(int[] arr, int difference) {
var dictionary = new Dictionary<int, int>();
var answer = 0;
for(int i = 0; i< arr.Length; i ++)
{
if(!dictionary.ContainsKey(arr[i] - difference))
dictionary[arr[i]] = 1;
else
dictionary[arr[i]] = dictionary[arr[i] - difference] + 1;
answer = Math.Max(answer, dictionary[arr[i]]);
}
return answer;
}
}
var longestSubsequence = function(arr, difference) {
const n = arr.length;
const dp = {}
let res = -Infinity
for(let i = 0; i < n; i++) {
if(!dp[arr[i]]) dp[arr[i]] = difference === 0 ? 0 : 1
dp[arr[i]] = Math.max(dp[arr[i]], (dp[String(arr[i] - difference)] || 0) + 1)
res = Math.max(res, dp[arr[i]])
}
return res
};Cũng ko để ý thím ơi, thím chăm cày contest đc top thì có nhiều point. Mình rảnh thì làm daily ko à
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
for (int& i : arr)
{
i += 10000;
}
int sz = arr.size();
std::vector<int> mark(20001, 0);
for (int i : arr)
{
int expect{i - difference};
if (mark[i] == 0 && expect != i)
{
mark[i] = 1;
}
if (expect < 0 || expect > 20000)
continue;
mark[i] = std::max(mark[expect] + 1, mark[i]);
}
int result{};
for (int i : mark)
{
result = std::max(result, i);
}
return result;
}
};class Solution:
def longestSubsequence(self, arr: List[int], difference: int) -> int:
d = defaultdict(int)
for num in arr:
d[num] = d[num-difference] + 1
return max(d.values())
