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

freedom.9 · 19/10/24

Bài này cho recursive sai vl, 2^20 - 1 mà gen hết ra list thì sẽ bị MLE ngay. Hèn gì AC cao thế

nchhnchh · 19/10/24

Python:

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def invert(s):
            return ''.join(['0' if c == '1' else '1' for c in s])
        
        @lru_cache(None)
        def genBinaryString(i):
            if i == 1:
                return "0"
            return genBinaryString(i-1) + "1" + invert(genBinaryString(i-1))[::-1]
        
        s = genBinaryString(n)
        return s[k-1]

mrsimonle · 19/10/24

Để ý thấy binary string luôn đối xứng qua bit ở giữa.

Mã:

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n == k == 1:
            return "0"
       
        binStrLen = pow(2, n) - 1
        l = 0
        r = binStrLen - 1

        nextBit = 1
        while l <= r:
            pivot = (l + r) // 2

            if pivot == k - 1:
                return str(nextBit)
            elif pivot > k - 1:
                r = pivot - 1
                nextBit = 1
                if r == l:
                    nextBit = 0
            else:
                l = pivot + 1
                nextBit = 0
                if r == l:
                    nextBit = 1

        return "0"

LmaoSuVuong · 19/10/24

Java:

class Solution {
    public char findKthBit(int n, int k) {
        if(n==1) return '0';
        int len = (int)Math.pow(2,n-1);
        //System.out.println(len);
        if(k==len) return '1';
        if(k>len)
        {
            return findKthBit(n-1,2*len-k)=='0'?'1':'0';
        }
        return findKthBit(n-1,k);
    }
}

freedom.9 · 19/10/24

Tìm điểm đối xứng qua vị trí middle, phần cuối chắc optimize đc mà xỉn quá rồi mai sửa :ah:

Python:

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        flips = 0
        length = (1 << n) - 1
        while k > 1:
            mid = length//2 + 1
            if k == mid:
                return str(1^flips)
            elif k > mid:
                k -= 2*(k - mid)
                flips ^= 1
            
            length//=2
        return str(flips^0)
[/SPOILER]

Konstante · 19/10/24

C++:

class Solution {
private:
    bool findbit(int n, int k, bool b) {
        if (k == 1 || n == 1) return !b;
        auto c = 1 << (n - 1);
        if (k < c) return findbit(n - 1, k, b);
        else if (k == c) return b;
        else return findbit(n - 1, (1 << n) - k, !b);
    }
public:
    char findKthBit(int n, int k) {
        return findbit(n, k, true) ? '1' : '0';
    }
};

Kroosm4 · 19/10/24

Lâu rồi mới làm lại :beated:

C#:

    public char FindKthBit(int n, int k) {
        int mid = (int)Math.Pow(2, n - 1);
        if (k == mid)
        {
            return n == 1 ? '0' : '1';
        }

        if (k < mid)
        {
            return FindKthBit(n - 1, k);
        }

        return FindKthBit(n - 1, 2 * mid - k) == '1' ? '0' : '1';
    }

seichan502 · 19/10/24

Aluminum21 đã nói:
Leetcode có vẻ mới update compiler hay gì, C# trước giờ không bao giờ có runtime 0ms kể cả chạy 2 case cơ bản mà qua giờ được hơi nhiều. ae tranh thủ lấy 100% để gáy nào.

C#:

public class Solution { public char FindKthBit(int n, int k) { List<char> result = new(); result.Add('0'); Recursive(result, 1, n); return result[k - 1]; } public void Recursive(List<char> currentS, int ith, int n) { if (ith == n) { return; } int from = currentS.Count - 1; currentS.Add('1'); for (int i = 0; i <= from; i++) { char c = currentS[from - i]; currentS.Add(c == '1' ? '0' : '1'); } Recursive(currentS, ith + 1, n); } }

Công nhận làm recursion naiive luôn mà beat 100% với C#, nó tính sai runtime hay sao ấy

LmaoSuVuong · 19/10/24

seichan502 đã nói:
Công nhận làm recursion naiive luôn mà beat 100% với C#, nó tính sai runtime hay sao ấy

n <= 20 thôi mà bác, chạy có vài phép tính

garanphomai · 19/10/24

Java:

class Solution {
    public char findKthBit(int n, int k) {
        StringBuilder sb = new StringBuilder();
        sb.append('0');

        int len = sb.length();
        n--;

        while (n > 0 && k > len) {
            sb.append('1');

            for (int i = len - 1; i >= 0; i--) {
                if (sb.charAt(i) == '1')
                    sb.append('0');

                else
                    sb.append('1');
            }

            len = sb.length();
            n--;
        }

        return sb.charAt(k - 1);
    }
}

Đoán là có cách tối ưu mà k nghĩ ra được => đọc sol cũng chưa hiểu lắm :big_smile:

Tinh Hoa Đông Lào · 19/10/24

selune.nashor đã nói:

Python:

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        r = 0
        while True:
            if n == 1:
                return '1' if r%2==1 else '0'
            if k == 1:
                return '1' if r%2==1 else '0'
            if k == 2**n-1:
                return '0' if r%2==1 else '1'
            if k == 2**(n-1):
                return '0' if r%2==1 else '1'
            if k > 2**(n-1):
                k = 2**n-k
                r+=1
            n-=1

Xem tệp đính kèm 2741468

giai thich cach lam di bac

LmaoSuVuong · 19/10/24

