thảo luận Leetcode mỗi ngày

Python: 
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def variations(lock):
            variations = []
            for i in range(0,4):
                variations.append(lock[:i] + ('0' if lock[i] == '9' else str(int(lock[i])+1))  + lock[i+1:])
                variations.append(lock[:i] + ('9' if lock[i] == '0' else str(int(lock[i])-1))  + lock[i+1:])
            return variations
           
        deadends = set(deadends)
        visited = set([])
        de = collections.deque([('0000', 0)])
        while de:
            lock = de.popleft()
            if lock[0] == target:
                return lock[1]
            if lock[0] in deadends or lock[0] in visited:
                continue
            varations = variations(lock[0])
            for variation in varations:
                if variation not in visited:
                    de.append((variation, lock[1]+1))
            visited.add(lock[0])
        return -1

lần đầu đăng bài, mới tập tành nên chỉ beat được 33% :(
 
JavaScript: 
function* nextOf(n) {
    for (const scale of [1, 10, 100, 1000]) {
        if (Math.trunc(n / scale) % 10 === 9) {
            yield n - scale * 9;
        } else {
            yield n + scale;
        }
        if (Math.trunc(n / scale) % 10 === 0) {
            yield n + scale * 9;
        } else {
            yield n - scale;
        }
    }
}
var openLock = function(deadends, target) {
    deadends = new Set(deadends.map(num => Number(num)));
    if (deadends.has(0)) {
        return -1;
    }
    const enqueued = new Set([0]);
    let q = [0];
    target = Number(target);
    let rounds = 0;
    while (q.length > 0) {
        const next = [];
        for (const n of q) {
            if (n === target) {
                return rounds;
            }
            for (const m of nextOf(n)) {
                if (!enqueued.has(m) && !deadends.has(m)) {
                    enqueued.add(m);
                    next.push(m);
                }
            }
        }
        q = next;
        rounds++;
    }
    return -1;
};
 
billy_don said:
Toàn bài easy post lên tốn tiền net :look_down:
Java: 
class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<Integer>[] graph = new List[n];

        for (int[] edge: edges) {
            if (graph[edge[0]] == null) graph[edge[0]] = new ArrayList<>();
            if (graph[edge[1]] == null) graph[edge[1]] = new ArrayList<>();

            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        boolean[] visited = new boolean[n];

        return dfs(source, visited, graph, destination);
    }

    private boolean dfs(int source, boolean[] visited, List<Integer>[] graph,int destination) {
        if (source == destination) {
            return true;
        }

        visited[source] = true;

        for (int next: graph[source]) {
            if (!visited[next]) {
                if (dfs(next, visited, graph, destination)) {
                    return true;
                }
            }
        }

        return false;
    }
}
Click to expand...
Dm chảnh thế, post code đẹp lên cho mng mở rộng tầm mắt chứ
 
Toàn xài dfs quen, qua bfs tốn time quá :burn_joss_stick:
Xài map hàng loạt nên beat 88% time, 95% space :D
Mấy lần dính edge case, thói quen ẩu k sửa được :beat_brick:
Python: 
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if "0000" in deadends:
            return -1
        if "0000" == target:
            return 0
        count = 0
        mapping = {
            "0" : ["9", "1"],
            "1" : ["0", "2"],
            "2" : ["1", "3"],
            "3" : ["2", "4"],
            "4" : ["3", "5"],
            "5" : ["4", "6"],
            "6" : ["5", "7"],
            "7" : ["6", "8"],
            "8" : ["7", "9"],
            "9" : ["8", "0"],
        }
        q = deque([["0000"]])
        self.visited = dict(zip(deadends, [1] * len(deadends)))
        def gen_codes(codes):
            res = {}
            for code in codes:
                for idx, char in enumerate(code):
                    for x in mapping[char]:
                        word = code[:idx] + x + code[idx+1:]
                        if self.visited.get(word, 0) == 0:
                            res[word] = 1
            return res
        while q:
            count += 1
            codes = q.popleft()
            for code in codes:
                if self.visited.get(code, 0) == 0:
                    self.visited[code] = 1
            new_codes = gen_codes(codes)
            if len(new_codes) == 0:
                return -1
            if new_codes.get(target, 0) != 0:
                return count
            q.append([x for x in new_codes.keys()])
 
LmaoSuVuong said:
@billy_don union find cũm khá dễ hiểu
s3QunT2.gif

Java: 
class Solution {
    int[] parent;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        parent=new int[n];
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
        for(int[] edge:edges){
            union(edge[0],edge[1]);
        }
        return findRoot(source) == findRoot(destination);
    }
    public int findRoot(int x){
        while(x!=parent[x]){
            x= parent[parent[x]];
        }
        return x;
    }
    public void union(int x,int y){
        int rootX= findRoot(x);
        int rootY= findRoot(y);
        if(rootX!= rootY){
            parent[rootY]= rootX;
        }
    }
}
Click to expand...
Chưa compress path kìa :D find tới đâu update parent lại tới đấy
 
