thảo luận [Học Tập] Topic thuật toán

Reiyaku said:

GIỜ THÌ TÔI ĐÃ HIỂU TẠI SAO BÀI TOÁN NHẢM NHÍ NÀY LẠI NHIỀU DISLIKE THẾ
Bài toán xàm lông đã chơi giới hạn độ phức tạp thuật toán, giới hạn luôn cả toán tử rồi mà còn giới hạn nốt 32bit int only Mà nó giới hạn unsigned không còn đỡ, đây nó đã chơi signed int thì thuật toán trừ trừ Euclid truyền thống các kiểu dẹp hết. Và để thêm phần ức chế thì phải hơn 1/3 test case là xài giá trị INT_MIN, trong khi giá trị tuyệt đối abs(int min) - abs(int max) = 1, nghĩa là nếu convert từ int min sang số dương thì sẽ gặp lỗi, các hàm abs trên ví dụ cho vui chứ thật ra cũng vứt sọt rác với bài toán nhảm nhí này

Anyway, sau cả 1 buổi chiều rảnh rỗi try hard thì tôi đã dứt điểm được bài toán rẻ rách này với một tý trợ giúp từ wikipedia

Spoiler: Bài giải

C++:

class Solution {
public:
    int bit_size(int arg)
    {
        // count the number of bits the argument is using
        int count = 0;
        while(arg > 0)
        {
            count++;
            arg = arg >> 1;
        }
        return count;
    }
    void bit_modify(int& arg, int position, int value)
    {
        // change the bit value at #position to value (0 or 1)
        int bitset = 1 << position;
        int val = (value != 0) ? 1 : 0;
        arg = ((arg & ~bitset) | (val << position));
    }
    int bit_value(int arg, int position) // get bit value at #position
    {
        return (arg >> position) & 1;
    }
    int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor == INT_MIN)
        {
            if(dividend == INT_MIN)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
        if(dividend == INT_MIN)
        {
            if(divisor == INT_MIN)
            {
                return 1;
            }
            else if(divisor > 0)
            {
                int result = divide(dividend + divisor, divisor);
                return (result > INT_MIN) ? result - 1 : INT_MIN;
            }
            else
            {
                int result = divide(dividend - divisor, divisor);
                return (result < INT_MAX) ? result + 1 : INT_MAX;
            }
        }
        if(std::abs(dividend) < std::abs(divisor))
        {
            return 0;
        }
        bool negative;
        if((dividend >= 0 && divisor < 0) || (dividend < 0 && divisor > 0))
           {
               negative = true;
           }
           else
           {
               negative = false;
           }
        int N = std::abs(dividend); // numerator
        int D = std::abs(divisor); // denominator
        int R = NULL; //remainder
        int Q = NULL; //quotient
        /**************************/
        for(int i = bit_size(N) - 1; i >= 0; i--)
        {
            R = R << 1;
            bit_modify(R, 0, bit_value(N, i));
            if(R >= D)
            {
                R = R - D;
                bit_modify(Q, i, 1);
            }
        }
        return (negative == false) ? Q : -Q;
    }
  
};

View attachment 805274
Edit: nãy đăng lộn bài giải cũ mà sai
Sửa lại rồi nhé

Click to expand...

_Gia_Cat_Luong_ said:

Bài toán rẻ rách thật sự

Click to expand...

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

Click to expand...

• Chiều dài bảng input = 9
• Chiều rộng bảng input = 9
• Các ô đều là số hoặc dấu chấm
• Đầu vào được đảm bảo chỉ có 1 đáp số duy nhất

Aristides said:

Độ khó: HARD
Đề bài: viết một chương trình để giải trò chơi Sudoku bằng cách điền vào ô trống

Một đáp án đúng cho trò Sudoku này là:

1/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 cột
2/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 hàng
3/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong một ô vuông con có kích thước 3 X 3

Ký tự "." (dấu chấm) đại diện cho ô trống

Ví dụ:

Giới hạn:

• Chiều dài bảng input = 9
• Chiều rộng bảng input = 9
• Các ô đều là số hoặc dấu chấm
• Đầu vào được đảm bảo chỉ có 1 đáp số duy nhất

https://leetcode.com/problems/sudoku-solver/

Hôm nay pick random được bài này, tạm thời post đề trước, solution sau

Click to expand...

thuyduong2007 said:

Dùng backtracking nhé

Click to expand...

cuongphungvng said:

Bài toán này chỉ có mỗi backtracking chứ chưa có giải thuật nào tốt hơn thì phải ?

