Terminus

在考虑加入「记忆化」时，我们只需要将 DFS 方法签名中的【可变】参数作为维度，DFS 方法中的返回值作为存储值即可。 123456789101112131415161718192021222324252627282930313233343536373839class Solution { public: int n; vector<int> stones; map<int, int> mp; map<int, bool> f; // 记忆化搜索 cache bool canCross(vector<int>& _stones) { stones = _stones; n = stones.size(); if (stones[1] != 1) return false; for (int i = 0; i < n; i++) mp[stones[i]] = i; // 反查表 return dfs(1, 1); } /** * 判定是否能够跳 ...

所有可能的路径 1234567891011121314151617181920212223class Solution { public: vector<int> path; vector<vector<int>> ans; int n; vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { n = graph.size(); path.push_back(0); dfs(0, graph); return ans; } void dfs(int u, vector<vector<int>>& g) { if (u == n - 1) { ans.push_back(path); return; } for (int i = 0; i < ...

写几个策略类，都实现同一个接口。写一个 Context 类，里面有一个策略对象属性，通过构造函数传入一个策略对象，对外暴露一个 exec 方法，用于传入执行策略所需的上下文，然后执行策略。

代理类和被代理的类都实现同一个接口，代理类可以根据条件决定是否执行被代理对象的方法。代理类里有一个被代理对象的属性，通过代理类的构造函数传输被代理对象来初始化它。代理类可以有自己的接口，接口可以定义代理相关的方法。 普通代理 将被代理对象的初始化放到代理类中，不允许直接初始化被代理类。必须通过创建代理对象来访问被代理对象。 强制代理 必须通过真实角色找到代理角色进行访问操作。真实角色的成员方法中判断是不是通过代理访问，如果不是就抛错。真实角色接口增加一个 getProxy 方法用于获取它的代理对象。 虚拟代理 在调用被代理对象方法时才初始化被代理对象，避免被代理对象较多时引起的初始化缓慢问题。 动态代理 被代理类必须实现一个接口。AOP。动态代理的初始化，接收一个 Class，接口，和一个用于实现接口方法的 InvocationHandler。全部由 InvocationHandler.invoke 执行接口真实对象的方法，因此可以在执行前、执行后插入一些逻辑。

Invoker 上面有一个 AbstractCmd 属性，构造函数负责初始化它。还有一个 execute 方法，负责接受参数并调用 cmd.execute。 场景类里，new 一个 Command，用 cmd 作为参数 new 一个 Invoker，然后 invoker.execute(参数)。

每个节点有两个选择：要么承担责任做出回应，要么把请求发到后续环节。 new 几个 Handler，通过 Handler.setNext 编排责任链，请求会沿着责任链传递，每个 Handler.handlerMessage 方法会检测当前能否处理这个 request，如果不能就调用 this.nextHandler.handleMessage(request)，如果可以处理，就直接返回结果。 注意链中节点数目不应该过多。 例：Express 中间件，将 request 在不同的中间件传递，执行不同的操作。

将原问题转化为求矩阵的幂的问题，然后利用矩阵快速幂求解。 123456789101112131415161718192021222324252627typedef long long LL;class Solution { public: const int N = 3; vector<vector<LL>> mul(vector<vector<LL>>& a, vector<vector<LL>>& b) { vector<vector<LL>> c(N, vector<LL>(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j]; } ...

超级丑数 12345678910111213141516171819202122typedef long long LL;class Solution { public: int nthSuperUglyNumber(int n, vector<int>& primes) { unordered_set<LL> s; priority_queue<LL, vector<LL>, greater<LL>> q; q.push(1l); s.insert(1l); while (n--) { auto t = q.top(); q.pop(); if (n == 0) return (int)t; for (auto x : primes) { if (!s.count(t * x)) { s.insert(t * x); q.push(t * x); ...

Invoker 上面有一个 AbstractCmd 属性，构造函数负责初始化它。还有一个 execute 方法，负责接受参数并调用 cmd.execute。 场景类里，new 一个 Command，用 cmd 作为参数 new 一个 Invoker，然后 invoker.execute(参数)。