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

noobdev · 26/11/24

Xem tệp đính kèm 2801269

Đề bài bảo ko circle, troll quá

Python:

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)

        def bfs(node):
            cnt = 0
            q = deque([node])
            visited = {node}
           
            while q:
                curr = q.popleft()
                cnt += 1

                for nei in graph[curr]:
                    if nei not in visited:
                        q.append(nei)
                        visited.add(nei)

            return cnt == n
       
        champs = [i for i in range(n) if bfs(i)]
       
        return champs[0] if len(champs) == 1 else -1

DAG ko có circle, đây là nhiều hơn 1 champions nên trả về -1 thôi. Bác đọc kỹ đề đi.

LmaoSuVuong · 26/11/24

Tinh Hoa Đông Lào đã nói:

Xem tệp đính kèm 2801269

Đề bài bảo ko circle, troll quá

Python:

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)

        def bfs(node):
            cnt = 0
            q = deque([node])
            visited = {node}
           
            while q:
                curr = q.popleft()
                cnt += 1

                for nei in graph[curr]:
                    if nei not in visited:
                        q.append(nei)
                        visited.add(nei)

            return cnt == n
       
        champs = [i for i in range(n) if bfs(i)]
       
        return champs[0] if len(champs) == 1 else -1

bác lày cày bài khó nhiều quá tẩu hỏa r

freedom.9 · 26/11/24

noobdev đã nói:
Cơm thêm mời anh em:

https://leetcode.com/problems/remove-duplicate-letters/
Bài này làm lại đến 2 lần rồi mà vẫn ngọng ko nhớ được, mono stack khó quá

Bài này giải O(26) n chắc dễ hơn
Ở mỗi i thì nếu như có thằng character nào < i ở vị trí tiếp theo và còn 1 thằng i nào sau đó thì remove thằng i đó, còn lại thì giữ thằng i.
Dùng 1 deque để lưu vị trí của mỗi character, loop từ đầu tới cuối là xong, xử lí tới thằng i nào thì pop cái i ra khỏi deque, chứ mình ko nhìn ra cái stack solution luôn đó
via theNEXTvoz for iPhone

noobdev · 26/11/24

freedom.9 đã nói:
Bài này giải O(26) n chắc dễ hơn
Ở mỗi i thì nếu như có thằng character nào < i ở vị trí tiếp theo và còn 1 thằng i nào sau đó thì remove thằng i đó, còn lại thì giữ thằng i.
Dùng 1 deque để lưu vị trí của mỗi character, loop từ đầu tới cuối là xong, xử lí tới thằng i nào thì pop cái i ra khỏi deque, chứ mình ko nhìn ra cái stack solution luôn đó
via theNEXTvoz for iPhone

