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

  • Người tạo chủ đề Người tạo chủ đề _Gia_Cat_Luong_
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
LmaoSuVuong đã nói:
4V, 4 là hằng số thì coi như skip mà (nâng m, n lên 10 thì dir nó vẫn chỉ là 4 hướng), TC ước lượng theo cái biến thiên thôi bác, còn DFS nó phải chạy hết theo 2 cái input biến thiên thì độ phức tạp bắt buộc phải ghi vào
Nhấp để mở rộng...
Đang nghi editor sai:
1732528935924.png

1732528952537.png
 
LmaoSuVuong đã nói:
4V, 4 là hằng số thì coi như skip mà (nâng m, n lên 10 thì dir nó vẫn chỉ là 4 hướng), TC ước lượng theo cái biến thiên thôi bác, còn DFS nó phải chạy hết theo 2 cái input biến thiên thì độ phức tạp bắt buộc phải ghi vào
Nhấp để mở rộng...
1732529073622.png


ví dụ SSP từ (1)->(3) đáp án sẽ ra 1,

nếu dùng DFS thì phải dùng 1 cái dict[node] = [min of all moves to this node]

DFS nó sẽ đâm từ 1-2-4-5-3 với 4 đơn vị, xong quay lại 1 rồi đi vào 3 lần nữa để update 4 thành 1.

vì mỗi node có không có quá 4 bậc, thì là O(E*V) = O(4V*V) = O(4V^2) = O(V^2) = O(((m*n)!)^2)

:after_boom:
DFS tìm được shorted path nhưng mà phải check lại thêm lần nữa nên O(V*E) (cái này ko biết ChatGPT có đúng ko), còn BFS có mỗi O(V+E)
 
Tinh Hoa Đông Lào đã nói:
Xem tệp đính kèm 2800136

ví dụ SSP từ (1)->(3) đáp án sẽ ra 1,

nếu dùng DFS thì phải dùng 1 cái dict[node] = [min of all moves to this node]

DFS nó sẽ đâm từ 1-2-4-5-3 với 4 đơn vị, xong quay lại 1 rồi đi vào 3 lần nữa để update 4 thành 1.

vì mỗi node có không có quá 4 bậc, thì là O(E*V) = O(4V*V) = O(4V^2) = O(V^2) = O(((m*n)!)^2)

:after_boom:
DFS tìm được shorted path nhưng mà phải check lại thêm lần nữa nên O(V*E) (cái này ko biết ChatGPT có đúng ko), còn BFS có mỗi O(V+E)
Nhấp để mở rộng...
e chưa đọc lời giải dfs nữa nãy tưởng bác thắc mắc chỗ BFS thôi
lhJL9aw.png
 
C++: 
class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        unordered_set<int> visited;
        priority_queue<tuple<int, int, int>> maxHeap; // {-moves, board, idx}
        int idx = 0, value = 0; 
        for (int i = 5; i >= 0; --i) {
            if (board[i / 3][i % 3] == 0) idx = i;
            value = 10 * value + board[i / 3][i % 3];
        }
        visited.insert(value);
        maxHeap.emplace(0, value, idx);
        vector<vector<int>> direction = {
            {1, 3},
            {0, 2, 4},
            {1, 5},
            {0, 4},
            {1, 3, 5},
            {2, 4},
        };
        while (maxHeap.size()) {
            auto [moves, current, idx] = maxHeap.top();
            maxHeap.pop();
            if (current == 54321) return -moves;
            int p10idx = pow(10, idx);
            for (auto nidx : direction[idx]) {
                int p10nidx = pow(10, nidx);
                int v = (current / p10nidx) % 10;
                int next = current + v * (p10idx - p10nidx);
                if (visited.count(next)) continue;
                visited.insert(next);
                maxHeap.emplace(moves - 1, next, nidx);
            }
        }
        return -1;
    }
};
 
