首页 > 其他分享 >二叉搜索树，Map，Set，LeetCode刷题

二叉搜索树，Map，Set，LeetCode刷题

时间：2024-08-01 15:56:55浏览次数：16  
标签：Map Set cur map public add set key LeetCode

二叉搜索树，Map，Set

1. 二叉搜索树

二叉搜索树是一棵特殊的树，它是“有序的”，因此又被叫做二叉排序树，它具有以下的性质：

  • 根节点左子树的任意元素都小于根节点的元素
  • 根节点右子树的任意元素都大于根节点的元素
  • 上述两条性质对于该树的任意子树都成立

2. 二叉搜索树的模拟实现

待实现代码：

public class BinarySearchTree {

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;

    /**
     * 插入一个元素
     * @param key
     */
    public boolean insert(int key) {
        
        return true;
    }
    //查找key是否存在
    public TreeNode search(int key) {
      
        return null;
    }
    //删除key的值
    public boolean remove(int key) {
       
        return false;
    }
}

1.1 插入操作

插入一个新节点，首先要遍历原树，找到一个合适的位置去插入，而插入的节点会成为新树的叶子节点

具体实现如下：

    public boolean insert(int key) {
        if(root == null) {
            root = new TreeNode(key);
            return true;
        }
        TreeNode node = new TreeNode(key);
        TreeNode cur = root;
        TreeNode curParent = null;
        //找插入新节点的合适位置
        while(cur != null) {
            curParent = cur;
            if(cur.key < key) {
                cur = cur.right;
            }else if(cur.key > key) {
                cur = cur.left;
            }else {
                return false;
            }
        }
        //进行插入新节点操作
        if(curParent.key < key) {
            curParent.right = node;
        }else {
            curParent.left = node;
        }
        return true;
    }

1.2 查找操作

    public TreeNode search(int key) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.key < key) {
                cur = cur.right;
            }else if(cur.key > key) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }

1.3 删除操作

二叉搜索树的删除操作是三个操作里最难的，难在需要考虑的情况较多，需要不断用测试用例去调试代码，可以用下面这个链接去验证代码是否还有遗漏的情况

题目链接：NC297 删除一个二叉搜索树中的节点

实现代码：

    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode curParent = root;
        //找到删除节点位置
        while(cur != null) {
            if(cur.key < key) {
                curParent = cur;
                cur = cur.right;
            }else if(cur.key > key) {
                curParent = cur;
                cur = cur.left;
            }else {
                break;
            }
        }
        if(cur == null) {
            return true;//节点不存在
        }
        TreeNode del = cur;//待删除节点
        TreeNode delParent = curParent;//待删除节点的父亲节点
        //找到待删除节点左子树的最大值（即左子树最右边的元素），用来替换法1待删除节点值
        if(del.left == null) {//待删除节点无左子树
            if(del.key > delParent.key) {
                delParent.right = del.right;
            }else if(del.key < delParent.key){
                delParent.left = del.right;
            }else {
                //此时，待删除节点为根节点
                root = root.right;
            }
        }else {
            //找到待删除节点左子树的最大值（即左子树最右边的元素），用来替换待删除节点值
            curParent = cur;
            cur = cur.left;
            while(cur.right != null) {
                curParent = cur;
                cur = cur.right;
            }
            del.key = cur.key;
            if(curParent == del) {
                //此时，待删除节点的左子树根节点无右子树
                curParent.left = cur.left;
            }else {
                curParent.right = cur.left;
            }
        }
        return true;
    }

3. 二叉搜索树时间复杂度分析

  • 在最优情况下，即二叉搜索树是一棵完全二叉树，时间复杂度是O（log2N）
  • 在最坏情况下，即二叉搜索树是一棵单支二叉树，时间复杂度是O（N）

最优情况：
在这里插入图片描述
最坏情况：
在这里插入图片描述

4. TreeMap和TreeSet

TreeMap和TreeSet底层都是一棵红黑树，而红黑树是一棵近似平衡的二叉搜索树。TreeMap是Map接口的一个实现类，TreeSet是Set接口的一个实现类

5. Map

Map是一个接口，其实现需要依靠TreeMap类或者HashMap类。Map里存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。这就类比于一个集合，这个集合里放的都是具有两个元素的集合，例如：{{“abc”, 2}, {“cde”, 3}}

