LeetCode 热题 HOT 100 ------- 22. 括号生成(回溯,dfs)394. 字符串解码(回溯) 105. 从前序与中序遍历序列构造二叉树(递归)_slow is fast.的博客-程序员宅基地

技术标签: 算法  # LeetCode 热题 HOT 100  leetcode  数据结构  

dsaddsds在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

 /**
解题思路:递归,因为我们知道前序遍历的数组和中序遍历的数组
前序遍历:当前节点,左子树前序遍历,右子树前序遍历
中序遍历:左子树中序遍历,当前节点,右子树中序遍历
我们发现:前序遍历的第一个节点就是“根节点”,然后我们可以根据这个“根节点”的值去中序遍历的数组中找对应的“根节点”的下标,
这个操作我们可以通过hashmap查找,也就是将中序遍历的数组放入到hashmap中,key为“节点值”,value为中序遍历数组对应的下标

为什么要将中序遍历的数组放入到哈希表中呢?因为中序遍历是 左-->根-->右  我们可以通过根节点坐标求左子树的节点数和右子树
  */
class Solution {
    
    //定义一个哈希表
    Map<Integer,Integer> indexMap ;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        //首先求得当前树一共多少个节点,也就是前序遍历数组和中序遍历数组的个数一致
        int len = preorder.length;
        //将中序遍历得数组放入到hashmap中
        indexMap = new HashMap<Integer,Integer>();
        for(int i=0 ; i<len ;i++){
    
            indexMap.put(inorder[i],i);
        }
        //为了低耦合,我们用单独的方法去计算,返回的就是根节点
        return myBuildTree(preorder , inorder , 0, len-1 , 0 , len-1);
    }
    /**
        @ preorder 前序遍历的二叉树
        @ inorder  右序遍历的二叉树
        @ preorder_left  前序遍历的二叉树组的左边界
        @ preorder_right 前序遍历的二叉树组的右边界
        @ inorder_left  中序遍历的二叉树组的左边界
        @ inorder_right  中序遍历的二叉树组的右边界
     */
    public TreeNode myBuildTree(int[] preorder,int[] inorder,int preorder_left , int preorder_right , int inorder_left , int inorder_right){
    
        //递归边界条件
        if(preorder_left>preorder_right){
    
            return null;
        }
        //前序遍历中的左边界节点就是根节点
        int preorder_root = preorder_left; //根节点下标
        //找对应的中序遍历数组的根节点的下标
        int inorder_root = indexMap.get(preorder[preorder_root]);
        //建立根节点
        TreeNode root = new TreeNode(preorder[preorder_root]);
        //根节点的左子树的个数就是:  -------对应的就是前序遍历数组的左边界~根节点
        int size_left_subTree = inorder_root - inorder_left;
        //进行递归
        //先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder , inorder , preorder_root+1 , size_left_subTree+preorder_root , inorder_left , inorder_root-1);
        //先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder , inorder ,size_left_subTree+preorder_root+1 , preorder_right , inorder_root+1 ,inorder_right);
        //但是发现递归怎么结束呢????找边界条件 也就是左边界<右边界
        return root;
    }
}

dsadasd在这里插入图片描述

//解题思路:可以用辅助栈操作,或者递归
//栈操作:这个题很符合“先入后出”
//1、构建辅助栈,遍历字符串s中每个字符c
//当c为数字时,将字符转为数字multi,用于后面重复
//当c为字母时,在字母尾部添加c
//当c为‘[’时,将当前 multi 和 res 入栈,并分别置空置 0:
//当c为']'时,stack 出栈,拼接字符串 res = last_res + cur_multi * res,其中

class Solution {
    
