leetcode算法题解(Java版)-12-中序遍历

简介: 题目看上去像是二叉搜索树的题,实际上是动态规划。给到1~n的数,要找出多少种二叉查找树,对于取值为k的数来说,在它左边的又1~k-1,右边的有k+1~n.所以可以把左子树排列的种数乘右子树的种数得到以这个为根的二叉查找树的个数。

日子又恢复正常了,浪了半个月。。。
还是学习的时候感觉好~~

一、动态规划

题目描述

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路

  • 题目看上去像是二叉搜索树的题,实际上是动态规划。给到1~n的数,要找出多少种二叉查找树,对于取值为k的数来说,在它左边的又1~k-1,右边的有k+1~n.所以可以把左子树排列的种数乘右子树的种数得到以这个为根的二叉查找树的个数。
  • 用一个状态数组记录下值。

代码

public class Solution {
    public int numTrees(int n) {
        if(n==0){
            return 0;
        }
        int [] f = new int[n+1];
        f[0]=1;
        for(int i=1;i<=n;i++){//外循环,刷新1,2,3,4.。。n的结果
            for(int j=1;j<=i;j++){//小循环,计算各个的值
                f[i]+=f[j-1]*f[i-j];
            }
        }
        return f[n];
    }
}

二、中序遍历

题目描述

Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree{1,#,2,3},

   1
    \
     2
    /
   3

return[1,3,2].

思路

  • 二叉树的中序遍历,就是所谓的左-中-右。
  • 递归和非递归方法,直接看代码!

代码

//递归
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer>  res=new ArrayList<Integer>();
        if(root==null)return res;
        inorder(root,res);
        return res;
    }
     public static void inorder(TreeNode root, ArrayList<Integer> list){
        if(root != null){
            inorder(root.left,list);
            list.add(root.val);
            inorder(root.right,list);
        }
    }
}
//非递归
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        TreeNode node = root;
        if(root==null){
            return res;
        }
        while(!stack.isEmpty()||node!=null){
            while(node!=null){
                stack.add(node);
                node = node.left;
            }
            node = stack.pop();
            res.add(node.val);
            node = node.right;
        }
        return res;
    }
}

三、深搜

题目描述

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given"25525511135",
return["255.255.11.135", "255.255.111.35"]. (Order does not matter)

思路

  • 深度搜索+回溯的时候剪枝

代码

import java.util.ArrayList;

public class Solution {
    public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> res =new  ArrayList<String>();
        ArrayList<String> ip =new ArrayList<String>();
        int start = 0 ;
        dfs(s,res,ip,start);
        return res;
    }
    
    public void dfs(String s,ArrayList<String> res,ArrayList<String> ip,int start){
        if(ip.size()==4&&start==s.length()){
            res.add(ip.get(0)+'.'+ip.get(1)+'.'+ip.get(2)+'.'+ip.get(3));
        }
        
        
        if(s.length()-start > 3*(4-ip.size())){//剪枝
            return ;
        }
        if(s.length()-start+1 < 4-ip.size()){//剪枝
            return ;
        }
        int num = 0 ;
        for(int i=start;i<start+3&&i<s.length();i++){
            num = num*10+(s.charAt(i)-'0');
            if(num<0||num>255){
                return ;
            }
            ip.add(s.substring(start,i+1));
            dfs(s,res,ip,i+1);
            ip.remove(ip.size()-1);
            if(num==0){//可以添加0,但不允许有前缀为0的
                break;
            }
        }
    }
}
目录
相关文章
|
2月前
|
存储 监控 算法
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
60 0
|
2月前
|
存储 负载均衡 算法
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
|
3月前
|
存储 算法 安全
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法(AES、DES、3DES)的实现原理及应用。对称加密使用相同密钥进行加解密,适合数据安全传输与存储。AES作为现代标准,支持128/192/256位密钥,安全性高;DES采用56位密钥,现已不够安全;3DES通过三重加密增强安全性,但性能较低。文章提供了各算法的具体Java代码示例,便于快速上手实现加密解密操作,帮助用户根据需求选择合适的加密方案保护数据安全。
336 58
|
4月前
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
182 0
|
4月前
|
存储 缓存 监控
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
102 3
|
6天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案
Java 数据库 Spring
41 0
|
18天前
|
算法 Java
Java多线程编程:实现线程间数据共享机制
以上就是Java中几种主要处理多线程序列化资源以及协调各自独立运行但需相互配合以完成任务threads 的技术手段与策略。正确应用上述技术将大大增强你程序稳定性与效率同时也降低bug出现率因此深刻理解每项技术背后理论至关重要.
49 16
|
27天前
|
缓存 并行计算 安全
关于Java多线程详解
本文深入讲解Java多线程编程,涵盖基础概念、线程创建与管理、同步机制、并发工具类、线程池、线程安全集合、实战案例及常见问题解决方案,助你掌握高性能并发编程技巧,应对多线程开发中的挑战。
|
1月前
|
数据采集 存储 前端开发
Java爬虫性能优化:多线程抓取JSP动态数据实践
Java爬虫性能优化:多线程抓取JSP动态数据实践

热门文章

最新文章