深圳网站建设 迈,开发者模式关掉好还是开着好,成都 网站建设培训班,seo外链网站大全目录二叉搜索树二叉搜索树---查找二叉搜索树---插入二叉搜索树---删除Map和SetMap的使用Set的使用哈希表哈希冲突冲突避免冲突解决冲突解决---闭散列冲突解决---开散列题目练习只出现一次的数复制带随机指针的链表宝石与石头旧键盘二叉搜索树
二叉搜索树也叫二叉排序树#x…
目录二叉搜索树二叉搜索树---查找二叉搜索树---插入二叉搜索树---删除Map和SetMap的使用Set的使用哈希表哈希冲突冲突避免冲突解决冲突解决---闭散列冲突解决---开散列题目练习只出现一次的数复制带随机指针的链表宝石与石头旧键盘二叉搜索树
二叉搜索树也叫二叉排序树具有以下性质
若它的左子树不为空则左子树的所有结点的值都小于根结点的值。若它的右子树不为空则右子树的所有结点的值都大于根结点的值。左右子树都是二叉搜索树。
例如
二叉搜索树—查找
二叉搜索树和普通二叉树的结构都一样只是结点的值不太一样。
//二叉搜索树结构
static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val val;}
}public TreeNode root null;如何在二叉搜索树中查找某一结点值我们可以根据二叉搜索树的性质如果要查找的值大于根结点的值就继续往右边查找如果要查找的值小于根结点的值就继续往左边查找。 查找代码
public TreeNode find(int val) {TreeNode cur root;while (cur ! null) {//大于往右边if (val cur.val) {cur cur.right;} else if (val cur.val) {//小于往左边cur cur.left;} elsereturn cur;}return null;
}二叉搜索树—插入 插入代码
public boolean insert(int val) {TreeNode node new TreeNode(val);//空树if (root null) {root node;return true;}TreeNode cur root;TreeNode parent null;while (cur ! null) {if (val cur.val) {return false;} else if (val cur.val) {parent cur;cur cur.left;} else {parent cur;cur cur.right;}}//cur为空了小于放左边大于放右边if (val parent.val) {parent.left node;} else {parent.right node;}return true;
}二叉搜索树—删除
假设待删除结点为 cur待删除结点的双亲结点为 parent那么有下面几种情况 cur.left 为空 cur.right 为空 cur.left 不为空 并且 cur.right 不为空
删除代码
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;}}
}Map和Set
map 和 set 是一种专门用来进行搜索的容器或者数据结构属于动态查找也就是在查找时可以进行插入和删除操作。
一般把搜索的数据称为关键字(Key)和 Key 对应的称为值(Value)将其称为 Key-value 的键值对。分为以下两种
纯 key 模型Set 例如某单词是否在一句话中。Key-Value 模型Map 例如某单词出现的次数 单词出现次数。
Map的使用 put(K key, V value)设置 key 对应的 value 使用 put 方法时插入的 key 一定不能是 null否则会空指针异常但是 value 可以。 插入的 key 一定是可以比较的否则会报错。
如果 key 相同则会替换原来的 value。 get(Object key) 返回 key 对应的 value getOrDefault(Object key, V defaultValue) 返回 key 对应的 valuekey 不存在返回默认值 remove(Object key) 删除 key 对应的映射关系 SetK keySet() 返回所有 key 的不重复集合 CollectionV values() 返回所有 value 的可重复集合 SetMap.EntryK, V entrySet() 返回所有的 key-value 映射关系 containsKey(Object key) 判断是否包含 key containsValue(Object value) 判断是否包含 value Set的使用 哈希表 通过某种函数使元素的存储位置与它的关键码之间建立映射关系的一种存储结构叫做哈希表(散列表)。 插入元素 根据待插入元素的关键码使用函数计算出该元素的存储位置并按此位置进行存放。 搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功。 例如
哈希冲突
假设现在要插入 23就会出现冲突
不同关键字通过相同的哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。
注意 哈希表底层数组的容量往往小于实际要存储的数量这就导致一个问题冲突的发生是必然的我们只能尽量的低冲突。 冲突避免
设计合理的哈希函数可以减小冲突的概率。哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有 m 个地址时其值域必须在 0 到 m-1 之间。哈希函数计算出来的地址能均匀分布在整个空间中。哈希函数应该比较简单。
常见哈希函数 直接定制法 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况 除留余数法 设散列表中允许的地址数为 m取一个不大于 m但最接近或者等于 m 的质数 p 作为除数按照哈希函数Hash(key) key% p(pm)将关键码转换成哈希地址。
还有几个不常用的平方取中法、折叠法、随机数法、数学分析法。 负载因子调节 α(负载因子) 元素个数 / 表的长度 负载因子越大产生冲突的可能性就越大所以要想减小负载因子就要增大表的长度(扩容)。 冲突解决
解决哈希冲突两种常见的方法是闭散列和开散列。
冲突解决—闭散列
闭散列 也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去。
寻找下一个空位置 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 如果再插入 33那几个数据就会在一块那就需要其他方法解决这个问题。 二次探测 线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为Hiii ( H000iii2)% mi 等于123……。 冲突解决—开散列
开散列法又叫链地址法(开链法)同样先计算出散列地址把相同地址的关键码放于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。类似下面这种 开散列中每个桶中放的都是发生哈希冲突的元素开散列就是把一个在大集合中的搜索问题转化为在小集合中做搜索了。我们还可以继续优化在小集合中搜索例如每个桶的背后是另一个哈希表或者每个桶的背后是一棵搜索树。 题目练习
只出现一次的数
题目链接【leetcode】136. 只出现一次的数字 题目描述
这题我们利用 set 的性质来做使用异或将数组里的元素全部异或最后结果就是只出现一次的数字或者 map统计每个元素出现的次数value 为1的就是只出现一次的数字也可以。 代码
class Solution {public int singleNumber(int[] nums) {SetInteger set new HashSet();for(int x : nums){//利用add函数的返回值返回false//说明set中已经存在这个元素那我们就移除if(!set.add(x)){set.remove(x);}}//最后 set 中就剩下只出现一次的数字for (Integer x : set) {return x;}return -1;}
}复制带随机指针的链表
题目链接【leetcode】138. 复制带随机指针的链表 题目描述
题目的意思就是我们需要根据题目给的链表生成同等个数并且结点的 val 相等所给链表的 next 和 random 域指向链表中的哪个结点我们就需要在自己生成的链表中指向位置相对应的结点。 为了达到题目要求我们可以使用 map 来存储他们对应位置的结点。 代码
public Node copyRandomList(Node head) {MapNode, Node map new HashMap();Node cur head;//遍历链表while (cur ! null) {//生成和题目的链表节点 相同值 的结点Node node new Node(cur.val);//再把题目中链表的结点 和 生成的新结点存储到 map中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;}//新链表的头结点对应老链表头结点的valuereturn map.get(head);
}宝石与石头
题目链接【leetcode】771. 宝石与石头 题目描述
我们可以把宝石都放到 set 中然后遍历石头如果 set 中有这个元素那就是宝石否则就不是。
代码
class Solution {public int numJewelsInStones(String jewels, String stones) {SetCharacter set new HashSet();//先把宝石加到 set中for (int i 0; i jewels.length(); i) {set.add(jewels.charAt(i)); }int count 0;//遍历石头如果 set中包含就是宝石for (int i 0; i stones.length(); i) {if (set.contains(stones.charAt(i))) {count;}}return count;}
}旧键盘
题目链接【牛客网】旧键盘 题目描述
和上题类似我们把坏键(_hs_s_a_es) 输出的字符串添加到 set 中在遍历好键(7_This_is_a_test) 输出的字符串如果没有哪个字符那个键就是坏的也就是我们要输出的。
代码
public static void func(String str1,String str2) {SetCharacter set new HashSet();//把坏键先转成大写然后存储到 set中for (char c : str2.toUpperCase().toCharArray()) {set.add(c);}SetCharacter res new HashSet();//遍历好键把不存在的添加到 res中for (char c : str1.toUpperCase().toCharArray()) {//!res.contains(c) 避免重复输出 if (!set.contains(c) !res.contains(c)) {res.add(c);System.out.print(c);}}
}
