用dfs搜,只不过这个dfs要添加个leave用来表示当前所在的层数
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root==null) return res;
dfs(root,res,0);
return res;
}
public void dfs(TreeNode root,List<List<Integer>> res,int leave){
if(root==null)return;
if(res.size()<=leave)res.add(new ArrayList<Integer>());
res.get(leave).add(root.val);
dfs(root.left,res,leave+1);
dfs(root.right,res,leave+1);
}
}
就是把左右子节点交换,然后再递归下一个节点,从左到右,最后返回节点即可。
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)return null;
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
就镜像翻转,即做左子树的左子节点等于右子树的右子节点,右子节点等于左子节点。还有对应的值,分别根据条件判断即可。
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return dfs(root.left,root.right);
}
public boolean dfs(TreeNode left,TreeNode right){
if(left==null&&right==null){
return true;
}
else if(left==null||right==null){
return false;
}
else if(left.val!=right.val){
return false;
}
return dfs(left.left,right.right)&&dfs(left.right,right.left);
}
}
这题可以看成变形的01背包。因为数组中的每个数只能使用一次,把数组里的数据看作物品的重量,如果这些物品不能填满大小为k的背包,就说明不能组成数k。
背包容量的范围在【min,max】,arr数组相当于每个物品的重量
如果背包容量和所承载的物品重量不相等,就是所求
可以转换的原因是:背包容量[min,max]是数组的子集之和的范围,
比如数组2 3 4,背包从2~9,背包2号承载了子集2的和,背包5就是子集2,3的和,这里的2,3,4就可看作是元素权重,而某一个背包如果不能承载这些权重,就不是子集之和
dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
所以dp[j]可以看成为 j容量的背包下的最大价值为,所以就分为不选第i个和选第i个。 选第i个意味着第i个是必选的,所以直接加上第i个的大小,然后背包剩余容量就为j-arr[i],意味着变化发生在前1~i-1个之中。
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
//只有一个元素 ,在区间[min,max]上,如果所有的数都可以被arr的某一个子集相加得到,
//那么max+1是arr的最小不可组成和;
public class Main {
public static int unformedSum(int[] arr) {
if (arr == null || arr.length == 0) {
return 1;
}
//sum就是最大和,就是区间最大值,
int sum = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i != arr.length; i++) {
sum += arr[i];
min = Math.min(min, arr[i]);
}
int [] dp = new int[sum + 1];
for (int i = 0; i != arr.length; i++) {
for (int j = sum; j >= arr[i]; j--) {
//dp数组从后向前赋值
//dp[j-arr[i]]意思是背包承重为j时,如果已经放置了arr[i]的重量后还能放置的最大重量
dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
}
}
for (int i = min; i < sum; i++) {
if (dp[i]!=i) {
return i;
}
}
return sum + 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int len = sc.nextInt();
int max = 30;
int[] arr = new int[len];
for(int i = 0 ; i < len ; i++)
{
arr[i] = sc.nextInt();
}
System.out.println(unformedSum(arr));
}
}
这题题意比较难懂,在列了几个例子之后,我们发现这其实就是求斐波那契数列。
链接:https://www.nowcoder.com/questionTerminal/34f17d5f2a8240bea661a23ec095a062
来源:牛客网
/*
set A=|1 1| A^2=|2 1| A^3=|3 2| A^4=|5 3| A^5=|8 5|
|1 0| |1 1| |2 1| |3 2| |5 3|
事实上,实对称矩阵相乘仍然是实对称矩阵。观察易得,A^(n-1)由于左乘A(也可以右乘,此处举例左乘)
X1为上A^(n-1)的第一行元素相加 X2为A^(n-1)的第一个元素(左上角元素),由于对称X3和X2一样,
X4=A^(n-1)的第2个元素
迭代得到规律左上角元素X1[n]=X1[n-1]+X1[n-2] 为fb数列1 2 3 5 8
另外,不只是X1为此数列,其他所有元素都是这个数列
取4位只需%10000即可。
*/
import java.util.*;
public class Main{
public static void main(String[] args){
int[] arr = new int[10001];
arr[1] = 1;
arr[2] = 2;
for(int i = 3;i < 10001;i++){
arr[i] = arr[i - 1] + arr[i - 2];
arr[i] = arr[i] % 10000;
}
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
StringBuffer sb = new StringBuffer();
int n = sc.nextInt();
for(int i = 0;i < n;i++){
int x = sc.nextInt();
sb.append(String.format("%04d",arr[x]));
}
System.out.println(sb);
}
}
}