God Emperor Leto
Senior Member
sửa lại cho ngắn hơn
C++:
namespace std {
namespace {
template <class T>
size_t hash_combine(size_t seed, const T& v) {
return seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
} // namespace
template <class... Args>
struct hash<tuple<Args...>> {
template <size_t Index = sizeof...(Args) - 1>
size_t operator()(const tuple<Args...>& t, size_t seed = 0) const {
if constexpr (Index == 0) {
return hash_combine(seed, get<0>(t));
} else {
seed = operator()<Index - 1>(t, seed);
return hash_combine(seed, get<Index>(t));
}
}
};
} // namespace std
template <class RecursiveFunc, class Result, class... Args>
class Memo {
using Params = std::tuple<Args...>;
public:
explicit Memo(RecursiveFunc&& f) : f{move(f)} {}
Result operator()(Args... args) {
Params t = std::forward_as_tuple(args...);
auto it = cache.find(t);
if (it == end(cache))
std::tie(it, std::ignore) = cache.emplace(std::move(t), f(*this, std::forward<Args>(args)...));
return it->second;
}
private:
RecursiveFunc f;
std::unordered_map<Params, Result> cache;
};
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
auto f = [&](auto& f, int target) -> uint32_t {
if (target == 0) return 1;
uint32_t res = 0;
for (int n : nums) if (target >= n) res += f(target - n);
return res;
};
return Memo<decltype(f), uint32_t, int>{move(f)}(target);
}
};ko cần cái hàm set kia làm gì nữa
C++:
if (target == 0) return 1;
uint32_t res = 0;
for (int n : nums) if (target >= n) res += f(target - n);
return res;
dòng
C++:
return Memo<decltype(f), uint32_t, int>{move(f)}(target);
có lẽ CRTP làm được nhưng phải viết class kế thừa vào, phải lấy cái nums kia qua ctor, ko gọn bằng [&]
---
edit: lấy ResultType được kìa
C++:
namespace std {
namespace {
template <class T>
size_t hash_combine(size_t seed, const T& v) {
return seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
} // namespace
template <class... Args>
struct hash<tuple<Args...>> {
template <size_t Index = sizeof...(Args) - 1>
size_t operator()(const tuple<Args...>& t, size_t seed = 0) const {
if constexpr (Index == 0) {
return hash_combine(seed, get<0>(t));
} else {
seed = operator()<Index - 1>(t, seed);
return hash_combine(seed, get<Index>(t));
}
}
};
} // namespace std
template <class RecursiveFunc, class... Args>
class Memo {
using Params = std::tuple<std::remove_cv_t<std::remove_reference_t<Args>>...>;
using Result = std::result_of_t<RecursiveFunc(Memo<RecursiveFunc, Args...>&, Args...)>;
public:
explicit Memo(RecursiveFunc&& f) : f{std::move(f)} {}
Result operator()(Args... args) {
Params t = std::forward_as_tuple(args...);
auto it = cache.find(t);
if (it == end(cache))
std::tie(it, std::ignore) = cache.emplace(std::move(t), f(*this, std::forward<Args>(args)...));
return it->second;
}
private:
RecursiveFunc f;
std::unordered_map<Params, Result> cache;
};
template <class RecursiveFunc, class... Args>
auto memoize(RecursiveFunc/*&&*/ f, Args/*&&*/... args) {
return Memo<RecursiveFunc, Args...>{std::move(f)}(std::forward<Args>(args)...);
}
C++:
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
auto f = [&](auto& f, int i) -> uint32_t {
if (i == 0) return 1;
uint32_t res = 0;
for (int n : nums) if (i >= n) res += f(i - n);
return res;
};
return memoize(f, target);
}
};- xài using Params = std::tuple<Args...>; thì nó chạy sai: https://rextester.com/QTC87092 với lvalue/const/volatile gì tùm lum chắc là do dangling ref, phải sửa lại remove ref/cv hết
- xài perfect forwarding Args&& cho memoize thì gọi memoize(f, target) ko được vì f nhận int, mà perfect forwarding nó forward int& target khi xài phải viết lại 1 là memoize(f, target + 0) 2 là memoize(f, int(target)) đều xấu
vì Params luôn là tuple<T1, T2, ... Tn> ko có ref/cv gì hết nên xài Args cho ròi, xài Args&& thì viết t1 + 0 t2 + 0 gì chắc
test thử bài unique path bữa trước: https://leetcode.com/submissions/detail/766251301/
Last edited:
