bài hnay dùng dp, lúc đầu dùng recursion bị tle
Nó là 1 trong 2 phương pháp trong dynamic programing mà. memo là top-down, còn tabular là bottom-upHầu hết các bài giải được bằng dp đều có thể giải bằng recursion + memo.
Mình dùng recursion chạy phà phà beat 90% luôn, cứ thêm memo vào là ổn thôi.bài hnay dùng dp, lúc đầu dùng recursion bị tle
xin chỉ giáoMình dùng recursion chạy phà phà beat 90% luôn, cứ thêm memo vào là ổn thôi.
bài hnay dùng dp, lúc đầu dùng recursion bị tle
nums = list(range(201))
target = 1000
đây phenxin chỉ giáo
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];
}
};
Đã viết kiểu nguy hiểm ntn sao k viết cái cache nó general luôn thím kân,đâ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]; } };
muốn bắt chước Python thêm @cache vô cái lambda mà ko được, C++23 cóĐã viết kiểu nguy hiểm ntn sao k viết cái cache nó general luôn thím kân,
@cache // tự động cache f(i)
auto fact = [&](int n) {
return fact(n - 1) + fact(n - 2); // recursive lambda
});
đâ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]; } };
nhiều tham số thì cái vector n chiều ko biết viết, vẽ code 1 tham số hù con nít thoyHay đấy bác. Thử mở rộng class Cache để accept nhiều tham số xem.
nhiều tham số thì cái vector n chiều ko biết viết, vẽ code 1 tham số hù con nít thoy
cụ viết đi, toy mù mấy cái template...vector thay bằng hash map của tuple.
Cần phải định nghĩa thêm hàm hash cho tuple.
cụ viết đi, toy mù mấy cái template...
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];
}
};
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ì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
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
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?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.