Thấy có thằng cài đặt đẹp vãi nên post cho các bác tham khảo
Python: 
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        neighbors = collections.defaultdict(set)
        for v, w in edges:
            neighbors[v].add(w)
            neighbors[w].add(v)
        def maxpath(v, visited):
            visited.add(v)
            paths = [maxpath(w, visited) for w in neighbors[v] if w not in visited]
            path = max(paths or [[]], key=len)
            path.append(v)
            return path
        path = maxpath(0, set())
        path = maxpath(path[0], set())
        m = len(path)
        return path[(m-1)//2:m//2+1]
 
Python: 
from collections import defaultdict, deque
from typing import List

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]

        graph = defaultdict(set)
        for edge in edges:
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])

        queue = deque()
        for key, value in graph.items():
            if len(value) == 1:
                queue.append(key)

        while n > 2:
            size = len(queue)
            n -= size
            for _ in range(size):
                vertex = queue.popleft()
                neighbor = graph[vertex].pop()
                graph[neighbor].remove(vertex)
                if len(graph[neighbor]) == 1:
                    queue.append(neighbor)

        return list(queue)
 
Code xong submit thấy beat được mỗi 5%, mặt mình đần thối, ngồi đọc lại code một lúc mới hiểu tại sao :sad:
Python: 
import queue
class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        if n == 2:
            return [0, 1]
        edgeHash = {}
        for edge in edges:
            if edge[0] in edgeHash:
                edgeHash[edge[0]].add(edge[1])
            else:
                edgeHash[edge[0]] = {edge[1]}
            if edge[1] in edgeHash:
                edgeHash[edge[1]].add(edge[0])
            else:
                edgeHash[edge[1]] = {edge[0]}
        
        while len(edgeHash) != 0:
            leafs = []
            for key in edgeHash:
                if len(edgeHash[key]) <= 1:
                    leafs.append(key)
            for leaf in leafs:
                for neighbour in edgeHash[leaf]:
                    if neighbour in edgeHash:
                        edgeHash[neighbour].remove(leaf)
                del edgeHash[leaf]
            if len(edgeHash) == 0:
                return leafs
 
togepy said:
Code xong submit thấy beat được mỗi 5%, mặt mình đần thối, ngồi đọc lại code một lúc mới hiểu tại sao :sad:
Python: 
import queue
class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        if n == 2:
            return [0, 1]
        edgeHash = {}
        for edge in edges:
            if edge[0] in edgeHash:
                edgeHash[edge[0]].add(edge[1])
            else:
                edgeHash[edge[0]] = {edge[1]}
            if edge[1] in edgeHash:
                edgeHash[edge[1]].add(edge[0])
            else:
                edgeHash[edge[1]] = {edge[0]}
    
        while len(edgeHash) != 0:
            leafs = []
            for key in edgeHash:
                if len(edgeHash[key]) <= 1:
                    leafs.append(key)
            for leaf in leafs:
                for neighbour in edgeHash[leaf]:
                    if neighbour in edgeHash:
                        edgeHash[neighbour].remove(leaf)
                del edgeHash[leaf]
            if len(edgeHash) == 0:
                return leafs
Click to expand...
fen còn pass dc, vẫn còn đang kẹt đây
ChZIh4i.png

1713853353241.png

update: nhích lên dc 1 testcase
IJWw4zO.png

1713854520771.png
 
Last edited:
xóa leaf
Java: 
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        Set<Integer>[] neighbors = new HashSet[n];
        Set<Integer> ans = new HashSet();
        for (int i = 0; i < n; i++) {
            neighbors[i] = new HashSet();
            ans.add(i);
        }
        if (n <= 2) {
            return new ArrayList(ans);
        }
        int[] adjs = new int[n];
        for (int[] edge : edges) {
            neighbors[edge[0]].add(edge[1]);
            neighbors[edge[1]].add(edge[0]);
            adjs[edge[0]]++;
            adjs[edge[1]]++;
        }
        Queue<Integer> leaves = new LinkedList();
        for (int i = 0; i < n; i++) {
            if (adjs[i] == 1) {
                leaves.add(i);
                ans.remove(i);
            }
        }
        while (ans.size() > 2) {
            List<Integer> remove = new ArrayList();
            while (!leaves.isEmpty()) {
                remove.add(leaves.poll());
            }
            for (int leaf : remove) {
                for (int i : neighbors[leaf]) {
                    if (ans.contains(i)) {
                        adjs[i]--;
                        if (adjs[i] == 1) {
                            leaves.add(i);
                        }
                    }
                }
                ans.remove(leaf);
            }
          
        } 
        return new ArrayList(ans);
    }
}
 