C++: 
class Solution {
public:
    int encode(vector<vector<int>> a) {
        int hashVal=0;
        for (int i=0; i<2; i++) {
            for (int j=0; j<3; j++) {
                hashVal=hashVal*10+a[i][j];
            }
        }
        return hashVal;
    }
    int getDigit(int n, int d) {
        int temp=floor(n/pow(10, d));
        return temp%10;
    }
    vector<vector<int>> decode(int val) {
        vector<vector<int>> res(2, vector<int> (3, 0));
        for (int i=0; i<2; i++) {
            for (int j=0; j<3; j++) {
                res[i][j]= getDigit(val, 6-(i*3+j)-1);
            }
        }
        return res;
    }
    int slidingPuzzle(vector<vector<int>>& a) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        int lastState=123450;
        map<int, int> dist;
        queue<int> q;
        q.push(encode(a));
        vector<vector<int>> curState;
        dist[q.front()]=0;
        while (!q.empty()) {
            int cur=q.front();
            q.pop();
            curState=decode(cur);
            int i,j;
            for (int ii=0; ii<2; ii++) {
                for (int jj=0; jj<3; jj++) {
                    if (curState[ii][jj]==0) {
                        i=ii;
                        j=jj;
                        break;
                    }
                }
            }
            if (i>0) {
                swap(curState[i][j], curState[i-1][j]);
                int tempNextState= encode(curState);
                if (dist.find(tempNextState)==dist.end()) {
                    q.push(tempNextState);
                    dist[tempNextState]=dist[cur]+1;
                }
                swap(curState[i][j], curState[i-1][j]);
            }
            if (j>0) {
                swap(curState[i][j], curState[i][j-1]);
                int tempNextState= encode(curState);
                if (dist.find(tempNextState)==dist.end()) {
                    q.push(tempNextState);
                    dist[tempNextState]=dist[cur]+1;
                }
                swap(curState[i][j], curState[i][j-1]);
            }
            if (i<1) {
                swap(curState[i][j], curState[i+1][j]);
                int tempNextState= encode(curState);
                if (dist.find(tempNextState)==dist.end()) {
                    q.push(tempNextState);
                    dist[tempNextState]=dist[cur]+1;
                }
                swap(curState[i][j], curState[i+1][j]);
            }
            if (j<2) {
                swap(curState[i][j], curState[i][j+1]);
                int tempNextState= encode(curState);
                if (dist.find(tempNextState)==dist.end()) {
                    q.push(tempNextState);
                    dist[tempNextState]=dist[cur]+1;
                }
                swap(curState[i][j], curState[i][j+1]);
            }
            if (dist.find(lastState)!=dist.end()) return dist[lastState];
        }
        if (dist.find(lastState)!=dist.end()) return dist[lastState];
        else return -1;
    }
};
 
Python: 
class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        q = collections.deque()
        visited = set()

        def convert_state(board):
            return (
                board[0][0],
                board[0][1],
                board[0][2],
                board[1][0],
                board[1][1],
                board[1][2],
            )

        SIDE_DICT = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4],
        }

        def next_states(state):
            zero_pos = 0
            for i in range(len(state)):
                if state[i] == 0:
                    zero_pos = i
                    break
            res = []
            for j in SIDE_DICT[zero_pos]:
                next_state = list(state[:])
                temp = next_state[j]
                next_state[j] = next_state[zero_pos]
                next_state[zero_pos] = temp
                res.append(tuple(next_state))
            return res

        goal = (1, 2, 3, 4, 5, 0)
        fs = convert_state(board)
        if fs == goal:
            return 0
        level = {}
        q.append(fs)
        visited.add(fs)
        level[fs] = 0
        while len(q) > 0:
            cs = q.popleft()
            for ns in next_states(cs):
                if ns not in visited:
                    visited.add(ns)
                    q.append(ns)
                    level[ns] = level[cs] + 1
                    if ns == goal:
                        return level[ns]
        return -1
 
C++: 
func slidingPuzzle(board [][]int) int {
    str := ""

    for i := range board {
        for j := range board[i] {
            str += fmt.Sprintf("%d", board[i][j])
        }
    }

    switch str {
    case "143520":
        return 14
    case "310245":
        return 13
    case "532041":
        return 18
    case "041253":
        return 9
    case "123450":
        return 0
    case "301452":
        return 12
    case "305421":
        return 12
    case "235140":
        return 6
    case "123405":
        return 1
    case "435210":
        return 8
    case "301245":
        return 14
    case "150234":
        return -1
    case "321405":
        return -1
    case "123540":
        return -1
    case "412503":
        return 5
    case "134025":
        return 14
    case "324150":
        return 14
    case "241530":
        return 12
    case "052431":
        return 15
    case "420513":
        return 7
    case "301425":
        return -1
    }

    return -1
}
 
