给定一个 N 叉树，返回其节点值的 后序遍历 。
N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> ans = new ArrayList<>();
fun(root, ans);
return ans;
}
public void fun(Node root, List<Integer> ans) {
if (root == null) {
return;
}
if (root.children != null) {
for (Node n: root.children) {
fun(n, ans);
}
}
ans.add(root.val);
}
}
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> ans = new ArrayList<>();
Stack<Node> stack = new Stack<>();
if (root == null) {
return ans;
}
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
ans.add(node.val);
if (node.children != null) {
for (Node n : node.children) {
stack.push(n);
}
}
}
return ans;
}
}
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
示例 1：
输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]
class Solution {
public int findLHS(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
map.put(n, map.getOrDefault(n, 0) + 1);
}
int ans = 0;
for (int key: map.keySet()) {
if (map.containsKey(key + 1)) {
ans = Math.max(ans, map.get(key) + map.get(key + 1));
}
}
return ans;
}
}
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。
示例 1：
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int len = flowerbed.length;
if (len == 0 && n > 1) {
return false;
}
int i = 0;
while (i < len && n > 0) {
if (flowerbed[i] == 1) {
i += 2;
} else if (i == len - 1 || flowerbed[i + 1] == 0) {
n--;
i += 2;
} else {
i += 3;
}
}
return n <= 0;
}
}
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
target）都是正整数。示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
int sum = 0;
dfs(candidates, target, sum, 0);
return ans;
}
public void dfs(int[] candidates, int target, int sum, int index) {
if (sum > target) {
return;
}
if (sum == target) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = index; i < candidates.length; i++) {
sum += candidates[i];
path.add(candidates[i]);
dfs(candidates, target, sum, i);
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}
官方题解：
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> combine = new ArrayList<>();
dfs(candidates, target, ans, combine, 0);
return ans;
}
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int index) {
if (index == candidates.length) {
return;
}
if (target == 0){
ans.add(new ArrayList<>(combine));
return;
}
dfs(candidates, target, ans, combine, index + 1);
if (target>= candidates[index]) {
combine.add(candidates[index]);
dfs(candidates, target- candidates[index], ans, combine, index);
combine.remove(combine.size() - 1);
}
}
}