Last edited:
RTX3090 said:
Thấy có thằng cài đặt đẹp vãi nên post cho các bác tham khảo
Python: 
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        neighbors = collections.defaultdict(set)
        for v, w in edges:
            neighbors[v].add(w)
            neighbors[w].add(v)
        def maxpath(v, visited):
            visited.add(v)
            paths = [maxpath(w, visited) for w in neighbors[v] if w not in visited]
            path = max(paths or [[]], key=len)
            path.append(v)
            return path
        path = maxpath(0, set())
        path = maxpath(path[0], set())
        m = len(path)
        return path[(m-1)//2:m//2+1]
Click to expand...
đọc code python khóc théc
JhHSQ2y.gif

java tuy wall of text nhưng mà kiên nhẫn đọc hết thì dễ hiểu.
mấy page đầu còn có bác Kanteam cố rút code ngắn nhất có thể nữa.
 
LmaoSuVuong said:
đọc code python khóc théc
JhHSQ2y.gif

java tuy wall of text nhưng mà kiên nhẫn đọc hết thì dễ hiểu.
mấy page đầu còn có bác Kanteam cố rút code ngắn nhất có thể nữa.
Click to expand...
Tôi thì thấy dễ hiểu mà. Java thì dài thật sự. Code python dễ nghiện cái trò comprehension lắm.
Ví dụ viết code đẹp của python
gist.github.com

[Beautiful Idiomatic Python] Transforming Code into Beautiful, Idiomatic Python #python

[Beautiful Idiomatic Python] Transforming Code into Beautiful, Idiomatic Python #python - beautiful_idiomatic_python.md
gist.github.com gist.github.com
 
dfs tới chết
dfs lần một để lấy một đầu của path dài nhất trong graph, dfs lần 2 lấy đầu còn lại, travel hết path lọc ra median của path là kết quả
1713894455571.png

Java: 
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer>[] g = new List[n];
        Set<Integer> leaves = new HashSet<>();
        Map<Integer, List<Integer>> layers = new HashMap<>();

        if (n == 2) return List.of(0, 1);
        if (n == 1) return List.of(0);

        for (int[] edge: edges) {
            if (g[edge[0]] == null) g[edge[0]] = new ArrayList<>();
            if (g[edge[1]] == null) g[edge[1]] = new ArrayList<>();

            g[edge[0]].add(edge[1]);
            g[edge[1]].add(edge[0]);
        }

        int source = findSource(g, 0, -1, new int[n]);
        int destination = findSource(g, source, -1, new int[n]);

        return findMedian(g, source, destination);
    }

    private int findSource(List<Integer>[] g, int v, int parent, int[] dist) {
        int farthestV = v;
        for (int adj: g[v]) {
            if (adj != parent) {
                dist[adj] = dist[v] + 1;
                int farthest = findSource(g, adj, v, dist);
                if (dist[farthest] > dist[farthestV]) {
                    farthestV = farthest;
                }
            }
        }

        return farthestV;
    }

    public List<Integer> findMedian(List<Integer>[] g, int source, int destination) {
        Stack<Integer> pathStack = new Stack<>();
        dfs(g, -1, pathStack, source, destination);
        System.out.println(Arrays.toString(pathStack.toArray()));
        
        int pathLength = pathStack.size();
        
        int medianIndex1 = pathLength / 2;
        int medianIndex2 = (pathLength - 1) / 2;
        
        List<Integer> medianPoints = new ArrayList<>();
        while (!pathStack.isEmpty()) {
            int vertex = pathStack.pop();
            if (pathLength % 2 == 0) {
                if (pathStack.size() == medianIndex1 || pathStack.size() == medianIndex2) {
                    medianPoints.add(vertex);
                }
            } else {
                if (pathStack.size() == medianIndex1) {
                    medianPoints.add(vertex);
                }
            }
        }
        
        return medianPoints;
    }

    private void dfs(List<Integer>[] g, int parent, Stack<Integer> pathStack, int current, int destination) {
        pathStack.push(current);

        if (current == destination) {
            return;
        }

        for (int neighbor : g[current]) {
            if (neighbor != parent) {
                dfs(g, current, pathStack, neighbor, destination);
                if (!pathStack.isEmpty() && pathStack.peek() == destination) {
                    return;
                }
            }
        }

        pathStack.pop();
    }
}
 
Python: 
class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0

        if n == 1 or n == 2:
            return 1

        t0 = 0
        t1 = 1
        t2 = 1
        ans = 0
        for i in range(3, n + 1):
            ans = t0 + t1 + t2
            t0 = t1
            t1 = t2
            t2 = ans

        return ans
 

Similar threads

Masterchiefs
8 tờ báo Mỹ kiện OpenAI và Microsoft
Replies
9
Views
629
porpro84
porpro84
T
kiến thức Kèo play to earn miễn phí - Delabs Game
Replies
4
Views
80
Tranviethai98
T
T
kiến thức Kèo play to earn miễn phí - Delabs Games
Replies
4
Views
149
Tranviethai98
T
elementary
Ta thay đổi trước khi Google thay đổi
2 3
Replies
58
Views
4K
ProfessorX
ProfessorX
Masterchiefs
Núi lửa ở Nam Cực phun vàng thật mỗi ngày
2
Replies
24
Views
3K
xuccam2
xuccam2

Share this page

Back
Top