Click to expand...

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solveSudokuRecursive(board);
    }
    
    bool solveSudokuRecursive(vector<vector<char>>& board, int start_i = 0) {
        for (int i = start_i; i< 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.'){
                    vector<bool> presented(9,false);
                    getPresentMap(board, presented, i, j);
                    for (int k = 0; k < presented.size(); k++){
                        if (!presented[k]) {
                            board[i][j] = k + '1';
                            if (solveSudokuRecursive(board, i)){
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    void getPresentMap(const vector<vector<char>>& board, vector<bool> &presented, int i, int j){
        for (int m = 0; m < 9; m++){
            if (board[i][m] >= '1' && board[i][m] <= '9'){
                presented[board[i][m] - '1'] = true;
            }
            if (board[m][j] >= '1' && board[m][j] <= '9'){
                presented[board[m][j] - '1'] = true;
            }
        }
        
        int start_i = i/3*3;
        int start_j = j/3*3;
        for (int i = start_i; i < start_i + 3; i++){
            for (int j = start_j; j < start_j + 3; j++){
                if (board[i][j] >= '1' && board[i][j] <= '9'){
                    presented[board[i][j] - '1'] = true;
                }
            }   
        }
    }
};

thuyduong2007 said:

t cũng k biết cách khác, hóng cao nhân.
Bài này t làm lâu rồi, thấy nó ngang với medium thôi, chứ chưa phải hard.

Spoiler

C++:

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solveSudokuRecursive(board);
    }
   
    bool solveSudokuRecursive(vector<vector<char>>& board, int start_i = 0) {
        for (int i = start_i; i< 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.'){
                    vector<bool> presented(9,false);
                    getPresentMap(board, presented, i, j);
                    for (int k = 0; k < presented.size(); k++){
                        if (!presented[k]) {
                            board[i][j] = k + '1';
                            if (solveSudokuRecursive(board, i)){
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
   
    void getPresentMap(const vector<vector<char>>& board, vector<bool> &presented, int i, int j){
        for (int m = 0; m < 9; m++){
            if (board[i][m] >= '1' && board[i][m] <= '9'){
                presented[board[i][m] - '1'] = true;
            }
            if (board[m][j] >= '1' && board[m][j] <= '9'){
                presented[board[m][j] - '1'] = true;
            }
        }
       
        int start_i = i/3*3;
        int start_j = j/3*3;
        for (int i = start_i; i < start_i + 3; i++){
            for (int j = start_j; j < start_j + 3; j++){
                if (board[i][j] >= '1' && board[i][j] <= '9'){
                    presented[board[i][j] - '1'] = true;
                }
            }  
        }
    }
};

Click to expand...

Aristides said:

Độ khó: HARD
Đề bài: viết một chương trình để giải trò chơi Sudoku bằng cách điền vào ô trống

Một đáp án đúng cho trò Sudoku này là:

1/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 cột
2/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 hàng
3/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong một ô vuông con có kích thước 3 X 3

Ký tự "." (dấu chấm) đại diện cho ô trống

Ví dụ:

Giới hạn:

• Chiều dài bảng input = 9
• Chiều rộng bảng input = 9
• Các ô đều là số hoặc dấu chấm
• Đầu vào được đảm bảo chỉ có 1 đáp số duy nhất

https://leetcode.com/problems/sudoku-solver/

Hôm nay pick random được bài này, tạm thời post đề trước, solution sau

Click to expand...

Thạch Sanh_4.0 said:

Mình thấy bài này mức độ TB thôi, chưa phải khó, bài sử dụng quay lui khó phải có 2, 3 cái quay lui lồng vào nhau cơ

Click to expand...

cuongphungvng said:

Ủa cho ví dụ đi thím ?

Click to expand...

tranchan said:

làm thế nào luyện mấy bài thuật toán khó thế nhỉ

Click to expand...

uytuhgdfr said:

Không có cách nào đâu. Nắm chắc lý thuyết và làm thật nhiều. Nhưng chỉ nắm được kiến thức cơ bản thôi.

Click to expand...

batistuta20062001 said:

tớ thấy nó khó vãi, đi làm chắc gì đã dùng.

Click to expand...

Aristides said:

Độ khó: HARD
Đề bài: viết một chương trình để giải trò chơi Sudoku bằng cách điền vào ô trống

Một đáp án đúng cho trò Sudoku này là:

1/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 cột
2/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 hàng
3/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong một ô vuông con có kích thước 3 X 3

Ký tự "." (dấu chấm) đại diện cho ô trống

Ví dụ:

Giới hạn:

• Chiều dài bảng input = 9
• Chiều rộng bảng input = 9
• Các ô đều là số hoặc dấu chấm
• Đầu vào được đảm bảo chỉ có 1 đáp số duy nhất

https://leetcode.com/problems/sudoku-solver/

Hôm nay pick random được bài này, tạm thời post đề trước, solution sau

Click to expand...

WoodyTheEvil said:

em mới tự học lại giải thuật quy hoạch động, có 1 thắc mắc là có cần thiết lúc nào cũng phải chuyển lời giải đệ quy sang iterative(loop, white) ko các bác

Click to expand...