5.1 Map的常用方法

  1. V put (K key, V value)
    用于往map中存放键值对

演示1：

public class Test {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("fbc",2);
        map.put("cde",3);
        map.put("abc",5);
        map.put("grh",8);
        System.out.println(map);//Map类可以直接输出
    }
}

输出结果：
在这里插入图片描述
演示2：
在这里插入图片描述
map类存储的key是不能重复的，但往map里put同一个key，是可以的，只是在key里依然只会保存一个key，只是key对应的value会发生更新

  • 如果key不存在，会将key-value的键值对插入到map中,返回null
  • 如果key存在，会使用value替换原来key所对应的value，返回旧value
  • put(key,value): 注意key不能为空，但是value可以为空。 key如果为空，会抛出空指针异常
  1. V get(Object key)
    用于得到key对应的value

演示：

public class Test {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("fbc",2);
        map.put("cde",3);
        map.put("abc",5);
        map.put("grh",8);
        Integer val = map.get("cde");
        System.out.println(val);
    }
}

输出结果为：3

注意： 该方法接收返回值时，建议使用包装类而不是基本数据类型，因为使用基本数据类型会发生自动拆箱，会调用intValue方法，假如该key不存在，就会返回null，这时如果进行拆箱的话，就会出现空指针异常
在这里插入图片描述
在这里插入图片描述
3. V getOrDefault(Object key, V defaltValue)
该方法与get方法的不同之处在于有一个默认值，如果key存在，则返回key对应的value值；如果key不存在，就会返回这个默认值

演示：

public class Test {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("fbc",2);
        map.put("cde",3);
        map.put("abc",5);
        map.put("grh",8);
        Integer val = map.getOrDefault("cde2",-1);
        System.out.println(val);
    }
}

输出结果为：-1

  1. V remove(Object key)
    删除key对应的映射关系

演示：

public class Test {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("fbc",2);
        map.put("cde",3);
        map.put("abc",5);
        map.put("grh",8);
        System.out.println("删除前：" + map);
        map.remove("abc");
        System.out.println("删除后：" +map);
    }
}

输出结果：
在这里插入图片描述

  1. Set<K> keySet()
    返回所有的key的不重复集合，keySet()是将map中的key放在set中返回的

演示：

public class Test {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("fbc",2);
        map.put("cde",3);
        map.put("abc",5);
        map.put("grh",8);
        // 打印所有的key
        Set<String> set = map.keySet();
        System.out.println(set);
        for(String s : set) {
            System.out.print(s + " ");
        }
    }
}

输出结果：
在这里插入图片描述

  1. Collection<V> values()
    返回所有value的可重复集合，values()是将map中的value放在collect的一个集合中返回的

演示：

public class Test {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("fbc",2);
        map.put("cde",3);
        map.put("abc",5);
        map.put("grh",8);
        // 打印所有的value
        Collection<Integer> collection = map.values();
        System.out.println(collection);
        for(Integer x: collection) {
            System.out.print(x + " ");
        }
    }
}

输出结果：
在这里插入图片描述

  1. boolean containsKey(Object key)
    判断是否包含key

演示：

public class Test {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("fbc",2);
        map.put("cde",3);
        map.put("abc",5);
        map.put("grh",8);
        boolean flg1 = map.containsKey("abc");
        boolean flg2 = map.containsKey("cba");
        System.out.println(flg1);
        System.out.println(flg2);
    }
}

输出结果：
在这里插入图片描述

  1. boolean containsValue(Object value)
    判断是否包含value

演示：

public class Test {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("fbc",2);
        map.put("cde",3);
        map.put("abc",5);
        map.put("grh",8);
        boolean flg1 = map.containsValue(1);
        boolean flg2 = map.containsValue(3);
        System.out.println(flg1);
        System.out.println(flg2);
    }
}

输出结果：
在这里插入图片描述

  1. Set<Map.Entry<K, V>> entrySet()
    返回所有的 key-value 映射关系，entrySet()将Map中的键值对放在Set中返回了

注意：

  • Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入
  • 在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，因为插入键值对时，会在二叉搜索树里进行比较（因此插入的key元素类型要可比，或者在key类中实现了比较方式），将新节点插入到合适位置，而value可以为空。但是HashMap的key和value都可以为空，因为插入时不涉及比较。因此，输出时，如果是TreeMap实现的，则是有序的；若是HashMap实现的，则是无序的