Queue + map là O26N là chuẩn rồi bác, nhưng optimal là dùng stack, khó lòi kèn, =((

freedom.9 · 26/11/24

noobdev đã nói:
Queue + map là O26N là chuẩn rồi bác, nhưng optimal là dùng stack, khó lòi kèn,

Thì ko nhìn ra stack thì phải giải bằng deque thôi chứ sao giờ, linh hoạt lên tí

Cái solution stack nó kiểu tư duy ngược nên khó nghĩ ra hơn, còn kiểu tư duy xuôi thì nó dễ làm hơn kiểu như topdown hay bottom up dp vậy
via theNEXTvoz for iPhone

Tinh Hoa Đông Lào · 26/11/24

noobdev đã nói:
Cơm thêm mời anh em:

https://leetcode.com/problems/remove-duplicate-letters/
Bài này làm lại đến 2 lần rồi mà vẫn ngọng ko nhớ được, mono stack khó quá

sao lại nói topic mono stack ra

), để thử làm mono stack

LmaoSuVuong · 26/11/24

noobdev đã nói:
Cơm thêm mời anh em:

https://leetcode.com/problems/remove-duplicate-letters/
Bài này làm lại đến 2 lần rồi mà vẫn ngọng ko nhớ được, mono stack khó quá

cơm thêm thì đừng hint nhé bác

Tinh Hoa Đông Lào · 26/11/24

noobdev đã nói:
DAG ko có circle, đây là nhiều hơn 1 champions nên trả về -1 thôi. Bác đọc kỹ đề đi.

à đúng rùi, e nhầm bác

LmaoSuVuong đã nói:
bác lày cày bài khó nhiều quá tẩu hỏa r

nhìn giới hạn thấy dùng bfs được thì dùng thui bác, bfs là brufoce như for loop của array thì nghĩ ra đầu tiên trong đầu rồi
tăng giới hạn lên 10^5 chắc e cũng ko nghĩ ra được, đã biết gì về indeg đâu :sweat:

mà toàn làm bài easy với medium mà chứ có làm hard bao giờ đâu mà bác bảo làm bài khó, bài hard auto bỏ qua, đang luyện medium thành thạo theo lời bác freedom

noobdev · 26/11/24

LmaoSuVuong đã nói:
cơm thêm thì đừng hint nhé bác

ok pác

LmaoSuVuong · 26/11/24

Tinh Hoa Đông Lào đã nói:
à đúng rùi, e nhầm bác

nhìn giới hạn thấy dùng bfs được thì dùng thui bác, bfs là brufoce như for loop của array thì nghĩ ra đầu tiên trong đầu rồi
tăng giới hạn lên 10^5 chắc e cũng ko nghĩ ra được, đã biết gì về indeg đâu

mà toàn làm bài easy với medium mà chứ có làm hard bao giờ đâu mà bác bảo làm bài khó, bài hard auto bỏ qua, đang luyện medium thành thạo theo lời bác freedom

hôm này giải dc nên e gáy tí thôi mong bác đừng để bụng

hôm nào ngọng là im thin thít ý mà

Tinh Hoa Đông Lào · 26/11/24

chiyeuemthoi đã nói:

Mã:

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        mp = {}
        for x , y in edges:
            mp[y] = x
        champion = -1
        cnt = 0
        for i in range(n):
            if i not in mp:
                champion = i
                cnt += 1
        return champion if cnt == 1 else -1

Làm lại Daily vậy :cry:

Python:

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        return s.pop() if len(s := set(range(n)) - {w for _, w in edges}) == 1 else -1

Bo_MinhAnh · 26/11/24

LC 2924 Java

Java:

class Solution {
  public int findChampion(int n, int[][] e) {
    return n == 1 ? 0 : Arrays.stream(e).map(s -> s[1]).collect(Collectors.toSet()).size() == n - 1 ? Arrays.stream(e)
    .filter(s -> !Arrays.stream(e).anyMatch(w -> w[1] == s[0])).findFirst().orElse(new int[] { -1 })[0] : -1;
  }
}

emyeumeonhatF17 · 26/11/24

Swift:

class Solution {
    func findChampion(_ n: Int, _ edges: [[Int]]) -> Int {
        var degree = Array(repeating: 0, count: n)
        for edge in edges {
            degree[edge[1]] += 1
        }
        var champion = -1
        for (team, count) in degree.enumerated() {
            if count == 0 {
                if champion == -1 {
                    champion = team
                } else {
                    return -1
                    break
                }
            }
        }
        return champion
    }
}

Tinh Hoa Đông Lào · 26/11/24

freedom.9 đã nói:
Bài này giải O(26) n chắc dễ hơn
Ở mỗi i thì nếu như có thằng character nào < i ở vị trí tiếp theo và còn 1 thằng i nào sau đó thì remove thằng i đó, còn lại thì giữ thằng i.
Dùng 1 deque để lưu vị trí của mỗi character, loop từ đầu tới cuối là xong, xử lí tới thằng i nào thì pop cái i ra khỏi deque, chứ mình ko nhìn ra cái stack solution luôn đó
via theNEXTvoz for iPhone

e cũng nghĩ như vậy mà nó sai bác ạ, cdcb, không được xoá 'c' dù phía trước có 'b' bé hơn và vẫn còn 1 'c' nữa nhưng thằng 'd' nó ngáng đường :sweat:

Tinh Hoa Đông Lào · 26/11/24

noobdev đã nói:
Cơm thêm mời anh em:

https://leetcode.com/problems/remove-duplicate-letters/
Bài này làm lại đến 2 lần rồi mà vẫn ngọng ko nhớ được, mono stack khó quá

e cũng pó tay bác, phải xem giải :sweat:

Độ khó 2184 là hard rồi, trình guardian mới ăn đc :go:

EzLink · 26/11/24

Tinh Hoa Đông Lào đã nói:
e cũng pó tay bác, phải xem giải
Xem tệp đính kèm 2801541

Độ khó 2184 là hard rồi, trình guardian mới ăn đc

làm thế nào để hiển thị cái 2184 đó thế bác

LmaoSuVuong · 26/11/24

EzLink đã nói:
làm thế nào để hiển thị cái 2184 đó thế bác

cài extension lc rating ..., mà e khuyên ko nên cài bác ạ, cài xong nó như 1 cái hint v. ko tốt cho suy nghĩ. làm blindbox cho quen

bài nào muốn xem độ khó thì cop tên bài bỏ vào trang CLIST

space dust · 26/11/24

Java:

class Solution {
    public int findChampion(int n, int[][] edges) {
        int[] indegree = new int[n];

        for(int[] edge: edges) {
            int a = edge[0];
            int b = edge[1];
            
            indegree[b] = 1;
        }

        List<Integer> res = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            if(indegree[i] == 0) {
                res.add(i);
            }
        }

        return res.size() == 1 ? res.get(0) : -1;
    }
}

Tinh Hoa Đông Lào · 26/11/24

LmaoSuVuong đã nói:
cài extension lc rating ..., mà e khuyên ko nên cài bác ạ, cài xong nó như 1 cái hint v. ko tốt cho suy nghĩ. làm blindbox cho quen

bài nào muốn xem độ khó thì cop tên bài bỏ vào trang CLIST

sao lại là hint được fen

)), độ khó cao quá còn biết đường mà từ bỏ sớm chứ :big_smile:

vào contest, mức độ xếp Q2 rồi đến Q3 cũng là hint thôi, Q2 dễ hơn Q3, cả 2 cùng mid, cứ thế tự dánh giá được Q2~1k5, Q3 ~ 1k7

LmaoSuVuong · 26/11/24

Tinh Hoa Đông Lào đã nói:
sao lại là hint được fen )), độ khó cao quá còn biết đường mà từ bỏ sớm chứ

vào contest, mức độ xếp Q2 rồi đến Q3 cũng là hint thôi, Q2 dễ hơn Q3, cả 2 cùng mid, cứ thế tự dánh giá được Q2~1k5, Q3 ~ 1k7

cái đợt e cài vào thấy cảm giác dễ bỏ cuộc hơn hẳn. hở tí là bỏ đọc sol, ko ổn 1 chút nào hết

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

Member

Senior Member

Senior Member

Member

Senior Member

Junior Member

Senior Member

Junior Member

Member

Senior Member

Junior Member

Member

Member

Junior Member

Junior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này