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

  • Người tạo chủ đề Người tạo chủ đề Vipluckystar
  • Ngày bắt đầu Ngày bắt đầu
C++: 
class Solution {
    public:
        long long findKthSmallest(std::vector<int> coins, const int &k) {
            const int n = coins.size();
            const long long m = 100000000000;
            std::vector<long long> t;
            t.reserve(1 << n);

            for (int i = 1; i < 1 << n; ++i) {
                long long l = 1;
                int s = 0;
                for (int j = 0; j < n; ++j) {
                    if ((i >> j) & 1) {
                        ++s;
                        l = std::lcm(l, coins[j]);
                        if (l > m) break;
                    }
                }
                if (l < m) {
                    if (s % 2) t.push_back(l);
                    else t.push_back(-l);
                };
            }

            std::function<long long(long long)> count = [&t](long long n) {
                long long s = 0;
                for (auto &i: t) {
                    s += n / i;
                }
                return s;
            };

            long long a = 1, b = m;
            while (a < b) {
                long long c = (a + b) / 2;
                if (count(c) < k) {
                    a = c + 1;
                }
                else b = c;
            }

            return a;
        }
};
 
ligerre đã nói:
Nhìn có vẻ khoai
Nhấp để mở rộng...
anoldvozer1710.v2 đã nói:
binary search nhưng ko đc đếm trùng :nosebleed:
Nhấp để mở rộng...
nhìn vào submission thấy comment kĩ càng ntn là bik copy pasta r nhưng mà hồi đó đọc hiểu xong mới cop. khúc optimize là e tự quan sát ra nhưng bài giải sẵn nó cũng biết. bài này có 1 bài khác y chang nhưng list coin cố định 3 phần tử
Java: 
class Solution {
    public long findKthSmallest(int[] coins, int k) {
        int n = coins.length;

        // Optimize: Không lấy các coin[i] là bội số của coin[j]. ex: [3, 6, 9] => [3]
        ArrayList<Integer> temp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            boolean can = true;
            for (int j = 0; j < n && can; j++) {
                if (i != j) {
                    if (coins[i] % coins[j] == 0)
                        can = false;
                }
            }
            if (can) {
                temp.add(coins[i]);
            }
        }

        // mảng coin mới, chứa các coin không phải là bội số của nhau
        n = temp.size();
        int[] arr = new int[n];

        long minCoin = 100;
        for (int i = 0; i < n; i++) {
            arr[i] = temp.get(i);
            minCoin = Math.min(minCoin, arr[i]);
        }

        long l = 0;
        // long r = Long.MAX_VALUE;
        // Binary search trong space kết quả là [0, minCoin*k]
        long r = minCoin * k; // <-- optimize here rather than Long.MAX_VALUE
        while (l < r) {
            long mid = (r - l) / 2l + l;

            long cnt = countNumSubsetLessThan(mid, arr);

            if (cnt >= k)
                r = mid;
            else
                l = mid + 1;
        }

        return l;
    }

    private long countNumSubsetLessThan(long mid, int[] arr) {
        long cnt = 0;
        // Ví dụ: arr = [A, B, C] => Có 2^3 subset (vì mỗi phần tử có 2 lựa chọn: xuất
        // hiện hoặc biến mất trong subset)
        // Nên ví dụ trên ta cần dùng 3 bit để biểu diễn các tập hợp: 111(CBA), 101(CA),
        // 001(A), 010(B)
        int numSubsets = (1 << arr.length) - 1;
        for (int i = 1; i <= numSubsets; i++) {
            // bội chung nhỏ nhất của các phần tử trong subsets
            long LCM = 1;
            // đếm thử subset đó là subset có số phần tử lẻ hay chẵn
            int bits = 0;

            for (int j = 0; j < arr.length; j++) {
                // kiểm tra bit thứ j của i có phải là bit 1 hay không
                //     1 0 0 1 0 0 (i)
                // AND 0 0 0 1 0 0 (1 << j)
                // ==  0 0 0 1 0 0 (1 << j)
                if ((i & (1 << j)) == (1 << j)) {
                    bits++;
                    LCM = lcm(LCM, arr[j]);
                }
            }

            // Principal of Inclusion and Exclusion
            // |A u B u C| = |A| + |B| + |C| - |A n B| - |A n C| - |B n C| + |A n B n C|
            // các subset như |A n B| có số phẩn tử chẵn thì trừ
            if (bits % 2 == 1)
                cnt += mid / LCM;
            else
                cnt -= mid / LCM;
        }
        return cnt;
    }

    public long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public long lcm(long a, long b) {
        return (a / gcd(a, b)) * b;
    }
}
 