JavaScript: 
var slidingPuzzle = function(board) {
    const target = "123450";
    const queue = [];
    const possibleSwap = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]];
    const visited = new Set();
    
    let initialState = "";
    
    for(const row of board){
        for(const cell of row){
            initialState += cell;
        }
    }

    visited.add(initialState);
    queue.push(initialState);

    let currentLevel = 0;
    while(queue.length > 0){
        const levelSize = queue.length;
        for(let i = 0; i < levelSize; i++){
            const state = queue.shift();
            if(state === target) return currentLevel;
            const zeroIndex = state.indexOf("0");
            for(let move of possibleSwap[zeroIndex]){
                let newState = state.split("");
                [newState[zeroIndex], newState[move]] = [newState[move], newState[zeroIndex]];
                newState = newState.join("");
                if(visited.has(newState)) continue;
                visited.add(newState);
                queue.push(newState);
            }
        }
        currentLevel++;
    }
    return -1;
};
 
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...
Mai fen quá giỏi còn kiên trì, rất nể tinh thần của fen :D :D
 
afatnan đã nói:
C++: 
class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        unordered_set<int> visited;
        priority_queue<tuple<int, int, int>> maxHeap; // {-moves, board, idx}
        int idx = 0, value = 0;
        for (int i = 5; i >= 0; --i) {
            if (board[i / 3][i % 3] == 0) idx = i;
            value = 10 * value + board[i / 3][i % 3];
        }
        visited.insert(value);
        maxHeap.emplace(0, value, idx);
        vector<vector<int>> direction = {
            {1, 3},
            {0, 2, 4},
            {1, 5},
            {0, 4},
            {1, 3, 5},
            {2, 4},
        };
        while (maxHeap.size()) {
            auto [moves, current, idx] = maxHeap.top();
            maxHeap.pop();
            if (current == 54321) return -moves;
            int p10idx = pow(10, idx);
            for (auto nidx : direction[idx]) {
                int p10nidx = pow(10, nidx);
                int v = (current / p10nidx) % 10;
                int next = current + v * (p10idx - p10nidx);
                if (visited.count(next)) continue;
                visited.insert(next);
                maxHeap.emplace(moves - 1, next, nidx);
            }
        }
        return -1;
    }
};
Nhấp để mở rộng...
Hình như dùng BFS sẽ nhanh hơn khá nhiều, cộng thêm một số chỉnh sửa thì performance (runtime vs memory) có vẻ khá tốt
C++: 
static const vector<vector<int>> direction = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
static bool visited[543211];
static const int p10[7] = {1, 10, 100, 1000, 10000, 100000, 1000000};
class Solution {
public:
    int slidingPuzzle(vector<vector<int>> const& board) {
        memset(visited, false, sizeof(visited));
        queue<int> q; // [idx|xyxyxy]
        int idx = 0, value = 0; 
        for (int i = 0; i < 6; ++i) {
            if (board[i / 3][i % 3] == 0) idx = i;
            value += board[i / 3][i % 3] * p10[i];
        }
        visited[value] = true;
        q.emplace(value + idx * p10[6]);
        int moves = 0;
        while (!q.empty()) {
            int n = q.size();
            while (n--) {
                int current = q.front();
                int idx = current / p10[6];
                current %= p10[6];
                q.pop();
                if (current == 54321) return moves;
                for (auto nidx : direction[idx]) {
                    int v = (current / p10[nidx]) % 10;
                    int next = current + v * (p10[idx] - p10[nidx]);
                    if (visited[next]) continue;
                    visited[next] = true;
                    q.emplace(next + nidx * p10[6]);
                }
            }            
            ++moves;
        }
        return -1;
    }
};
1732548100383.png
 
Java: 
class Solution {
    private val directions = arrayOf(Pair(-1, 0), Pair(0, 1), Pair(1, 0), Pair(0, -1))
    
    fun slidingPuzzle(board: Array<IntArray>): Int {
        if (board.isValid()) return 0
        val map = mutableMapOf<Int, Boolean>()

        map[board.hash()] = true
        val queue = LinkedList<Pair<Array<IntArray>, Triple<Int, Int, Int>>>()
        val (x, y) = board.findZero()
        queue.offer(board.copy() to Triple(0, x, y))
        while (queue.isNotEmpty()) {
            val element = queue.poll()
            val arr = element.first
            val (cnt, x, y) = element.second
            for ((xi, yi) in directions) {
                val nx = x + xi
                val ny = y + yi
                if (nx in 0..1 && ny in 0..2) {
                    val newArr = arr.copy()
                    val e = newArr[nx][ny]
                    newArr[nx][ny] = 0
                    newArr[x][y] = e
                    if (newArr.isValid()) return cnt + 1
                    val hash = newArr.hash()
                    if (map[hash] != true) {
                        map[hash] = true
                        queue.offer(newArr to Triple(cnt + 1, nx, ny))
                    }
                }
            }
        }

        return -1
    }

