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

noobdev · 8/11/24

Python:

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        mask = 2**maximumBit - 1
        xor = nums[0]
        n = len(nums)
        res = []
        for i in range(1, n):
            xor ^= nums[i]
        for i in range(n-1,-1,-1):
            res.append(xor ^ mask)
            xor ^= nums[i]
        return res

Husqvarna701SM · 8/11/24

freedom.9 đã nói:

Bài này AC hơi cao hư cấu nhỉ, nhưng mà làm quen bit manipulation cũng không khó lắm

Python:

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        n = len(nums)
        xOr = 0
        for num in nums:
            xOr = xOr ^ num
    
        maxK = 2**maximumBit
        ans = []
        for i in range(n - 1, -1, -1):
            current = 0
            currentK = maxK
            for j in range(32, -1, -1):
                if xOr >> j & 1 == 0 and 1 << j < currentK:
                    currentK -= 1 << j
                    current |= 1 << j

            ans.append(current)
            xOr ^= nums[i]
        return ans

Python:

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        n = len(nums)
        xOr = 0
        for num in nums:
            xOr = xOr ^ num
     
        maxK = (1 << maximumBit) - 1
        ans = [0]*n
        for i in range(n - 1, -1, -1):
            ans[n - i - 1] = maxK ^ xOr
            xOr ^= nums[i]
         
        return ans

=> Đã hiểu lí do, thế mà ko nghĩ ra cách đơn giản thế nghĩ hơi phức tạp

Để lớn nhất thì cần tìm số bù của prefixXor thoai

Husqvarna701SM · 8/11/24

noobdev đã nói:
Bài hôm nay éo hiểu cho cái sorted property vào làm cái gì? lừa nhau à

Thì nay bài này có hai điều kiện sort với nhỏ hơn 2^ maxbit đều nhảm mà

freedom.9 · 8/11/24

Mắt Xích Yếu đã nói:
0 <= nums < 2maximumBit

Lúc đầu mình code ko nhìn cái constrain này đó fen, nên cách của mình đúng cho mọi nums < 2*32 đó

freedom.9 · 8/11/24

Husqvarna701SM đã nói:
Thì nay bài này có hai điều kiện sort với nhỏ hơn 2^ maxbit đều nhảm mà

Nếu nums bất kì thì cái cách xor với 2**max - 1 ko đúng. Phức tạp hơn
Nên nhìn cái solution mình ko hiểu tại sao nó đúng cho tới khi nhìn tới cái constrain

noobdev · 8/11/24

freedom.9 đã nói:
Nếu nums bất kì thì cái cách xor với 2**max - 1 ko đúng. Phức tạp hơn
Nên nhìn cái solution mình ko hiểu tại sao nó đúng cho tới khi nhìn tới cái constrain

chứng minh kiểu gì thế bác?

LmaoSuVuong · 8/11/24

noobdev đã nói:
chứng minh kiểu gì thế bác?

a xor b =c <-> b = a xor c

Husqvarna701SM · 8/11/24

freedom.9 đã nói:
Nếu nums bất kì thì cái cách xor với 2**max - 1 ko đúng. Phức tạp hơn
Nên nhìn cái solution mình ko hiểu tại sao nó đúng cho tới khi nhìn tới cái constrain

Nums bất kỳ thì thím xor với max INT xong lấy và với 2<<max -1 thôi.
Nói chung bài này constrain làm cho tính toán bit dễ hơn nhiều roài. Mình toàn làm r mới soi constraint =))

)

XzhaoyunX · 8/11/24

Python:

class Solution(object):
    def getMaximumXor(self, nums, maximumBit):
        """
        :type nums: List[int]
        :type maximumBit: int
        :rtype: List[int]
        """
        res = []
        k = (1 << maximumBit) - 1
        xor_all = reduce(lambda x,y: x^y, nums)
        for i in range(len(nums)-1, -1, -1):

            res.append(xor_all ^ k)
            xor_all ^= nums[i]
        
        return res

lúc đầu không biết cứ tính lại xor_all sau mỗi lần xóa phần tử cuối, hóa ra chỉ cần xor với pt đó là xóa đc đi. a^a =0, x^0 = x => x^a = x ^a ^a

freedom.9 · 8/11/24

noobdev đã nói:
chứng minh kiểu gì thế bác?

Vì nếu 1 num < 2**bit thì ở mỗi phép xOr chỉ có thể flips được tối đa tất cả các bit về 1, nghĩa là 2**maxBit - 1. Vì phép toán XOR nó chỉ cho phép flip bit.
ví dụ 2**3 thì tối đa chỉ có thể tạo ra được 2**3 - 1 = 7
=> xOr^x = 2**maxBit - 1 với x là số cần tìm.
=> xOr^xOr^x = (2**maxBit - 1)^xOr => x = (2**maxBit - 1)^xOr

Còn nếu như nums là bất kì thì đầu tiên cần tính xOr của mảng, sau rồi flip xOr dần dần từ bit 0 lớn nhất của xOr vì việc flip bit 1 nó sẽ tạo ra 1 số nhỏ hơn. Mà để flip bit 0 lớn nhất của xOr thì cần 1 bit 1 ở vị trí đấy, nên mình chỉ việc so sánh (1 << i) < 2**k thì thêm cái bit 1 vô kết quả cuối cùng là xong.

