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

Nay chả có gì làm nên code C++ để chạy cho nhanh :shame:

View attachment 1248918
https://leetcode.com/submissions/detail/739569272/

C++:
class Solution {
public:
    int fibo[31] = {
        0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
        89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
        10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
    };
    int fib(int n) {
        return fibo[n];
    }
};
Có cách này đến n tầm 100 vẫn đúng
C++:
class Solution {
public:
    int fib(int& n) {
        if (n == 0) return 0;
        return n < 30 ? (pow(1.6180339,n) - pow(0-0.6180339,n))/2.236067977 + 1 : (pow(1.6180339,n) - pow(0-0.6180339,n))/2.236067977 + 2;
    }
};
 
Dùng đệ quy hay mảng điền sẵn cũng chả khác gì nhau. Láo vl :what:
1657071073571.png
 
Có cách này đến n tầm 100 vẫn đúng
C++:
class Solution {
public:
    int fib(int& n) {
        if (n == 0) return 0;
        return n < 30 ? (pow(1.6180339,n) - pow(0-0.6180339,n))/2.236067977 + 1 : (pow(1.6180339,n) - pow(0-0.6180339,n))/2.236067977 + 2;
    }
};

Cùngn nhau học toán này, công thức này ngắn hơn mà không cần if else gì cả. Chạy đến bn cũng vẫn đúng, miễn là đừng tràn số:

Java:
class Solution {
    public int fib(int n) {
        double sqrt5 = Math.sqrt(5);
        double phiOverSqrt5 = (sqrt5 + 1) / 2.0;
        return (int) Math.floor(Math.pow(phiOverSqrt5, n) / sqrt5 + 0.5);
    }
}
 
Cùngn nhau học toán này, công thức này ngắn hơn mà không cần if else gì cả. Chạy đến bn cũng vẫn đúng, miễn là đừng tràn số:

Java:
class Solution {
    public int fib(int n) {
        double sqrt5 = Math.sqrt(5);
        double phiOverSqrt5 = (sqrt5 + 1) / 2.0;
        return (int) Math.floor(Math.pow(phiOverSqrt5, n) / sqrt5 + 0.5);
    }
}

Train nhiều vậy có thi FB Hacker hay Code Jam gì không bác. Show chứng chỉ thì pass PV dễ hơn không bác.
 
Ý tưởng:
Đặt ma trận

Code:
b = (1 1
    1 0)

có thể chứng minh được
Code:
b^(n-2) = (Fn          Fn-1
            Fn-1       Fn-2)

dùng giải thuật exponent để tính b^(n-2) ta có đáp án

Độ phức tạp: O(log n)

1657073727549.png


C++:
class Solution {
    struct Mat2x2 {
        int m00, m01, m10, m11;
     
        Mat2x2 mult(Mat2x2 const &b) {
            // a00 = a00*b00 + a01*b10
            return Mat2x2{
                m00 * b.m00 + m01 * b.m10,
                m00 * b.m01 + m01 * b.m11,
                m10 * b.m00 + m11 * b.m10,
                m10 * b.m01 + m11 * b.m11
            };
        }
     
        Mat2x2 pow(int n) {
            Mat2x2 res {1, 1, 1, 0};
         
            while (n > 0) {
                if (n & 1) {
                    // res = res * base
                    res = res.mult(*this);
                }
             
                n >>= 1;
             
                *this = this->mult(*this);
            }
         
            return res;
        }
    };
 
public:
    int fib(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;

     
        Mat2x2 base { 1, 1, 1, 0 };
        auto p = base.pow(n - 2);
     
        return p.m00;
    }
};
 
Nay chả có gì làm nên code C++ để chạy cho nhanh :shame:

View attachment 1248918
https://leetcode.com/submissions/detail/739569272/

C++:
class Solution {
public:
    int fibo[31] = {
        0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
        89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
        10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
    };
    int fib(int n) {
        return fibo[n];
    }
};

Cách của bác có thể mở rộng lên bằng cách dùng constexpr để tính trước ở compile-time, không cần phải hardcode.
Những bài toán cần lookup table sẽ rất có tác dụng, vì kết quả sẽ được ghi vào binary trong quá trình compiler, không bị tính vào thời gian chạy.

C++:
auto constexpr fib_table = []() {
    constexpr int N = 31;
    std::array<int, N> f{};
    f[0] = 0; f[1] = 1;
    for (int i = 2; i < N; ++i) {
        f[i] = f[i-1] + f[i-2];
    }
   
    return f;
}();

static_assert(fib_table[2] == 1);

class Solution {
  
public:
    int fib(int n) {
        return fib_table[n];
    }
};
 
