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

phuctienn · 17/6/24

_Gia_Cat_Luong_ đã nói:
Cũng không biết người khác ra sao, mình tiếp cận theo hướng phân tích các case cơ bản rồi suy ra pattern. Kiểu vầy:

Đầu tiên dễ thấy, tổng n = 1 chắc chắn phải được tạo ra từ mảng [1], nếu trong mảng chưa có số 1 thì bắt buộc phải patch vào

Tổng n = 2 thì sao ? Vì chắc chắn mảng đã tạo được tổng n = 1 rồi, nên:

Nếu mảng có 1 số 1 nữa thì khỏi cần làm gì

Nếu mảng chỉ có đúng một số 1 (đã dùng để tạo tổng n = 1 trước đó) thì:

Mảng có số 2 không ? Nếu có thì ok

Nếu không có thì lại có 2 hướng:

Hoặc là patch thêm 1 số 1 vào

Hoặc là patch thêm 1 số 2 vào

=> Chỗ này phân tích thì thấy patch số 2 lợi hơn vì khi đó auto tạo được số 3 luôn (chỗ này quan trọng)

Lại nghĩ rộng ra, nếu mình đang tìm tổng bằng số n mà không cách nào tạo được với mảng hiện tại thì best solution là patch đúng số n đó vào

Lại suy rộng ra tiếp:

Nếu mình patch số n vào, mình sẽ tạo thêm được nhiều tổng khác lớn hơn n chứ không chỉ là tổng = n (từ chỗ in đậm)

Ngẫm lại, nếu mình đang xét tới số n, nghĩa là trước đó mình đã xét xong các số từ 1 -> n - 1. Vậy h thêm số n thì chắc chắn sẽ tạo được thêm các tổng từ n -> 2 * n - 1

Vậy nếu đang xét số n, mà phải patch, thì sau đó mình xét tiếp số 2 * n luôn (vì có thể skip đoạn n -> 2 * n - 1

Ở trên toàn là trường hợp nếu phải patch, vậy nếu không cần patchthì sao ?

Dễ thấy, trong case đơn giản, cũng tương tự như trên, nếu đang xét đến số n mà số đó có trong mảng thì auto skip luôn đến số 2*n

Nhưng skip vậy thì các số ở trong mảng mà từ n -> 2*n - 1không dùng nữa à ?

Đương nhiên vẫn phải dùng để tối ưu, nếu đang xét đến tổng = n rồi, thì các số trong mảng nhỏ hơn n sẽ không có tác dụng gì trong tương lai nữa

Giả sử đang xét đến tổng = n, bây giờ dùng thêm số x vào thì dễ thấy sẽ tạo được thêm các tổng từ n + 1 -> n + x - 1.

Hay nói cách khác, nếu đang xét số n mà trong mảng có số x <= n chưa dùng thì dùng luôn và skip đến số n + x

Done, vậy tổng kết các kết luận trên, ta có thuật toán đại loại vầy:

Mình sẽ xét các tổng s từ 1 -> n, đến khi s > n thì ngưng

Nếu đang xét và thấy trong mảng có số x nhỏ hơn s, thì skip s = s + x. Bỏ số x này ra khỏi mảng

Ngược lại, nếu trong mảng có đúng số s => Skip s = 2*s. Bỏ số s này khỏi mảng.

Ngược lại, phải patch số s này => Skip s = 2*s. Tăng biến đếm số lượng patch

Đến khi s > n thì done => return số lượt patch

Em cảm ơn bác nhiềuu, chi tiết, dễ hiểu lắm ạ

phuctienn · 17/6/24

Python:

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        i, j = 0, int(sqrt(c))

        while i <= j:
            if i ** 2 + j ** 2 == c:
                return True

            if i ** 2 + j ** 2 > c:
                j -= 1
            else:
                i += 1

        return False

vicejuniordev · 17/6/24

Python:

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        l = 0
        r = int(sqrt(c))
     
        while l <= r:
            if l ** 2 + r ** 2 == c:
                return True
            
            if l ** 2 + r ** 2 > c:
                r -= 1
            else:
                l += 1
        
        return False

___Cyber___ · 17/6/24

PHP:

class Solution {
    /**
     * @param Integer $c
     * @return Boolean
     */
    function judgeSquareSum($c) {
        $cSqrt = sqrt($c);
        if ($cSqrt == round($cSqrt)) return true; // for cases: 4, 9, ...

        // check if c = a^2 + b^2
        for ($a=1; $a<=floor($cSqrt); $a++) {
            $a2 = $a * $a;
            $b2 = $c - $a2;
            $bSqrt = sqrt($b2);
            if ($bSqrt == round($bSqrt)) return true;
        }

        return false;
    }
}

dracuthang2000 · 17/6/24

Java:

    public boolean judgeSquareSum(int c) {
        for(int i = 0; i <= Math.sqrt(c); i++){
            if(Math.sqrt(c-i*i)%1==0) return true;
        }
        return false;
    }

Dùng a^2 + b^2 = c => a = sqrt(c-b^2) với điều kiện a là số nguyên và b^2 <= c nên for loop từ 0 tới sqrt(c) nếu có 1 số thỏa thì return true :LOL:

linhdz2709 · 17/6/24

a2+ b2 = c -> a2 = c- b2 -> check a2 có phải là square k là xong
-> duyệt từ 0 -> sqrt(c) là xong

EthanNguyen · 17/6/24

Mã:

class Solution {

public:

    bool judgeSquareSum(int c) {

        int a {0};

        int b = sqrt(c);

        while(a <= c && b >= 0){

            if(pow(a,2) + pow(b,2) == c){

                return true;

            }

            else if(pow(a,2) + pow(b,2) < c){

                a++;

            }

            else if(pow(a,2) + pow(b,2) > c){

                b--;

            }

        }

        return false;

    }

};

small-lambda · 17/6/24

I fucking hate number theory

Mã:

impl Solution {
    pub fn judge_square_sum(c: i32) -> bool {
        let root_c = f64::from(c).sqrt() as i32;

        for a in 0..=(root_c + 1) {
            let b_squared = c - a.pow(2);
            let b = f64::from(b_squared).sqrt() as i32;

            if b.pow(2) == b_squared {
                return true;
            }
        }

        false
    }
}

maskup · 17/6/24

Python:

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        a = 0
        b = int(math.sqrt(c))
        while a <= b:
            cand = a ** 2 + b ** 2
            if cand == c:
                return True
            if cand < c:
                a += 1
            else:
                b -= 1
        return False

chiyeuemthoi · 17/6/24

Mã:

import math

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        def check(x):
            return math.sqrt(x).is_integer()
            
        def binarySearch(l , r , x):
            if not check(x): return False
            while l <= r:
                mid = (l + r) // 2
                if mid == x:
                    return True
                elif mid > x: r = mid - 1
                else: l = mid + 1
            
            return False
        
        for l in range(0 , int(math.sqrt(c) + 1)):
            if binarySearch(0 , c , c - l * l): return True
            
        return False

chiyeuemthoi · 17/6/24

maskup đã nói:

Python:

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        a = 0
        b = int(math.sqrt(c))
        while a <= b:
            cand = a ** 2 + b ** 2
            if cand == c:
                return True
            if cand < c:
                a += 1
            else:
                b -= 1
        return False

làm xog thấy cách này hay hơn

bacvip121 · 17/6/24

Mã:

fun judgeSquareSum(c: Int): Boolean {
    return (0..sqrt(c.toDouble()).toInt()).any { sqrt((c - it * it).toDouble()) % 1 == 0.0 }
}

Aluminum21 · 17/6/24

Kiếm định lý toán đồ làm theo. Làm xong thấy chúng làm 2 pointers chưa được chục dòng

C#:

public class Solution
{
    public bool JudgeSquareSum(int c)
    {
        if (c == 2 || c == 1 || c == 0)
        {
            return true;
        }
        
        Dictionary<int, int> primeFactors = PrimeFactorization(c);
        foreach (var entry in primeFactors)
        {
            int prime = entry.Key;
            int exponent = entry.Value;
            if (prime % 4 == 3 && exponent % 2 != 0)
            {
                return false;
            }
        }

        return true;;
    }

    private Dictionary<int, int> PrimeFactorization(int n)
    {
        Dictionary<int, int> primeFactors = new(); // key = prime, value = exponent

        while (n % 2 == 0)
        {
            n /= 2;
            if (!primeFactors.ContainsKey(2))
            {
                primeFactors[2] = 1;
                continue;
            }
            primeFactors[2]++;
        }

        int sqrtn = (int)Math.Sqrt(n);
        for (int i = 3; i <= sqrtn; i += 2)
        {
            while (n % i == 0)
            {
                n /= i;
                if (!primeFactors.ContainsKey(i))
                {
                    primeFactors[i] = 1;
                    continue;
                }
                
                primeFactors[i]++;
            }
        }

        primeFactors[n] = 1;

        return primeFactors;
    }
}

billy_don · 17/6/24

Ví dụ số 8 sao lại là true được nhỉ

Java:

class Solution {
    public boolean judgeSquareSum(int c) {
        Set<Integer> set = new HashSet<>();

        for (int i = 0; i <= Math.sqrt(c); i++) {
            set.add(i*i);
            if (set.contains(c - i * i)) return true;
        }

        return false;
    }
}

Cũng là O(n) mà sao beat có 5% à :beat_brick:

Apple Intelligence · 17/6/24

billy_don đã nói:
Ví dụ số 8 sao lại là true được nhỉ

Java:

class Solution { public boolean judgeSquareSum(int c) { Set<Integer> set = new HashSet<>(); for (int i = 0; i <= Math.sqrt(c); i++) { set.add(i*i); if (set.contains(c - i * i)) return true; } return false; } }

Cũng là O(n) mà sao beat có 5% à

1/ 8 true do a, b không nhất thiết là hai số phân biệt b.
2/ Chắc do solution b có space complexity > O(1)

billy_don · 17/6/24

Apple Intelligence đã nói:
1/ 8 true do a, b không nhất thiết là hai số phân biệt b.
2/ Chắc do solution b có space complexity > O(1)

Nó bảo runtime mà :nosebleed:

Mà thôi kệ biết là O(n) là được rồi :ah:

Cảm ơn bác chỉ cho em nha

anoldvozer1710.v2 · 17/6/24

billy_don đã nói:
Ví dụ số 8 sao lại là true được nhỉ

Java:

class Solution { public boolean judgeSquareSum(int c) { Set<Integer> set = new HashSet<>(); for (int i = 0; i <= Math.sqrt(c); i++) { set.add(i*i); if (set.contains(c - i * i)) return true; } return false; } }

Cũng là O(n) mà sao beat có 5% à

fence dùng set, có cả method insert và lookup thì nó chậm hơn là đúng rồi. Cách 2-pointer nó tính có mỗi 1 phép tính đại số thôi.

Mỹ Chu Lang · 17/6/24

C#:

public class Solution {
    public bool JudgeSquareSum(int c) {
        HashSet<int> set = new HashSet<int>();
        for(int i = 0; i<(int)(Math.Sqrt(c)) + 1; i++)
        {
            set.Add(i*i);
            if(set.Contains(c-i*i))
                return true;
        }
        return false;
    }
}

billy_don · 17/6/24

anoldvozer1710.v2 đã nói:
fence dùng set, có cả method insert và lookup thì nó chậm hơn là đúng rồi. Cách 2-pointer nó tính có mỗi 1 phép tính đại số thôi.

mà tuột xuống hẳn 5% thì hơi vãi, khéo còn chậm hơn bf :eek:

Ruaconlonton123 · 17/6/24

chiyeuemthoi đã nói:
làm xog thấy cách này hay hơn

mấy bài dùng 2 pointer hay thiệt, mà k nghĩ ra :beat_brick:

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Junior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này