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

suruki · 13/11/24

Bo_MinhAnh đã nói:
Thanks bác,
solution working well (and efficient).

Nếu bác wrap giữa cặp thẻ CODE /CODE nữa là đẹp.
[CODE=Java]
class Solution {
public static void main(String[] args) {}
}
[/CODE]
->

Java:

class Solution { public static void main(String[] args) {} }

nếu ko có highlight ngôn ngữ Kotlin thì có thể chọn Java (java) hoặc CLike (clike)

cảm ơn bác đỡ góp ý

suruki · 13/11/24

Java:

    class Solution {
        fun countFairPairs(nums: IntArray, lower: Int, upper: Int): Long {
            var ans = 0L
            nums.sort()
            for (i in 0 until nums.lastIndex) {
                val lowerIdx = findLower(i, nums, lower)
                if (lowerIdx == -1) continue
                    
                val upperIdx = findUpper(i, nums, upper)
                if (upperIdx == -1) continue
                if (lowerIdx > upperIdx) continue

                ans += upperIdx - lowerIdx + 1
            }

            return ans
        }

        private fun findLower(i: Int, nums: IntArray, lower: Int): Int {
            var s = i + 1
            var e = nums.lastIndex
            var idx = -1
            while (s <= e) {
                val mid = (s + e) / 2
                if (nums[mid] + nums[i] >= lower) {
                    idx = mid
                    e = mid - 1
                } else {
                    s = mid + 1
                }
            }
            return idx
        }

        private fun findUpper(i: Int, nums: IntArray, upper: Int): Int {
            var s = i + 1
            var e = nums.lastIndex
            var idx = -1
            while (s <= e) {
                val mid = (s + e) / 2
                if (nums[mid] + nums[i] <= upper) {
                    idx = mid
                    s = mid + 1
                } else {
                    e = mid - 1
                }
            }
            return idx
        }

    }

mrsimonle · 13/11/24

Python:

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        n = len(nums)

        def search(target, l, r):
            while l <= r:
                pivot = l + (r - l) // 2
                
                if nums[pivot] >= target:
                    r = pivot - 1
                else:
                    l = pivot + 1

            return l

        res = 0
        for i in range(n):
            minSatisfy = search(lower - nums[i], i + 1, n - 1)
            maxSatisfy = search(upper - nums[i] + 1, i + 1, n - 1)
            res += maxSatisfy - minSatisfy

        return res

mrsimonle · 13/11/24

freedom.9 đã nói:

Python:

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        left, right, greaterThanUpperPairs= 0, n - 1, 0
        while left < right:
            if nums[left] + nums[right] > upper:
                greaterThanUpperPairs += right - left
                right -= 1
            else:
                left += 1
 
        left, right, smallerThanLowerPairs= 0, n - 1, 0
        while left < right:
            if nums[left] + nums[right] >= lower:
                right -= 1
            else:
                smallerThanLowerPairs += right - left
                left += 1

        return (n*(n-1)//2) - (smallerThanLowerPairs + greaterThanUpperPairs)

Python:

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        def countPairsLowerThanTarget(target):
            left = 0
            right = n -1
            ans = 0
            while left < right:
                if nums[left] + nums[right] >= target:
                    right -= 1
                else:
                    ans += right - left
                    left += 1

            return ans

        return countPairsLowerThanTarget(upper + 1) - countPairsLowerThanTarget(lower)

Python:

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        def bisearch(left, target):
            right = n - 1
            while left <= right:
                mid = left + (right - left)//2
                if nums[mid] >= target:
                    right = mid - 1

                else:
                    left = mid + 1

            return right + 1

        ans = 0
        for i, val in enumerate(nums):
            left = bisearch(i + 1, lower - nums[i])
            right = bisearch(i + 1, upper + 1 - nums[i])
            ans += right - left

        return ans

https://leetcode.com/problems/count-subarrays-with-median-k/

Cơm thêm cho ae 1 bài counting khá hay, dạo này dấu hiệu tuổi tác rồi làm 1 2 bài medium với hard là đau đầu vcl =((

Thanks bác :love:

Python:

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        pos = nums.index(k)
        res = 0
        n = len(nums)

        curr = 0
        countRight = {}
        for i in range(pos + 1, n):
            if nums[i] < k:
                curr -= 1
            if nums[i] > k:
                curr += 1

            if curr == 0 or curr == 1:
                res += 1

            if curr not in countRight:
                countRight[curr] = 0
            countRight[curr] += 1

        curr = 0
        for i in range(pos - 1, -1, -1):
            if nums[i] < k:
                curr -= 1
            if nums[i] > k:
                curr += 1
               
            if curr == 0 or curr == 1:
                res += 1
           
            if -curr in countRight: # left + right = 0
                res += countRight[-curr]
            if 1 - curr in countRight: # left + right = 1
                res += countRight[-curr + 1]

        return res + 1

Tinh Hoa Đông Lào · 13/11/24

Python:

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        return sum(
            max(bisect_right(nums, upper - num), i + 1) 
            - max(bisect_left(nums, lower - num), i + 1) 
            for i, num in enumerate(nums)
        )

freedom.9 · 13/11/24

thangkc89 đã nói:

Bác làm em đau đầu rồi đấy :mad:

C++:

class Solution {
public:
    int countSubarrays(vector<int>& nums, int k) {
        int index = find(nums.begin(), nums.end(), k) - nums.begin();
        unordered_map<int, int> diff_counter;

        for (int i=index+1, diff=0; i<nums.size(); ++i) {
            if (nums[i] < k) {
                --diff;
            } else {
                ++diff;
            }
            ++diff_counter[diff];
        }
        ++diff_counter[0];

        int res = 0;
        for (int i=index, diff = 0; i>=0; --i) {
            if (nums[i] < k) {
                --diff;
            } else if (nums[i] > k) {
                ++diff;
            }
            res += diff_counter[-diff];
            res += diff_counter[-diff+1];
        }

        return res;
    }
};

mrsimonle đã nói:

Thanks bác :love:

Python:

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        pos = nums.index(k)
        res = 0
        n = len(nums)

        curr = 0
        countRight = {}
        for i in range(pos + 1, n):
            if nums[i] < k:
                curr -= 1
            if nums[i] > k:
                curr += 1

            if curr == 0 or curr == 1:
                res += 1

            if curr not in countRight:
                countRight[curr] = 0
            countRight[curr] += 1

        curr = 0
        for i in range(pos - 1, -1, -1):
            if nums[i] < k:
                curr -= 1
            if nums[i] > k:
                curr += 1
               
            if curr == 0 or curr == 1:
                res += 1
           
            if -curr in countRight: # left + right = 0
                res += countRight[-curr]
            if 1 - curr in countRight: # left + right = 1
                res += countRight[-curr + 1]

        return res + 1

via theNEXTvoz for iPhone

freedom.9 · 13/11/24

anoldvozer1710.v2 đã nói:
Hoodie LC thấy mở lại rồi, có ae nào ở HN đặt bao giờ chưa, không biết nó có ship về tận nhà ko nhỉ

Đặt cái áo với cái khóa nửa năm nay rồi chưa mặc, giờ lượm cái mũ chứ hoodie mang vô che cái áo thì sao

via theNEXTvoz for iPhone

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

dùng siêu template cho binary search, đặt right = len(nums) chứ ko phải len(nums)-1 để xử lý trường hợp uppperbound = nums[-1] :ah:

mà sao voz lại quay về theme mặc định của xenforo thế này, hết tiền thuê dev à :ops:

Python:

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        count = 0
        for i in range(len(nums)):
            low = self.binary_search(nums,i+1,lower-nums[i])
            high = self.binary_search(nums,i+1,upper-nums[i]+1)
            print(low,high)
            count+=high-low
        return count

    def binary_search(self,nums,low,target):
        l,r = low, len(nums)
        while l<r:
            mid = (l+r)//2
            if nums[mid]<target:
                l = mid+1
            else:
                r = mid
        return l

afatnan · 13/11/24

C++:

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(begin(nums), end(nums));
        long long res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            res += distance(
                lower_bound(begin(nums) + i + 1, end(nums), lower - nums[i]),
                upper_bound(begin(nums) + i + 1, end(nums), upper - nums[i])
            );
        }
        return res;
    }
};

LmaoSuVuong · 13/11/24

Người quan sát cô đơn đã nói:
dùng siêu template cho binary search, đặt right = len(nums) chứ ko phải len(nums)-1 để xử lý trường hợp uppperbound = nums[-1]
mà sao voz lại quay về theme mặc định của xenforo thế này, hết tiền thuê dev à

Python:

class Solution: def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int: nums.sort() count = 0 for i in range(len(nums)): low = self.binary_search(nums,i+1,lower-nums[i]) high = self.binary_search(nums,i+1,upper-nums[i]+1) print(low,high) count+=high-low return count def binary_search(self,nums,low,target): l,r = low, len(nums) while l<r: mid = (l+r)//2 if nums[mid]<target: l = mid+1 else: r = mid return l

@Cố Trường Ca thằng e tính time complexity On này thì xứng đáng mấy gậy nhỉ

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

LmaoSuVuong đã nói:
@Cố Trường Ca thằng e tính time complexity On này thì xứng đáng mấy gậy nhỉ

O(nlogn), cmn ghi theo gợi ý quên chưa sửa, tha e các a ơi :too_sad:

Taylor.Swiftt · 14/11/24

Java:

class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int l = 0, r = 0;
        for(int quantity : quantities) {
            if(r < quantity) r = quantity;
        }
        while(l <= r) {
            int mid = l + (r - l)/2;
            if(dis(mid, quantities, n)) {
                r = mid - 1;
            } else l = mid + 1;
        }
        return l;
    }
    public boolean dis(int x, int[] q, int n) {
        int type = 0;
        int remain = q[type];
        for(int i = 0; i < n; i++) {
            if(remain <= x) {
                type++;
                if(type == q.length) return true;
                else remain = q[type];
            } else remain -= x;
        }
        return false;
    }
}

Newbie, xin hãy góp ý nhẹ nhàng chứ ko tôy bỏ đấy 8-)

aNotHeRNo0b · 14/11/24

Java:

class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int maxQuantity = quantities[0];
        for (int quantity : quantities) {
            maxQuantity = Math.max(
                maxQuantity,
                quantity
            );
        }

        int left = 0, right = maxQuantity;
        int minimumMax = maxQuantity;
        while (left <= right) {
            int curQuantity = (left + right) / 2;
            if (canDistribute(quantities, n, curQuantity)) {
                right = curQuantity - 1;
                minimumMax = Math.min(
                    minimumMax,
                    curQuantity
                );
            } else {
                left = curQuantity + 1;
            }
        }

        return minimumMax;
    }

    public boolean canDistribute(int[] quantities, int numRetailStore, int maxQuantity) {
        if (maxQuantity == 0) return false;
        int numRetailStoreRequire = 0;
        for (int i = 0; i < quantities.length; i++) {
            numRetailStoreRequire += (quantities[i] - 1) / maxQuantity + 1;
        }

        return numRetailStoreRequire <= numRetailStore;
    }
}

Binary Search Week

aNotHeRNo0b · 14/11/24

Taylor.Swiftt đã nói:
Newbie, xin hãy góp ý nhẹ nhàng chứ ko tôy bỏ đấy

Fence post code bị lỗi à

freedom.9 · 14/11/24

Python:

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        quantities = sorted(quantities, reverse = True)
        def canDistribute(x):
            stores = 0
            for quantity in quantities:
                stores += math.ceil(quantity/x)
                if stores > n:
                    return False
            return True
        left = 1
        right = max(quantities)
        while left <= right:
            mid = left + (right - left)//2
            if canDistribute(mid):
                right = mid - 1
            else:
                left = mid + 1
        return right + 1

Làm tí graph nâng cao nào ae :ah:

https://leetcode.com/problems/minimum-cost-walk-in-weighted-graph/

aNotHeRNo0b · 14/11/24

freedom.9 đã nói:
Làm tí graph nâng cao nào ae

https://leetcode.com/problems/minimum-cost-walk-in-weighted-graph/

:v yếu nhất Graph

bác cho quả này bí luôn

freedom.9 · 14/11/24

aNotHeRNo0b đã nói:
:v yếu nhất Graph

bác cho quả này bí luôn

Mấy fen phải học nhiều graph vô vì interview thường ra Graph rồi chứ DP ra mấy đâu :ah:

Bài này xưa ra contest rồi thì phải, hồi đó chưa làm được mà nay làm tí là xong rồi

aNotHeRNo0b · 14/11/24

freedom.9 đã nói:
Làm tí graph nâng cao nào ae

https://leetcode.com/problems/minimum-cost-walk-in-weighted-graph/

Vì có thể đi lại 1 vertex 1 đỉnh, nên ý tưởng của em là tìm đường đi sao cho AND nó bé nhất trong mỗi thành phần liên thông (AND hết tất cả weight trong 1 TPLT), rồi xem thằng nào tới được đường đấy :v. Lúc query thì chỉ cần đi qua là nó nhỏ nhất :v

Anh Thợ Săn · 14/11/24

C++:

bool canDistribute(int n, vector<int>& quantities, int k) {
    int required = 0;
    for (int q : quantities) {
        required += q / k + (q % k == 0 ? 0 : 1);       
    }
    return required <= n;
}

int Solution::minimizedMaximum(int n, vector<int>& quantities) {
    int left = 1;
    int right = 1;
    for (int q : quantities) {
        if (right < q)
            right = q;
    }
    int k = right;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canDistribute(n, quantities, mid)) {
            right = mid - 1;
            k = mid;
        } else {
            left = mid + 1;
        }
    }
    return k;
}

nchhnchh · 14/11/24

Python:

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        def valid(target):
            return target > 0 and sum([math.ceil(q / target) for q in quantities]) <= n

        l, r = 1, max(quantities)
        while l <= r:
            mid = l + (r - l) // 2
            if valid(mid):
                r = mid - 1
            else:
                l = mid + 1
        result = r + 1
        return result

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

Junior Member

Junior Member

Junior Member

Junior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior 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