目录
第7章
第8章
第9章
从5随机到7随机及其扩展
一行代码求两个数的最大公约数
有关阶乘的两个问题
判断一个点是否在矩形的内部
判断一个点是否在三角形内部
折纸问题
蓄水池算法
设计有setAll功能的哈希表
最大的leftMax与rightMax之差的绝对值
设计可以变更的缓存结构
设计RandoPool结构
调整[0,x)区间上的数出现的概率
路径数组变为统计数组
正数数组的最小不可组成和
一种字符串和数字的对应关系
1到n中1出现的次数
从N个数中等概率打印M个数
判断一个数是否是回文数
在有序旋转数组中找到一个数
数字的英文表达和中文表达
分糖果问题
一种消息接收并打印的结构设计
设计一个没有扩容负担的堆结构
随时找到数据流的中位数
在两个长度相等的排序数组中找到上中位数
在两个排序数组中找到第K小的数
两个有序数组间相加和的TOP K问题
Manacher算法
KMP算法
丢棋子问题
画匠问题
邮局选址问题
第7章
第8章
设计RandoPool结构
单独从hash表上而言其增删改查操作都是O(1)，这道题目的关键是如何等概率返回任何一个key，这个key可以是数字，也可以是字符串等各种类型。
用两个map来存储输入的key，当没有删除操作时0~25这些数字是连续的，可以很利用Random随机函数随机得到这些数字
当有删除时，便不连续了很难随机得到，那么有没有办法把不连续的变为连续的？当要删除b时，可以考虑把z覆盖b，25变为1，然后map的长度减一，这样即使删除了数据但仍然是连续的。
public static class Pool<K>{ private HashMap<K,Integer> keyIndexMap; private HashMap<Integer,K> indexKeyMap; private int size; public Pool(){ keyIndexMap = new HashMap<>(); indexKeyMap = new HashMap<>(); size = 0; } public void insert(K key){ if (!keyIndexMap.containsKey(key)){ keyIndexMap.put(key,size); indexKeyMap.put(size++,key); } } public void delete(K key){ if (keyIndexMap.containsKey(key)){ int deleteIndex = keyIndexMap.get(key); //因为size是从1开始计数的所以要先自减 int lastIndex = --size; K lastKey = indexKeyMap.get(lastIndex); keyIndexMap.put(lastKey,deleteIndex); indexKeyMap.put(deleteIndex,lastKey); keyIndexMap.remove(key); indexKeyMap.remove(lastIndex); } } public K getRandom(){ if (size == 0){ return null; } int randomIndex = (int)(Math.random()*size); return indexKeyMap.get(randomIndex); } }
0
原文：https://www.cnblogs.com/youngao/p/12078102.html