5.2 Map.Entry<K,V>

Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式

  1. K getKey()
    返回entry中的key

  2. V getValue()
    返回entry中的value

  3. V setValue(V value)
    将键值对中的value值替换成指定value

通过该方法转化，既可以获取key，也可以获取value；而Map中的get方法只能获取key所对应的value值

public class Test {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("fbc",2);
        map.put("cde",3);
        map.put("abc",5);
        map.put("grh",8);
         打印所有的键值对
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        System.out.println(entrySet);
        System.out.println("========");
        for (Map.Entry<String,Integer> entry:entrySet) {
            System.out.println("key:" + entry.getKey()+" val:" + entry.getValue());
        }
    }
}

输出结果：
在这里插入图片描述

6. Set

Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key，且Key唯一。Set类似于一个集合，具有互异性，最大的作用就是去重。Set的实现依靠TreeSet、HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。

6.1 Set的常用方法

  1. boolean add(E e)
    用来给集合添加元素，但不会添加重复元素

演示1：

    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(4);
        set.add(7);
        set.add(1);
        set.add(3);
        System.out.println(set);
    }

输出结果：
在这里插入图片描述

演示2：

    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(1);
        set.add(7);
        set.add(1);
        set.add(3);
        System.out.println(set);
    }

输出结果

在这里插入图片描述
和Map类似，Set也可以add集合中已有的元素，但不会将其加入集合中，从而达到去重的效果

  1. void clear()
    清空集合中的元素
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(4);
        set.add(7);
        set.add(1);
        set.add(3);
        System.out.println(set);
        set.clear();
        System.out.println(set);
    }

输出结果：
在这里插入图片描述

  1. boolean contains(Object o)
    判断o是否在集合中
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(4);
        set.add(7);
        set.add(1);
        set.add(3);
        System.out.println(set);
        System.out.println(set.contains(4));
        System.out.println(set.contains(5));
    }

输出结果：
在这里插入图片描述

  1. Iterator iterator()
    返回迭代器
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(4);
        set.add(7);
        set.add(1);
        set.add(3);
        Iterator<Integer> it = set.iterator();
        while(it.hasNext()) {
            System.out.print(it.next()+" ");
        }
    }

输出结果：
在这里插入图片描述

  1. boolean remove(Object o)
    删除集合中的o
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(4);
        set.add(7);
        set.add(1);
        set.add(3);
        System.out.println(set);
        set.remove(4);
        System.out.println(set);
    }

输出结果：
在这里插入图片描述

  1. int size()
    返回set中的元素个数
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(4);
        set.add(7);
        set.add(1);
        set.add(3);
        System.out.println(set.size());
    }

在这里插入图片描述

  1. boolean isEmpty()
    判断集合set是否为空，为空则返回true，反之返回false
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        System.out.println(set.isEmpty());
        set.add(4);
        set.add(7);
        set.add(1);
        set.add(3);
        System.out.println(set.isEmpty());
    }

输出结果：
在这里插入图片描述

  1. Object[] toArray()
    将set中的元素转换为数组返回
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(4);
        set.add(7);
        set.add(1);
        set.add(3);
        System.out.println(Arrays.toString(set.toArray()));
        System.out.println("========");
        Object[] arr = set.toArray();
        for (Object o : arr) {
            System.out.print(o + " ");
        }
    }

输出结果：
在这里插入图片描述

  1. boolean containsAll(Collection<?> c)
    检查集合c中的元素是否在set中全部存在，是则返回true，否则返回false
    public static void main(String[] args) {
        Collection<Integer> c = new ArrayList<>();
        c.add(1);
        c.add(2);
        c.add(3);
        Set<Integer> set = new TreeSet<>();
        set.add(1);
        set.add(2);
        System.out.println(set.containsAll(c));
        set.add(3);
        System.out.println(set.containsAll(c));
    }

输出结果：
在这里插入图片描述

  1. boolean addAll(Collection<?extends E> c)
    将集合c中的元素添加到set中，可以达到去重的效果
    public static void main(String[] args) {
        Collection<Integer> c = new ArrayList<>();
        c.add(1);
        c.add(2);
        c.add(1);
        c.add(3);
        c.add(2);
        c.add(4);
        System.out.println(c);
        Set<Integer> set = new TreeSet<>();
        set.addAll(c);
        System.out.println(set);
    }