    public String decodeString(String s) {
    
        //创建栈   
        Deque<Integer> stack_multi = new LinkedList<>();  //用于存放数字
        Deque<String> stack_str = new LinkedList<>();   //用于存放字符和数字
        //数字
        int multi = 0;
        //用于存放返回值
        StringBuilder str = new StringBuilder();

        for(char c : s.toCharArray()){
    
            if( c>='0' && c<='9'){
      //数字
                multi = multi * 10 + Integer.parseInt(c+"");    //数字,为了避免数字是两位以上
            }else if(c == '['){
    
                stack_multi.addLast(multi); //这里是为了得到重复值
                stack_str.addLast(str.toString());     //这里是为了拼接用的
                multi = 0;                  //使其初始化
                str = new StringBuilder();  //同样使其初始化
            }else if(c == ']'){
         //开始取值
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.removeLast(); //取']'对应的‘[’的前面的数
                for(int i=0 ; i<cur_multi ; i++){
    
                    tmp.append(str);
                }
                //进行拼接
                str = new StringBuilder(stack_str.removeLast() + tmp);
            }else{
      //字母
                str.append(c);
            }
        }
        return str.toString();
    }
}

/**
思路2:同样是递归,但是更简单  强烈推荐!!!!
 */
class Solution {
    
    //递归中需要用到下标,为了方便,定义一个成员变量
    private int index =0;
    public String decodeString(String s) {
    
        String str = recurve(s);
        return str;
    }
    private String recurve(String s){
    
        StringBuilder str = new StringBuilder();
        while(index < s.length()){
    
            char c = s.charAt(index++);
            if(c>='0' && c<='9'){
    
                int multi = c - '0';
                //当遇到数字时,可能有很多,因此需要循环遍历完
                while(s.charAt(index) >= '0' && s.charAt(index)<='9'){
    
                    multi = multi * 10 + s.charAt(index) - '0';
                    index++;
                }
                //然后去获得子串
                String tmp = recurve(s);
                for(int i=0 ; i<multi ; i++){
      //将子串重复相应的次数
                    str.append(tmp);
                }
            }else if(c == '['){
     //如果是[,不需要做什么
                
            }else if(c == ']'){
    //如果是],则子串已经建立完成,退出循环
                break;
            }else{
              //如果是普通字符,则拼接
                str.append(c);
            }
        }
        return str.toString();//返回子串
    }
}

dasdasdd在这里插入图片描述

//暴力搜索:先遍历出所有的括号的组合,然后判断该组合是否满足条件,满足就添加到数组 时间复杂度O(2^2n*n),空间复杂度O(n)
class Solution {
    
    public List<String> generateParenthesis(int n) {
    
        //返回值
        List<String> str_lst = new ArrayList<>();
        //每种情况
        generateAllStr(new char[2*n] , 0 , str_lst);
        return str_lst;
    }
    public void generateAllStr(char[] str_ary , int index , List<String> str_lst){
    
        if(index == str_ary.length){
    
            if(isVaild(str_ary)){
    
                str_lst.add(new String(str_ary));
            }
        }else{
    
            str_ary[index] = '(';
            generateAllStr(str_ary,index+1,str_lst);
            str_ary[index] = ')';
            generateAllStr(str_ary,index+1,str_lst);
        }
    }
    public boolean isVaild(char[] str_ary){
     //判断该组合是否有效
        int balance = 0;    //左括号+1,右括号-1,如果左括号小于右括号了也就是balance<0,则不能满足
        for(char c : str_ary){
    
            if(c == '('){
    
                balance++;
            }else{
    
                balance--;
            }
            if(balance < 0){
    
                return false;
            }
        }
        return balance == 0 ? true : false; 
    }
}


/*
    第二种方法:回溯,递归中我们每次当出现一个组合时才进行判断是否有效,
    但是我们可以让其在组合其中就判断是否有效,左括号有n,右括号有n
    用str代替string也行,因为每次添加string相当于创建了一个新对象,所以不需要删除
    而StringBuilder这种没有创建,所以每次加完,还要删一个,不过这样写感觉就像dfs了
    只不过是dfs的另一种表达
*/
class Solution {
    
    public List<String> generateParenthesis(int n) {
    
        List<String> str_list = new ArrayList<>();
        String str = "";
        recall(str_list , str , 0 , 0 , n);
        return str_list;
    }
    public void recall(List<String> str_list , String str , int left , int right , int n){
    
        if(str.length() == 2*n){
       //进行回溯时已经保证'('<=')'
            str_list.add(str);
            return;
        }
        if(left<n){
       //当左括号<n的时候,我们就放左括号,然后进一步回溯 , 这里不用删除,因为每次string+括号都是新对象
            recall(str_list , str +'(' , left+1 , right , n);
        }
        if(right<left){
      //当右括号<左括号的个数时,我们就放左括号,然后进一步回溯
            recall(str_list , str + ')' , left , right+1 , n);
        }
    }
}

