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
AI 代码解读

思路

  • 题目看上去像是二叉搜索树的题,实际上是动态规划。给到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];
    }
}
AI 代码解读

二、中序遍历

题目描述

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

   1
    \
     2
    /
   3
AI 代码解读

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);
        }
    }
}
AI 代码解读
//非递归
/**
 * 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;
    }
}
AI 代码解读

三、深搜

题目描述

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;
            }
        }
    }
}
AI 代码解读
目录
相关文章
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
61 3
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
72 3
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
140 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
11月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
112 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
231 2
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
135 3
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
198 1

热门文章

最新文章