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.
Swift: 
class Solution {
    func minimizedMaximum(_ n: Int, _ quantities: [Int]) -> Int {
        func check(_ max: Int) -> Bool {
            var store = 0
            for q in quantities {
                store += (q + max - 1)/max // round up
                if store > n { return false }
            }
            return store <= n
        }

        var low = 1
        var high = quantities.max()!

        while low < high {
            let mid = (low + high)/2
            if check(mid) {
                high = mid
            } else {
                low = mid + 1
            }
        }

        return low
    }
}
 
Java: 
class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int l = 1, r = (int) 1e5;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (distributed(quantities, n, m)) r = m - 1;
            else l = m + 1;
        }
        return l;
    }

    private boolean distributed(int[] quantities, int n, int x) {
        for (int quantity : quantities) {
            n -= (quantity + x - 1) / x;
            if (n < 0) return false;
        }
        return true;
    }
}
Xin phép thó phần check distributed của top 1
P5P1Om6.gif
 
Java: 
class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int m = quantities.length;
        int left = 0;
        int right = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            right = Math.max(right, quantities[i]);
        }

        while (left < right) {
            int mid = (right + left) / 2;
            if (canDistribute(mid, n, quantities)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean canDistribute(int k, int n, int[] quantities) {
        int sum = 0;
        for (int i = 0; i < quantities.length; i++) {
            sum += Math.ceil(quantities[i] * 1.0 / k);
        }
        return sum <= n;
    }
}
 
Java: 
class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int l = 1;
        int r = 100000;
        int res =1;
        while(l<=r){
            int mid = l  + (r-l)/2;
            if(condition(mid,n,quantities)){
                res= mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return res;
    }
    public boolean condition(int a, int n, int[] quantities){
        int cnt=0;
        for(int quantity:quantities){
            cnt+=(quantity+a-1)/a;
            if(cnt>n) return false;
        }
        return true;
    }
}
 
Sửa lần cuối:
JavaScript: 
var minimizedMaximum = function (n, quantities) {
    const go = x => {
        let k = 0;
        for (const q of quantities) {
            k += Math.ceil(q / x);
        }
        return k <= n;
    };
    let l = 1, h = _.max(quantities) + 1;
    while (l < h) {
        const m = (l + h) >> 1;
        if (go(m)) {
            h = m;
        } else {
            l = m + 1;
        }
    }
    return l;
};
 
JavaScript: 
function minimizedMaximum(n: number, qs: number[]): number {
    const feasible = (x: number) => {
        let y = 0;
        for (const q of qs) {
            y += Math.ceil(q / x);
        }
        return y <= n;
    }
    let l = 0, r = Math.max(...qs)
    while (l < r) {
        const m = l + Math.floor((r - l) / 2);
        if (feasible(m)) r = m
        else l = m + 1
    }
    return l
};
 
Python: 
class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        m = len(quantities)

        def can_distribute(target):
            if target == 0:
                return False
            k = n
            for i in range(m):
                k -= quantities[i] // target
                if quantities[i] % target > 0:
                    k -= 1
            return k >= 0
        
        l, r = 0, max(quantities)
        while l <= r:
            mid = (l + r) // 2
            if can_distribute(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l
 
anoldvozer1710.v2 đã nói:
JavaScript: 
function minimizedMaximum(n: number, qs: number[]): number {
    const feasible = (x: number) => {
        let y = 0;
        for (const q of qs) {
            y += Math.ceil(q / x);
        }
        return y <= n;
    }
    let l = 0, r = Math.max(...qs)
    while (l < r) {
        const m = l + Math.floor((r - l) / 2);
        if (feasible(m)) r = m
        else l = m + 1
    }
    return l
};
Nhấp để mở rộng...
ủa là sao dị, sao hôm bữa hong làm dị đó :ah: :what:
 
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

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 =((
Nhấp để mở rộng...
Cơm thêm chạy UF to tay ăn bug sml :beat_brick:
Edit: Tag nhầm post, :beat_brick:
Làm tí graph nâng cao nào ae :ah:

https://leetcode.com/problems/minimum-cost-walk-in-weighted-graph/
 
Sửa lần cuối:
freedom.9 đã nói:
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:

Nhấp để mở rộng...
BFS cơ bản :beauty:
C++: 
#define ii pair<int,int>

class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        vector<int> colors(n, -1);
        vector<int> component_cost;
        vector<vector<ii>> adj(n);

        for (const vector<int> &edge: edges) {
            adj[edge[0]].push_back(ii(edge[1], edge[2]));
            adj[edge[1]].push_back(ii(edge[0], edge[2]));
        }

        int color = 0;
        for (int i=0; i<n; ++i) {
            if (colors[i] > -1) {
                continue;
            }
            // cout << i << " here" << endl;

            queue<int> q;
            q.push(i);
            colors[i] = color;
            int cost = (1ll*1<<31) - 1;

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                for (const ii &p : adj[u]) {
                    
                    // cout << "cost: " << cost << ", w: " << p.second << ", new cost: " << (cost & p.second) << endl;
                    cost &= p.second;
                    if (colors[p.first] == -1) {
                        colors[p.first] = color;
                        q.push(p.first);
                    }
                    
                }
            }

            component_cost.push_back(cost);
            color += 1;
        }

        // cout << "component_cost: " << endl;
        // for (int &cost : component_cost) {
        //     cout << cost << endl;
        // }
        // cout << "colors: " << endl;
        // for (int &color : colors) {
        //     cout << color << endl;
        // }

        vector<int> res(query.size());
        for (int i=0; i<query.size(); ++i) {
            int u = query[i][0];
            int v = query[i][1];
            if (colors[u] != colors[v]) {
                res[i] = -1;
            } else {
                res[i] = component_cost[colors[u]];
            }
        }
        return res;
    }

};
 
thangkc89 đã nói:
BFS cơ bản :beauty:
C++: 
#define ii pair<int,int>

class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        vector<int> colors(n, -1);
        vector<int> component_cost;
        vector<vector<ii>> adj(n);

        for (const vector<int> &edge: edges) {
            adj[edge[0]].push_back(ii(edge[1], edge[2]));
            adj[edge[1]].push_back(ii(edge[0], edge[2]));
        }

        int color = 0;
        for (int i=0; i<n; ++i) {
            if (colors[i] > -1) {
                continue;
            }
            // cout << i << " here" << endl;

            queue<int> q;
            q.push(i);
            colors[i] = color;
            int cost = (1ll*1<<31) - 1;

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                for (const ii &p : adj[u]) {
                   
                    // cout << "cost: " << cost << ", w: " << p.second << ", new cost: " << (cost & p.second) << endl;
                    cost &= p.second;
                    if (colors[p.first] == -1) {
                        colors[p.first] = color;
                        q.push(p.first);
                    }
                   
                }
            }

            component_cost.push_back(cost);
            color += 1;
        }

        // cout << "component_cost: " << endl;
        // for (int &cost : component_cost) {
        //     cout << cost << endl;
        // }
        // cout << "colors: " << endl;
        // for (int &color : colors) {
        //     cout << color << endl;
        // }

        vector<int> res(query.size());
        for (int i=0; i<query.size(); ++i) {
            int u = query[i][0];
            int v = query[i][1];
            if (colors[u] != colors[v]) {
                res[i] = -1;
            } else {
                res[i] = component_cost[colors[u]];
            }
        }
        return res;
    }

};
Nhấp để mở rộng...
Em ban đầu ko nghĩ dùng BFS thế méo nào nhảy vô UF code to tay tốn cả tiếng đồng hồ :beat_brick:
 