/*
    dfs: 和第二种差不多
    有效的括号、n对,也就是说n个左括号,n个右括号,每次添加一个
    但是要注意:一定要保证右括号的个数一定要少于左括号的个数,如果多了就一定不有效
*/
class Solution {
    
    public List<String> generateParenthesis(int n) {
    
        List<String> str_lst = new ArrayList<>();
        String str = "";
        dfs(str_lst , str , 0 , 0 , n);
        return str_lst;
    }
    private void dfs(List<String> str_lst , String str , int left , int right , int n){
    
        if(left == n && right == n){
    
            str_lst.add(str);
        }
        // if(right > left){ 
        //     return;
        // }
        if(left < n){
    
            dfs(str_lst , str+'(' , left+1 , right , n);
        }
        if(right < left){
     
        // right<n , right<left 都可以 因为上面的if(right>left) return 保证了 left<right
        //所以取其1就行
            dfs(str_lst , str+')' , left , right+1 , n);
        }
    }
}

/*
    另一种方法的dfs,直接上代码吧
*/
class Solution {
    
    public List<String> generateParenthesis(int n) {
    
       List<String> res = new ArrayList<String>();
       String str = "";
       int left = n , right = n;
       dfs(str , n , n , res);
       return res;
    }
    private void dfs(String str , int l , int r , List<String> res){
    
       //递归头
        if(l == 0 && r == 0)
            res.add(str);
        if(l > r)
            return;
        if(l>0){
    
            dfs(str+"(" , l-1 , r , res);
        }
        if(r>0){
    
            dfs(str+")" , l , r-1 , res);
        }
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wwj17647590781/article/details/116086213

智能推荐

Redis的应用场景及安装启动[email protected]的博客-程序员宅基地

Redis的应用场景1.1 使用关系型数据做高速缓存实现功能: 1、高频次,热门访问的数据,降低数据的I/O; 2、分布式架构,实现Session共享Redis服务器的安装准备Redis环境# 下载Redis安装包wget https://download.redis.io/releases/redis-6.2.4.tar.gz# 安装C语言编译环境yum install gcc centos-release-scl scl-utils-build devtoolset-8-tool

muduo网络库学习笔记(四) 通过eventfd实现的事件通知机制_青丶空゛的博客-程序员宅基地

muduo网络库学习笔记(四) 通过eventfd实现的事件通知机制文章目录muduo网络库学习笔记(四) 通过eventfd实现的事件通知机制eventfd的使用eventfd系统函数使用示例EventLoop对eventfd的封装工作时序`runInLoop()``queueInLoop()``wakeup()``handleRead()``doPendingFunctors()`总结上...

java 拆分xml,Java:使用SAXParser拆分大型XML文件_TF Lau的博客-程序员宅基地

I am trying to split a large XML file into smaller files using java's SAXParser (specifically the wikipedia dump which is about 28GB uncompressed).I have a Pagehandler class which extends DefaultHandl...

MySQL常用日期时间函数_bo o ya ka的博客-程序员宅基地

日期和时间函数可能的需求:  当前时间是多少、下个月的今天是星期几、统计截止到当前日期前 3 天的收入总和……上述需求就需要使用日期和时间函数来实现:MySQL服务器中的三种时区设置:  ①系统时区---保存在系统变量system_time_zone  ②服务器时区---保存在全局系统变量global.time_zone  ③每个客户端连接的时区---保存在会话变量...

java 调用postgresql 函数_实现PostgreSQL函数自定义例外处理_leeloo deng的博客-程序员宅基地

代码搬运也需要发挥想象力,让不可能变为可能,这里讲一个例子。1、 有人问PostgreSQL有没有自定义例外,Oracle是有的:--定义myex Exception;--抛出RAISE myex;--捕获WHEN myex THEN简单易用2、再来看PostgreSQL的PL/pgSQLRAISE [ level ] condition_name [ USING option = express...

sdut oj 实验9- 字符串的应用_snowman22的博客-程序员宅基地

A - C语言实验——字符编码Description请将一串长度为5的纯字母文本译成一个密码,密码规律如下:用原来的字母后面的第4个字母代替原来的字母。如C用G代替(文本中不存在W/w、X/x、Y/y、Z/z等字母),最后得到的文本即为密码。Input输入一串文本,长度固定为5。Output输出对应的密码。格式为:password is 密码SampleInputChinaOutputpassword is Glmre#include&lt;std..

随便推点

datawhale-transformers教程答疑手册_神洛华的博客-程序员宅基地

transformers29期问题点1. BERT的三个Embedding直接相加会对语义有影响吗?原帖子在这这是一个非常有意思的问题,苏剑林老师也给出了回答,真的很妙啊:Embedding的数学本质,就是以one hot为输入的单层全连接,也就是说,世界上本没什么Embedding,有的只是one hot。我们将token,position,segment三者都用one hot表示,然后concat起来,然后才去过一个单层全连接,等价的效果就是三个Embedding相加。原文链接:词向量与Emb

MySQL常用日期时间函数_bo o ya ka的博客-程序员宅基地

日期和时间函数可能的需求:  当前时间是多少、下个月的今天是星期几、统计截止到当前日期前 3 天的收入总和……上述需求就需要使用日期和时间函数来实现:MySQL服务器中的三种时区设置:  ①系统时区---保存在系统变量system_time_zone  ②服务器时区---保存在全局系统变量global.time_zone  ③每个客户端连接的时区---保存在会话变量...

树莓派教程 - 1.2 树莓派GPIO库wiringPi 软件PWM_Mark_md的博客-程序员宅基地

使用到的硬件:led,200Ω左右的电阻、杜邦线。上一节使用硬件PWM来控制led亮度,可树莓派的硬件PWM引脚只有1路,在实际应用中,1路PWM几乎干不了什么。庆幸的是wiringPi库提供了一个软PWM功能。可以将任意GPIO都复用为PWM,但缺点是会增加CPU负担。树莓派的软件PWM软件PWM默认频率是100Hz,一般的pwm范围设置为100,太大会增加CPU开销。int softPwmCreate (int pin, int initialValue, int pwmR.

使用Python获取Linux系统的各种信息_moonhillcity的博客-程序员宅基地

转自:http://www.jb51.net/article/52058.htm在本文中,我们将会探索使用Python编程语言工具来检索Linux系统各种信息。走你。哪个Python版本?当我提及Python,所指的就是CPython 2(准确的是2.7).我会显式提醒那些相同的代码在CPython 3 (3.3)上是不工作的,以及提供一份解释不同之处的备选代码。请确保你已

判断ViewPager2的页(自定义View或fragment)被预加载或被回收_JayWang1024的博客-程序员宅基地

1.如果使用自定义view作为页,onDetachedFromWindow和onAttachedToWindow分别表示被回收和被重新利用,前者是回收资源的时机,后者是重新初始化的时机2.如果使用Fragment作为页,回收资源和重新初始化时机都应该在onRsume方法(如何保证visible-可见时会回调onRsume详见链接),onDestroyView方法也应该做回收资源工作3.Vi...

微信小程序wx:if的配合block的使用,点击箭头有折叠效果---三元表达式_Specialize in Linxu的博客-程序员宅基地_block wx:if

我们可以先看一下效果图点击箭头会出现隐藏的内容再次点击我们将其收起来,我的想法是通过wx:if写两个block,然后通过wx:if的布尔值来实现这样的功能下面我们首先写两个块级元素&lt;block wx:if='{{collapse==true?flase:true}}'&gt; &lt;view class="introduce"&gt;简介:十六路咖啡公司总部位于厦门市,截至2019年底,直营门店数达到4507家。十六路咖啡以“从咖啡开始,让十六路成为人们日常生活的一部分”为愿景,

推荐文章

热门文章

相关标签