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

billy_don · Apr 21, 2024

LmaoSuVuong said:
@billy_don bữa nay chưa thấy bác trả bài

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;
    }
}

LmaoSuVuong · Apr 21, 2024

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;
    }
}

mai nó nâng độ khó graph lên dijkstra union find khóc théc h

billy_don · Apr 21, 2024

LmaoSuVuong said:
mai nó nâng độ khó graph lên dijkstra union find khóc théc h

Tối nay fen nhanh trí kiếm bài hard làm trước, đi tắt đón đầu đi :byebye:

LmaoSuVuong · Apr 21, 2024

billy_don said:
Tối nay fen nhanh trí kiếm bài hard làm trước, đi tắt đón đầu đi

đang địa code solution xem người ta biểu diễn graph ntn để ăn cắp style

billy_don · Apr 21, 2024

LmaoSuVuong said:
đang địa code solution xem người ta biểu diễn graph ntn để ăn cắp style

Nếu vertices range từ 0... n - 1 thì lưu graph thành mảng 2 chiều là chuẩn rồi, nếu gặp graph có thêm weight thì thêm một cột nữa thôi. Còn gặp vertices lộn xộn thì tạo một cái hashmap hoặc tạo cmn luôn class vertex với edge

Ủa rồi code đâu :beat_brick:

LmaoSuVuong · Apr 21, 2024

billy_don said:
Nếu vertices range từ 0... n - 1 thì lưu graph thành mảng 2 chiều là chuẩn rồi, nếu gặp graph có thêm weight thì thêm một cột nữa thôi. Còn gặp vertices lộn xộn thì tạo một cái hashmap hoặc tạo cmn luôn class vertex với edge

Ủa rồi code đâu

nay code xấu quá nên giấu r

hôm nào code sạch biến đẹp thì đăng

cmajor · Apr 22, 2024

Lần đầu làm graph, học implement mất mớ thời gian

Python:

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if source == destination:
            return True
        source_graph = {}
        for e in edges:
            if source in e:
                source_graph[e[0]] = True
                source_graph[e[1]] = True
                break
        else:
            return False
        es = deque(edges)
        count = n
        while es:
            edge = es.pop()
            if  source_graph.get(edge[0], False) or source_graph.get(edge[1], False):
                source_graph[edge[0]] = True
                source_graph[edge[1]] = True
                if edge[0] == destination or edge[1] == destination:
                    return True
                count = len(es)
            else:
                es.appendleft(edge)
                count -= 1
            if count == 0:
                break
        return source_graph.get(destination, False)

freedom.9 · Apr 22, 2024

https://leetcode.com/problems/open-the-lock/submissions/1238648106/

nchhnchh · Apr 22, 2024

Python:

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        deadendsSet = set(deadends)

        visited = set(['0000'])
        q = ['0000']

        def turning(c):
            prev, next = '0', '0'
            if c == '0':
                prev = '9'
                next = '1'
            elif c == '9':
                prev = '8'
                next = '0'
            else:
                prev = str(int(c) - 1)
                next = str(int(c) + 1)

            return (prev, next)

        if q[0] in deadendsSet:
            return -1

        if q[0] == target:
            return 0
    
        result = 0
        while q:
            result += 1
            temp = []
            for current in q:
                for i, c in enumerate(current):
                    prev, next = turning(c)
                    prev_value = current[0:i] + prev + current[i+1:4]
                    next_value = current[0:i] + next + current[i+1:4]

                    if prev_value == target or next_value == target:
                        return result

                    if not prev_value in deadendsSet and not prev_value in visited:
                        visited.add(prev_value)
                        temp.append(prev_value)

                    if not next_value in deadendsSet and not next_value in visited:
                        visited.add(next_value)
                        temp.append(next_value)
            q = temp

        return -1

RTX3090 · Apr 22, 2024

C++:

    int openLock(vector<string>& deadends, string target) {

        auto nextSlot = [](char x) {return (x == '0') ? '9' : x - 1;};
        auto prevSlot = [](char x) {return (x == '9') ? '0' : x + 1;};

        unordered_set<string> visited(deadends.begin(), deadends.end());
        if (visited.count("0000")) return -1;
        visited.insert("0000");
        
        int turns = 0;
        queue<string> q;
        q.push("0000");

        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                string curr = q.front(); q.pop();
                
                if (curr == target) return turns;
    
                for (int j = 0; j < 4; j += 1) {
                    string next = curr;
                    next[j] = nextSlot(next[j]);
                    if (!visited.count(next)) {
                        q.push(next);
                        visited.insert(next);
                    }
                    next = curr;
                    next[j] = prevSlot(next[j]);
                    if (!visited.count(next)) {
                        q.push(next);
                        visited.insert(next);
                    }
                }
            }
            turns += 1;
        }
        return -1;
    }