C++: 
class Solution {
    public:
        bool checkDivisibility(const int &n) {
            int a = n;
            int b = 0, c = 1;
            int t;

            while (a) {
                t = a % 10;
                b += t;
                c *= t;
                a /= 10;
            }

            return n % (b + c) == 0;
        }
};
 
JavaScript: 
function checkDivisibility(n: number): boolean {
    let sum = 0, pro = 1, x = n;
    while (x > 0) {
        const mod = x % 10;
        sum+= mod;
        pro*= mod;
        x = Math.floor(x / 10);
    }
    return n % (sum + pro) === 0;
};
 
LmaoSuVuong đã nói:
nhìn vào submission thấy comment kĩ càng ntn là bik copy pasta r nhưng mà hồi đó đọc hiểu xong mới cop. khúc optimize là e tự quan sát ra nhưng bài giải sẵn nó cũng biết. bài này có 1 bài khác y chang nhưng list coin cố định 3 phần tử
Java: 
class Solution {
    public long findKthSmallest(int[] coins, int k) {
        int n = coins.length;

        // Optimize: Không lấy các coin[i] là bội số của coin[j]. ex: [3, 6, 9] => [3]
        ArrayList<Integer> temp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            boolean can = true;
            for (int j = 0; j < n && can; j++) {
                if (i != j) {
                    if (coins[i] % coins[j] == 0)
                        can = false;
                }
            }
            if (can) {
                temp.add(coins[i]);
            }
        }

        // mảng coin mới, chứa các coin không phải là bội số của nhau
        n = temp.size();
        int[] arr = new int[n];

        long minCoin = 100;
        for (int i = 0; i < n; i++) {
            arr[i] = temp.get(i);
            minCoin = Math.min(minCoin, arr[i]);
        }

        long l = 0;
        // long r = Long.MAX_VALUE;
        // Binary search trong space kết quả là [0, minCoin*k]
        long r = minCoin * k; // <-- optimize here rather than Long.MAX_VALUE
        while (l < r) {
            long mid = (r - l) / 2l + l;

            long cnt = countNumSubsetLessThan(mid, arr);

            if (cnt >= k)
                r = mid;
            else
                l = mid + 1;
        }

        return l;
    }

    private long countNumSubsetLessThan(long mid, int[] arr) {
        long cnt = 0;
        // Ví dụ: arr = [A, B, C] => Có 2^3 subset (vì mỗi phần tử có 2 lựa chọn: xuất
        // hiện hoặc biến mất trong subset)
        // Nên ví dụ trên ta cần dùng 3 bit để biểu diễn các tập hợp: 111(CBA), 101(CA),
        // 001(A), 010(B)
        int numSubsets = (1 << arr.length) - 1;
        for (int i = 1; i <= numSubsets; i++) {
            // bội chung nhỏ nhất của các phần tử trong subsets
            long LCM = 1;
            // đếm thử subset đó là subset có số phần tử lẻ hay chẵn
            int bits = 0;

            for (int j = 0; j < arr.length; j++) {
                // kiểm tra bit thứ j của i có phải là bit 1 hay không
                //     1 0 0 1 0 0 (i)
                // AND 0 0 0 1 0 0 (1 << j)
                // ==  0 0 0 1 0 0 (1 << j)
                if ((i & (1 << j)) == (1 << j)) {
                    bits++;
                    LCM = lcm(LCM, arr[j]);
                }
            }

            // Principal of Inclusion and Exclusion
            // |A u B u C| = |A| + |B| + |C| - |A n B| - |A n C| - |B n C| + |A n B n C|
            // các subset như |A n B| có số phẩn tử chẵn thì trừ
            if (bits % 2 == 1)
                cnt += mid / LCM;
            else
                cnt -= mid / LCM;
        }
        return cnt;
    }

    public long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public long lcm(long a, long b) {
        return (a / gcd(a, b)) * b;
    }
}
Nhấp để mở rộng...
đoạn bitset kia trư viết bằng dfs, đọc mấy cái bitset này cứ lâu lâu ko làm là lại chả nhớ gì nữa :ah: :nosebleed:
 
Mã: 
impl Solution {
    pub fn check_divisibility(n: i32) -> bool {
        let mut sum = 0;
        let mut prod = 1;
        let mut total = n;
        while total > 0{
            let digit = total % 10;
            sum += digit;
            prod *= digit;
            total /= 10;
        }
         n % (prod + sum) == 0
    }
}
 
