• 算法刷题日志10.20


    二叉树的层序遍历

    在这里插入图片描述

    用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);
    
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    翻转二叉树

    在这里插入图片描述

    就是把左右子节点交换,然后再递归下一个节点,从左到右,最后返回节点即可。

    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;   
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    对称二叉树

    在这里插入图片描述

    就镜像翻转,即做左子树的左子节点等于右子树的右子节点,右子节点等于左子节点。还有对应的值,分别根据条件判断即可。

    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);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    求正数数组的最小不可组成和

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    这题可以看成变形的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));
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    星际密码

    在这里插入图片描述

    这题题意比较难懂,在列了几个例子之后,我们发现这其实就是求斐波那契数列。
    链接: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);
            }
             
        }    
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
  • 相关阅读:
    投稿开奖丨轻量应用服务器征文活动(5月)奖励公布
    【kerberos】使用 curl 访问受 Kerberos HTTP SPNEGO 保护的 URL
    10.0 探索API调试事件原理
    【openSSH】通过证书文件免密码远程登录
    【数模之数据分析-1】
    这个困扰程序员50年的问题,终于要被解决了?
    第一章 操作系统概述
    【计算机网络】75 张图详解:网络设备、网络地址规划、静态路由(万字长文)
    【Maven】Unknown lifecycle phase “.skip.test=true“.
    Mybatis-plus的介绍与使用
  • 原文地址:https://blog.csdn.net/crisp0530/article/details/127437250