一.引言

我们本篇文章主要讲解
1.掌握Map/Set及实际实现类HashMap/TreeMap/HashSet/TreeSet的使用
⒉.掌握HashMap 和HashSet 背后的数据结构哈希表的原理和简单实现.

二.搜索树

在介绍Map和Set之前,我们要介绍一个新的知识就是二叉搜索树.话不多说,我们直接看下面的概念.

2.1 概念

什么是二叉搜索树.
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:·

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值·
3. 它的左右子树也分别为二叉搜索树

大家看了上面的文字,如果还没理解的话,大家可以看一下下面的图片

2.2二叉搜索树基本操作

public class BinarySearchTree {static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public TreeNode root = null;/*** 查找二叉搜索树中指定的val值* @param val* @return*/public TreeNode find(int val) {}/*** 插入一个数据* @param val*/public void insert(int val) {}/*** 删除值为val的节点* @param val*/public void remove(int val) {}}

2.3 操作-查找

我们先来看二叉搜索树的第一个操作,就是查找操作,我画一个图,大家看一下其中的规则,是怎么样的.

根据上述的图示,我提供一下写代码的思路.

1. 从根节点开始查找。
2. 如果要查找的数值等于根节点的值,则查找成功。
3. 如果要查找的数值小于根节点的值,则在左子树中继续查找。
4. 如果要查找的数值大于根节点的值,则在右子树中继续查找。
5. 重复步骤3和4,直到找到要查找的数值,或者查找到叶子节点仍未找到,此时查找失败。
6. 如果查找失败,则树中不存在要查找的数值。

代码如下:

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

2.4 操作-插入

搜素二叉树的插入操作,我们还是来看看,他究竟具体是怎么做的.

代码思路如下:

1. 如果树为空,则直接插入一个根节点。
2. 如果树不为空,则从根节点开始往下查找,和插入值进行比较。
3. 如果插入值等于当前节点的值,则插入失败,树中不插入新节点。
4. 如果插入值小于当前节点的值,则判断当前节点的左子节点是否为空。

• 如果为空,则在当前节点的左子节点插入新节点。
• 如果不为空,则在左子树中继续查找,重复步骤3和4。

5. 如果插入值大于当前节点的值,则判断当前节点的右子节点是否为空。

• 如果为空,则在当前节点的右子节点插入新节点。
• 如果不为空,则在右子树中继续查找,重复步骤3和4。