输出结果：
在这里插入图片描述

注意：

  • Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
  • TreeSet中不能插入null的key，若插入null，则会抛出空指针异常；而HashSet可以

LeetCode刷题

1. 二叉搜索树与双向链表

题目链接：将二叉搜索树转化为排序的双向链表

解题思路：

  1. 对该二叉搜索树采取中序遍历，先找到二叉搜索树最左边的节点
  2. 定义两个引用prev和head，prev用来引用当前pRootOfTree的前一个节点，head始终引用原二叉搜索树最左边的节点，用于返回转化成的双向链表

代码如下：

public class Solution {
    public TreeNode prev;
    public TreeNode head;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        Convert(pRootOfTree.left);
        if (prev == null) {
            prev = pRootOfTree;
            head = pRootOfTree;
        } else{
            prev.right = pRootOfTree;
            pRootOfTree.left = prev;
            prev = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}

标签：Map,Set,cur,map,public,add,set,key,LeetCode
From： https://blog.csdn.net/ijj_zZ/article/details/140752563

相关文章

  • New-SmbMapping命令在PowerShell中用于创建新的SMB映射，其主要参数如下：
    New-SmbMapping命令在PowerShell中用于创建新的SMB映射，其主要参数如下：RemotePath：指定远程共享的路径。可以是网络共享的UNC路径，如\\server\share。LocalPath：指定本地计算机上的映射路径，通常是一个驱动器号或者文件夹路径。例如，Z:或C:\Share。Credential：用于连接远程共......
  • LeetCode | 209 MinimumSizeSubarraySum
    分析本题中是找与target相符的最小连续的子数组和，找一个能够容纳target这么大的最小子区间。虽然本节引入了滑动窗口的概念，可我更偏好于，这是一只毛毛虫在数组上的移动，找到最小的容纳自己位置的地方target可看作毛虫本身的重量，数组中的每个元素值表示可承受的重量，right右指针看......
  • LeetCode 322 零钱兑换
    题目描述给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。你可以认为每种硬币的数量是无限的。思路这是一个完全背包问题，背包问题当满足：物品不......
  • 每日一题：Leetcode-48 旋转图像
    力扣题目解题思路java代码力扣题目：给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转90度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。示例1：输入：matrix=[[1,2,3],[4,5,6]......
  • Getter访问器和Setter修改器
    Getter访问器与Setter修改器Getter访问器和Setter修改器是为private修饰的类成员变量提供安全访问的一种方式publicclassMan{privateintage;privateStringname;publicintgetAge(){//Getter访问器returnage;......
  • mapbox 结合deckgl添加3DTiles等操作
    1.初始化import{MapboxOverlay}from"@deck.gl/mapbox";import{LineLayer,GeoJsonLayer}from"@deck.gl/layers"; import{TripsLayer,Tile3DLayer}from"@deck.gl/geo-layers"; import{Tiles3DLoader}from"@loade......
  • Getter访问器和Setter访问器
    Getter访问器和Setter访问器Getter访问器和Setter访问器是面向对象编程（OOP）中常见的概念，特别是在使用如Java、C#、Python（通过@property装饰器）等语言时。它们用于封装对象的属性，提供对对象内部状态的访问和修改，同时可以控制这些访问的权限和方式。Getter访问器Getter访问器（也称为......
  • LeetCode 2024/8 每日一题合集
    2024-7-1LCP40.心算挑战代码实现classSolution{public:intmaxmiumScore(vector<int>&cards,intcnt){intn=size(cards);std::sort(cards.rbegin(),cards.rend());intsum=std::accumulate(cards.begin(),cards.begin()......
  • 使用Python时如何避免`setattr`（和`getattr`）？以及是否有必要避免
    如果我想向协议缓冲区中的字段添加一个在编译时未知的值，我目前正在做setattr我通常不喜欢使用setattr，因为它看起来不太安全。但是当我知道该对象是protobuf时，我认为这很好，因为我设置它的值必须是protobuf允许的类型。所以也许它并不是真的不安全？让我举......
  • pydantic_settings 没有正确调用“之前”验证器
    我正在编写一个pydantic_settings类来从.env文件/环境变量中读取数据。相关部分如下所示：frompydantic_settingsimportBaseSettingsfrompydanticimportField,field_validatorfromtypingimportTupleclassJobSettings(BaseSettings):wp_generate_funnel_b......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99