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

xin chỉ giáo
đây phen

C++:
class Solution {
    template <class T, class RecursiveFunc>
    class Cache {
    public:
        Cache(int target, RecursiveFunc&& f) : data(target + 1), f{std::move(f)} {}
        void set(int i, T value) { data[i] = value; }
        T operator[](int i) {
            if (!data[i]) data[i] = f(*this, i);
            return *data[i];
        }
        
    private:
        vector<optional<T>> data;
        RecursiveFunc f;
    };
    
public:
    int combinationSum4(vector<int>& nums, int target) {
        auto f = [&](auto& cache, int target){
            uint32_t res = 0;
            for (int n : nums) if (target >= n) res += cache[target - n];
            return res;
        };
        Cache<uint32_t, decltype(f)> m{target, std::move(f)};
        m.set(0, 1);
        return m[target];
    }
};
irGoYrZ.gif
irGoYrZ.gif
irGoYrZ.gif
 
đây phen

C++:
class Solution {
    template <class T, class RecursiveFunc>
    class Cache {
    public:
        Cache(int target, RecursiveFunc&& f) : data(target + 1), f{std::move(f)} {}
        void set(int i, T value) { data[i] = value; }
        T operator[](int i) {
            if (!data[i]) data[i] = f(*this, i);
            return *data[i];
        }
       
    private:
        vector<optional<T>> data;
        RecursiveFunc f;
    };
   
public:
    int combinationSum4(vector<int>& nums, int target) {
        auto f = [&](auto& cache, int target){
            uint32_t res = 0;
            for (int n : nums) if (target >= n) res += cache[target - n];
            return res;
        };
        Cache<uint32_t, decltype(f)> m{target, std::move(f)};
        m.set(0, 1);
        return m[target];
    }
};
irGoYrZ.gif
irGoYrZ.gif
irGoYrZ.gif
Đã viết kiểu nguy hiểm ntn sao k viết cái cache nó general luôn thím kân, :D
 
Đã viết kiểu nguy hiểm ntn sao k viết cái cache nó general luôn thím kân, :D
muốn bắt chước Python thêm @cache vô cái lambda mà ko được, C++23 có recursive lambdadeducing this may ra
KV0XGIA.gif


đại loại như
C++:
@cache // tự động cache f(i)
auto fact = [&](int n) {
   return fact(n - 1) + fact(n - 2); // recursive lambda
});
 
Last edited:
đây phen

C++:
class Solution {
    template <class T, class RecursiveFunc>
    class Cache {
    public:
        Cache(int target, RecursiveFunc&& f) : data(target + 1), f{std::move(f)} {}
        void set(int i, T value) { data[i] = value; }
        T operator[](int i) {
            if (!data[i]) data[i] = f(*this, i);
            return *data[i];
        }
       
    private:
        vector<optional<T>> data;
        RecursiveFunc f;
    };
   
public:
    int combinationSum4(vector<int>& nums, int target) {
        auto f = [&](auto& cache, int target){
            uint32_t res = 0;
            for (int n : nums) if (target >= n) res += cache[target - n];
            return res;
        };
        Cache<uint32_t, decltype(f)> m{target, std::move(f)};
        m.set(0, 1);
        return m[target];
    }
};
irGoYrZ.gif
irGoYrZ.gif
irGoYrZ.gif

Hay đấy bác. Thử mở rộng class Cache để accept nhiều tham số xem.
 
cụ viết đi, toy mù mấy cái template...
1xEuo02.gif

Vẫn phải nhập manual Result type chứ không tự deduce bằng invoke_result_t được ví lúc đó 2 type bị phụ thuộc vòng: lambda phụ thuộc Cache, Cache lại phụ thuộc lambda.

C++:
namespace std {
namespace {

template <typename T>
inline size_t hash_combine(size_t seed, T&& v)
{
    return seed ^= hash<remove_cv_t<remove_reference_t<T>>>()(forward<T>(v)) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

template <typename Tuple, size_t Index = tuple_size<Tuple>::value - 1>
struct TupleHash
{
    static size_t calculate(size_t seed, Tuple const &t)
    {
        seed = TupleHash<Tuple, Index - 1>::calculate(seed, t);
        return hash_combine(seed, std::get<Index>(t));
    }
};

template <typename Tuple>
struct TupleHash<Tuple, 0>
{
    static size_t calculate(size_t seed, Tuple const &t)
    {
        return hash_combine(seed, std::get<0>(t));
    }
};

} // namespace

template <typename... Args>
struct hash<tuple<Args...>>
{
    size_t operator()(tuple<Args...> const &tt) const
    {
        return TupleHash<tuple<Args...>>::calculate(0, tt);
    }
};

} // namespace std

template <typename RecursiveFunc, typename Result, typename... Args>
class Cache {
    using Params = std::tuple<Args...>;
    // using Result = std::invoke_result_t<RecursiveFunc, Cache&, Args...>;
public:
    Cache(RecursiveFunc&& f) : f{std::move(f)} {}

    void set(Result value, Args&&... args) {
        data[std::make_tuple(std::forward<Args>(args)...)] = value;
    }

    Result operator[](Args&&... args) {
        auto t = std::make_tuple(std::forward<Args>(args)...);
        if (auto it = data.find(t); it != data.end())
            return it->second;

        return data[t] = f(*this, std::forward<Args>(args)...);
    }

private:
    std::unordered_map<Params, Result> data;
    RecursiveFunc f;
};

using namespace std;

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        auto f = [&](auto& cache, uint32_t target){
            uint32_t res = 0;
            for (uint32_t n : nums) if (target >= n) res += cache[target - n];
            return res;
        };
        Cache<decltype(f), uint32_t, uint32_t> m{std::move(f)};
        m.set(1, 0);
        return m[target];
    }
};
[/spoler]
 
Last edited:
Mình mới làm cái Assement của AMZ nó có bài thế này:
Cho 1 mảng gồm các string thế này: a=["abc","bcd","cgh","hdg","bkv"]. Đếm số chuỗi là family trong mảng.
Định nghĩa 2 chuỗi family với nhau là như sau: So sánh 2 chuỗi nếu từng ký tự của chuỗi 1 là ký tự nối tiếp của chuỗi 2 thì nó là family. Ví dụ: "abc" và "bcd" là family do b là nối tiếp của a, c là nối tiếp của b, và d là nối tiếp của c... "abc" và "abc" không phải family.
Bạn nào gặp dạng bài này rồi chỉ mình với
Bài này e nghĩ là lưu toàn bộ chuỗi vào hashmap. Rồi duyệt qua từng chuỗi, nếu thấy chuỗi nối tiếp của nó trong hashmap thì cộng lên.
 
Em chưa leetcode bao giờ mà chuẩn bị phỏng vấn yêu cầu leetcode thì cắm đầu học cơ bản ở đâu đây các bác ?, biết là không kịp nhưng mà cố gắng còn hơn
 
Em chưa leetcode bao giờ mà chuẩn bị phỏng vấn yêu cầu leetcode thì cắm đầu học cơ bản ở đâu đây các bác ?, biết là không kịp nhưng mà cố gắng còn hơn

Vào leetcode làm mấy bài mức easy trước.

Sent from Samsung SM-A528B using vozFApp
 
Bài này e nghĩ là lưu toàn bộ chuỗi vào hashmap. Rồi duyệt qua từng chuỗi, nếu thấy chuỗi nối tiếp của nó trong hashmap thì cộng lên.
Mà vấn đề là bạn xét một chuỗi là nối tiếp của chuỗi kia thế nào? Dùng for loop từng chữ trong chuỗi hay sao?
 
Back
Top