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

  • Người tạo chủ đề Người tạo chủ đề _Gia_Cat_Luong_
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
Java: 
class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        int n = nums.length;
        int or = 0;
        int[] cur_state = new int[33];
       
        int i = 0;
        int l = 0;
        for (int r = 0; r < n; r++) {
            or |= nums[r];
            int num = nums[r];
            i = 0;
            while (num > 0) {
                cur_state[i++] += num & 1;
                num >>= 1;
            }

            if (or>=k) {
                while (l <= r && or>=k) {
                    int num_left = nums[l];
                    i = 0;
                    while (num_left > 0) {
                        cur_state[i] -= num_left & 1;
                        if(cur_state[i]==0){
                            or&=~(1<<i);//flip ith bit to 0
                        }
                        i++;
                        num_left >>= 1;
                    }
                    l++;
                }
                res = Math.min(res, r - l+ 2);
            }
        }
        return res==Integer.MAX_VALUE?-1:res;
    }
}
 
JavaScript: 
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumSubarrayLength = function (nums, k) {
    class C {
        constructor() {
            this.bits = Array(34).fill(0);
            this.val = 0;
        }
        add(n) {
            for (let i = 0; n; i++) {
                const v = 1 << i;
                if (n & v) {
                    this.bits[i]++;
                    this.val |= v;
                    n -= v;
                }
            }
        }
        remove(n) {
            for (let i = 0; n; i++) {
                const v = 1 << i;
                if (n & v) {
                    if (!--this.bits[i]) {
                        this.val -= v;
                    }
                    n -= v;
                }
            }
        }
    }
    const n = nums.length, c = new C();
    let ans = +Infinity;
    for (let i = 0, j = 0; i < n; i++) {
        c.add(nums[i]);
        while (j <= i && c.val >= k) {
            ans = Math.min(ans, i - j + 1);
            c.remove(nums[j++]);
        }
    }
    return Number.isFinite(ans) ? ans : -1;
};
 
Bo_MinhAnh đã nói:
LC 3097 Java
Java: 
class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int MV = 200002, rs = MV, x = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= k) return 1;
            x |= nums[i];
            if (x >= k) {
                int j = i;
                for (int t = nums[i]; t < k; t |= nums[j]) { j--; }
                rs = Math.min(rs, i - j + 1);
                j++;
                x = nums[j];
                i = j;
            }
        }
        return rs < MV ? rs : -1;
    }
}
Nhấp để mở rộng...
Không nhầm thì là O(n^2)
 
thanks for your comment.
Mình chép sol từ đâu đó trên mạng, đoán chừng là amortized O(N) ~ linear :D .

Edited: Mới thử cách trên của fan
thanbaiks đã nói:
JavaScript: 
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumSubarrayLength = function (nums, k) {
    class C {
        constructor() {
            this.bits = Array(34).fill(0);
            this.val = 0;
        }
        add(n) {
            for (let i = 0; n; i++) {
                const v = 1 << i;
                if (n & v) {
                    this.bits[i]++;
                    this.val |= v;
                    n -= v;
                }
            }
        }
        remove(n) {
            for (let i = 0; n; i++) {
                const v = 1 << i;
                if (n & v) {
                    if (!--this.bits[i]) {
                        this.val -= v;
                    }
                    n -= v;
                }
            }
        }
    }
    const n = nums.length, c = new C();
    let ans = +Infinity;
    for (let i = 0, j = 0; i < n; i++) {
        c.add(nums[i]);
        while (j <= i && c.val >= k) {
            ans = Math.min(ans, i - j + 1);
            c.remove(nums[j++]);
        }
    }
    return Number.isFinite(ans) ? ans : -1;
};
Nhấp để mở rộng...
Chạy thử thấy time 100% (~ 85ms) ?
 