anoldvozer1710.v2 · Apr 22, 2024

bài này là BFS kiểu mẫu này. Dùng DFS 99% là TLE :canny:

JavaScript:

function openLock(deadends: string[], target: string): number {
    const set = new Set(deadends);
    if (set.has('0000')) return -1;
    const go = (str: string) => {
        const res: string[] = [];

        for (let i = 0; i < str.length; i++) {
            res.push(str.slice(0, i) + ((+str[i] + 1) % 10).toString() + str.slice(i + 1));
            res.push(str.slice(0, i) + ((+str[i] + 9) % 10).toString() + str.slice(i + 1));
        }
        return res;
    }
    const q: string[] = ['0000'];
    for (let i = 0; q.length > 0; i++) {
        let size = q.length;
        while (size--) {
            const item = q.shift();
            if (item === target) return i;
            for (const adj of go(item)) {
                if (set.has(adj)) continue;
                set.add(adj);
                q.push(adj)
            }
        }
    }
    return -1;
};

togepy · Apr 22, 2024

Python:

from queue import Queue
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        queue = Queue()
        queue.put(("0000", 0))
        visited = {}
        visited["0000"] = True
        for deadend in deadends:
            if deadend == '0000':
                return -1
            visited[deadend] = True
        while not queue.empty():
            (cur, step) = queue.get()
            if cur == target:
                return step
            for i in range(0,4):
                num = int(cur[i])
                up = (num + 1) % 10
                down = (num - 1) % 10
                upStr = cur[0:i] + str(up) + cur[i+1:]
                if upStr not in visited:
                    visited[upStr] = True
                    queue.put((upStr, step + 1))
                downStr = cur[0:i] + str(down) + cur[i+1:]
                if downStr not in visited:
                    visited[downStr] = True
                    queue.put((downStr, step+1))
        return -1

LmaoSuVuong · Apr 22, 2024

anoldvozer1710.v2 said:

bài này là BFS kiểu mẫu này. Dùng DFS 99% là TLE :canny:

JavaScript:

function openLock(deadends: string[], target: string): number {
    const set = new Set(deadends);
    if (set.has('0000')) return -1;
    const go = (str: string) => {
        const res: string[] = [];

        for (let i = 0; i < str.length; i++) {
            res.push(str.slice(0, i) + ((+str[i] + 1) % 10).toString() + str.slice(i + 1));
            res.push(str.slice(0, i) + ((+str[i] + 9) % 10).toString() + str.slice(i + 1));
        }
        return res;
    }
    const q: string[] = ['0000'];
    for (let i = 0; q.length > 0; i++) {
        let size = q.length;
        while (size--) {
            const item = q.shift();
            if (item === target) return i;
            for (const adj of go(item)) {
                if (set.has(adj)) continue;
                set.add(adj);
                q.push(adj)
            }
        }
    }
    return -1;
};

sao bài này implement DFS dc nhỉ bác, theo lý thuyết thì DFS đâu giải dc bài tìm min

billy_don · Apr 22, 2024

Java:

class Solution {
    public int openLock(String[] deadends, String target) {
        Queue<String> q = new LinkedList<>();
        Set<String> set = new HashSet<>();
        Set<String> visited = new HashSet<>();
        int layers = 0;

        for (String seq: deadends) {
            set.add(seq);
        }

        q.offer("0000");

        while (!q.isEmpty()) {
            int counter = q.size();
            layers++;
            while (counter > 0) {
                String cur = q.poll();
                counter--;

                if (cur.equals(target)) return layers - 1;
                if (set.contains(cur) || visited.contains(cur)) continue;

                for (String adj: getAdjacents(cur)) {
                    q.offer(adj);
                }
                visited.add(cur);
            }
        }

        return -1;
    }

    private List<String> getAdjacents(String s) {
        List<String> ans = new ArrayList<>();

        for (int i = 0; i < s.length(); i++) {
            char curChar = s.charAt(i);
            char adjChar1;
            char adjChar2;

            if (curChar == '9') {
                adjChar1 = '8';
                adjChar2 = '0';
            } else if (curChar == '0') {
                adjChar1 = '1';
                adjChar2 = '9';
            } else {
                adjChar1 = (char) (curChar + 1);
                adjChar2 = (char) (curChar - 1);
            }

            ans.add(s.substring(0, i) + adjChar1 + s.substring(i + 1));
            ans.add(s.substring(0, i) + adjChar2 + s.substring(i + 1));
        }

        return ans;
    }
}

@LmaoSuVuong :byebye:

LmaoSuVuong · Apr 22, 2024

billy_don said:

Java:

class Solution {
    public int openLock(String[] deadends, String target) {
        Queue<String> q = new LinkedList<>();
        Set<String> set = new HashSet<>();
        Set<String> visited = new HashSet<>();
        int layers = 0;

        for (String seq: deadends) {
            set.add(seq);
        }

        q.offer("0000");

        while (!q.isEmpty()) {
            int counter = q.size();
            layers++;
            while (counter > 0) {
                String cur = q.poll();
                counter--;

                if (cur.equals(target)) return layers - 1;
                if (set.contains(cur) || visited.contains(cur)) continue;

                for (String adj: getAdjacents(cur)) {
                    q.offer(adj);
                }
                visited.add(cur);
            }
        }

        return -1;
    }

    private List<String> getAdjacents(String s) {
        List<String> ans = new ArrayList<>();

        for (int i = 0; i < s.length(); i++) {
            char curChar = s.charAt(i);
            char adjChar1;
            char adjChar2;

            if (curChar == '9') {
                adjChar1 = '8';
                adjChar2 = '0';
            } else if (curChar == '0') {
                adjChar1 = '1';
                adjChar2 = '9';
            } else {
                adjChar1 = (char) (curChar + 1);
                adjChar2 = (char) (curChar - 1);
            }

            ans.add(s.substring(0, i) + adjChar1 + s.substring(i + 1));
            ans.add(s.substring(0, i) + adjChar2 + s.substring(i + 1));
        }

        return ans;
    }
}

@LmaoSuVuong :byebye:

Java:

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> set = new HashSet<>(Arrays.asList(deadends));
        if (set.contains("0000")) {
            return -1;
        }
        Queue<Pair<String, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>("0000",0));
        Set<String> visited = new HashSet<>();
        while(!queue.isEmpty()){
            Pair<String, Integer> tryCode=queue.poll();
            int move = tryCode.getValue();
            String code =tryCode.getKey();
            if(code.equals(target)) return move;
            if(visited.contains(code))continue;
            visited.add(code);
            for(int i =0;i<4;i++){
                char digit= code.charAt(i);
                String scrollUp = code.substring(0,i) + (char)((digit-'0'+1)%10+'0') + code.substring(i+1);
                String scrollDown = code.substring(0,i) + (char)((digit-'0'-1+10)%10+'0') + code.substring(i+1);
                if(!set.contains(scrollUp)){
                    queue.add(new Pair<>(scrollUp,move+1));
                }
                if(!set.contains(scrollDown)){
                    queue.add(new Pair<>(scrollDown,move+1));
                }
            }
        }
        return -1;
    }
}

mặc dù biết giải nhưng có nghía vài solution xem ngta implement

Violet_7 · Apr 22, 2024

LmaoSuVuong said:

Java:

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> set = new HashSet<>(Arrays.asList(deadends));
        if (set.contains("0000")) {
            return -1;
        }
        Queue<Pair<String, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>("0000",0));
        Set<String> visited = new HashSet<>();
        while(!queue.isEmpty()){
            Pair<String, Integer> tryCode=queue.poll();
            int move = tryCode.getValue();
            String code =tryCode.getKey();
            if(code.equals(target)) return move;
            if(visited.contains(code))continue;
            visited.add(code);
            for(int i =0;i<4;i++){
                char digit= code.charAt(i);
                String scrollUp = code.substring(0,i) + (char)((digit-'0'+1)%10+'0') + code.substring(i+1);
                String scrollDown = code.substring(0,i) + (char)((digit-'0'-1+10)%10+'0') + code.substring(i+1);
                if(!set.contains(scrollUp)){
                    queue.add(new Pair<>(scrollUp,move+1));
                }
                if(!set.contains(scrollDown)){
                    queue.add(new Pair<>(scrollDown,move+1));
                }
            }
        }
        return -1;
    }
}

mặc dù biết giải nhưng có nghía vài solution xem ngta implement

Vl code java. Wall of text :sweat:

LmaoSuVuong · Apr 22, 2024

Violet_7 said:
Vl code java. Wall of text

ide nhắc code toàn tab ra chứ gõ cũng ít lắm bác

billy_don · Apr 22, 2024

LmaoSuVuong said:
ide nhắc code toàn tab ra chứ gõ cũng ít lắm bác

Luyện lc bằng ide khác j tập chạy bộ bằng xe máy :cautious:

LmaoSuVuong · Apr 22, 2024

billy_don said:
Luyện lc bằng ide khác j tập chạy bộ bằng xe máy

code sơ trên text, cảm thấy ko ổn thì dán vào ide debug, xong dán lại trả vào lc

bọn lc đâu có cho runcode liên tục

LmaoSuVuong · Apr 22, 2024

@billy_don union find cũm khá dễ hiểu

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;
        }
    }
}

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Similar threads

Share this page