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

freedom.9 · 28/8/23

Leetcode premium có cái assesment online interview hay vãi ae.
Nó tự đánh giá solution với lại ranking luôn.

freedom.9 · 29/8/23

https://leetcode.com/problems/pancake-sorting/
Có bài này khá hay, giải chơi ae

Mới tìm thấy 1 bài còn sv hơn cả bài hôm qua, 1 bài easy dislike gấp 10 lần like :gach:

https://leetcode.com/problems/day-of-the-week/

TLE_WA · 29/8/23

Leetcode phân loại bài loạn quá, lắm bài medium khó như hard, lắm bài medium lại như easy :beat_brick:

C++:

class Solution {
public:
    int bestClosingTime(string customer) {
        int n = customer.size();
        vector<int> pref(n+1);
        for (int i = 1; i <= n; i++){
            pref[i] = pref[i-1] + (customer[i-1] == 'N');
        }
        int mn = n - pref[n];
        int id = 0;
        for (int i = 1; i <= n; i++){
            if (mn > pref[i] + n - i - pref[n] + pref[i]){
                mn = pref[i] + n - i - pref[n] + pref[i];
                id = i;
            }
        }
        return id;
    }
};

Violet_7 · 29/8/23

TLE_WA đã nói:

Leetcode phân loại bài loạn quá, lắm bài medium khó như hard, lắm bài medium lại như easy :beat_brick:

C++:

class Solution {

public:

    int bestClosingTime(string customer) {

        int n = customer.size();

        vector<int> pref(n+1);

        for (int i = 1; i <= n; i++){

            pref = pref[i-1] + (customer[i-1] == 'N');

        }

        int mn = n - pref[n];

        int id = 0;

        for (int i = 1; i <= n; i++){

            if (mn > pref + n - i - pref[n] + pref){

                mn = pref + n - i - pref[n] + pref;

                id = i;

            }

        }

        return id;

    }

};

Space O(n) :look_down:

TLE_WA · 29/8/23

Violet_7 đã nói:
Space O(n)

đã fix

C++:

class Solution {
public:
    int bestClosingTime(string customer) {
        int n = customer.size();
        int tot = 0;
        for (int i = 1; i <= n; i++){
            tot += (customer[i-1] == 'N');
        }
        int mn = n - tot;
        int id = 0, cur = 0;
        for (int i = 1; i <= n; i++){
            cur += customer[i-1] == 'N';
            if (mn > 2 * cur + n - i - tot){
                mn = 2 * cur + n - i - tot;
                id = i;
            }
        }
        return id;
    }
};

Bleach & Sarcasm · 29/8/23

bài hôm lay 1 dòng là xong xao lại medium

C++:

struct Solution {
    int bestClosingTime(string_view customers) {
        return accumulate(begin(customers), end(customers), pair{0, 0},
            [pen = 0, i = 0](auto sum, char ch) mutable {
                return ++i, ch == 'N' ? ++pen, sum : --pen < sum.second ? pair{i, pen} : sum;
            }
        ).first;
    }
};

chỗ return ... sum ... sum đáng lẽ xài move(sum) nhưng mà sum là 2 int very cheap copy nên ko cần move() chắc cũng ko xao

realhaidinh · 29/8/23

lúc đầu ngu ngu làm 2 mảng prefix với suffix sum mất o(n) space, đọc editorial mới nhận ra chỉ cần o(1) là đủ :cry:

C++:

class Solution {
public:
    int bestClosingTime(string_view customers) {
        int penalty = count(customers.begin(), customers.end(), 'Y');
        int result = penalty, time = 0;
        for(int i = 1; i <= customers.size(); ++i){
            if(customers[i - 1] == 'Y')
                penalty--;
            else
                penalty++;
            if(result > penalty){
                result = penalty;
                time = i;
            }
        }
        return time;
    }
};

nhethanh2 · 29/8/23

JavaScript:

function bestClosingTime(customers: string): number {
    let result = 0;
    let maxDiff = 0;

    customers.split('').reduce((currentDiff, customer, index) => {
        const nextDiff = currentDiff + (customer === 'Y' ? 1 : -1);
        if (nextDiff > maxDiff) {
            maxDiff = nextDiff;
            result = index + 1;
        }
        return nextDiff;
    }, 0);
    
    return result;
}

thanbaiks · 29/8/23

JavaScript:

var bestClosingTime = function(customers) {
    let ans = 0, min = +Infinity;
    let y = 0, n = 0;
    for (let i = 0; i < customers.length; i++) {
        y += customers[i] === 'Y' ? 1 : 0;
    }
    for (let i = 0; i <= customers.length; i++) {
        if (i > 0) {
            if (customers[i-1] === 'N') {
                n++;
            } else {
                y--;
            }
        }
        if (n + y < min) {
            min = n + y;
            ans = i;
        }
    }
    return ans;
};

Character_L · 29/8/23

class Solution {
public:
int bestClosingTime(string customers) {
int res = customers.length();
int tmp = res;
int pen = 0;
for(int i = 0; i < res; i++){
if(customers == 'N') pen++;
}
int tmppen = pen;
for(int i = tmp - 1 ; i >=0 ; i--){
if(customers == 'Y') tmppen++;
else tmppen--;
if(tmppen <= pen){
res = i;
pen = tmppen;
}
}
return res;
}
};

Vegabond_Ref · 29/8/23

Python:

class Solution:

    def bestClosingTime(self, customers):

        n = len(customers)

        pref = [0] * (n+1)

        for i in range(1, n+1):

            pref = pref[i-1] + (customers[i-1] == 'N')

        mn = n - pref[n]

        id = 0

        for i in range(1, n+1):

            if mn > pref + n - i - pref[n] + pref:

                mn = pref + n - i - pref[n] + pref

                id = i

        return id

freedom.9 · 30/8/23

Mới giữa tuần đã cho hard à, bookmark từ từ làm :ah:

thanbaiks · 30/8/23

JavaScript:

var minimumReplacement = function(nums) {
  let ceil = nums[nums.length-1];
  let ans = 0;
  for (const v of nums.reverse()) {
    const t = Math.ceil(v / ceil);
    ans += t - 1;
    ceil = Math.floor(v / t);
  }
  return ans;
};

TLE_WA · 30/8/23

không nên tách số cuối cùng vì nếu tách sẽ gây ảnh hưởng đến các số đằng trước
ví dụ 5 9 => nếu tách 9 thì 5 cũng phải tách
như vậy ta duyệt từ phải sang trái, update số nhỏ nhất (mn) sau mỗi lần duyệt
chỉ thực sự tách khi cần thiết
Gọi số hiện tại là x, nếu x <= mn thì ta update mn = x
nếu x > mn thì ta phải tách x ra thành comp số <= mn
comp = round up (x / mn)
round up nhằm đảm bảo sau khi tách các số chắc chắn <= mn
tại sao ? vì sau khi chia phần dư (nếu có) sẽ được dành ra để tạo thành một số mới
và mn = round down (x / comp) vì sẽ có một vài số chịu phần thiệt
ví dụ: 49 và 11
ta phải tách 49 thành 5 số (không có cách nào tách thành 4 số vì sẽ dư ra)
49 = 10 + 10 + 10 + 10 + 9
9 = 49 // 5
số phải chịu phần thiệt ở đây là 9 (round down)
kết quả sẽ cộng với comp - 1 (để tách thành comp số cần comp - 1 lần tách)

C++:

class Solution {
public:
    long long minimumReplacement(vector<int>& nums) {
        long long ans = 0;
        int mn = nums.back();
        for (int i = nums.size() - 2; i >= 0; i--){
            if (nums[i] <= mn) mn = nums[i];
            else{
                int comp = (nums[i] + mn - 1) / mn;
                mn = nums[i] / comp;
                ans += comp - 1;
            }
        }
        return ans;
    }
};

Ayanokoji Kiyotaka · 30/8/23

1 bài số học rất thú vị

C++:

class Solution {
public:
    long long minimumReplacement(vector<int>& nums) {
        long long res = 0;
        int index = nums.size() - 2;
        int value = nums[index + 1];
        for (int i = index; i >= 0; i--){
            if (nums[i] < value){
                value = nums[i]; continue;
            }
            long long count = (nums[i] % value == 0) ? nums[i] / value : nums[i] / value + 1;
            value = nums[i] / count;
            res += count - 1;
        }
        return res;
    }
};

bribnt · 30/8/23

TLE_WA đã nói:
không nên tách số cuối cùng vì nếu tách sẽ gây ảnh hưởng đến các số đằng trước
ví dụ 5 9 => nếu tách 9 thì 5 cũng phải tách
như vậy ta duyệt từ phải sang trái, update số nhỏ nhất (mn) sau mỗi lần duyệt
chỉ thực sự tách khi cần thiết
Gọi số hiện tại là x, nếu x <= mn thì ta update mn = x
nếu x > mn thì ta phải tách x ra thành comp số <= mn
comp = round up (x / mn)
round up nhằm đảm bảo sau khi tách các số chắc chắn <= mn
tại sao ? vì sau khi chia phần dư (nếu có) sẽ được dành ra để tạo thành một số mới
và mn = round down (x / comp) vì sẽ có một số chịu phần thiệt
ví dụ: 49 và 11
ta phải tách 49 thành 5 số (không có cách nào tách thành 4 số vì sẽ dư ra)
49 = 10 + 10 + 10 + 10 + 9
9 = 49 // 5
số phải chịu phần thiệt ở đây là 9 (round down)
kết quả sẽ cộng với comp - 1 (để tách thành comp số cần comp - 1 lần tách)