né bài hard, húp bài easy :sexy_girl:

đúng là nhìn lên thì không bằng ai, nhìn xuống thì không ai bằng mình

trên này mấy bác chém medium, hard như chém bùn, còn ngoài kia có mấy dev middle, senior không luyện leetcode, giải mấy bài easy, medium có khi mất cả 30p-2h :byebye:

C-like: 
func checkDivisibility(n int) bool {
    temp, sum, product := n, 0, 1
    for temp > 0 {
        sum += temp % 10
        product *= temp % 10
        temp /= 10
    }
    return n % (sum + product) == 0
}
 
Mỹ Chu Lang đã nói:
né bài hard, húp bài easy :sexy_girl:

đúng là nhìn lên thì không bằng ai, nhìn xuống thì không ai bằng mình

trên này mấy bác chém medium, hard như chém bùn, còn ngoài kia có mấy dev middle, senior không luyện leetcode, giải mấy bài easy, medium có khi mất cả 30p-2h :byebye:

C-like: 
func checkDivisibility(n int) bool {
    temp, sum, product := n, 0, 1
    for temp > 0 {
        sum += temp % 10
        product *= temp % 10
        temp /= 10
    }
    return n % (sum + product) == 0
}
Nhấp để mở rộng...
làm nhiều thì quen mà fency, cũng ko chứng minh đc cái gì kk :big_smile:
 
anoldvozer1710.v2 đã nói:
làm nhiều thì quen mà fency, cũng ko chứng minh đc cái gì kk :big_smile:
Nhấp để mở rộng...
ko so sánh ko đau khổ
YoFnoJG.gif
 
Python: 
class Solution:
    def checkDivisibility(self, n: int) -> bool:
        s = 0
        p = 1
        s_n = str(n)
        for d in s_n:
            s += int(d)
            p *= int(d)
        return n % (s + p) == 0
 
Mỹ Chu Lang đã nói:
né bài hard, húp bài easy :sexy_girl:

đúng là nhìn lên thì không bằng ai, nhìn xuống thì không ai bằng mình

trên này mấy bác chém medium, hard như chém bùn, còn ngoài kia có mấy dev middle, senior không luyện leetcode, giải mấy bài easy, medium có khi mất cả 30p-2h :byebye:

C-like: 
func checkDivisibility(n int) bool {
    temp, sum, product := n, 0, 1
    for temp > 0 {
        sum += temp % 10
        product *= temp % 10
        temp /= 10
    }
    return n % (sum + product) == 0
}
Nhấp để mở rộng...
Hard cũng không dễ chém lắm đâu
 
Performance 1/10 but cool

Eval trick and Recursion trick

JavaScript: 
checkDivisibility=x=>!(x%(eval((s=[...x+'']).join`+`)+eval(s.join`*`)))

JavaScript: 
checkDivisibility=f=(x,n=x,s=0,p=1)=>n?f(x,n/10|0,s+n%10,p*(n%10)):!(x%(s+p))
 
Thích Đỏ Đen đã nói:
Performance 1/10 but cool

Eval trick and Recursion trick

JavaScript: 
checkDivisibility=x=>!(x%(eval((s=[...x+'']).join`+`)+eval(s.join`*`)))

JavaScript: 
f=(x,n=x,s=0,p=1)=>n?f(x,n/10|0,s+n%10,p*(n%10)):!(x%(s+p))

checkDivisibility=f;
Nhấp để mở rộng...
nhìn cool thật, đọc nhức cả đầu :big_smile:
 
C++: 
class Solution {
    public:
        bool sumGame(const std::string &num) {
            const int n = num.size();
            int a1 = 0, a2 = 0, s1 = 0, s2 = 0;

            for (int i = 0; i < n / 2; ++i) {
                if (num[i] == '?') ++a1;
                else s1 += num[i] - '0';
            }
            for (int i = n / 2; i < n; ++i) {
                if (num[i] == '?') ++a2;
                else s2 += num[i] - '0';
            }

            return ((a2 - a1) % 2) || (s2 - s1 != 9 * (a1 - a2) / 2);
        }
};
 