anoldvozer1710.v2 đã nói:
giới tính linh hoạt mà mao huynh :beauty:
Có phải bài nào cũng viết feasible tìm left, tìm right đâu :sweet_kiss:
cũng có bài chỉ cần l <= r, assign kết quả trong vòng while :hell_boy:
cong ăn cong, thẳng ăn thẳng đi :hungry: bài này l <= r thì thành r = m - 1 thôi
Nhấp để mở rộng...
binary search thì chỉ nên follow theo 1 pattern thôi. Làm nhiều kiểu dễ bị rối hoặc sai linh tinh lắm.

Như pattern t đi học lỏm đc + và có chỉnh sửa lại thì sẽ ntn:
  • đầu tiên là có 1 hàm check, trả về true, false để thỏa mãn mấy cái điều kiện của bài toán
  • khởi tạo giá trị bên trái, bên phải, đảm bảo rằng 1 thằng nếu quăng vào hàm check thì sẽ là true, 1 thằng sẽ là false. thằng nào là true thì dùng để return về
  • đoạn vòng lặp thì chỉ để ý chỗ gán i, j thôi
C++: 
class Solution {
public:
    int minimizedMaximum(int n, vector<int>& quantities) {
        auto check = [&quantities, n] (int p) {
            if (p == 0) return false;
            return accumulate(quantities.begin(), quantities.end(), 0, [p] (int acc, int x) {
                return acc + (x + p - 1)/p; 
            }) <= n;
        };
      
        int i = 0, j = *max_element(quantities.begin(), quantities.end());
        while (i < j - 1) {
            int pivot = i + (j - i)/2;
            if (check(pivot)) j = pivot;
            else i = pivot;
        }
        return j;
    }
};

