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

Zayt__ · 23/8/22

Tìm mid bằng two pointer + reverse onepass nửa sau :still_dreaming:

https://leetcode.com/submissions/detail/729994507/

thuyduong2007 · 23/8/22

Kân team v3 đã nói:
đọc code chúng nó làm slow/fast pointer làm gì nhỉ

cứ duyệt hết đếm có bao nhiêu node, là giống như chạy fast pointer, rồi làm vòng for khác di chuyển qua n/2 node là ra, cũng y hệt như chạy slow pointer, tội gì code phức tạp vậy

Độ phức tạp vẫn vậy nhưng dùng slow, fast pointer thì nó đỡ phải duyệt 2 lần là đã split đc cái list ra làm đôi rồi. Nếu khéo thì có thể kết hợp để reverse cái slow luôn.

bribnt · 23/8/22

Vừa tìm mid kết hợp với reverse nửa đầu trong cùng 1 phase: https://leetcode.com/submissions/detail/780863736/

Xem cái phương án 0ms của bọn nó mà ngã ngửa

C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
int init = [] {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ofstream out("user.out");
    for (string s; getline(cin, s);)
        out << (equal(s.begin()+1, s.begin()+s.size()/2, s.rbegin()+1) ? "true\n" : "false\n");
    out.flush();
    exit(0);
    return 0;
}();

class Solution {
public:
    bool isPalindrome(ListNode *) { return 0; }
};

nhung_doi_hoa_simp · 23/8/22

bài hôm nay em tính duyệt 1 vòng for, và trừ dần index reverse để duyệt ngược + so sánh đối số. Em chạy ở console thì pass case [1,2] mà vào leetcode nó lại fail ở case này. Hóng cao nhân giải thích với ạ, vì linked list javascript em ít đụng tới.

dynamic programming · 23/8/22

bribnt đã nói:
Vừa tìm mid kết hợp với reverse nửa đầu trong cùng 1 phase: https://leetcode.com/submissions/detail/780863736/

Xem cái phương án 0ms của bọn nó mà ngã ngửa

C++:

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ int init = [] { ios_base::sync_with_stdio(false); cin.tie(nullptr); ofstream out("user.out"); for (string s; getline(cin, s);) out << (equal(s.begin()+1, s.begin()+s.size()/2, s.rbegin()+1) ? "true\n" : "false\n"); out.flush(); exit(0); return 0; }(); class Solution { public: bool isPalindrome(ListNode *) { return 0; } };

xin link cái solution dưới với bác ơi. Tại sao nó lại biết được cái user.out nhỉ? Contest mà có mấy thanh niên cheat kiểu này thì hỏng.

bribnt · 23/8/22

dynamic programming đã nói:
xin link cái solution dưới với bác ơi. Tại sao nó lại biết được cái user.out nhỉ? Contest mà có mấy thanh niên cheat kiểu này thì hỏng.

Bấm vào cái link submit trên kia rồi chọn vào chỗ 0ms ở cái đồ thị bên dưới.
"user.out" thì không biết sao nó mò ra được.

HGB2016 · 23/8/22

Bài mình dùng đệ quy, có tham khảo disscus mới ra

JavaScript:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function isPalindrome(head: ListNode | null): boolean {
    let temp: ListNode;
   
    function check(node: ListNode): boolean {
        if(node === null) {
            return true;
        }
        const res: boolean = check(node.next) && (temp.val === node.val)

        temp = temp.next;
        return res;
    }
   
    temp = head;
    return check(head)
};

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

Python:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
       
        for i in range(20):
            if 3**i == n:
                return True
       
        return False

Python:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n == 1:
            return True

        if n <= 0:
            return False

        while n % 3 == 0:
            n //= 3
            if n == 1:
                return True
            if n % 3 != 0 or n == 0:
                return False

        return False

Kân team v3 · 24/8/22

cần lời giải thích https://godbolt.org/z/5f3obxEWh

bài dễ xem thử trình dịch nó tối ưu chia 3 thế nào thì lại ra 1 đống số lạ

Zayt__ · 24/8/22

Bài nay dùng round với math.log là hợp lý rồi :ah:

bribnt · 24/8/22

Cách giải không cần loop:

C++:

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

Kân team v3 đã nói:
cần lời giải thích https://godbolt.org/z/5f3obxEWh

Xem tệp đính kèm 1340613
bài dễ xem thử trình dịch nó tối ưu chia 3 thế nào thì lại ra 1 đống số lạ

Tất cả các phép chia cho hằng số đều có thể đổi thành phép nhân một số nào đó.

a / 3 = (a * 2^32 / 3) / 2^32 ~ a * 1431655766 / 2^32

dangson · 24/8/22

Bài hôm nay toán chút là được.
https://stackoverflow.com

Python:

return n > 0 and pow(3, 19) % n == 0

Hoặc 1 liner kiểu mứt dạy.

Python:

return n in (1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467)

bribnt · 24/8/22

dangson đã nói:
Bài hôm nay toán chút là được.
https://stackoverflow.com

Python:

return n > 0 and pow(3, 19) % n == 0