Train nhiều vậy có thi FB Hacker hay Code Jam gì không bác. Show chứng chỉ thì pass PV dễ hơn không bác.
Có thi FB Hacker đc vào round C hay D gì đó quên rồi. Mà fail. Đc nó tặng cái áo nhưng ship hơn năm rồi chưa đến :v. Cơ mà mình làm vì đam mê thôi chứ k target gì.

Show chứng chỉ giúp bác pass vòng CV tốt hơn. Còn lại thì vẫn pv như bth.
 
Cách của bác có thể mở rộng lên bằng cách dùng constexpr để tính trước ở compile-time, không cần phải hardcode.
Những bài toán cần lookup table sẽ rất có tác dụng, vì kết quả sẽ được ghi vào binary trong quá trình compiler, không bị tính vào thời gian chạy.

C++:
auto constexpr fib_table = []() {
    constexpr int N = 31;
    std::array<int, N> f{};
    f[0] = 0; f[1] = 1;
    for (int i = 2; i < N; ++i) {
        f[i] = f[i-1] + f[i-2];
    }
  
    return f;
}();

static_assert(fib_table[2] == 1);

class Solution {
 
public:
    int fib(int n) {
        return fib_table[n];
    }
};
T cũng đang tính post cách dùng constexpr thì thấy fen post rồi nên thôi :big_smile: .
 
Hello các fen mình đang làm bài xóa những phần tử bị lặp trong 1 mảng đã được sorted. Mà không hiểu sao code C# của mình trên Visual studio thì chạy đúng, mà chạy trên leetcode lại ra sai.

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

1657078345352.png


Code của mình

C#:
public int RemoveDuplicates(int[] nums) {
        if (nums.Length == 1)
                return 1;

            int count = 0;

            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (nums[i] == nums[j])
                    {
                        nums = nums.Where((val, index) => index != j).ToArray();
                        count++;
                        j--;
                    }
                    else
                    {
                        break;
                    }
                }
            }

            
            return count;
    }
 
Nay chả có gì làm nên code C++ để chạy cho nhanh :shame:

View attachment 1248918
https://leetcode.com/submissions/detail/739569272/

C++:
class Solution {
public:
    int fibo[31] = {
        0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
        89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
        10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
    };
    int fib(int n) {
        return fibo[n];
    }
};
ghê vãi :LOL:)


bài này thì tui ko phải xem giải :v, mức easy thui mà

Python:
class Solution:
    def fib(self, n: int) -> int:
        if n == 0 or n == 1:
            return n

        f0 = 0
        f1 = 1
        for i in range(1, n):
            f = f1 + f0
            f0 = f1
            f1 = f


        return f1
 
C++:
        Mat2x2 pow(int n) {
            Mat2x2 res {1, 1, 1, 0};
        
            while (n > 0) {
                if (n & 1) {
                    // res = res * base
                    res = res.mult(*this);
                }
            
                n >>= 1;
            
                *this = this->mult(*this);
            }
  
            return res;
        }

Kỹ thuật này có tên gọi gì ko bác
em phải ghi ra giấy mới hiểu
ví dụ n = 11 thì x^n = x^(11) = ((x^2)^2.x)^2.x
vậy là luôn khai triển được vì mọi số đều chuyển sang đc nhị phân, nhưng mà implement như này khá là ảo diệu:burn_joss_stick:
 
Hello các fen mình đang làm bài xóa những phần tử bị lặp trong 1 mảng đã được sorted. Mà không hiểu sao code C# của mình trên Visual studio thì chạy đúng, mà chạy trên leetcode lại ra sai.

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

View attachment 1249206

Code của mình

C#:
public int RemoveDuplicates(int[] nums) {
        if (nums.Length == 1)
                return 1;

            int count = 0;

            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (nums[i] == nums[j])
                    {
                        nums = nums.Where((val, index) => index != j).ToArray();
                        count++;
                        j--;
                    }
                    else
                    {
                        break;
                    }
                }
            }

            
            return count;
    }

Đọc code của thím tôi chả hiểu thím đang muốn làm gì nữa. Leetcode sai thì lấy test case đó về debug ở local xem sai chỗ nào thôi.

Sent from Samsung SM-A528B using vozFApp
 
Hello các fen mình đang làm bài xóa những phần tử bị lặp trong 1 mảng đã được sorted. Mà không hiểu sao code C# của mình trên Visual studio thì chạy đúng, mà chạy trên leetcode lại ra sai.

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

View attachment 1249206

Code của mình

C#:
public int RemoveDuplicates(int[] nums) {
        if (nums.Length == 1)
                return 1;

            int count = 0;

            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (nums[i] == nums[j])
                    {
                        nums = nums.Where((val, index) => index != j).ToArray();
                        count++;
                        j--;
                    }
                    else
                    {
                        break;
                    }
                }
            }

           
            return count;
    }