Còn một phần quan trọng nữa là cách để tách.
Để tối ưu kết quả, giảm khả năng phần tử tiếp theo phải chia nữa thì cần làm sao để số nhỏ nhất trong các phần được chia ra là lớn nhất.
VD: ..., 18, 5, ... tách số 18 ra thành 4 4 5 5 sẽ tốt hơn là 3 5 5 5

TIEU PH0NG · 30/8/23

Java:

class Solution {
    //nums=[..., a, b, ...]
    //Duyệt từ phải sang trái, tách a nếu gặp b < a
    //VD: b=4, a=15 => newA= 4,4,7 (4+3)
    //VD: b=10, a=55 => newA= 10,10,10,10,15 (10+5)
    public long minimumReplacement(int[] nums) {
        long a, b, ret = 0;

        for (int i = nums.length - 1; i >= 1; --i) {
            a = nums[i - 1];
            b = nums[i];

            if (b < a) {
                ret += (a - 1) / b;
                nums[i - 1] = (int) (a / ((a - 1 + b) / b));
            }
        }

        return ret;
    }
}

Bleach & Sarcasm · 30/8/23

TLE_WA đã nói:
không nên tách số cuối cùng vì nếu tách sẽ gây ảnh hưởng đến các số đằng trước
ví dụ 5 9 => nếu tách 9 thì 5 cũng phải tách
như vậy ta duyệt từ phải sang trái, update số nhỏ nhất (mn) sau mỗi lần duyệt
chỉ thực sự tách khi cần thiết
Gọi số hiện tại là x, nếu x <= mn thì ta update mn = x
nếu x > mn thì ta phải tách x ra thành comp số <= mn
comp = round up (x / mn)
round up nhằm đảm bảo sau khi tách các số chắc chắn <= mn
tại sao ? vì sau khi chia phần dư (nếu có) sẽ được dành ra để tạo thành một số mới
và mn = round down (x / comp) vì sẽ có một vài số chịu phần thiệt
ví dụ: 49 và 11
ta phải tách 49 thành 5 số (không có cách nào tách thành 4 số vì sẽ dư ra)
49 = 10 + 10 + 10 + 10 + 9
9 = 49 // 5
số phải chịu phần thiệt ở đây là 9 (round down)
kết quả sẽ cộng với comp - 1 (để tách thành comp số cần comp - 1 lần tách)

C++:

class Solution { public: long long minimumReplacement(vector<int>& nums) { long long ans = 0; int mn = nums.back(); for (int i = nums.size() - 2; i >= 0; i--){ if (nums[i] <= mn) mn = nums[i]; else{ int comp = (nums[i] + mn - 1) / mn; mn = nums[i] / comp; ans += comp - 1; } } return ans; } };

bài hard mà tham lam dễ vậy à, toy thấy hard là ko làm ròi mà bài này 1 dòng được thì xiaolol` cái

C++:

struct Solution {
    long long minimumReplacement(vector<int>& nums) {
        return accumulate(nums.rbegin(), nums.rend(), 0LL, [mx = nums.back(), ops = 0](auto sum, int n) mutable {
            return n > mx ? (ops = n / mx + (n % mx > 0), mx = n / ops, sum + ops - 1) : (mx = min(mx, n), sum);
        });
    }
};

thanbaiks · 31/8/23

JavaScript:

var minTaps = function(n, ranges) {
    ranges = ranges
        .map((r, i) => [Math.max(0, i-r), Math.min(n, i+r)])
        .filter(([s, e]) => s !== e)
        .sort((u, v) => u[1] - v[1]);
    const arr = Array(n+1).fill(+Infinity);
    arr[0] = 0;

    for (const [s, e] of ranges) {
        for (let i = s; i < e; i++) {
            arr[e] = Math.min(arr[e], arr[i] + 1);
        }
    }

    return arr[n] === +Infinity ? -1 : arr[n];
};

hungmessi2 · 31/8/23

Brute force ỉa chảy

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

Senior Member

Senior Member

Junior Member

Member

Junior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Senior Member

Tệp đính kèm

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này