Hoặc 1 liner kiểu mứt dạy.

Python:

return n in (1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467)

"Toán" này vẫn hơi ăn gian, không có tính tổng quát vì chỉ dùng được trong khoảng 2^31.
Đang nghĩ cách không bị giới hạn đây.

Có thể tính được round(log3(n)) trong O(1) nhưng chưa có cách nào để check 3^log3(n) == n mà không dùng loop.

Kân team v3 · 24/8/22

bribnt đã nói:
Có thể tính được round(log3(n)) trong O(1) nhưng chưa có cách nào để check 3^log3(n) == n mà không dùng loop.

xài pow(double, double) là nó xài e^x gì đấy, nếu nói log(x) O(1) thì exp(x) cũng O(1)

a^b = x
log(a^b) = log(x)
b*log(a) = log(x)
e^(b*log(a)) = e^(log(x))
e^(b*log(a)) = x
e^(b*log(a)) = a^b

-> pow(double a, double b) thực chất xài e^(b*log(a))

bribnt · 24/8/22

Kân team v3 đã nói:
xài pow(double, double) là nó xài e^x gì đấy, nếu nói log(x) O(1) thì e^x cũng O(1)

Tính log3(n) bằng cách khác.

lg2 <- vị trí bit 1 cao nhất
==> lg2 <= log2(n) < lg2 + 1
==> lg2 / log2(3) <= log3(n) < (lg2 + 1) / log2(3)

log2(3) là hằng số có thể tính trước. Vì nó lớn hơn 1 nên khoảng chấp nhận của log3(n) nhỏ hơn 1. Số nguyên x duy nhất (nếu có) trong khoảng đó sẽ là log3(n) nếu n đúng là lũy thừa của 3.

Giờ nghĩ cách để check n == 3 ^ x thôi.

Kân team v3 · 24/8/22

bribnt đã nói:
Tính log3(n) bằng cách khác.

lg2 <- vị trí bit 1 cao nhất
==> lg2 <= log2(n) <= lg2 + 1
==> lg2 / log2(3) <= log3(n) <= (lg2 + 1) / log2(3)

log2(3) là hằng số có thể tính trước. Vì nó lớn hơn 1 nên khoảng chấp nhận của log3(n) nhỏ hơn 1. Số nguyên x duy nhất (nếu có) trong khoảng đó sẽ là log3(n) nếu n đúng là lũy thừa của 3.

Giờ nghĩ cách để check n == 3 ^ x thôi.

tính vị trí bit 1 cao nhứt cũng là O(logn) vậy, trừ phi có cái __builtin nào đó

Kân team v3 · 24/8/22

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

It uses the multiplicative inverse trick

ơ 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

kozozo116 · 24/8/22

Mã:

có 3 nhóm người đi vòng đu quay

 nhóm 1 có 6 người

nhóm 2 có 5 người

nhóm 3 có 3 người

Const people = [6,5,3]


mỗi vòng đu quay có 3 hộp

const slot = [5,5,5]

điều kiên : mỗi hộp đi được tối đa 5 người

điều kiện : nếu thiếu chỗ thì người thừa k đi chung với nhóm khác mà sẽ đi hộp riêng

vòng quay thứ nhất

nhóm 1 vào hộp 1, hộp 1 chỉ đi dc max 5 người

nhóm 1 dư 1 người, 1 người dư đi 1 mình ở hộp thứ 2

tiếp đến nhóm 2 5 người đi hết vào hộp 3

tổng số nguoi đã chở của vòng quay đầu tiên của mỗi hộp là
5
1      
5

vòng quay thứ 2 còn nhóm thứ 3 là 3 người
 =>> đi hộp 1


=>> out put
tổng số người mỗi hộp đã chở cả 2 vòng đu quay lần lượt là
8
1
5

e có bài thuật toán này, thím nào giải hộ e bằng javascript với

ngoctan_95 · 24/8/22

Kân team v3 đã nói:
xài pow(double, double) là nó xài e^x gì đấy, nếu nói log(x) O(1) thì exp(x) cũng O(1)

a^b = x
log(a^b) = log(x)
b*log(a) = log(x)
e^(b*log(a)) = e^(log(x))
e^(b*log(a)) = x
e^(b*log(a)) = a^b

-> pow(double a, double b) thực chất xài e^(b*log(a))

Bac xai cao cap qua, em xai co ban thoi

n< 0 => false
n/3 cho toi khi n%3 !=0
return n co == 1 hay khong la duoc roi

nhoccoi96vp · 24/8/22

Lập Trình Viên Số Khổ đã nói:

Python:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
      
        for i in range(20):
            if 3**i == n:
                return True
      
        return False

Python:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n == 1:
            return True

        if n <= 0:
            return False

        while n % 3 == 0:
            n //= 3
            if n == 1:
                return True
            if n % 3 != 0 or n == 0:
                return False

        return False

Follow up: Could you solve it without loops/recursion? thím ơi

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

Senior Member

Member

Đã tốn tiền

Senior Member

Junior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Đã tốn tiền

Đã tốn tiền

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Senior Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này