Sửa lần cuối:
Lâu lâu ngoi lên được 1 cặp 100%, gáy phát8-)
C#: 
public class Solution
{
    public int MinimumSubarrayLength(int[] nums, int k)
    {
        int or = 0;
        int left = 0;
        
        int result = int.MaxValue;
        int[] bitCount = new int[32];
        for (int right = 0; right < nums.Length; right++)
        {
            or |= nums[right];
            Include(bitCount, nums[right]);
            while (k <= or && left <= right)
            {
                or = Exclude(bitCount, nums[left]);
                result = Math.Min(result, right - left + 1);
                left++;
            }
        }
        
        return result == int.MaxValue ? -1 : result;
    }

    private void Include(int[] bitCount, int include)
    {
        for (int i = 0; i < 32; i++)
        {
            bitCount[i] += (include & 1) == 1 ? 1 : 0;
            include >>= 1;
        }
    }

    private int Exclude(int[] bitCount, int excluded)
    {
        int result = 0;
        for (int i = 0; i < 32; i++)
        {
            bitCount[i] -= (excluded & 1) == 1 ? 1 : 0;
            excluded >>= 1;
            int set = bitCount[i] == 0 ? 0 : 1;
            result |= set << i;
        }

        return result;
    }
}

1731216125773.png
 
Java: 
class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int l = 0, r = 0;
        int minLen = Integer.MAX_VALUE;
        int or = 0;
        int[] bits  = new int[32];
        if(k == 0) return 1;
        while(r < nums.length){
            or |= nums[r];
            add(bits, nums[r]);
            while(or >= k) {
                minLen = Math.min(minLen, r-l+1);
                or = remove(bits, nums[l]);
                l++;
            }
            r++;
        }
        return minLen != Integer.MAX_VALUE ? minLen : -1;
    }

    public int remove(int[] arr, int n){
        int i = 0;
        while(n > 0){
            if((n & 1) == 1) arr[i]--;
            n >>= 1;
            i++;
        }
        int decimal = 0;
        i = 0;
        while(i < 32){
            if(arr[i] > 0) decimal += 1 << i;
            i++;
        }
        return decimal;
    }

    public void add(int[] arr, int n){
        int i = 0;
        while(n > 0){
            if((n & 1) == 1) arr[i]++;
            n >>= 1;
            i++;
        }
    }
}
 
thangkc89 đã nói:
Bài daily hôm nay viết thử ra giấy sẽ thấy được pattern :sure: xài python quen rồi ko thèm để ý mấy cái integer limit, giờ đổi qua c++ mất 1 đấm vì không cast qua long long
Đọc đề thì e thấy có 2 nhận xét như thế này:
  • Số đầu tiên luôn luôn là x, vì chắc chắn không có số nào bé hơn x mà AND với tất cả số còn lại ra được x cả
  • Các số còn lại AND x = x -> các vị trí có bit = 1 của x phải được giữ nguyên

-> Fill các bit của (n-1) vào các bit 0 của số x

C++: 
class Solution {
public:
    long long minEnd(int n, int x) {
        int significant_bit = 0;
        long long res = x;

        n -= 1;

        for (int i=0; (1<<i) <= x; ++i) {
            if ((1<<i) & x) {
                significant_bit = i;
            } else {
                res |= ((long long)(n & 1) << i);
                n >>= 1;
            }
        }

        res |= ((long long)n << (significant_bit + 1));

        return res;
    }
};
Nhấp để mở rộng...
bác này chắc cũng ở can hay mẽo gì hả, 5h sáng giải leetcode
Xv0BtTR.png
 
