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

LmaoSuVuong đã nói:

tụi ngoài contest cũng gà dp đây

Nhấp để mở rộng...

LmaoSuVuong đã nói:

tụi ngoài contest cũng gà dp đây

Nhấp để mở rộng...

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

cơm thêm Q3 Jun-23
hehe e tuần tiếp theo lại DP, bài này dễ mà rate thấp hơn cả Q4 ảo

https://leetcode.com/problems/maximize-total-cost-of-alternating-subarrays/

Spoiler: Python

Python:

class Solution:
    def maximumTotalCost(self, nums: List[int]) -> int:
        @cache
        def f(i, sign):
            if i >= len(nums):
                return 0
            r1 = sign * nums[i] + f(i+1, -sign)
            r2 = nums[i] + f(i+1, -1)
            return max(r1, r2)

        return f(0, 1)

Nhấp để mở rộng...

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

phải có tý kiến thức Number Theory Xem tệp đính kèm 2797139

Nhấp để mở rộng...

noobdev đã nói:

đặc quyền của Bảo Vệ đó bác ơi, cầm gậy đi gõ mấy cháu 2Q gang lỏ ko tượt cái lào

Nhấp để mở rộng...

Phó GOAT đã nói:

Spoiler: JAVA 25/11/2024 BFS

Java:

class Solution {
    class Moves {
        String s;
        int move = 0;
        public Moves(String s, int move) {
            this.s = s;
            this.move = move;
        }
    }

    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        String s = "";
        for (int[] row : board) {
            for (int cell : row) {
                s += cell;
            }
        }
        Set<String> visited = new HashSet<>();
        Map<Integer, int[]> map = new HashMap<>();
        Queue<Moves> queue = new ArrayDeque<>();
        map.put(0, new int[] {1, 3});
        map.put(1, new int[] {0, 2, 4});
        map.put(2, new int[] {1, 5});
        map.put(3, new int[] {0, 4});
        map.put(4, new int[] {1, 3, 5});
        map.put(5, new int[] {2, 4});
        queue.add(new Moves(s, 0));
        while (!queue.isEmpty()) {
            Moves curr = queue.poll();
            if (Objects.equals(curr.s, target)) return curr.move;
            int i = curr.s.indexOf("0");
            for (int j : map.get(i)) {
                String string = swap(curr.s, i, j);
                if (!visited.contains(string)) {
                    queue.offer(new Moves(string, curr.move + 1));
                    visited.add(string);
                }
            }
        }
        return -1;
    }

    private String swap(String s, int i, int j) {
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        for (char c : chars) {
            sb.append(c);
        }
        return sb.toString();
    }
}

Chán quá, có mỗi cái áo mà cày mãi ko thấy vạt

dm lạm phát, dm leetcode

Nhấp để mở rộng...

freedom.9 đã nói:

Đang canh mai sales mua cái premium chứ cày kiểu này mùa quýt ko đc cái mũ rồi
Có thằng đang khóc lóc mất 13k points vì dùng 2 accounts trong contest để tránh penalties cười vl. À mai fence vô contest rồi report tụi cheaters ấy tuần nào cũng đc 100 points đều đều rất thơm.

Nhấp để mở rộng...

freedom.9 đã nói:

DP chỉ có mấy cái templates thôi fen, nắm đc pattern thì dễ lắm cũng dễ nhìn ra bài nào xài đc DP dựa vô constrain.
Hard DP thường là những bài phải có traceback lại optimal path hoặc là Dp on Tree, hoặc optimize bằng mấy cái kĩ thuật như prefixsum hoặc bitmask dp. Còn mấy bài medium thì dễ ko làm vài chục bài là hiểu ngay

Nhấp để mở rộng...

nchhnchh đã nói:

hóng cao nhân phi đôm viết blog hay gist chia sẻ pattern DP nào

Nhấp để mở rộng...

freedom.9 đã nói:

Đang bận học Toefl quá mai fen, chờ lấy đc 90 rồi share ae cách học English + Algorithm theo topic luôn

via theNEXTvoz for iPhone

Nhấp để mở rộng...

LmaoSuVuong đã nói:

sống bên mẽo r vẫn phải cày thêm TA nữa hả bác phi đôm

Nhấp để mở rộng...

freedom.9 đã nói:

Học chứ, ko phải cứ qua đây là TA ngon đâu fen, còn gà lắm.
Mình cũng đang muốn đăng kí học Master chuyển qua AI lùa gà, học algorithm suốt cũng chán giờ duy trì thôi chứ ko tìm hiểu như mấy ông CP nữa.

