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

bkhoang said:
em xin lỗi các thầy dạy DSA và tin đại cương :( giờ cứ tree với bitwise là em đọc solution :(
C#: 
public class Solution {
    public int SubsetXORSum(int[] nums) {
        int or = 0;

        foreach (int num in nums)
        {
            or |= num;
        }

        return or << (nums.Length - 1);
    }
}
Click to expand...
Cần gì phức tạp đâu fency, không biết nhiều về bitwise thì cứ backtrack generate ra hết subsets rồi tính từng cái 1. Từ cái đó rồi optimize tiếp
JavaScript: 
function subsetXORSum(nums: number[]): number {
    let res: number[][] = [], n = nums.length
    const backtrack = (idx: number, cur: number[], curIdx: number) => {
        if (cur.length === curIdx) {
            res.push([...cur]);
            return;
        }

        for (let i = idx; i < n; i++) {
            cur.push(nums[i]);
            backtrack(i + 1, cur, curIdx)
            cur.pop();
        }
    }

    const cal = (arr: number[]) => {
        if (arr.length === 0) return 0;
        let temp = arr[0];
        for (let i = 1; i < arr.length; i++) temp^= arr[i];
        return temp;
    }
    for (let k = 0; k < n + 1; k++) backtrack(0, [], k);
    let ans = 0;
    for (const num of res) ans+= cal(num);
    return ans;
};
 
Em mới bước vào con đường cày cuốc, mấy bác cho em hỏi mình submit sai nhiều lần có bị ảnh hưởng gì ko mấy bác nhỉ?
 
Mấy bài về bit manipulation toàn nhìn vào pattern, hên thì nhìn ra pattern ko hên thì chịu. Thôi xài backtracking cho lành
Python: 
class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        n = len(nums)
        total = 0
        for i in range(2**n):
            current = 0
            for j in range(n):
                if i >> j & 1 == 1:
                    current ^= nums[j]
            
            total += current

        return total
 
Ủa mà sao bài subsets là Medium mà bài này lại là Easy ta
JavaScript: 
var subsetXORSum = function (nums) {
    let backtrack = function (i, xor) {
        if (i === nums.length) {
            res += xor;
            return;
        }
        xor ^= nums[i];
        backtrack(i + 1, xor);
        xor ^= nums[i];
        backtrack(i + 1, xor);
    }
    let res = 0;
    backtrack(0, 0);
    return res;
}
 
Java: 
class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length;
        int c = 0, max = 0;
        for (int num : nums) {
            c |= num;
            max = Math.max(max, num);
        }
        int length = Integer.toBinaryString(max).length();
        int res = 0;
        for (int i = 0; i < length; i++) {
            int mask = 1 << i;
            res += ((mask & c) == 0) ? 0 : 1 << (n - 1 + i);
        }
        return res;
    }
}

Xét các bit tại vị trí đầu tiên
Dễ nhận thấy 1 ^ 1 ^ .... 1 ^ 0 ^ .... ^ 0 bằng 1 khi và chỉ khi có lẻ các bit 1, bao nhiêu bit 0 không quan trọng
Có n bit, giả sử là k bit 1 (k > 0), và n - k bit 0
Khi đó ta sẽ tính xem có bao nhiêu tổ hợp mà kết quả xor all trả về = 1 (giá trị 0 tất nhiên không cần quan tâm)
Có bao nhiêu cách chọn lẻ các bit 1 ?
( 1Ck + 3Ck + 5Ck +...+ (k-x)Ck ) = 2^(k - 1) (x = 1 nếu k chẵn, 0 nếu k lẻ)
Các bit 0 có thể chọn bao nhiêu tuỳ thích : 2 ^ (n - k) cách chọn
=> có 2^(k-1) * 2^(n-k) = 2^(n-1) tổ hợp mà giá trị xor all = 1
To be continued...
 
Last edited:
Python: 
class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        xor_arr = [0]
        for num in nums:
            tmp_xor = [xor ^ num for xor in xor_arr]
            xor_arr += tmp_xor
        return sum(xor_arr)
 
ngoi lên sau 2 hôm bài khó, bài hôm nay phải medium chứ easy gì nhỉ
jKMNvAf.gif

C#: 
public class Solution {
    public static int result = 0;

    public int CalculateXOR(int[] nums)
    {
        int temp = 0;
        for(int i = 0; i<nums.Length; i++)
        {
            temp ^= nums[i];
        }
        return temp;
    }

    public void BackTrack(int[] nums, int[] temp, int k, int n, int start)
    {
        for(int i = start; i < nums.Length-n+k+1; i++)
        {
            temp[k] = nums[i];
            if(k < n-1)
            {
                BackTrack(nums, temp, k+1, n, i+1);
            }
            if(k == n-1)
            {
                result += CalculateXOR(temp);
            }
        }
    }

    public int SubsetXORSum(int[] nums) {
        result = 0;
        for(int i = 1; i<=nums.Length; i++)
        {
            int[] temp = new int[i];
            BackTrack(nums, temp, 0, i, 0);
        }
        return result;
    }
}
 
Code: 
impl Solution {
    pub fn subset_xor_sum(nums: Vec<i32>) -> i32 {
        let n = nums.len();

        let mut sum = 0;

        for k in 1..=n {
            sum += Self::subsequences(&nums, k);
        }

        sum
    }

    fn subsequences(sequence: &[i32], k: usize) -> i32 {
        if k == 0 || k > sequence.len() {
            return 0;
        }

        Self::subsequences_helper(sequence, k, 0)
    }

    fn subsequences_helper(sequence: &[i32], remaining: usize, acc: i32) -> i32 {
        if remaining == 0 {
            return acc;
        }

        let mut sum = 0;

        for i in 0..=(sequence.len() - remaining) {
            sum += Self::subsequences_helper(&sequence[(i + 1)..], remaining - 1, acc ^ sequence[i]);
        }

        sum
    }
}
 
có nên luyện kỹ bit manipulation ko nhỉ, thấy dạo này tần suất ra dạng này nhiều quá, mấy bác pvan nhiều cho e hỏi OA với live code có bh gặp mấy bài bit này ko
 
LmaoSuVuong said:
có nên luyện kỹ bit manipulation ko nhỉ, thấy dạo này tần suất ra dạng này nhiều quá, mấy bác pvan nhiều cho e hỏi OA với live code có bh gặp mấy bài bit này ko
Click to expand...
Hên xui đó bác. nên luyện cho biết vì live code bạn mình apply Bytedance từng gặp một bài dùng bit manipulation để giải rồi :v
 
Python: 
class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for mask in range(1, 1 << n):
            currentXor = 0
            for i in range(n):
                if (mask >> i) & 1:
                    currentXor ^= nums[i]
            ans += currentXor
        return ans
 
Python: 
class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        bits = 0
        # Finding bitwise OR of all elements
        for i in range(len(nums)):
            bits |= nums[i]
    
        ans = bits * pow(2, len(nums)-1)
    
        return ans
 
Python: 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for e in nums:
            res += [sub + [e] for sub in res]
        return res

Python: 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return [[]]
        x = self.subsets(nums[1:])
        return x + [[nums[0]] + y for y in x]
 
Code: 
impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let n = nums.len();
        let mut results = vec![];

        for i in 0..=n {
            results.append(&mut Self::subsequences(&nums, i));
        }

        results
    }

    fn subsequences(sequence: &[i32], k: usize) -> Vec<Vec<i32>> {
        let mut results = vec![];

        Self::subsequences_helper(sequence, k, &mut vec![0; k], &mut results);

        results
    }

    fn subsequences_helper(sequence: &[i32], remaining: usize, holder: &mut Vec<i32>, acc: &mut Vec<Vec<i32>>) {
        if remaining == 0 {
            acc.push(holder.clone());

            return;
        }

        for i in 0..=(sequence.len() - remaining) {
            holder[remaining - 1] = sequence[i];

            Self::subsequences_helper(&sequence[(i + 1)..], remaining - 1, holder, acc);
        }
    }
}
 
C++: 
class Solution {
public:
    void backtrace(int cur, vector<int> &vCur,vector<vector<int>> &vRe, vector<int>& nums)
    {
        vRe.push_back(vCur);
        while(cur<nums.size())
        {
            vCur.push_back(nums[cur]);
            cur++;
            backtrace(cur,vCur,vRe,nums);
            vCur.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> vRe;
        vector<int> vCur;
        backtrace(0,vCur,vRe,nums);
        return vRe;
    }
};
 

Similar threads

Duy1122
kiến thức Phân biệt Encrypt và Hashing
Replies
15
Views
841
langdangbendoi
langdangbendoi
Xuan Ha Thu Dong
thảo luận [Review] Cuộc sống và công việc Dev ở Hà Lan. Làm thế nào để tìm việc ở HL và châu Âu nói chung?
4 5 6
Replies
108
Views
9K
asklyking
asklyking
hatayquelua
thắc mắc Cần kiến thức gì để được nhận thực tập Dev
3 4 5
Replies
87
Views
5K
BaoC3H1
BaoC3H1
freezer0604
  • Locked
Động lực để 'phượt' mỗi ngày gần 30, 40 km đến công ty làm việc
13 14 15
Replies
288
Views
20K
yb123123
yb123123
MasterchiefsReborn
Tác dụng bất ngờ của việc đi chân trần mỗi ngày
Replies
18
Views
1K
Nacuto
Nacuto

Share this page

Back
Top