6. 重复步骤3、4和5,直到找到一个空的叶子节点,将新节点插入该位置。

 public void insert(int val) {if(root == null) {root = new TreeNode(val);return;}//这里的parent是记录上一个节点的位置,如果节点为空,我们就知道上一个节点的位置.TreeNode cur = root;TreeNode parent = null;while (cur != null) {if(cur.val < val) {parent = cur;cur = cur.right;}else if(cur.val == val){return;}else {parent = cur;cur = cur.left;}}TreeNode node = new TreeNode(val);if(parent.val < val) {parent.right = node;}else {parent.left = node;}}

2.5 操作-删除

二叉搜索树的删除是里面最复杂的,为什么这么说呢?大家且看我分析一波.
实际上大方向分为三种情况
第一种

第二种

第三种

具体的代码思路;

1. 从根节点开始查找要删除的节点cur。如果cur的值小于当前节点,则在左子树中查找;如果cur的值大于当前节点,则在右子树中查找。
2. 找到要删除的节点cur后,开始执行删除操作。
3. 如果cur没有左子节点,则将其父节点指向其右子节点。如果cur是根节点,则将根节点指向其右子节点。
4. 如果cur没有右子节点,则将其父节点指向其左子节点。如果cur是根节点,则将根节点指向其左子节点。
5. 如果cur有左右子节点,则使用替换法进行删除:

• 在cur的右子树中查找后继节点,也就是右子树中值最小的节点。
• 将后继节点的值赋给cur,这样就相当于删除了后继节点。
• 现在要删除的节点变为后继节点,后继节点一定没有左子节点,只需要考虑它是否有右子节点:
• 如果没有,则将其父节点指向null。
• 如果有,则将其父节点指向其右子节点。

6. 这样就完成了删除操作,删除了cur节点,同时最大限度地保留了树的结构。
   具体的代码:

  public void remove(int val) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if(cur.val == val) {removeNode(parent,cur);return;}else if(cur.val < val) {parent = cur;cur = cur.right;}else {parent = cur;cur = cur.left;}}}private void removeNode(TreeNode parent, TreeNode cur) {if(cur.left == null) {if(cur == root) {root = cur.right;}else if(parent.left == cur) {parent.left = cur.right;}else {parent.right = cur.right;}}else if(cur.right == null) {if(cur == root) {root = cur.left;}else if(parent.left == cur) {parent.left = cur.left;}else {parent.right = cur.left;}}else {//使用俩个标记来记录父节点和它的的子节点.TreeNode target = cur.right;TreeNode targetParent = cur;while (target.left != null) {targetParent = target;target = target.left;}cur.val = target.val;if(target == targetParent.left) {targetParent.left = target.right;}else {targetParent.right = target.right;}}}}

2.6 性能分析

时间复杂度:

• 查找:O(n)。最坏情况下需要遍历树的所有节点。在平衡二叉搜索树中为O(logn)。
• 插入:O(n)。需要遍历树找到正确的插入位置。在平衡二叉搜索树中为O(logn)。
• 删除:O(n)。需要找到要删除的节点以及其后继节点。在平衡二叉搜索树中为O(logn)。

空间复杂度:O(n),因为二叉搜索树需要存储n个节点。
二叉搜索树的性能比较依赖于树的平衡性。如果树失去平衡,其性能会急剧下降到O(n)。所以我们通常使用平衡二叉搜索树,比如AVL树和红黑树,来保证树的平衡,从而获得较好的时间复杂度O(logn)。

二叉搜索树的优点:

• 查找、插入和删除的算法简单明了。
• 可以快速查找到最小值和最大值。
• 单调性:中序遍历得到的节点值呈单调递增(或递减)。

二叉搜索树的缺点:

• 树的性能依赖于平衡性,如果失去平衡会变慢。
• 平衡二叉搜索树的实现较复杂。
• 空间消耗略高,需要存储左右子节点的指针。

三. Map和set简介

Map和Set是Java集合框架中的两个非常重要的接口。

Map:

• Map是一组键值对的集合,其中键唯一,值可以重复。
• Map中的键值对通常用来建立映射关系,如用户名到用户对象的映射等。
• Map最常用的实现类是HashMap、TreeMap和HashTable。

Set:

• Set是一组无序不可重复元素的集合。
• Set中的元素只有键,没有值。
• Set最常用的实现类是HashSet和TreeSet。

Map和Set的区别:

• Map有键和值,Set只有键,没有值。
• Map中的键唯一,值可以重复,Set中的元素唯一。
• Map是双列集合,Set是单列集合。

Map和Set的共性:

• 都不允许重复元素。Map的键不可重复,Set的所有元素不可重复。
• 都使用equals()方法来判断两个元素是否相等。
• 都使用hashCode()方法来判断元素的索引位置。

四.Map接口和实现类

• HashMap:基于哈希表的Map实现类,支持null键和值
• TreeMap:基于红黑树的Map实现类,键有序
  接下来我们来介绍一下

4.1 HashMap的api

接下来我们来看看HashMap具体的api有哪些.

• HashMap():构造一个默认的HashMap。
• HashMap(int capacity):构造一个指定容量的HashMap。
• put(K key, V value):向HashMap中添加键值对。
• get(K key):根据键获取值。
• remove(K key):根据键删除键值对。
• containsKey(K key):判断HashMap中是否包含指定键。
• containsValue(V value):判断HashMap中是否包含指定值。
• size():获取HashMap中的键值对个数。
• isEmpty():判断HashMap是否为空。
• clear():清空HashMap。

具体的代码练习:

 public static void main(String[] args) {// 构造一个HashMapHashMap<String, Integer> map = new HashMap<>();// 向HashMap中添加键值对map.put("Apple", 10);map.put("Banana", 20);// 根据键获取值int appleCount = map.get("Apple"); // 10// 根据键删除键值对map.remove("Apple");// 判断HashMap中是否包含键boolean containsKey = map.containsKey("Apple"); // false// 判断HashMap中是否包含值boolean containsValue = map.containsValue(10); // true// 获取HashMap的大小int size = map.size(); // 1// 清空HashMapmap.clear();}

4.2 TreeMap的api

接下来我们来看看TreeMap的api有哪些

• TreeMap():构造一个默认的TreeMap。
• put(K key, V value):向TreeMap中添加键值对。
• get(K key):根据键获取值。
• getOrDefault(K key, V defaultValue):根据键获取值,如果键不存在则返回默认值。
• keySet():获取TreeMap中的所有键。
• entrySet():获取TreeMap中的所有键值对。
• firstKey():获取第一个键。
• lastKey():获取最后一个键。
• floorKey(K key):获取小于等于给定键的最大键。
• ceilingKey(K key):获取大于等于给定键的最小键。
• subMap(K fromKey, K toKey):获取fromKey到toKey之间的子Map。

具体的代码如下:

public static void main(String[] args) {  // 构造一个TreeMapMap<String,Integer> treeMap = new TreeMap<>();  // 向TreeMap中添加键值对treeMap.put("hello",3);treeMap.put("abc",4);treeMap.put("the",8);// TreeMap不支持null键,所以这行代码会抛出NullPointerExceptiontreeMap.put(null,18);  // 打印TreeMapSystem.out.println(treeMap);  // 根据键获取值,如果键不存在则返回默认值Integer val = treeMap.getOrDefault("hello2",100);  System.out.println(val);  // 获取TreeMap中的所有键Set<String> keySet = treeMap.keySet();System.out.println(keySet);  // 获取TreeMap中的所有键值对System.out.println("===========");Set<Map.Entry<String,Integer>> set = treeMap.entrySet();for (Map.Entry<String,Integer> entry :set) {System.out.println("key:"+entry.getKey()+" value: "+entry.getValue());} 
}

五.Set接口和实现类

• HashSet:基于哈希表的Set实现类,支持null值
• TreeSet:基于红黑树的Set实现类,元素有序

5.1HashSet常用的Api

• HashSet():构造一个默认的HashSet。
• HashSet(int initialCapacity):构造一个指定初始容量的HashSet。
• add(E element):向HashSet中添加元素。
• remove(E element):从HashSet中删除元素。
• contains(E element):判断HashSet中是否包含指定元素。
• size():返回HashSet中的元素个数。
• isEmpty():判断HashSet是否为空。
• clear():清空HashSet。

具体代码的案例

public static void main(String[] args) {  
// 构造一个HashSet 
HashSet<String> set = new HashSet<>();// 向HashSet中添加元素
set.add("Apple");
set.add("Banana");
set.add("Apple"); // 重复元素,添加失败// HashSet的大小
int size = set.size(); // 2// 判断HashSet是否包含某元素
boolean contains = set.contains("Apple"); // true// 移除某元素
set.remove("Apple");// 清空HashSet
set.clear(); // 遍历HashSet
for (String elem : set) {System.out.println(elem);
}

5.2 TreeSet的常用api

• boolean add(E e) 添加元素，但重复元素不会被添加成功
• void clear() 清空集合
• boolean contains(Object o) 判断 o 是否在集合中
• Iterator iterator() 返回迭代器
• boolean remove(Object o) 删除集合中的 o
• int size() 返回set中元素的个数
• boolean isEmpty() 检测set是否为空，空返回true，否则返回false
• Object[] toArray() 将set中的元素转换为数组返回
• boolean containsAll(Collection<?> c) 集合c中的元素是否在set中全部存在，是返回true，否则返回
  false
• boolean addAll(Collection<? extendsE> c) 将集合c中的元素添加到set中，可以达到去重的效果

具体代码例子

    public static void TestSet(){Set<String> s = new TreeSet<>();
// add(key): 如果key不存在，则插入，返回ture
// 如果key存在，返回falseboolean isIn = s.add("apple");s.add("orange");s.add("peach");s.add("banana");System.out.println(s.size());System.out.println(s);例如：数据集合{1，7，6，4，5，9}；哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。isIn = s.add("apple");
// add(key): key如果是空，抛出空指针异常
//s.add(null);
// contains(key): 如果key存在，返回true，否则返回falseSystem.out.println(s.contains("apple"));System.out.println(s.contains("watermelen"));
// remove(key): key存在，删除成功返回true
// key不存在，删除失败返回false
// key为空，抛出空指针异常s.remove("apple");System.out.println(s);s.remove("watermelen");System.out.println(s);Iterator<String> it = s.iterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();}

六.哈希表的概念

6.1 概念

我们在开始搜索的时候,有以下几种方式.
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为o(N)，平衡树中为树的高度，即O(Log2N)，搜索的效率取决于搜索过程中元素的比较次数。

我们试想有没有一种理想的搜索方法:可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
这种结构的具体如下:
当向该结构中:

• 插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

• 搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相同,则搜索成功.

那究竟有没有这种数据结构呢?其实是有的.就是哈希表就完全满足了上述要求.
哈希表（英文名字为Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hash table就可以了）。
当然我还是来举一个例子大家就明白了.
哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

6.2 为什么会引起冲突

什么是冲突呢?
对于两个数据元素的关键字 和 (i != j)，有 != ，但有：Hash( ) == Hash( )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”.
知道了冲突了,我们来看一下下面的发生冲突的原因.
这里有会有一件事情发生,如果我们按照上述的哈希函数去插入的话,就会引起哈希冲突的效果,具体是怎么回事呢?看下图

6.3 解决冲突措施

哈希表函数设计

先来看一下哈希表函数设计的原则:

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单

使用哈希函数避免冲突

1. 直接定制法–(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关
键字的分布情况 使用场景：适合查找比较小且连续的情况 面试题：字符串中第一个只出现一次字符

2. 除留余数法–(常用)
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：
   Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3. 平方取中法–(了解)
   假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对
   它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分
   布，而位数又不是很大的情况

4. 折叠法–(了解)
   比特就业课
   折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，
   并按散列表表长，取后几位作为散列地址。
   折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法–(了解)
   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。
   通常应用于关键字长度不等时采用此法

6. 数学分析法–(了解)
   设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某
   些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据
   散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

负载因子的调节

具体看一下解释

我这里就粗略的说一下这两者之间的关系:

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。
已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小.

闭散列

先来看看什么叫闭散列吧.
闭散列:也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的下一个”空位置中去。那如何寻找下一个空位置呢?
找到下一个空位置的方法分为两种:

• 第一种:线性探索
  比如上面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
  线性探测:从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
  具体过程如下:
  
  采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素

• 第二种:二次探索
  线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为: Hi=(Ho +i^2 )% m,或者: Hi=(Ho -i^2 )% m。其中: i= 1,2,3.，Ho是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置，m是表的大小。对于如果要插入44，产生冲突，使用解决后的情况为:
  

开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

具体怎么个放入法,如图所示:

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了
刚才我们提到了，哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味
着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：

1. 每个桶的背后是另一个哈希表
2. 每个桶的背后是一棵搜索树

七. 实现hash桶

我们在了解开散列这种机制之后,我们接下来要手动实现一下这种机制.这只是一种简单的范例,具体怎么做,如下所示:

7.1 基本代码框架

public class HashBuck {static class Node {public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;}}public Node[] array;public int usedSize;public static final double LOAD_FACTOR = 0.75;public HashBuck() {array = new Node[10];}//1.放入一个元素public void put(int key,int val) {}//2.扩容方法private void resize() {}//3..计算负载因子private double calculateLoadFactor() {}//4.根据k得到一个元素public int get(int key) {}}

7.2 放入一个元素

具体思路:

1. 计算键key的散列值,得到散列桶索引index。
2. 查找散列桶中是否存在键key的节点,如果存在则更新值,否则进行头插法插入新节点。
3. 插入新节点后,判断负载因子是否达到阈值,如果达到则进行扩容resize。
4. 扩容resize会构建更大散列表并重新散列插入所有节点,以降低负载因子。

具体代码:

 public void put(int key,int val) {int index = key % array.length;Node cur = array[index];while (cur != null) {if(cur.key == key) {cur.val = val;return;}cur = cur.next;}//采用头插法进行插入Node node = new Node(key,val);node.next = array[index];array[index] = node;usedSize++;if(calculateLoadFactor() >= LOAD_FACTOR) {//扩容resize();}}private void resize() {Node[] newArray = new Node[2* array.length];for (int i = 0; i < array.length; i++) {Node cur = array[i];while (cur != null) {Node curNext = cur.next;int index = cur.key % newArray.length;//找到了在新的数组当中的位置cur.next = newArray[index];newArray[index] = cur;cur = curNext;}}array = newArray;}//计算负载因子private double calculateLoadFactor() {return usedSize*1.0 / array.length;}

7.3 根据k得到一个元素

具体思路:

1. 根据key计算index的散列函数。
2. 采用开链法来解决散列冲突,在同一散列桶上形成链表。
3. 查找时需要遍历散列桶上的全部节点,直到找到key相等的节点或者查找结束。
   具体代码:

 public int get(int key) {int index = key % array.length;Node cur = array[index];while (cur != null) {if(cur.key == key) {return cur.val;}cur = cur.next;}return -1;}

7.4 泛型版本

public class HashBuck<K,V> {static class Node<K,V> {public K key;public V value;public Node<K,V> next;public Node(K key,V value) {this.key = key;this.value = value;}}public Node<K,V>[] array = (Node<K,V>[])new Node[10];public int usedSize;public void put(K key,V value) {int hash = key.hashCode();int index = hash % array.length;Node<K,V> cur = array[index];while (cur != null) {if(cur.key.equals(key)) {cur.value = value;return;}cur = cur.next;}Node<K,V> node = new Node<>(key, value);node.next = array[index];array[index] = node;usedSize++;}public V get(K key) {int hash = key.hashCode();int index = hash % array.length;Node<K,V> cur = array[index];while (cur != null) {if(cur.key.equals(key)) {return  cur.value;}cur = cur.next;}return null;}
}

八.具体的例子

只出现一次的数字

OJ链接
题目的具体描述
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
具体的题目解释,你可以直接点开oj链接,我这里就直接展开讲解,首先这道题有三种解决方式,我在下面一一给出思路和代码.

• 方法一:位运算
  具体的思路就是利用异或运算的规则,如果所有的数字出现的次数都相同的话,异或运算的结果就是0,如果有一个不相同异或出来的就是这个数的本身.
  具体的代码如下:

public int singleNumber(int[] nums) {int single = 0;for(int n : nums) single ^= n;return single; 
}

• 方法二:将数组排序后,相邻两个元素进行比较。当两个元素不相同时,第一个元素必为只出现一次的元素。
  具体代码如下:

public int singleNumber(int[] nums) {Arrays.sort(nums);for (int i = 0; i < nums.length-1; i+=2)  if (nums[i] != nums[i+1]) return nums[i];return nums[nums.length-1];
}

• 方法三:利用Set集合去解决问题.

1. 使用HashSet保存元素。HashSet是一个不允许元素重复的Set,只存放一个特定对象的单个副本。
2. 遍历整数数组,将每个数字添加到HashSet中。
3. 如果某个数字已经存在于集合中,则说明它至少出现过两次,不做操作。
4. 如果某个数字还没有出现过,则将其添加到集合中。
5. 最后集合中只剩下只出现一次的元素。

  Set<Integer> set = new HashSet<>();for (int n : nums) {if (set.contains(n)) {set.remove(n);} else {set.add(n);}}return set.iterator().next();
}

复制带随机指针的链表

OJ链接
这道题也比较有意思,就是复制带随机指针的链表,它最重要的两个要求入下:
1.深拷贝应该正好由 n 个 全新 节点组成
2.复制链表中的指针都不应指向原链表中的节点 。
懂得这两个要求以后,我们就可以操作了,这里我们主要利用HashMap去做相关操作.具体步骤如下:

1. 使用一个 Map 对每个节点建立映射,key 是原节点,value 是对应的新节点。
2. 第一次遍历时,创建新节点,放入 Map 中。
3. 第二次遍历时,根据 Map,设置新节点的 next 和 random 指针。
   

具体代码

  public Node copyRandomList(Node head) {Map<Node,Node> map = new HashMap<>();Node cur = head;while(cur != null) {Node node = new Node(cur.val);map.put(cur,node);cur = cur.next;}cur = head;while(cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).random =  map.get(cur.random);cur = cur.next;}return map.get(head);}

宝石与石头

OJ链接
具体解题思路

1. 遍历珠宝类型,放入 Set 中。
   利用 Set 的 O(1) 查找性质,把珠宝类型放入 Set 中。
2. 遍历石头类型。
3. 对每一个石头类型,判断是否存在对应的珠宝类型。
   使用 Set.contains() 方法来判断,时间复杂度是 O(1)。
4. 如果存在,则计数加 1。
   具体代码

 public int numJewelsInStones(String jewels, String stones) {int count = 0;Set<Character> set = new HashSet<>();//1、遍历jewelsfor(int i = 0;i < jewels.length();i++) {char ch = jewels.charAt(i);set.add(ch);}//2、遍历stonesfor(int i = 0;i < stones.length();i++) {char ch = stones.charAt(i);if(set.contains(ch)) {count++;}}return count;}

坏键盘打字

OJ链接
具体思路

1. 创建set,用来存储str2中所有不重复的大写字母
2. 转换str2为大写,存入set中
3. 创建setBroken ,用来存储str1中且不在set中的大写字母
4. 转换str1为大写
5. 遍历str1的每个大写字母:
   • 如果set不包含此字母,且setBroken还未包含此字母
     • 则将此字母加入setBroken,并打印出来
       具体代码

public static void func(String str1, String str2) {Set<Character> set = new HashSet<>();for (char ch : str2.toUpperCase().toCharArray()) {set.add(ch);}Set<Character> setBroken = new HashSet<>();for (char ch : str1.toUpperCase().toCharArray()) {if (!set.contains(ch)  && !setBroken.contains(ch) ) {setBroken.add(ch);System.out.print(ch);}}}

前K个高频单词

OJ练习
具体思路
1、遍历数组 统计每个单词出现的频率
2、建立小根堆,这里分为两种情况,频率相同和频率不相同.
3、遍历hashMap 把里面 的数据 放到小根堆,这里分为两种情况,频率相同和频率不相同.
4、输出具体结果
具体代码

  public static List<String> topKFrequent(String[] words, int k) {//1、遍历数组 统计每个单词出现的频率Map<String,Integer> hashMap = new HashMap<>();for (String s : words) {if(hashMap.get(s) == null) {hashMap.put(s,1);}else {hashMap.put(s,hashMap.get(s)+1);}}//2、建立小根堆PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {@Overridepublic int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {if(o1.getValue().compareTo(o2.getValue()) == 0) {return o2.getKey().compareTo(o1.getKey());}return o1.getValue().compareTo(o2.getValue());}});//3、遍历hashMap 把里面 的数据 放到小根堆for(Map.Entry<String,Integer> entry : hashMap.entrySet()) {if(minHeap.size() < k) {minHeap.offer(entry);}else {//小根堆放满了K个，下一个entry和堆顶元素比较Map.Entry<String,Integer> top = minHeap.peek();//堆顶的频率小于当前entry的频率 就出队 然后入队entryif(top.getValue().compareTo(entry.getValue()) < 0) {minHeap.poll();minHeap.add(entry);}else {//频率相同的情况if(top.getValue().compareTo(entry.getValue()) == 0) {if(top.getKey().compareTo(entry.getKey()) > 0) {minHeap.poll();minHeap.add(entry);}}}}}//4、 此时小根堆当中已经有了结果//System.out.println(minHeap);List<String> ret = new ArrayList<>();for (int i = 0; i < k; i++) {String key = minHeap.poll().getKey();ret.add(key);}Collections.reverse(ret);//System.out.println("ret: "+ret);return ret;}