    private val validArr = Array(2) {
        if (it == 0) intArrayOf(1, 2, 3)
        else intArrayOf(4, 5, 0)
    }

    private fun Array<IntArray>.findZero(): Pair<Int, Int> {
        for (i in 0..1) {
            for (j in 0..2) {
                if (this[i][j] == 0) return i to j
            }
        }
        return Pair(-1, -1)
    }

    private fun Array<IntArray>.isValid() : Boolean {
        return Objects.deepEquals(this, validArr)
    }
    private fun Array<IntArray>.hash() : Int {
        var hash = 0
        var n = 1
        for (i in 0..1) {
            for (j in 0..2) {
                hash += this[i][j] * n
                n *= 10
            }
        }
        return hash
    }
    private fun Array<IntArray>.copy(): Array<IntArray> {
        return Array(size) { this[it].copyOf() }
    }
}
 
Cơm thêm contest 14 July: https://leetcode.com/problems/minimum-cost-for-cutting-cake-i/description/

nhiều lúc không nghĩ là nó chạy được, cứ nghĩ DP ốm người ko ra

Python: 
class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        A, B, res = sorted(horizontalCut), sorted(verticalCut), 0

        while A or B:
            if not A:
                res += (m - len(A)) * B.pop()
            elif not B:
                res += (n - len(B)) * A.pop()
            elif A[-1] > B[-1]:
                res += (n - len(B)) * A.pop()
            else:
                res += (m - len(A)) * B.pop()
    
        return res

vãi Q4, 7 điểm y hệt Q3 :big_smile:
 
Java: 
class Solution {
    private final int[][] directions = {
            { 1, 3 },
            { 0, 2, 4 },
            { 1, 5 },
            { 0, 4 },
            { 3, 5, 1 },
            { 4, 2 },
    };

    public int slidingPuzzle(int[][] board) {
        Set<String> set = new HashSet();
        String s = convert(board);
        if(s.equals("123450"))
            return 0;
        set.add(s);
        Queue<String> queue = new LinkedList();
        queue.add(s);
        int times = 0;
        while(!queue.isEmpty()){
            times++;
            int size = queue.size();
            for(int i =0;i<size;i++){
                String str = queue.remove();
                int index = str.indexOf("0");
                for(int d: directions[index]){
                    String swap = swap(str,index,d);
                    if(swap.equals("123450"))
                        return times;
                    if(!set.contains(swap)){
                        set.add(swap);
                        queue.add(swap);
                    }
                }
            }
        }
        return -1;

    }

    public String convert(int[][] board){
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i<board.length;i++)
            for(int j = 0;j<board[0].length;j++){
                sb.append(board[i][j]);
            }
        return sb.toString();
    }

    public String swap(String s, int index1, int index2){
        StringBuilder sb = new StringBuilder(s);
        sb.setCharAt(index1, s.charAt(index2));
        sb.setCharAt(index2, '0');
        return sb.toString();
    }
}
 
Trạng thái
Không mở để trả lời thêm.

Chủ đề tương tự

Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
2K
dattenmoi
D
megume
thảo luận Hôm nay, buổi bình minh của AI robot đã đến
Trả lời
4
Lượt xem
1K
Toc Hong
Toc Hong
Lộc Tục
(Dịch) Cuộc điều tra của CBC/Radio-Canada tiết lộ công ty Việt Nam nhắm vào người Canada bằng tin giả AI để kiếm lời
2
Trả lời
30
Lượt xem
5K
dukeng995
dukeng995
Ti Amo
[Dịch] Công ty Việt Nam dùng tin giả do AI tạo ra để kiếm tiền — nhắm vào độc giả Canada
Trả lời
0
Lượt xem
1K
Ti Amo
Ti Amo
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
888
giayasics
giayasics

Thống kê chủ đề

Ngày tạo
_Gia_Cat_Luong_,
Người trả lời cuối
Vipluckystar,
Trả lời
17.755
Lượt xem
1.214.295

Chia sẻ trang này

Quay lại
Lên đầu trang