Husqvarna701SM · 8/11/24

XzhaoyunX đã nói:
Python:

class Solution(object): def getMaximumXor(self, nums, maximumBit): """ :type nums: List[int] :type maximumBit: int :rtype: List[int] """ res = [] k = (1 << maximumBit) - 1 xor_all = reduce(lambda x,y: x^y, nums) for i in range(len(nums)-1, -1, -1): res.append(xor_all ^ k) xor_all ^= nums[i] return res

lúc đầu không biết cứ tính lại xor_all sau mỗi lần xóa phần tử cuối, hóa ra chỉ cần xor với pt đó là xóa đc đi. a^a =0, x^0 = x => x^a = x ^a ^a

Có thể tính prefix rồi lưu kết quả vào mảng ban đầu để trả về :big_smile:

boztche · 8/11/24

C++:

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int acc = 0;
        for (int n: nums) acc ^= n;

        int exclude = 0;
        vector<int> res;
        for (int i = nums.size() - 1; i >= 0; i--) {
            acc ^= exclude;

            int k = 0;
            int tmp = acc;
            for (int j = 0; j < maximumBit; j++) {
                if (tmp & 1)
                    k &= ~(1<<j);
                else
                    k |= (1<<j);
                tmp >>= 1;
            }
            res.push_back(k);

            exclude = nums[i];
        }

        return res;
    }
};

bkhoang · 8/11/24

mấy ngày ko vào thớt chơi, thím @Cố Trường Ca lại bay màu rồi à

Takeitiz · 8/11/24

Mấy bác nghĩ ra quả giải thuật hay thật, em làm là đếm số bit 1 ở từng vị trí, số k của mình phải thỏa mãn sao cho tổng số bit 1 ở từng vị trí luôn là số lẻ là được.

LmaoSuVuong · 8/11/24

Takeitiz đã nói:
Mấy bác nghĩ ra quả giải thuật hay thật, em làm là đếm số bit 1 ở từng vị trí, số k của mình phải thỏa mãn sao cho tổng số bit 1 ở từng vị trí luôn là số lẻ là được.

bài này có giải thật j đâu :shame:

max là 11111111-1 , numsxor ^ k = max thì k = max ^ numsxor thôi mà

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

Java:

class Solution {
    public int[] getMaximumXor(int[] nums, int maximumBit) {
        int n = nums.length;
        int[] prefix = new int[n+1];
        int[] res = new int[n];
        for(int i=0;i<n;i++){
            prefix[i+1] = prefix[i]^nums[i];
        }
        for(int i = n;i>0;i--){
            int c = prefix[i];
            int k = 0;
            while(k<maximumBit) {
                int x = (1- c & 1 ) << k;
                res[n- i] += (1 - c & 1) << k;
                c >>= 1;
                k++;
            }
        }
        return res;
    }
}

chết mẹ ko để ý 0 <= nums < 2maximumBit

Java:

class Solution {
    public int[] getMaximumXor(int[] nums, int maximumBit) {
        int n = nums.length;
        int currXor = 0;
        int[] res = new int[n];
        int max = (1<<maximumBit) -1;
        for(int i=0;i<n;i++){
            currXor^=nums[i];
            res[n-1-i] = currXor^max;
        }
        return res;
    }
}

nghia_tran_tuan · 8/11/24

Mã:

func getMaximumXor(nums []int, maximumBit int) []int {
    n := len(nums)
    result := make([]int, n)
    maxNum := (1 << maximumBit) - 1

    currXor := 0

    for i := range nums {
        currXor ^= nums[i]
    }

    for i := 0; i < n; i++ {
        k := currXor ^ maxNum
        result[i] = k

        if i < n-1 {
            currXor ^= nums[n-1-i]
        }

    }

    return result
}

Takeitiz · 8/11/24

LmaoSuVuong đã nói:
bài này có giải thật j đâu max là 11111111-1 , numsxor ^ k = max thì k = max ^ numsxor thôi mà

kém phần bit nên suy nghĩ nó tù thế đấy bác.

emyeumeonhatF17 · 8/11/24

Medium giả cầy.

Swift:

class Solution {
    func getMaximumXor(_ nums: [Int], _ maximumBit: Int) -> [Int] {
        let max = (1 << maximumBit) - 1
        var result:[Int] = []
        var xor = 0
        for num in nums {
            xor ^= num
            result.append(max^xor)
        }
        return Array(result.reversed())
    }
}

Husqvarna701SM · 8/11/24

Husqvarna701SM đã nói:
Nums bất kỳ thì thím xor với max INT xong lấy và với 2<<max -1 thôi.
Nói chung bài này constrain làm cho tính toán bit dễ hơn nhiều roài. Mình toàn làm r mới soi constraint )

Chỗ này chuẩn hơn nữa thì dùng -1 thay cho max INT :big_smile:

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

Member

Senior Member

Senior Member

Senior Member

Senior Member

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

Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này