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

___Cyber___ · 22/8/24

PHP:

class Solution {

    /**
     * @param Integer $num
     * @return Integer
     */
    function findComplement($num) {
        $bin = decbin($num); // get bits
        $binLength = strlen($bin);

        $binFlip = "";
        for ($i=0; $i<$binLength; $i++) {
            $binFlip .= ($bin[$i]) ? '0' : '1';
        }

        return bindec($binFlip);
    }
}

Fzen · 22/8/24

Java:

public int findComplement(int n) {
    StringBuilder complement = new StringBuilder();
    while (n > 0) {
        int lastBit = n % 2;
        complement.append(lastBit == 0 ? '1' : '0');
        n /= 2;
    }
    return Integer.parseInt(complement.reverse().toString(), 2);
}

Takeitiz · 22/8/24

Bài hôm nay trừ cách tạo ra bitmask toàn 11111 để xor với số ra thì em nghĩ dùng toán cũng giải được nhanh. Vì tổng của num và nghịch bit của num là một số nhị phân toàn 1111 hay viết dưới dạng công thức là 2^0 + 2^1 +.... Thế nên là ta cứ việc duyệt i từ 0 đến 31 rồi cộng 2^i đến khi lớn hơn hoặc bằng số num ban đầu, kết quả đấy chính là tổng của num và nghịch của num. O(1) time và space.

i-am-groot · 22/8/24

Python:

class Solution:
    def findComplement(self, num: int) -> int:
        ans = 0
        for c in bin(num)[2:]:
            ans = 2 * ans + (1 - int(c))
        return ans

chiyeuemthoi · 22/8/24

Mã:

class Solution:
    def findComplement(self, num: int) -> int:
        binary = bin(num)[2:]
        res = ""
        for c in binary:
            res += "1" if c == '0' else "0"
        return int(res , 2)

LmaoSuVuong · 22/8/24

Takeitiz đã nói:
Bài hôm nay trừ cách tạo ra bitmask toàn 11111 để xor với số ra thì em nghĩ dùng toán cũng giải được nhanh. Vì tổng của num và nghịch bit của num là một số nhị phân toàn 1111 hay viết dưới dạng công thức là 2^0 + 2^1 +.... Thế nên là ta cứ việc duyệt i từ 0 đến 31 rồi cộng 2^i đến khi lớn hơn hoặc bằng số num ban đầu, kết quả đấy chính là tổng của num và nghịch của num. O(1) time và space.

Mã:

class Solution {
    public int findComplement(int n) {
        int offset = 1;
        int bit =1;
        while(offset<n){
            bit*=2;
            offset+=bit;
        }
        return offset-n;
    }
}

cách giải rất hay

vicejuniordev · 22/8/24

Takeitiz đã nói:
Bài hôm nay trừ cách tạo ra bitmask toàn 11111 để xor với số ra thì em nghĩ dùng toán cũng giải được nhanh. Vì tổng của num và nghịch bit của num là một số nhị phân toàn 1111 hay viết dưới dạng công thức là 2^0 + 2^1 +.... Thế nên là ta cứ việc duyệt i từ 0 đến 31 rồi cộng 2^i đến khi lớn hơn hoặc bằng số num ban đầu, kết quả đấy chính là tổng của num và nghịch của num. O(1) time và space.

Đều là O(1) vì < 32 loop nhưng không nhanh hơn flip bit đâu người anh em. Mình làm cách lấy mũ 2, chạy hết 40ms. Chuyển sang flip bit có 33 34ms thôi

Takeitiz · 22/8/24

vicejuniordev đã nói:
Đều là O(1) vì < 32 loop nhưng không nhanh hơn flip bit đâu người anh em. Mình làm cách lấy mũ 2, chạy hết 40ms. Chuyển sang flip bit có 33 34ms thôi

Xem tệp đính kèm 2643221

Em đưa ra cách mà em thấy nó hay hay để mọi người đánh giá xem có ổn không thôi ạ. Còn chạy thực tế trên leetcode này runtime nó cứ lỏ lỏ kiểu gì đấy anh.

vicejuniordev · 22/8/24

Takeitiz đã nói:
Xem tệp đính kèm 2643225
Em đưa ra cách mà em thấy nó hay hay để mọi người đánh giá xem có ổn không thôi ạ. Còn chạy thực tế trên leetcode này runtime nó cứ lỏ lỏ kiểu gì đấy anh.

Mình đồng ý mà, ý mình chỉ bổ sung là vẫn chậm hơn bitmask thôi.
Cá nhân mình cũng thấy cách dùng math đơn thuần dễ hiểu hơn. Kiểu mình convert từ decimal ra bit xong convert lại từ bit qua decimal. Cách đó phù hợp nhất với người ít làm bitmask, vì chỉ cần kiến thức basic nhất là convert cũng đủ làm rồi (không cần XOR vs shift bit) lại còn O(1). Không hiểu sao Editorial lại không có cách này.

via theNEXTvoz for iPhone