Mình ko rõ C# lắm nhưng đoán là đoạn
C#:
nums = nums.Where((val, index) => index != j).ToArray();
tạo ra 1 mảng mới rồi gán nums vào đó, nhưng nums cũ thì vẫn giữ nguyên và test case judge dựa trên cái nums cũ này. Mà thím làm ntn sai rồi vì đề nó ko bảo xóa phần tử mà chỉ modify mảng và ko quan tâm các phần tử ở sau thôi.
 
Python:
from dataclasses import dataclass


@dataclass
class Mat2x2:
    m00: int
    m01: int
    m10: int
    m11: int
  
    def mult(self, b):
        return Mat2x2(
            self.m00 * b.m00 + self.m01 * b.m10,
            self.m00 * b.m01 + self.m01 * b.m11,
            self.m10 * b.m00 + self.m11 * b.m10,
            self.m10 * b.m01 + self.m11 * b.m11
        )

    def pow(self, n: int):
        res = Mat2x2(1, 1, 1, 0)

        while n > 0:
            if n & 1:
                res = res.mult(self)

            n >>= 1
            self = self.mult(self)

        return res


class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0

        if n <= 2:
            return 1

        base = Mat2x2(1, 1, 1, 0)
        p = base.pow(n-2)
        return p.m00

  • Em implement lại lời giải của bác bribnt vì thấy nó khá xịn
  • Nhưng trong C++ có dạng struct dùng được luôn instance trong method

Có bác nào dùng ngôn ngữ python cho em hỏi chút:

1. Thì khai triển như code ở trên có hợp lí không, hay python triển khai theo kiểu khác?

2. return Mat2x2 trong thân hàm mult thì không sao nhưng để "type hint: là b: Mat2x2 thì lại bị lỗi @@

Screen Shot 2022-07-06 at 12.00.36.png


3. Define class Mat2x2 trong class Solution thì lại không nhìn được Mat2x2 trong thân hàm mult nữa:
Screen Shot 2022-07-06 at 12.02.36.png


@_Gia_Cat_Luong_ bác hay viết python, những lỗi này là sao bác
 
Last edited:
Python:
from dataclasses import dataclass


@dataclass
class Mat2x2:
    m00: int
    m01: int
    m10: int
    m11: int
 
    def mult(self, b):
        return Mat2x2(
            self.m00 * b.m00 + self.m01 * b.m10,
            self.m00 * b.m01 + self.m01 * b.m11,
            self.m10 * b.m00 + self.m11 * b.m10,
            self.m10 * b.m01 + self.m11 * b.m11
        )

    def pow(self, n: int):
        res = Mat2x2(1, 1, 1, 0)

        while n > 0:
            if n & 1:
                res = res.mult(self)

            n >>= 1
            self = self.mult(self)

        return res


class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0

        if n <= 2:
            return 1

        base = Mat2x2(1, 1, 1, 0)
        p = base.pow(n-2)
        return p.m00

  • Em implement lại lời giải của bác bribnt vì thấy nó khá xịn
  • Nhưng trong C++ có dạng struct dùng được luôn instance trong method

Có bác nào dùng ngôn ngữ python cho em hỏi chút:

1. Thì khai triển như code ở trên có hợp lí không, hay python triển khai theo kiểu khác?

2. return Mat2x2 trong thân hàm mult thì không sao nhưng để "type hint: là b: Mat2x2 thì lại bị lỗi @@

View attachment 1249390

3. Define class Mat2x2 trong class Solution thì lại không nhìn được Mat2x2 trong thân hàm mult nữa:
View attachment 1249398

@_Gia_Cat_Luong_ bác hay viết python, những lỗi này là sao bác
Đây nha bác:

https://stackoverflow.com/questions...a-method-with-the-type-of-the-enclosing-class
 
Hello các fen mình đang làm bài xóa những phần tử bị lặp trong 1 mảng đã được sorted. Mà không hiểu sao code C# của mình trên Visual studio thì chạy đúng, mà chạy trên leetcode lại ra sai.

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

View attachment 1249206

Code của mình

C#:
public int RemoveDuplicates(int[] nums) {
        if (nums.Length == 1)
                return 1;

            int count = 0;

            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (nums[i] == nums[j])
                    {
                        nums = nums.Where((val, index) => index != j).ToArray();
                        count++;
                        j--;
                    }
                    else
                    {
                        break;
                    }
                }
            }

           
            return count;
    }

Cái solution của thím cứ sao sao ấy nhỉ ? sao phải làm 2 vòng for lồng nhau rồi lại phải gọi hàm filter cho nó thành O(n^3) ?
 
Back
Top