Takeitiz đã nói:
Bài hôm nay biết là dùng sliding rồi nhưng mà không biết xóa bit đã or kiểu gì, thế là lại chép Sol =((.
Nhấp để mở rộng...
cũng chép sol :too_sad:

Python: 
class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        d = defaultdict(int)
        l, curr_or, res = 0, 0, float('inf')
        
        for i in range(len(nums)):
            # calculate curr_or
            curr_or |= nums[i]

            # update dict with value of num
            for pos in range(30):
                if nums[i] & (1 << pos): d[pos] += 1
            
            # cut left until curr_or < k to find minimun len
            while curr_or >= k and l <= i:
                for pos in range(30):
                    if nums[l] & (1 << pos): d[pos] -= 1
                
                curr_or = sum(1<<pos for pos in range(30) if d[pos])
                res = min(res, i - l + 1)
                l += 1
          
        return res if res != float('inf') else -1
 
Python: 
class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = inf 
        d = dict()  # `d` is a dictionary where the key is the OR result of a subarray ending at index `i`, and the value is the largest left endpoint of that subarray
        for i, x in enumerate(nums):
            # Update `d` by calculating the OR between `x` and each current key (OR result of previous subarrays).
            # Note: Since dictionaries in Python maintain insertion order, if the OR result is the same,
            # it will automatically keep the subarray with the larger `left` endpoint as the value.

            d = {or_ | x: left for or_, left in d.items()}
            d[x] = i  # Add a new entry for the subarray containing only `x` (new beginning left)


            # Now check each subarray OR result stored in `d`
            for or_, left in d.items():
                if or_ >= k:  # If the OR result is greater than or equal to `k`
                    # Update `ans` with the minimum length of the subarray that meets the requirement
                    ans = min(ans, i - left + 1)
            
        
        # Return the smallest valid subarray length if found; otherwise, return -1 if no such subarray exists
        return ans if ans < inf else -1


đây là lời giải của thằng nhanh nhất trong python, không hiểu sao nó lại nhanh như vậy, ae ai biết tính độ phức tạp không? vòng lặp bên ngoài là số lượng num là O(N),

còn bên trong là loop qua dict, nhưng không biết tính số lượng phần tử của dict như nào, chỉ biết nó không vượt quá N
 
Tinh Hoa Đông Lào đã nói:
Python: 
class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = inf
        d = dict()  # `d` is a dictionary where the key is the OR result of a subarray ending at index `i`, and the value is the largest left endpoint of that subarray
        for i, x in enumerate(nums):
            # Update `d` by calculating the OR between `x` and each current key (OR result of previous subarrays).
            # Note: Since dictionaries in Python maintain insertion order, if the OR result is the same,
            # it will automatically keep the subarray with the larger `left` endpoint as the value.

            d = {or_ | x: left for or_, left in d.items()}
            d[x] = i  # Add a new entry for the subarray containing only `x` (new beginning left)


            # Now check each subarray OR result stored in `d`
            for or_, left in d.items():
                if or_ >= k:  # If the OR result is greater than or equal to `k`
                    # Update `ans` with the minimum length of the subarray that meets the requirement
                    ans = min(ans, i - left + 1)
           
       
        # Return the smallest valid subarray length if found; otherwise, return -1 if no such subarray exists
        return ans if ans < inf else -1


đây là lời giải của thằng nhanh nhất trong python, không hiểu sao nó lại nhanh như vậy, ae ai biết tính độ phức tạp không? vòng lặp bên ngoài là số lượng num là O(N),

còn bên trong là loop qua dict, nhưng không biết tính số lượng phần tử của dict như nào, chỉ biết nó không vượt quá N
Nhấp để mở rộng...
này là sliding window chứ gì, syntax python khó đọc quá, chỉ thấy dc slidingwindow thôi còn nó thao tác bit ko hiểu
MjfezZB.png
 
Java: 
class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        if(k==0)
            return 1;
        int l = 0,r=0;
        int or = 0;
        int res=  Integer.MAX_VALUE;
        int[] bit = new int[30];
        while(l<=r && r<nums.length){
            or|=nums[r];
            int n = nums[r];
            for(int i = 0;n>0;i++){
                bit[i]+=n&1;
                n>>=1;
            }
            while(or>=k) {
                res = Math.min(res, r - l + 1);
                int left = nums[l];
                int temp = 0;
                for(int i = 0;left>0;i++){
                    if((left&1)==1)
                        bit[i]--;
                    left>>=1;
                }
                for(int i = 0;i<bit.length;i++){
                    int b = bit[i]>=1?1:0;
                    temp+=b<<i;
                }
                or = temp;
                l++;
            }
            r++;
        }

        return res==Integer.MAX_VALUE?-1:res;
    }
}
reverse or bit mệt quá
HR4W6DU.png
 