Takeitiz · 22/8/24

vicejuniordev đã nói:
Mình đồng ý mà, ý mình chỉ bổ sung là vẫn chậm hơn bitmask thôi.
Cá nhân mình cũng thấy cách dùng math đơn thuần dễ hiểu hơn. Kiểu mình convert từ decimal ra bit xong convert lại từ bit qua decimal. Cách đó phù hợp nhất với người ít làm bitmask, vì chỉ cần kiến thức basic nhất là convert cũng đủ làm rồi (không cần XOR vs shift bit) lại còn O(1). Không hiểu sao Editorial lại không có cách này.

via theNEXTvoz for iPhone

Em nhìn lại thì đúng là là vẫn chậm hơn thật, mấy phép tính như dịch bit với xor xử lý nhanh hơn phép cộng với nhân hơn.

Thầy ông cố nội · 22/8/24

JavaScript:

var findComplement = function(num) {
    const bin = [];
    while (num > 0) {
        bin.push(num % 2);
        num = Math.floor(num / 2);
    }

    let ans = 0;
    let power = 1;
    let i = 0;
    while (i < bin.length) {
        ans += (1 - bin[i++]) * power;
        power *= 2;
    }
    return ans;
};

thanhdonguyen01 · 22/8/24

C++:

class Solution {
public:
    int findComplement(int num) {
        return num ^ ((1U << (31 - __builtin_clz(num) + 1)) - 1);
    }
};

Phó GOAT · 22/8/24

Java:

class Solution {
    public int findComplement(int num) {
        int n = 1;
        while (n < num) {
            n = (n << 1) + 1;
        }
        return n ^ num;
    }
}

small-lambda · 22/8/24

C-like:

impl Solution {
    pub fn find_complement(num: i32) -> i32 {
        let mut mask = 1 << 31;
        let neg_num = !(num as u32);
        let mut msbi = 31;

        while (mask & neg_num) != 0 && mask != 0 {
            msbi -= 1;
            mask >>= 1;
        }

        let neg_mask = (1 << (msbi + 1)) - 1;

        (neg_mask & neg_num) as i32
    }
}

C-like:

impl Solution {
    pub fn find_complement(num: i32) -> i32 {
        let mut mask = 1 << 31;
        let neg_num = !(num as u32);
        let mut msbi = 31;

        while (mask & neg_num) != 0 && mask != 0 {
            msbi -= 1;
            mask >>= 1;
        }

        let d = (31 - msbi);

        ((neg_num << d) >> d) as i32
    }
}

C-like:

impl Solution {
    pub fn find_complement(num: i32) -> i32 {
        ((1 << 32 - num.leading_zeros()) - 1) ^ num
    }
}

Người quan sát cô đơn · 22/8/24

basic math :doubt:

Java:

class Solution {
    public int findComplement(int num) {
        int n = (int) (Math.log(num)/Math.log(2));
        int sum = (int) (Math.pow(2,n+1)-1);
        return sum - num;
    }
}

freedom.9 · 22/8/24

Người quan sát cô đơn đã nói:
basic math

Java:

class Solution { public int findComplement(int num) { int n = (int) (Math.log(num)/Math.log(2)); int sum = (int) (Math.pow(2,n+1)-1); return sum - num; } }

Đã xài log rồi còn 0(1)

via theNEXTvoz for iPhone

Người quan sát cô đơn · 22/8/24

freedom.9 đã nói:
Đã xài log rồi còn 0(1)

via theNEXTvoz for iPhone

Thế chẳng lẽ là O(logN) :oh:

Nhưng e nhìn trong đống này đâu có for hay while gì đâu ta :ops:

jdk/src/share/native/java/lang/fdlibm/src/e_log.c at jdk8u/jdk8u/master · openjdk-mirror/jdk

Single git repo mirroring a myriad of mercurial jdk repos - openjdk-mirror/jdk

github.com

Cố Trường Ca · 22/8/24

Người quan sát cô đơn đã nói:
Thế chẳng lẽ là O(logN) Nhưng e nhìn trong đống này đâu có for hay while gì đâu ta

jdk/src/share/native/java/lang/fdlibm/src/e_log.c at jdk8u/jdk8u/master · openjdk-mirror/jdk

Single git repo mirroring a myriad of mercurial jdk repos - openjdk-mirror/jdk

github.com

Chưa viết hàm pow bao giờ hả fen

Người quan sát cô đơn · 22/8/24

Cố Trường Ca đã nói:
Chưa viết hàm pow bao giờ hả fen

Hàm for thì ai chả viết r nhưng Math lib trong java nó có viết kiểu thế đâu :ops:

Cố Trường Ca · 22/8/24

Người quan sát cô đơn đã nói:
Hàm for thì ai chả viết r nhưng Math lib trong java nó có viết kiểu thế đâu

làm gì còn cách nào khác
À mới xem lại, có vẻ cũng không dùng vòng lặp, cố mỗ ta xin thứ tội, là ta học không bằng người

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

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này