每日一题部分记录
https://leetcode.cn/problemset/ (opens in a new tab)
2月28：2673. 使二叉树所有路径值相等的最小代价
2673. 使二叉树所有路径值相等的最小代价 (opens in a new tab)
思路：贪心
我们首先考虑所有的叶结点。
对于任一叶结点，它的值为 x，它的兄弟节点的值为 y。 可以发现，对于树上的其余节点，它们要么同时是这两个叶节点的祖先，要么同时不是这两个叶节点的祖先。 对这些节点进行一次操作，要么同时增加了根到这两个叶节点的路径值，要么没有任何效果。 因此，要想使得根到这两个叶节点的路径值相等，我们只能增加 x 和 y 本身。
待考虑完所有叶节点之后，互为兄弟节点的叶节点的值两两相等（并且根到它们的路径值显然也相等）。 如果我们还需要操作某个叶节点，那么为了使得路径值相等，它的兄弟节点同样也需要操作。 此时就需要两次操作，但不如直接操作它们的双亲节点，可以省去一次操作。
因此，所有的叶节点都无需进行操作。我们就可以将它们全部移除。 为了使得路径值保持不变，我们可以将叶节点的值增加至它们的双亲节点。 这样一来，所有的双亲节点都变成了新的叶节点，我们重复进行上述操作即可。 当只剩一个节点（根节点）时，就可以得到最终的答案。
// 其实没必要使用[layer_start, layer_end]显式地按层遍历，
// 不过没什么大的效率差异，就不改了
class Solution {
public int minIncrements(int n, int[] cost) {
int layer_end = n;
int count = 0;
while (layer_end > 0) {
// [layer_start, layer_end]
int layer_start = (layer_end + 1) / 2;
int cur = layer_end;
while (cur > layer_start) {
int parent = cur / 2;
int max = Math.max(cost[cur - 1], cost[cur - 2]);
count += max * 2 - cost[cur - 1] - cost[cur - 2];
cost[parent - 1] += max;
cur -= 2;
}
layer_end = layer_start - 1;
}
return count;
}
}3月1：2369. 检查数组是否存在有效划分
2369. 检查数组是否存在有效划分 (opens in a new tab)
思路：动态规划，dp数组含义如下：
dp[i][0] 拿到第一个数的状态 (blocked)
dp[i][1] 拿到2个相等元素的状态 (can over)
dp[i][2] 拿到3个相等元素的状态 (can over)
dp[i][3] 拿到2个连续递增元素的状态 (blocked)
dp[i][4] 拿到3个连续递增元素的状态 (can over)
blocked意思是不能作为划分的最后一个元素， can over意思是可以作为划分的最后一个元素。
最终判断的是上述can over的状态是否至少有一个为true。
class Solution {
public boolean validPartition(int[] nums) {
// dp[i][0] 拿到第一个数的状态 (blocked)
// dp[i][1] 拿到2个相等元素的状态 (can over)
// dp[i][2] 拿到3个相等元素的状态 (can over)
// dp[i][3] 拿到2个连续递增元素的状态 (blocked)
// dp[i][4] 拿到3个连续递增元素的状态 (can over)
boolean[][] dp = new boolean[nums.length][5];
dp[0][0] = true;
for (int i = 1; i < nums.length; i++) {
dp[i][0] = dp[i - 1][1] || dp[i - 1][2] || dp[i - 1][4];
if (nums[i] == nums[i - 1]) {
dp[i][1] = dp[i - 1][0];
dp[i][2] = dp[i - 1][1];
}
else if (nums[i] == nums[i - 1] + 1) {
dp[i][3] = dp[i - 1][0];
dp[i][4] = dp[i - 1][3];
}
}
if (dp[nums.length - 1][1] || dp[nums.length - 1][2] || dp[nums.length - 1][4]) {
return true;
}
else return false;
}
}3月2：2368. 受限条件下可到达节点的数目
2368. 受限条件下可到达节点的数目 (opens in a new tab)
自己解法1
思路：遍历边集，如果边的一个顶点和0相连且另一个顶点不是受限顶点，则将此顶点加入与0相连的集合。 重复上述操作，直到与0相连的集合不再变化。
这种解法会超时...
class Solution {
public int reachableNodes(int n, int[][] edges, int[] restricted) {
int ans = 1;
boolean changed = true;
boolean[] set = new boolean[n];
boolean[] restricted_set = new boolean[n];
set[0] = true;
for (int e : restricted) {
restricted_set[e] = true;
}
while (changed) {
changed = false;
for (int[] v : edges) {
if (set[v[0]] && !restricted_set[v[1]] && !set[v[1]]) {
set[v[1]] = true;
changed = true;
ans++;
}
if (set[v[1]] && !restricted_set[v[0]] && !set[v[0]]) {
set[v[0]] = true;
changed = true;
ans++;
}
}
}
return ans;
}
}自己解法2
建表，dfs遍历。
class Solution {
private int ans = 1;
List<Integer>[] matrix;
boolean[] set;
public int reachableNodes(int n, int[][] edges, int[] restricted) {
boolean[] restricted_set = new boolean[n];
matrix = new List[n];
set = new boolean[n];
for (int e : restricted) {
restricted_set[e] = true;
}
for (int i = 0; i < n; i++) {
matrix[i] = new ArrayList<Integer>();
}
for (int[] e : edges) {
if (!restricted_set[e[0]] && !restricted_set[e[1]]) {
matrix[e[0]].add(e[1]);
matrix[e[1]].add(e[0]);
}
}
set[0] = true;
dfs(n, 0);
return ans;
}
private void dfs(int n, int cur) {
for (int i = 0; i < matrix[cur].size(); i++) {
if (!set[matrix[cur].get(i)]) {
ans++;
set[matrix[cur].get(i)] = true;
dfs(n, matrix[cur].get(i));
}
}
}
}3月5：1976. 到达目的地的方案数
1976. 到达目的地的方案数 (opens in a new tab)
思路：dijkstra算法+动态规划
class Solution {
public int countPaths(int n, int[][] roads) {
long[][] G = new long[n][n];
long[] dist = new long[n];
long[] D = new long[n];
int[] count = new int[n];
for (long[] row : G) {
Arrays.fill(row, Long.MAX_VALUE / 2);
}
Arrays.fill(dist, Long.MAX_VALUE / 2);
Arrays.fill(D, Long.MAX_VALUE / 2);
Arrays.fill(count, 0);
// 构建邻接矩阵
for (int i = 0; i < roads.length; i++) {
G[roads[i][0]][roads[i][1]] = roads[i][2];
G[roads[i][1]][roads[i][0]] = roads[i][2];
}
// dij算法求最短路+dp计算路的数量
dist[0] = 0;
D[0] = 0;
count[0] = 1;
int i = 0;
for (int k = 0; k < n - 1; k++) {
int minIndex = 0;
long min = Long.MAX_VALUE / 2;
for (int j = 0; j < n; j++) {
// 如果ij有路
if (G[i][j] < Long.MAX_VALUE / 2) {
// 如果是新的最短路
if (D[i] + G[i][j] < dist[j]) {
// 更新最短路
dist[j] = D[i] + G[i][j];
// 更新dp：到j的最短路数量 = 到i最短路的数量
count[j] = count[i];
}
// 如果与记录的最短路相同
else if (D[i] + G[i][j] == dist[j]) {
// 更新dp：到j的最短路数量 += 到i最短路的数量
count[j] = (count[j] + count[i]) % (int) (1e9 + 7);
}
}
if (D[j] == Long.MAX_VALUE / 2 && dist[j] < min) {
min = dist[j];
minIndex = j;
}
}
D[minIndex] = min;
i = minIndex;
}
// System.out.println(D[n - 1]);
return count[n - 1];
}
}3月6：2917. 找出数组中的 K-or 值
2917. 找出数组中的 K-or 值 (opens in a new tab)
简单题，注意位运算和越界就行
((num >> i) & 1) != 0 代表第i位是否为1
3月7：2575. 找出字符串的可整除数组
2575. 找出字符串的可整除数组 (opens in a new tab)
分析：本题字符串数字长度过大，无法直接数字模除，当然可以考虑用java的BigInteger，但是这样效率太低。
思路：利用模除性质动规
余数的递推公式是：rest = (rest * 10 + 当前位) % m，
因为m是int范围，所以rest最大也可以用long存储，不会越界。
class Solution {
public int[] divisibilityArray(String word, int m) {
int[] resu = new int[word.length()];
int start = 0;
long rest = 0;
String str_m = Integer.toString(m);
for (int i = 0; i < word.length(); i++) {
// int now = Integer.parseInt(word.substring(i, i + 1));
// rest = (rest * 10 + now) % m;
// 直接操作char效率更高
char c = word.charAt(i);
rest = (rest * 10 + (c - '0')) % m;
if (rest == 0) resu[i] = 1;
}
return resu;
}
}这边也给出BigInteger的解法：
import java.math.BigInteger;
class Solution {
public int[] divisibilityArray(String word, int m) {
int[] resu = new int[word.length()];
int start = 0;
String str_m = Integer.toString(m);
for (int i = 0; i < word.length(); i++) {
BigInteger dived = new BigInteger(word.substring(start, i + 1));
BigInteger diver = new BigInteger(str_m);
if (dived.mod(diver).equals(BigInteger.ZERO)) {
resu[i] = 1;
start = i + 1;
}
}
return resu;
}
}3月8：2834. 找出美丽数组的最小和
2834. 找出美丽数组的最小和 (opens in a new tab)
思路：贪心
本来用hashset解的，但是超内存限制，所以还是按数学方式贪心来做
class Solution {
public int minimumPossibleSum(int n, int target) {
// Set<Integer> beauty = new HashSet<>(2 * n);
// int now = 1;
// int count = 0;
// int sum = 0;
// while (count < n) {
// if (!beauty.contains(now) && !beauty.contains(target - now)) {
// beauty.add(now);
// count++;
// sum = (sum + now) % (int) (1e9 + 7);
// }
// now++;
// }
// return sum;
long half = target / 2;
if (n <= half)
return (int) ((long) ((1 + n) * n / 2) % (int) (1e9 + 7));
else
return (int) ((long) (((1 + half) * half / 2) + (long) ((target + target + (n - half) - 1) * (n - half) / 2)) % (int) (1e9 + 7));
}
}3月10：299. 猜数字游戏
299. 猜数字游戏 (opens in a new tab)
思路：哈希
总共遍历3次：一次建立secret的哈希表，一次遍历计算bulls，一次遍历计算cows。
一定要先计算bulls，再计算cows，避免计算cows计算时把后面可能是bulls的地方先改了
class Solution {
public String getHint(String secret, String guess) {
int bulls = 0;
int cows = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < secret.length(); i++) {
int cur = secret.charAt(i) - '0';
if (map.containsKey(cur)) {
map.put(cur, map.get(cur) + 1);
}
else {
map.put(cur, 1);
}
}
for (int i = 0; i < guess.length(); i++) {
int cur = guess.charAt(i) - '0';
if (i < secret.length() && secret.charAt(i) == guess.charAt(i)) {
bulls++;
if (map.get(cur) > 1) map.put(cur, map.get(cur) - 1);
else map.remove(cur);
}
}
for (int i = 0; i < guess.length(); i++) {
int cur = guess.charAt(i) - '0';
if (i < secret.length() && secret.charAt(i) == guess.charAt(i)) {
}
else {
if (map.containsKey(cur)) {
cows++;
if (map.get(cur) > 1) map.put(cur, map.get(cur) - 1);
else map.remove(cur);
}
}
}
return "" + bulls + "A" + cows + "B";
}
}3月15：2312. 卖木头块
2312. 卖木头块 (opens in a new tab)
思路：递归+记忆化搜索
class Solution {
private long[][] dp;
private int[][] priceM;
public long sellingWood(int m, int n, int[][] prices) {
// dp[m][n]表示大小为m,n的木块的最大钱数
// 初始化
dp = new long[m + 1][n + 1];
for (long[] row : dp) {
Arrays.fill(row, -1L);
}
// priceM[i][j] 表示长i宽j的木块的价格
priceM = new int[m + 1][n + 1];
for (int[] price : prices) {
priceM[price[0]][price[1]] = price[2];
}
return recu(m, n);
}
private long recu(int m, int n) {
if (m == 0 || n == 0) return 0L;
if (dp[m][n] != -1) {
return dp[m][n];
}
long max = 0L;
if (priceM[m][n] != 0) max = (long) priceM[m][n];
// 可横切
for (int i = 1; i < m; i++) {
long cur_max = recu(i, n) + recu(m - i, n);
if (cur_max > max) max = cur_max;
}
// 可竖切
for (int j = 1; j < n; j++) {
long cur_max = recu(m, j) + recu(m, n - j);
if (cur_max > max) max = cur_max;
}
dp[m][n] = max;
return max;
}
}3月16：310. 最小高度树
310. 最小高度树 (opens in a new tab)
自己解法
思路1：两次深搜，找最长路径，其中点即为答案（可能有1个或2个）
注意n*n的邻接矩阵在面临n较大的稀疏矩阵时会超内存，建议使用邻接表
class Solution {
private List<Integer> path = new ArrayList();
private int max_height= 0;
private int farest_node = 0;
List<Integer>[] matrix;
boolean[] visited;
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
matrix = new List[n];
visited = new boolean[n];
List<Integer> ans = new ArrayList();
for (int i = 0; i < n; i++) {
matrix[i] = new ArrayList<Integer>();
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
matrix[u].add(v);
matrix[v].add(u);
}
dfs(n, 0, 1);
int endpoint1 = farest_node;
Arrays.fill(visited, false);
max_height = 0;
farest_node = 0;
dfs(n, endpoint1, 0);
int endpoint2 = farest_node;
Arrays.fill(visited, false);
max_height = 0;
farest_node = 0;
dfsPath(n, endpoint1, endpoint2);
if (path.size() % 2 == 0) {
ans.add(path.get(path.size() / 2));
ans.add(path.get(path.size() / 2 - 1));
}
else {
ans.add(path.get(path.size() / 2));
}
return ans;
}
private boolean dfsPath(int n, int start, int end) {
// System.out.println(start);
visited[start] = true;
path.add(start);
if (start == end) {
return true;
}
for (int i = 0; i < matrix[start].size(); i++) {
if (!visited[matrix[start].get(i)]) {
if (!dfsPath(n, matrix[start].get(i), end)) {
path.remove(path.size() - 1);
}
else return true;
}
}
return false;
}
private void dfs(int n, int root, int height) {
visited[root] = true;
if (height > max_height) {
max_height = height;
farest_node = root;
}
for (int i = 0; i < matrix[root].size(); i++) {
if (!visited[matrix[root].get(i)]) {
dfs(n, matrix[root].get(i), height + 1);
}
}
return;
}
}题解解法
思路2：拓扑排序
-
首先找到所有度为 1 的节点压入队列，此时令节点剩余计数
remainNodes=n； -
将当前
remainNodes计数减去度为 1 的节点数目，将最外层的度为 1 的叶子节点取出， 并将与之相邻的节点的度减少，重复上述步骤将当前节点中度为 1 的节点压入队列中； -
重复上述步骤，直到剩余的节点数组
remainNodes≤2时，此时剩余的节点即为当前高度最小树的根节点。
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer>[] matrix = new List[n];
int[] degree = new int[n];
List<Integer> ans = new ArrayList();
if (n == 1) {
ans.add(0);
return ans;
}
for (int i = 0; i < n; i++) {
matrix[i] = new ArrayList<Integer>();
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
matrix[u].add(v);
matrix[v].add(u);
degree[u]++;
degree[v]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 1) {
queue.offer(i);
}
}
int remain = n;
while (remain > 2) {
int sz = queue.size();
remain -= sz;
for (int i = 0; i < sz; i++) {
int curr = queue.poll();
for (int v : matrix[curr]) {
degree[v]--;
if (degree[v] == 1) {
queue.offer(v);
}
}
}
}
while (!queue.isEmpty()) {
ans.add(queue.poll());
}
return ans;
}
}3月19：1793. 好子数组的最大分数
1793. 好子数组的最大分数 (opens in a new tab)
思路：双指针，复杂度O(n)
从中间出发，向两边扩展：
-
保证答案变大的尝试：
-
如果左面的下一个数不小于当前区间最小的数，左指针左移（先判断指针是否越界）
-
如果右面的下一个数不小于当前区间最小的数，右指针右移（先判断指针是否越界）
-
-
不保证答案变大的尝试：经过上面的判断，左指针左边和右指针右边的数都小于当前区间最小的数，所以左右指针都可以左右移动（不越界的情况下）
-
如果移动左指针，先记录一个答案，但不更新左指针
-
如果移动右指针，先记录一个答案，但不更新右指针
-
判断到底该移动哪个：此时才更新左或右指针
-
如果左右指针都不越界，移动左右指针中大的那个（因为反正移动指针，区间就会变大，移动大的那个更可能会使答案变大）
-
如果只有一个指针越界，移动另一个
-
如果都越界，结束
-
-
class Solution {
public int maximumScore(int[] nums, int k) {
int left = k;
int right = k;
int ans = nums[k];
int min = nums[k];
while (left > 0 || right < nums.length - 1) {
// System.out.println("==================================");
// System.out.println("left: " + left + " right: " + right + " min: " + min);
while (left > 0 && nums[left - 1] >= min) {
left--;
}
ans = Math.max(ans, (right - left + 1) * min);
// System.out.println("right: " + right + ", left: " + left + " min: " + min + " ans: " + ans);
while (right < nums.length - 1 && nums[right + 1] >= min) {
right++;
}
ans = Math.max(ans, (right - left + 1) * min);
// System.out.println("right: " + right + ", left: " + left + " min: " + min + " ans: " + ans);
if (left > 0) {
// left--;
ans = Math.max(ans, (right - left + 2) * nums[left - 1]);
// System.out.println("right: " + right + ", left: " + (left - 1) + " min: " + nums[left - 1] + " ans: " + ans);
}
if (right < nums.length - 1) {
// right++;
ans = Math.max(ans, (right - left + 2) * nums[right + 1]);
// System.out.println("right: " + (right + 1) + ", left: " + left + " min: " + nums[right + 1] + " ans: " + ans);
}
if (left > 0 && right < nums.length - 1) {
if (nums[left - 1] < nums[right + 1]) {
min = nums[right + 1];
right++;
} else {
min = nums[left - 1];
left--;
}
} else if (left > 0) {
min = nums[left - 1];
left--;
} else if (right < nums.length - 1) {
min = nums[right + 1];
right++;
} else {
break;
}
// System.out.println("left: " + left + " right: " + right + " min: " + min);
// System.out.println("==================================");
}
return ans;
}
}3月20：1969. 数组元素的最小非零乘积
1969. 数组元素的最小非零乘积 (opens in a new tab)
思路：数学+快速幂
class Solution {
private final long MOD = (long) 1e9 + 7;
public int minNonZeroProduct(int p) {
if (p == 1) return 1;
long countOne = 1L;
// 每一位上1的数量
countOne = countOne << (p - 1);
// 每一位上0的数量
long countZero = countOne - 1;
// 因数和幂次
long factor = (1L << p) - 2;
long power = countZero;
// 最后一个要乘的数
long pow = quickPow(factor, power);
long last = (1L << p) - 1;
int resu = (int) (((pow % MOD) * (last % MOD)) % MOD);
return resu;
}
private long quickPow(long factor, long power) {
if (power == 0) return 1;
if (power == 1) return factor;
long part = quickPow(factor, power / 2);
if (power % 2 == 1) {
return (((part % MOD) * (part % MOD)) % MOD * (factor % MOD)) % MOD;
}
else {
return ((part % MOD) * (part % MOD)) % MOD;
}
}
}3月27：2580. 统计将重叠区间合并成组的方案数
2580. 统计将重叠区间合并成组的方案数 (opens in a new tab)
思路：贪心+数学（快速幂）
先排序，排序后贪心合并，然后计算方案数。
计算方案数：合并后的每个区间可以出现在组1也可以出现在组2，所以是2的区间数次方。别傻乎乎一个一个算组合数
class Solution {
public int countWays(int[][] ranges) {
if (ranges.length == 1) return 2;
// 计算不重叠区间数量(类似合并区间)
Arrays.sort(ranges, (a, b) -> {
if(a[0] == b[0]) return Integer.compare(a[1], b[1]);
else return Integer.compare(a[0], b[0]);
});
List<Integer> counts = new ArrayList<>();
int right = ranges[0][1];
int count = 1;
for (int i = 1; i < ranges.length; i++) {
if(ranges[i][0] > right) {
counts.add(count);
count = 1;
right = ranges[i][1];
if (i == ranges.length - 1) counts.add(count);
}
else {
count++;
right = Math.max(right, ranges[i][1]);
if (i == ranges.length - 1) counts.add(count);
}
}
return (int) quickPow(2, counts.size());
}
private final long MOD = (long) 1e9 + 7;
public long quickPow(long factor, long power) {
if (power == 0) return 1;
if (power == 1) return factor;
long part = quickPow(factor, power / 2);
if (power % 2 == 1) {
return (((part % MOD) * (part % MOD)) % MOD * (factor % MOD)) % MOD;
}
else {
return ((part % MOD) * (part % MOD)) % MOD;
}
}
}3月30：2952. 需要添加的硬币的最小数量
2952. 需要添加的硬币的最小数量 (opens in a new tab)
数组可重复、取硬币不可重复
思路：贪心
如果[0,getable]的数值是可以得到的，且getable+1的数在数组中，那么[0,getable*2+1]的数值也是可以得到的。
为了实现贪心，要先对数组排序，从最小硬币开始：
-
如果当前硬币小于getable+1，那么
getable = Math.max(coins[coinIndex] * 2 - 1, getable + coins[coinIndex]);. 含义是：当前硬币是没有用过的，如果当前数值小于等于getable，那么getable可以扩展到当前硬币的两倍减一，也可以扩展到添加当前硬币。 -
如果当前硬币等于getable+1，那么getable可以扩展到当前硬币的两倍减一。
-
如果当前硬币大于getable+1，那么需要添加一个硬币，其值为getable+1。
class Solution {
public int minimumAddedCoins(int[] coins, int target) {
Arrays.sort(coins);
int ans = 0;
int getable = 0;
int coinIndex = 0;
while (getable < target) {
System.out.println(getable);
while (coinIndex < coins.length && coins[coinIndex] < getable + 1) {
getable = Math.max(coins[coinIndex] * 2 - 1, getable + coins[coinIndex]);
coinIndex++;
}
// 注意额外判断一次跳出
if (getable >= target) break;
if (coinIndex < coins.length && getable + 1 == coins[coinIndex]) {
getable = coins[coinIndex] * 2 - 1;
coinIndex++;
}
else {
ans++;
System.out.println("add: " + (getable + 1));
getable = getable * 2 + 1;
}
}
return ans;
}
}4月2：894. 所有可能的真二叉树
894. 所有可能的真二叉树 (opens in a new tab)
思路：递归+记忆化搜索
非常考验对递归的理解，原来想的是到达叶子后把树从根节点拷贝一份，然后回溯，但是这样会导致重复计算，而且实际上一边到叶子时另一边不一定到叶子，所以不可行。
实际上在递归的时候就可以把左右子树的所有可能都计算出来，然后再组合。
组合是重点！！！
除此之外可以考虑用记忆化搜索，但是题目比较小，也无所谓了。
下面写了两种解法，一种是记忆化搜索，一种是普通递归。稍微统计了一下运行时间和访问递归次数，普通递归效率明显低得多。
public class Solution {
public static void main(String[] args) throws Exception {
try {
Solution s = new Solution();
int n = 25;
long startTime = System.currentTimeMillis();
s.allPossibleFBT(n);
long endTime = System.currentTimeMillis();
long duration = endTime - startTime; // Compute the elapsed time in milliseconds.
System.out.println("Execution time: " + duration + " milliseconds");
System.out.println("count: " + s.count);
long startTime2 = System.currentTimeMillis();
s.allPossibleFBT2(n);
long endTime2 = System.currentTimeMillis();
long duration2 = endTime2 - startTime2; // Compute the elapsed time in milliseconds.
System.out.println("Execution time: " + duration2 + " milliseconds");
System.out.println("count2: " + s.count2);
}
catch (Exception e) {
System.out.println(e.getMessage());
}
}
private int count2 = 0;
public List<TreeNode> allPossibleFBT2(int n) {
count2++;
List<TreeNode> possibles = new ArrayList<TreeNode>();
if (n % 2 == 0) return possibles;
if (n == 1) {
possibles.add(new TreeNode(0));
return possibles;
}
n -= 1;
for (int i = 1; i <= n; i += 2) {
List<TreeNode> leftPossibles = allPossibleFBT2(i);
List<TreeNode> rightPossibles = allPossibleFBT2(n - i);
for (TreeNode left : leftPossibles) {
for (TreeNode right : rightPossibles) {
possibles.add(new TreeNode(0, left, right));
}
}
}
return possibles;
}
private int count = 0;
private List<List<TreeNode>> global_possibles = new ArrayList<>();
public List<TreeNode> allPossibleFBT(int n) {
for (int i = 0; i <= n; i++) {
global_possibles.add(null);
}
List<TreeNode> resu = invert(n);
return resu;
}
private List<TreeNode> invert (int n) {
if (global_possibles.get(n) != null) return global_possibles.get(n);
count++;
List<TreeNode> possibles = new ArrayList<TreeNode>();
if (n % 2 == 0) return possibles;
if (n == 1) {
possibles.add(new TreeNode(0));
global_possibles.set(n, possibles);
return possibles;
}
n -= 1;
for (int i = 1; i <= n; i += 2) {
if (global_possibles.get(i) == null) global_possibles.set(i, invert(i));
List<TreeNode> leftPossibles = global_possibles.get(i);
if (global_possibles.get(n - i) == null) global_possibles.set(n - i, invert(n - i));
List<TreeNode> rightPossibles = global_possibles.get(n - i);
for (TreeNode left : leftPossibles) {
for (TreeNode right : rightPossibles) {
possibles.add(new TreeNode(0, left, right));
}
}
}
return possibles;
}
}// n = 25时：
// 记忆化
Execution time: 11 milliseconds
count: 13
// 普通
Execution time: 85 milliseconds
count2: 531441