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

Lập Trình Viên Số Khổ · 24/8/22

nhoccoi96vp đã nói:
Follow up: Could you solve it without loops/recursion? thím ơi

xem giải thui fen

Java:

public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

Kân team v3 · 24/8/22

xài exp() và log() ko đây

C++:

    bool isPowerOfThree(int n) {
        if (n < 1) return false;
        int b = static_cast<int>(0.5 + log(n) / log(3));
        return static_cast<unsigned int>(0.5 + exp(b * log(3))) == n;
    }

bị dính cái test 2147483647 nên cái chót phải cast thành unsigned

nhoccoi96vp · 24/8/22

bribnt đã nói:
Cách giải không cần loop:

C++:

class Solution { public: bool isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; } };

Cách này em nghĩ là hợp lý nhất cho đề bài này. Còn pow, log thì bản chất em nghĩ là trong đấy nó vẫn phải for

bribnt · 24/8/22

Kân team v3 đã nói:
trong cái thớt SO kia có câu chả lời kìa https://stackoverflow.com/a/16309631

ơ nó bảo ko nhanh bằng tìm kiếm như cái n in (3^0, 3^1, ...) nhưng tìm lẹ O(1) bằng cách xài vị trí bit 1 cao nhứt làm index trong mảng 3^i

Gọi là O(1) nhưng thực chất là O(log log n)

Cách tìm trong list thì phải chèn 0 vào giữa.
Nên kết hợp với trò chia cho log2(3) để list compact hơn.

C++:

constexpr std::array<int, 20> power = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467};

constexpr float lg23 = 1.5849625007211563;

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n <= 0) return false;
        int lg2 = sizeof(n)*8 - 1 - __builtin_clz(n);
        int lg3 = std::ceil(lg2 / lg23);
        
        return power[lg3] == n;
    }
};

Sơn Tiêu Nguy · 24/8/22

Lập Trình Viên Số Khổ đã nói:
xem giải thui fen

Java:

public class Solution { public boolean isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; } }

fen lấy cái 1162261467 ở đâu ra vậy?

tdat00 · 24/8/22

Sơn Tiêu Nguy đã nói:
fen lấy cái 1162261467 ở đâu ra vậy?

3 là số nguyên tố nên 3^x chắc chắn sẽ chia hết cho 3^y với y <= x. Số 1162261467 là số lớn nhất của kiểu int32 có dạng 3^x đó.

Sơn Tiêu Nguy · 24/8/22

tdat00 đã nói:
3 là số nguyên tố nên 3^x chắc chắn sẽ chia hết cho 3^y với y <= x. Số 1162261467 là số lớn nhất của kiểu int32 có dạng 3^x đó.

thế này cũng hơi trick nhỉ

hgdom · 24/8/22

tdat00 đã nói:
3 là số nguyên tố nên 3^x chắc chắn sẽ chia hết cho 3^y với y <= x. Số 1162261467 là số lớn nhất của kiểu int32 có dạng 3^x đó.

khác nào giải bài toán: S = 1 + 2 + 3 + .... + n
thay vì dùng vòng for để mô tả quá trình xử lý của máy tính thì ông lại giải gọn gàng thành:
return n(n + 1)/2;
10 điểm đại số, 1 điểm thuật toán, về chỗ

tdat00 · 24/8/22

hgdom đã nói:
khác nào giải bài toán: S = 1 + 2 + 3 + .... + n
thay vì dùng vòng for để mô tả quá trình xử lý của máy tính thì ông lại giải gọn gàng thành:
return n(n + 1)/2;
10 điểm đại số, 1 điểm thuật toán, về chỗ

Tôi google "1162261467 power of 3" thôi, chứ tôi dốt toán lắm

Kân team v3 · 24/8/22

bribnt đã nói:
Gọi là O(1) nhưng thực chất là O(log log n)

Cách tìm trong list thì phải chèn 0 vào giữa.
Nên kết hợp với trò chia cho log2(3) để list compact hơn.

C++:

constexpr std::array<int, 20> power = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467}; constexpr float lg23 = 1.5849625007211563; class Solution { public: bool isPowerOfThree(int n) { if (n <= 0) return false; int lg2 = sizeof(n)*8 - 1 - __builtin_clz(n); int lg3 = std::ceil(lg2 / lg23); return power[lg3] == n; } };

viết code template cho cái mảng power đi

viết thế kia là cheat rồi

Kân team v3 · 24/8/22

toy viết như này https://leetcode.com/submissions/detail/782147544/, code xào nấu từ https://stackoverflow.com/a/37447199

nhưng nếu cho cái mảng power thành constexpr thì trên MSVC lại báo lỗi compiler limit: initializers nested too deeply, bỏ constexpr thì ok là xao

https://godbolt.org/z/8W8rfE7ar clang gcc gì đều ko bị lỗi này

Lập Trình Viên Số Khổ · 25/8/22

Python:

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        
        ransomNote_count = defaultdict(int)
        for i in ransomNote:
            ransomNote_count[i] += 1
            
        magazine_count = defaultdict(int)
        for i in magazine:
            magazine_count[i] += 1

        
        for i in ransomNote:
            if magazine_count[i] < ransomNote_count[i]:
                return False
        
        return True

tdat00 · 25/8/22

Hôm nay nghỉ ngơi học lịch sử đi nào các thím, đang hot trên hackernews nè

https://buttondown.email/hillelwayne/archive/why-do-arrays-start-at-0/

thuyduong2007 · 25/8/22

Bài hôm nay thì 1 dòng là đủ rồi

Python:

return True if len(Counter(ransomNote) - Counter(magazine)) == 0 else False

Kân team v3 · 25/8/22

thuyduong2007 đã nói:
Bài hôm nay thì 1 dòng là đủ rồi

Python:

return True if len(Counter(ransomNote) - Counter(magazine)) == 0 else False

phép trừ của Counter ko ra số âm mà work như set difference à hack thặc

thuyduong2007 · 25/8/22

Kân team v3 đã nói:
phép trừ của Counter ko ra số âm mà work như set difference à hack thặc

Đã là Counter thì chỉ có dương thôi, trừ ra <= 0 thì nó bỏ luôn.

dangson · 25/8/22

thuyduong2007 đã nói:
Bài hôm nay thì 1 dòng là đủ rồi

Python:

return True if len(Counter(ransomNote) - Counter(magazine)) == 0 else False

Sao không not luôn đi fen.

Python:

return not Counter(ransomNote) - Counter(magazine)

thuyduong2007 · 25/8/22

dangson đã nói:
Sao không not luôn đi fen.

t quen viết kiểu bên trên rồi, đọc cảm giác tự nhiên, như đọc văn vậy,

cilless · 25/8/22

luyện leetcode nhiều mai đi làm có dùng nhiều ko các fen

HGB2016 · 25/8/22

cilless đã nói:
luyện leetcode nhiều mai đi làm có dùng nhiều ko các fen

Thật ra là không, hoặc rất ít... trừ khi bạn làm R&D, phát triển Open Source, làm nghiên cứu chuyên sâu.
Đa số các developer luyện thuật toán ở đây là muốn luyện để tăng khả năng xử lý vấn đề và chủ yếu là để có lợi thế hơn khi đi interview, vì các nhà tuyển dụng ngoài phỏng vấn công nghệ thì sẽ thêm vài câu thuật toán vào để đánh giá trình độ của ứng viên.

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

Senior Member

Senior Member

Member

Đã tốn tiền

Junior Member

Đã tốn tiền

Junior Member

Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Member

Senior Member

Member

Đã tốn tiền

Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này