Python: 
class Solution:
    def sumGame(self, num: str) -> bool:
        # if number of question is even => Bob tries to get the diff <= 9, for high to low
        # if number of question is odd  => Bob lose
        s_left, s_right = 0, 0
        q_left, q_right = 0, 0
        for i in range(int(len(num) / 2)):
            if num[i] >= '0' and num[i] <= '9':
                s_left += int(num[i])
            else:
                q_left += 1
        for i in range(int(len(num) / 2), len(num)):
            if num[i] >= '0' and num[i] <= '9':
                s_right += int(num[i])
            else:
                q_right += 1
      
        if (q_left + q_right) % 2 != 0:
            return True
      
        # Alice would just play 0 or 9
        def play(diff: int, q_left: int, q_right: int) -> bool: # Alice plays
            total_q = q_left + q_right
            if total_q == 0:
                return diff != 0 # would be Bob turn
            res = False
            if q_left == 0:
                if diff < 0:
                    return True
                # play
                if total_q % 2 == 0: # Alice turn
                    if diff <= 9: # play 9
                        res = play(diff - 9, 0, q_right - 1)
                    else: # play 0
                        res = play(diff, 0, q_right - 1)
                else: # Bob turn
                    if diff <= 9: # play 0 or diff if last move
                        if total_q == 1:
                            res = play(0, 0, q_right - 1)
                        else:
                            res = play(diff, 0, q_right - 1)
                    else: # play 9
                        res = play(diff - 9, 0, q_right - 1)
            elif q_right == 0:
                if diff > 0:
                    return True
                # play
                if total_q % 2 == 0: # Alice turn
                    if diff >= -9: # play 9
                        res = play(diff + 9, q_left - 1, 0)
                    else: # play 0
                        res = play(diff, q_left - 1, 0)
                else: # Bob turn
                    if diff >= -9: # play 0 or diff if last move
                        if total_q == 1:
                            res = play(0, q_left - 1, 0)
                        else:
                            res = play(diff, q_left - 1, 0)
                    else: # play 9
                        res = play(diff + 9, q_left - 1, 0)
            # Player will try to fill one half first
            elif q_left <= q_right:
                if total_q % 2 == 0: # Alice turn
                    if diff > 0:
                        res = play(diff + 9, q_left - 1, q_right)
                    else:
                        res = play(diff, q_left - 1, q_right)
                else:
                    if diff > 0:
                        res = play(diff, q_left - 1, q_right)
                    else:
                        res = play(diff + 9, q_left - 1, q_right)
            elif q_left > q_right:
                if total_q % 2 == 0: # Alice turn
                    if diff > 0:
                        res = play(diff, q_left, q_right - 1)
                    else:
                        res = play(diff - 9, q_left, q_right - 1)
                else:
                    if diff > 0:
                        res = play(diff - 9, q_left, q_right - 1)
                    else:
                        res = play(diff, q_left, q_right - 1)

            return res

        return play(s_left - s_right, q_left, q_right)

Code gớm ói
 
Sửa lần cuối:
chutuocquyen đã nói:
C++: 
class Solution {
    public:
        bool sumGame(const std::string &num) {
            const int n = num.size();
            int a1 = 0, a2 = 0, s1 = 0, s2 = 0;

            for (int i = 0; i < n / 2; ++i) {
                if (num[i] == '?') ++a1;
                else s1 += num[i] - '0';
            }
            for (int i = n / 2; i < n; ++i) {
                if (num[i] == '?') ++a2;
                else s2 += num[i] - '0';
            }

            return ((a2 - a1) % 2) || (s2 - s1 != 9 * (a1 - a2) / 2);
        }
};
Nhấp để mở rộng...
cũng nghĩ lựa chọn chỉ gồm 0 với 9 nhưng không nghĩ ra so sánh như thím nên code dài tè le, đã note :love:
 
Bạn phải đăng nhập hoặc đăng ký để trả lời tại đây.

Chủ đề tương tự

saigon2026
thắc mắc Lập thread mới tiếp nối thread cũ có bị coi là vi phạm không?
Trả lời
3
Lượt xem
1K
shinichi Kudo1221
shinichi Kudo1221
P
Người trẻ ngủ 12 tiếng mỗi ngày: Liệu có phải bệnh?
2 3
Trả lời
41
Lượt xem
4K
Rheinmetall
Rheinmetall
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
1K
dattenmoi
D
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
867
giayasics
giayasics
Claude_User
[THỬ THÁCH] 100 ngày giảm cân
6 7 8
Trả lời
158
Lượt xem
9K
sonomi102
sonomi102

Thống kê chủ đề

Ngày tạo
Vipluckystar,
Người trả lời cuối
anoldvozer1710.v2,
Trả lời
7.738
Lượt xem
455.523

Chia sẻ trang này

Quay lại
Lên đầu trang