Nhấp để mở rộng...

Konstante đã nói:

ChatGPT nó trả lời không hẳn sai nhưng tào lao, nhìn quả ví dụ mà ngán ngẩm "...9 far smaller than 6.", "...6 far smaller than 3.46" . Số ước số của n có thể tính bằng
Xem tệp đính kèm 2799402
tức là cỡ 0(n), đánh giá tốt hơn nữa thì có Xem tệp đính kèm 2799426(xem bài này của Terence Tao). Điều đặc biệt là giá trị tiệm cận của d(n) tuy nhỏ (nhỏ hơn lũy thừa của n với số mũ dương bất kỳ) nhưng lớn hơn log(n).

Nhấp để mở rộng...

Konstante đã nói:

ChatGPT nó trả lời không hẳn sai nhưng tào lao, nhìn quả ví dụ mà ngán ngẩm "...9 far smaller than 6.", "...6 far smaller than 3.46" . Số ước số của n có thể tính bằng
Xem tệp đính kèm 2799402
tức là cỡ 0(n), đánh giá tốt hơn nữa thì có Xem tệp đính kèm 2799426(xem bài này của Terence Tao). Điều đặc biệt là giá trị tiệm cận của d(n) tuy nhỏ (nhỏ hơn lũy thừa của n với số mũ dương bất kỳ) nhưng lớn hơn log(n).

Nhấp để mở rộng...

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

Spoiler: gục gã, copy sol

Python:

moves = ((1,3), (0,2,4), (1,5),
         (0,4), (1,3,5), (2,4))

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        state = (*board[0], *board[1])
        queue, seen, cnt = deque([state]), set(), 0

        while queue:
            for _ in range(len(queue)):
                state = list(queue.popleft())
                idx = state.index(0)
                if state == [1,2,3,4,5,0]: return cnt

                for i in moves[idx]:
                    curr = state[:]
                    curr[idx], curr[i] = curr[i], 0
                    curr = tuple(curr)
                    if curr in seen: continue
                    queue.append(curr)
                    seen.add(curr)
            cnt+= 1

        return -1

có một số vấn đề mn giải đáp giúp với, TC của BFS là O(V+E) nhưng đây (mn)! là mỗi V còn E sao edtor nó ko nói gì nhỉ.

của DFS cũng là O(V+E) tại sao trong editor lại là (mn)!*(mn)

Nhấp để mở rộng...

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

Spoiler: gục gã, copy sol

Python:

moves = ((1,3), (0,2,4), (1,5),
         (0,4), (1,3,5), (2,4))

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        state = (*board[0], *board[1])
        queue, seen, cnt = deque([state]), set(), 0

        while queue:
            for _ in range(len(queue)):
                state = list(queue.popleft())
                idx = state.index(0)
                if state == [1,2,3,4,5,0]: return cnt

                for i in moves[idx]:
                    curr = state[:]
                    curr[idx], curr[i] = curr[i], 0
                    curr = tuple(curr)
                    if curr in seen: continue
                    queue.append(curr)
                    seen.add(curr)
            cnt+= 1

        return -1

có một số vấn đề mn giải đáp giúp với, TC của BFS là O(V+E) nhưng đây (mn)! là mỗi V còn E sao edtor nó ko nói gì nhỉ.

của DFS cũng là O(V+E) tại sao trong editor lại là (mn)!*(mn)^2

Nhấp để mở rộng...

freedom.9 đã nói:

Vì với 6 thằng thì sẽ có at most 6! các vị trí, là permutation của nhau nên độ phức tạp là 6!.
Còn ở mỗi node thì bác sẽ visit at most 6 thằng trong cái queue để swap nữa nên là 6!*6

via theNEXTvoz for iPhone

Nhấp để mở rộng...

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

bỏ qua TC ở mỗi node thì, e thấy trong lý thuyết nó ghi BFS là O(V+E)
Xem tệp đính kèm 2799643
mà mỗi state sẽ có thể di chuyển đến tối đa 3 state khác, ví dụ state có index '0' là 1 thì sẽ có thể move đến (0,2,4)

vậy tức là mỗi node (state) sẽ có O(3) edges hay E = O(3V)

thì độ phức tạp của số lượng state phải là O(4V) = O(4 (m * n)!)

Đấy là BFS

còn ở BFS nó bảo là: O((m*n)! * (m*n)) thì chỗ này e ko hiểu cách chứng minh lắm

Nhấp để mở rộng...