thanbaiks đã nói:
Fen nghĩ thử tescase dạng này này;
nums = [1, <1e5 x 0>, <1e3 x 2>] và k = 3
Nhấp để mở rộng...
Ý fan là nums=[1,100000,2000], k=3 ?
Tôi chạy thử thì ra 1, chưa hiểu lắm ý của test case này.
if (nums[i] >= k) return 1;


Anyway, tôi đã thử sửa theo suy đoán, kq cũng ra không khác lắm với trước khi sửa, chỉ lệch 1ms.
-> sau khi xem xét thì tôi vẫn giữ quan điểm là amortized O(N*2) :)

TC_LongestLengthSubArraySumK.png
 
Sửa lần cuối:
Người quan sát cô đơn đã nói:
Java: 
class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        if(k==0)
            return 1;
        int l = 0,r=0;
        int or = 0;
        int res=  Integer.MAX_VALUE;
        int[] bit = new int[30];
        while(l<=r && r<nums.length){
            or|=nums[r];
            int n = nums[r];
            for(int i = 0;n>0;i++){
                bit[i]+=n&1;
                n>>=1;
            }
            while(or>=k) {
                res = Math.min(res, r - l + 1);
                int left = nums[l];
                int temp = 0;
                for(int i = 0;left>0;i++){
                    if((left&1)==1)
                        bit[i]--;
                    left>>=1;
                }
                for(int i = 0;i<bit.length;i++){
                    int b = bit[i]>=1?1:0;
                    temp+=b<<i;
                }
                or = temp;
                l++;
            }
            r++;
        }

        return res==Integer.MAX_VALUE?-1:res;
    }
}
reverse or bit mệt quá
HR4W6DU.png
Nhấp để mở rộng...
chém bit như chém bún thế lày thì @Cố Trường Ca quay lại thì tiểu đơn hiệp sĩ r mất
Q3OGEPn.gif
 
Java: 
class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        if (k == 0)
            return 1;
        int res = Integer.MAX_VALUE;
        int sum = 0;
        int[] ones = new int[32];
        for (int i = 0, j = 0; j < nums.length; j++)
        {
                sum |= nums[j];
                for (int pos = 0; pos < 32; pos++)
                    ones[pos] += (nums[j] >> pos & 1);

            while (sum >= k)
            {
                res = Math.min(res, j - i + 1);
                for (int pos = 0; pos < 32; pos++)
                    if ((nums[i] >> pos & 1) == 1)
                    {
                        ones[pos]--;
                        if (ones[pos] == 0)
                            sum ^= 1 << pos;
                    }
                i++;
            }
            
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
 
Trạng thái
Không mở để trả lời thêm.
AD · 970×250

Chủ đề tương tự

Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
2K
dattenmoi
D
megume
thảo luận Hôm nay, buổi bình minh của AI robot đã đến
Trả lời
4
Lượt xem
1K
Toc Hong
Toc Hong
Lộc Tục
(Dịch) Cuộc điều tra của CBC/Radio-Canada tiết lộ công ty Việt Nam nhắm vào người Canada bằng tin giả AI để kiếm lời
2
Trả lời
30
Lượt xem
5K
dukeng995
dukeng995
Ti Amo
[Dịch] Công ty Việt Nam dùng tin giả do AI tạo ra để kiếm tiền — nhắm vào độc giả Canada
Trả lời
0
Lượt xem
1K
Ti Amo
Ti Amo
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
891
giayasics
giayasics

Thống kê chủ đề

Ngày tạo
_Gia_Cat_Luong_,
Người trả lời cuối
Vipluckystar,
Trả lời
17.755
Lượt xem
1.214.491

Chia sẻ trang này

Quay lại
Lên đầu trang