1 bài bs tương tự, áp dụng pattern, chỉ cần thay đổi 1 chút là pass
C++: 
class Solution {
public:
    int maximumCandies(vector<int>& candies, long long k) {
        auto check = [&candies, k] (int p) {
            if (p == 0) return true;
            return accumulate(candies.begin(), candies.end(), 0l, [p] (long long acc, int x) {
                return acc + x/p; 
            }) >= k;
        };
      
        int i = 0, j = *max_element(candies.begin(), candies.end()) + 1;
        while (i < j - 1) {
            int pivot = i + (j - i)/2;
            if (check(pivot)) i = pivot;
            else j = pivot;
        }
        return i;
    }
};

Một bài tương tự, level hard khó hơn, áp dụng pattern tương tự, chỉ cần tối ưu hàm check
C++: 
class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        auto check = [&chargeTimes, &runningCosts, budget] (int p) {
            if (p == 0) return true;
            if (p > chargeTimes.size()) return false;
            multiset<int> charge(chargeTimes.begin(), chargeTimes.begin() + p);
            long long sum_running = accumulate(runningCosts.begin(), runningCosts.begin() + p, 0ll)*p;
            long long cost = sum_running + *charge.rbegin();
            for (int i = p; i < chargeTimes.size(); ++i) {
                charge.erase(charge.find(chargeTimes[i - p]));
                charge.insert(chargeTimes[i]);
                sum_running += ((long long)runningCosts[i] - runningCosts[i-p])*p;
                cost = min(cost, sum_running + *charge.rbegin());
            }
            return cost <= budget;
        };
      
        int i = 0, j = chargeTimes.size() + 1;
        while (i < j - 1) {
            int pivot = i + (j - i)/2;
            if (check(pivot)) i = pivot;
            else j = pivot;
        }
        return i;
    }
};
 
seastar đã nói:
binary search thì chỉ nên follow theo 1 pattern thôi. Làm nhiều kiểu dễ bị rối hoặc sai linh tinh lắm.

Như pattern t đi học lỏm đc + và có chỉnh sửa lại thì sẽ ntn:
  • đầu tiên là có 1 hàm check, trả về true, false để thỏa mãn mấy cái điều kiện của bài toán
  • khởi tạo giá trị bên trái, bên phải, đảm bảo rằng 1 thằng nếu quăng vào hàm check thì sẽ là true, 1 thằng sẽ là false. thằng nào là true thì dùng để return về
  • đoạn vòng lặp thì chỉ để ý chỗ gán i, j thôi
C++: 
class Solution {
public:
    int minimizedMaximum(int n, vector<int>& quantities) {
        auto check = [&quantities, n] (int p) {
            if (p == 0) return false;
            return accumulate(quantities.begin(), quantities.end(), 0, [p] (int acc, int x) {
                return acc + (x + p - 1)/p; 
            }) <= n;
        };
      
        int i = 0, j = *max_element(quantities.begin(), quantities.end());
        while (i < j - 1) {
            int pivot = i + (j - i)/2;
            if (check(pivot)) j = pivot;
            else i = pivot;
        }
        return j;
    }
};

1 bài bs tương tự, áp dụng pattern, chỉ cần thay đổi 1 chút là pass
C++: 
class Solution {
public:
    int maximumCandies(vector<int>& candies, long long k) {
        auto check = [&candies, k] (int p) {
            if (p == 0) return true;
            return accumulate(candies.begin(), candies.end(), 0l, [p] (long long acc, int x) {
                return acc + x/p; 
            }) >= k;
        };
      
        int i = 0, j = *max_element(candies.begin(), candies.end()) + 1;
        while (i < j - 1) {
            int pivot = i + (j - i)/2;
            if (check(pivot)) i = pivot;
            else j = pivot;
        }
        return i;
    }
};

Một bài tương tự, level hard khó hơn, áp dụng pattern tương tự, chỉ cần tối ưu hàm check
C++: 
class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        auto check = [&chargeTimes, &runningCosts, budget] (int p) {
            if (p == 0) return true;
            if (p > chargeTimes.size()) return false;
            multiset<int> charge(chargeTimes.begin(), chargeTimes.begin() + p);
            long long sum_running = accumulate(runningCosts.begin(), runningCosts.begin() + p, 0ll)*p;
            long long cost = sum_running + *charge.rbegin();
            for (int i = p; i < chargeTimes.size(); ++i) {
                charge.erase(charge.find(chargeTimes[i - p]));
                charge.insert(chargeTimes[i]);
                sum_running += ((long long)runningCosts[i] - runningCosts[i-p])*p;
                cost = min(cost, sum_running + *charge.rbegin());
            }
            return cost <= budget;
        };
      
        int i = 0, j = chargeTimes.size() + 1;
        while (i < j - 1) {
            int pivot = i + (j - i)/2;
            if (check(pivot)) i = pivot;
            else j = pivot;
        }
        return i;
    }
};
Nhấp để mở rộng...
Bookmark mai làm cái bài hard này, nhìn AC 35% có vẻ xịn :beauty:

via theNEXTvoz for iPhone
 
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
894
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.659

Chia sẻ trang này

Quay lại
Lên đầu trang