garanphomai đã nói:

Java:

class Solution {
    public char findKthBit(int n, int k) {
        StringBuilder sb = new StringBuilder();
        sb.append('0');

        int len = sb.length();
        n--;

        while (n > 0 && k > len) {
            sb.append('1');

            for (int i = len - 1; i >= 0; i--) {
                if (sb.charAt(i) == '1')
                    sb.append('0');

                else
                    sb.append('1');
            }

            len = sb.length();
            n--;
        }

        return sb.charAt(k - 1);
    }
}

Đoán là có cách tối ưu mà k nghĩ ra được => đọc sol cũng chưa hiểu lắm :big_smile:

Tinh Hoa Đông Lào đã nói:
giai thich cach lam di bac

làm ngược lại thao tác của đề bài, xem thằng k đó từ số nào biến thành

thanbaiks · 19/10/24

lần đầu 0ms

JavaScript:

const len = _.memoize((n) => {
    if (n === 1) {
        return 1;
    }
    return len(n-1) << 1 | 1;
});
/**
 * @param {number} n
 * @param {number} k
 * @return {character}
 */
var findKthBit = function(n, k) {
    if (n === 1) {
        return '0';
    }
    const l = len(n);
    if (k << 1 === l + 1) {
        return '1';
    } else if (k << 1 < l + 1) {
        return findKthBit(n-1, k);
    } else {
        return String(1 ^ findKthBit(n-1, l+1-k));
    }
};

hoangi19 · 19/10/24

sao nay ai cx 100% beats thế ko gáy dc

C++:

class Solution {
public:
    int findK(int lenN, int k) {
        if (lenN <= 2) {
            return k-1;
        }
        int mid = lenN/2 + 1;
        if (k == mid) return 1;
        if (k > mid) return 1 - findK(mid-1, 2*mid - k);
        return findK(mid-1, k);
    }

    char findKthBit(int n, int k) {
        int lenN = 1;
        while(lenN < k) {
            lenN = 2*(lenN) + 1;
        }
        return findK(lenN, k) ? '1' : '0';
    }
};

retarded_user · 19/10/24

Java:

class Solution {
    public char findKthBit(int n, int k) {
        StringBuilder sb = new StringBuilder("0");       

        for (int i = 2; i <= n; i++) {
            StringBuilder reverseAndInvertStr = invert(sb).reverse();
            sb.append("1").append(reverseAndInvertStr);
        }
        
        return sb.charAt(k - 1);
    }

    private StringBuilder invert(StringBuilder str) {
        StringBuilder res = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                res.append('1');
            } else {
                res.append('0');
            }
        }

        return res;
    }
}

behitek · 19/10/24

Mã:

class Solution:
    @staticmethod
    def revinv(s: str):
        res = ""
        for i, x in enumerate(s):
            if x == "0":
                res += "1"
            else:
                res += "0"
        return res[::-1]
    @staticmethod
    def nthBit(n: int) -> str:
        if n == 1:
            return "0"
        prev = Solution.nthBit(n - 1)
        return prev + "1" + Solution.revinv(prev)
    
    def findKthBit(self, n: int, k: int) -> str:
        s = Solution.nthBit(n)   
        return s[k-1]

analogy.2 · 19/10/24

C-like:

impl Solution {
    pub fn find_kth_bit(n: i32, k: i32) -> char {
        if k % 4 == 1{
            return '0';
        }
        if k % 4 == 3{
            return '1';
        }
        let mut kmut = k;
        while kmut%2 ==0{
            kmut >>= 1;
        }
        if kmut % 4 == 1{
            return '1';
        }
        '0'
    }
}

Phó GOAT · 19/10/24

Java:

class Solution {
    public char findKthBit(int n, int k) {
        if (n == 1) return '0';
        int len = (int) Math.pow(2, n);
        if (k < len / 2) return findKthBit(n - 1, k);
        else if (k == len / 2) return '1';
        else {
            char correspondingBit = findKthBit(n - 1, len - k);
            return (correspondingBit == '0') ? '1' : '0';
        }
    }
}

Xem sol

noobdev · 19/10/24

Phó GOAT đã nói:
Java:

class Solution { public char findKthBit(int n, int k) { if (n == 1) return '0'; int len = (int) Math.pow(2, n); if (k < len / 2) return findKthBit(n - 1, k); else if (k == len / 2) return '1'; else { char correspondingBit = findKthBit(n - 1, len - k); return (correspondingBit == '0') ? '1' : '0'; } } }

Xem sol

Má nó bài này chủ quan code 2^n thế ếu nào vẫn pass :beat_brick:

kangtk · 19/10/24

JavaScript:

function findKthBit(n: number, k: number): string {
    let currentLength = 1;
    let s = '0'
    while (n > 0) {
        if (k <= currentLength) {
            return s[k - 1]
        }
        if (k === currentLength + 1) {
            return '1'
        }
        const nextLength = (currentLength << 1) + 1;
        if (k <= nextLength) {
            let dif = nextLength - k;
            const toFlip = s[dif]
            return toFlip === '0' ? '1' : '0'
        } else {
            currentLength = nextLength;
            s = s + '1' + revert(s)
        }
        n--
    }
};

function revert(s: string) {
    let result = ''
    for (const ss of s) {
        if (ss === '0') {
            result = '1' + result
        } else {
            result = '0' + result
        }
    }
    return result;
}

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

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này