练手小题（哈希表搜索树）

喜欢ヅ旅行 2024-04-01 09:22 17阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：渴望力量的土狗
> 
> 博客主页：[渴望力量的土狗的博客主页][Link 1]
> 
> 专栏：[手把手带你刷牛客][Link 2]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 3]

![4b7bc61419b84632b80e477cd2cd590e.png][]

**目录**

1、旧键盘

2、二叉搜索树与双向链表

描述

输入描述：

返回值描述：

--------------------

## 1、旧键盘 ##

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出  
肯定坏掉的那些键。

**输入描述:**

输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、
    以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。

**输出描述:**

按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。

示例1

输入
    7_This_is_a_test<br/>_hs_s_a_es
    输出
    7TI

首先我们分析一下思路哈：简单理解一下题目：就是说要让我们输出字符串1没有在字符串2中的部分（也就是字符串1中多出来的那部分，同时每个字符(大写）按照字符串中出现的顺序只可以输出1次即可），所以我们可以写一个方法来实现这个功能：首先我们要把两个字符串都改为大写的字符数组，之后用一个HashSet把s2出现的字符存放起来，然后遍历s1所在的字符数组ch1，如果HashSet中不包含ch1中的元素就把它存放到一个List当中，最后打印List中的内容即可。

AC代码：

import java.util.*;
    public class Main{
        
        public static void main(String[]args){
            Scanner scan=new Scanner(System.in);
            while(scan.hasNextLine()){
                String s1=scan.nextLine();
                String s2=scan.nextLine();
                fun(s1,s2);
            }
        }
        public static void fun(String s1,String s2){
            char[]ch1=s1.toUpperCase().toCharArray();
            char[]ch2=s2.toUpperCase().toCharArray();
            HashSet<Character>set1=new HashSet<>();
            for(char x:ch2){
                set1.add(x);
            }
            List<Character> list=new ArrayList<>();
            
            for(char x:ch1){
                if(!set1.contains(x)){
                   if(!list.contains(x)){
                       list.add(x);
                   }
                }
            } 
            for(char x:list){
                System.out.print(x);
            }
        }
    }

![441869bb5757426888e507761dc3b242.png][]

## 2、二叉搜索树与双向链表 ##

### 描述 ###

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

![f862822849c24ac6aa1968376544c920.png][]

数据范围：输入二叉树的节点数 0≤n≤1000，二叉树中每个节点的值0≤val≤1000  
要求：空间复杂度O(1)O(1)（即在原树上操作），时间复杂度 O(n)O(n)

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继  
2.返回链表中的第一个节点的指针  
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出双向链表，程序会根据你的返回值自动打印输出

#### 输入描述： ####

二叉树的根节点

#### 返回值描述： ####

双向链表的其中一个头节点。

示例1

输入：
    {10,6,14,4,8,12,16}
    返回值：
    From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
    说明：
    输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。

示例2

输入：
    {5,4,#,3,#,2,#,1}
    返回值：
    From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
    
    说明：
                        5
                      /
                    4
                  /
                3
              /
            2
          /
        1
    树的形状如上图

AC代码：

/**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        //返回的第一个指针，即为最小值，先定为null
        public TreeNode head = null;  
        //中序遍历当前值的上一位，初值为最小值，先定为null
        public TreeNode pre = null;   
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null)
                //中序递归，叶子为空则返回
                return null;     
            //首先递归到最左最小值  
            Convert(pRootOfTree.left); 
            //找到最小值，初始化head与pre
            if(pre == null){       
                head = pRootOfTree;
                pre = pRootOfTree;
            }
            //当前节点与上一节点建立连接，将pre设置为当前值
            else{       
                pre.right = pRootOfTree;
                pRootOfTree.left = pre;
                pre = pRootOfTree;
            }
            Convert(pRootOfTree.right);
            return head;
        }
    }

![7cca78f09d104ddfbbb0cc581cc7d516.png][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/95dab87c12164c2ebbe6acdd1675b6ac.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[Link 2]: https://blog.csdn.net/m0_67995737/category_11980422.html
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[4b7bc61419b84632b80e477cd2cd590e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/10a6a00860504a0a9beeb65982379773.png
[441869bb5757426888e507761dc3b242.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/03d56d2484dd4a96b5c2c3f82786693d.png
[f862822849c24ac6aa1968376544c920.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3ae24780474e41038a45c33015f244da.png
[7cca78f09d104ddfbbb0cc581cc7d516.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e7326a39a4cd45ff8730bb4d030bbb8a.png