常见数据结构设计题
2020-03-28 本文已影响0人
yaco
- 设计RandomPool结构（LintCode657）
- 设计并查集结构
- 前缀树
- 随时可以获取中位数的流
RandomPool结构
描述: 设计一个数据结构实现在平均 O(1) 的复杂度下执行以下所有的操作。
insert(val): 如果这个元素不在set中，则插入。
remove(val): 如果这个元素在set中，则从set中移除。
getRandom: 随机从set中返回一个元素。每一个元素返回的可能性必须相同。
思路：
-
最关键的地方在删除某一个元素的可能性是一样的，那么这里必须使得可以随机出一个索引，这个索引最大值是集合中的元素个数。使用两个HashMap和一个size容量变量即可实现
-
keyIndexMap : 存放 键——索引的map
-
indexKeyMap : 存放 索引——键的map
-
添加元素时，如果 keyIndexMap 存在当前元素，则不添加，否则分别添加两张表，并将size指针+1；
-
删除元素时，将待删除的位置用最后一位去补上，然后将最后一位删除，size指针-1即可
-
随机返回值： random（） * size 获取随机指针，然后就可以实现实现每次都等可能性的获取返回值
-
代码：
// 设计的一种结构
public static class Pool<K> {
// 成员变量
private HashMap<K,Integer> keyIndexMap;
private HashMap<Integer,K> indexKeyMap;
private int size;// 构造器 public Pool() { keyIndexMap = new HashMap<K,Integer>(); indexKeyMap = new HashMap<Integer, K>(); this.size = 0; } // 向此结构中插入一个对象 public void insert(K key) { if(!this.keyIndexMap.containsKey(key)){ this.keyIndexMap.put(key,this.size); this.indexKeyMap.put(this.size++,key); } } // 从此结构中删除一个对象 public void delete(K key) { if(this.keyIndexMap.containsKey(key)){ int deleteIndex = this.keyIndexMap.get(key); K lastKey = this.indexKeyMap.get(this.size - 1); this.keyIndexMap.put(lastKey,deleteIndex); // 把最后一个元素的位置放到要删除的节点的位置 this.indexKeyMap.put(deleteIndex,lastKey); this.indexKeyMap.remove(--this.size); } } // 随机获取一个元素，要求是等可能性获取 public K getRandom(){ if(this.size == 0) return null; int randomIndex = (int)(Math.random() * this.size); return this.indexKeyMap.get(randomIndex); }
并查集
并查集： 并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
并查集需要实现的两个具体功能：
- ( isSameSet() )查找两个元素是否属于同一个集合
- ( union() )将两个元素所在的集合进行合并
常规的思路用两个set存储不同元素，检索两个元素是否在同一个集合中很容易，然是，合并两个集合的成本往往相当的大。那么并查集就是合并和查找操作都大大加速的一种操作，它可以使得对样本的查找和合并次数接近N时，操作的时间复杂度为O（1）。
基本思路：
-
首先一开始，需要提供所有的样本数组（可以时基本数据类型，也可以是自定义的对象），将所有的样本构建成为属于子集的集合，每个集合中只有它自己一个元素。
-
合并元素的时候，将数量较少的集合添加到数量较多的集合中去。合并集合之前，必须查找当前的元素所在的头节点（也就是代表节点，他保存了当前元素的size信息），然后合并也是两个size之间的合并，不会关系到底部子节点的变化。
-
查找两个集合是否属于同一个集合，只需要不停的向上查找，检查两个元素的代表节点是否相同即可。这里再查找操作的用时，回额外进行一步优化，将沿途路过的所有节点的父节点都变为最终查找的节点。从而降低链的长度。
-
详细代码如下：
//节点类
public static class Node{
// 自定义并查集结构中操作的对象
}
public static class UnionFindSet{
private HashMap<Node,Node> fatherMap; // key:当前节点， value当前节点的父节点
private HashMap<Node,Integer> sizeMap; // 表示当前节点所在集合的大小
//空参构造器,构造并查集结构
public UnionFindSet(){
fatherMap = new HashMap<Node,Node>();
sizeMap = new HashMap<Node,Integer>();
}
//初始化并查集结构之前必须加入样本集
public void makeSets(List<Node> nodes) {
fatherMap.clear(); // 清空操作，避免之前记录影响
sizeMap.clear();
for (Node node : nodes) {
fatherMap.put(node,node);
sizeMap.put(node,1);
}
}
//查找指定Node的代表节点（递归操作，将沿途的所有节点都加到父节点下面去）
public Node findFather(Node node) {
Node father = fatherMap.get(node);
if(node != father) {
// 如果当前的节点和node不一样，表示node不是代表节点，则递归求node上一层的代表节点
father = fatherMap.get(father);
}
// 走到这里father已经是确定的值了，将沿途得所有node改为father就可以了
fatherMap.put(node,father);
return father;
}
//判断两个节点是否属于同一集合(只需要判断两个节点是否有一样的代表节点即可)
public boolean isSameSet(Node a, Node b) {
return findFather(a) == findFather(b);
}
//合并两个集合
public void Union(Node a, Node b) {
if(a == null || b == null) return;
// 首先查找出两个集合得代表节点
Node aHead = findFather(a);
Node bHead = findFather(b);
// 如果不在同一个集合，则合并
if(aHead != bHead){
// 分别获取两个集合得代表节点所存储的集合大小
int aSize = sizeMap.get(aHead);
int bSize = sizeMap.get(bHead);
// 如果a集合数量小于等于b，那么将a集合的代表节点加到b集合的代表节点中去
if(aSize <= bSize) {
fatherMap.put(aHead,bHead);
sizeMap.put(bHead,aSize + bSize);
}else{
fatherMap.put(bHead,aHead);
sizeMap.put(aHead,aSize + bSize);
}
}
}
}
并查集案例分析
1. 岛屿问题
给一个 01 矩阵，求不同的岛屿的个数。
0 代表海，1 代表岛，如果两个 1 相邻，那么这两个 1 属于同一个岛。我们只考虑上下左右为相邻。
思路一——暴力递归搜索：
- 遍历二维数组，一旦碰到1，结果集加一，表示找到了一个岛，则进入感染函数，利用递归将沿途经过的所有1均变成0。
- 具体代码如下
public static int countIslands(int[][] m) {
if(m == null || m.length == 0 || m[0].length == 0) {
return 0;
}
int res = 0; //记录结果
int row = m.length;
int col = m[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(m[i][j] == 1) {
res++;
infect(m,i,j,row,col);
}
}
}
return res;
}
// 感染函数（递归将小岛上的数全部改为2）
private static void infect(int[][] m, int i, int j, int row, int col) {
if(i < 0 || i >= row || j < 0 || j >= col || m[i][j] != 1) return;
m[i][j] = 2;
infect(m,i+1,j,row,col);
infect(m,i-1,j,row,col);
infect(m,i,j+1,row,col);
infect(m,i,j-1,row,col);
}
public static void main(String[] args) {
int[][] m1 = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0, 1, 1, 1, 0 },
{ 0, 1, 1, 1, 0, 0, 0, 1, 0 },
{ 0, 1, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 1, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
System.out.println(countIslands(m1));
int[][] m2 = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 1, 1, 1, 1, 0 },
{ 0, 1, 1, 1, 0, 0, 0, 1, 0 },
{ 0, 1, 1, 0, 0, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 1, 1, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
System.out.println(countIslands(m2));
}
思路二： 并查集结构求解
- 首先创建并查集UF结构，参数类型为int，表示数组中的元素的位置，起始可以用二维数组，这里检查为一位数组，长度为（row * col）
- 每次找到1的时候，检查上下左右四个方向是否也是1，如果是那就将两个元素合并，是他们都有共同的代表节点。这样连通的元素就会有相同的代表节点
- 然后遍历每个1位置，坚持有多少个不同的代表节点，就是最终的结果。
class UF{
private int[] parent;
public UF(int n){
parent = new int[n];
for(int i = 0 ; i < n ; i ++)
parent[i] = i;
}
public int find(int p){
if( p != parent[p] )
parent[p] = find( parent[p] );
return parent[p];
}
public boolean isConnected(int p , int q){
return find(p) == find(q);
}
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
parent[pRoot] = qRoot;
}
}
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int n = grid.length, m = grid[0].length;
UF uf = new UF(n * m);
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1') {
if (i > 0 && grid[i - 1][j] == '1') {
uf.unionElements(i * m + j, (i - 1) * m + j);
}
if (i < n - 1 && grid[i + 1][j] == '1') {
uf.unionElements(i * m + j, (i + 1) * m + j);
}
if (j > 0 && grid[i][j - 1] == '1') {
uf.unionElements(i * m + j, i * m + j - 1);
}
if (j < m - 1 && grid[i][j + 1] == '1') {
uf.unionElements(i * m + j, i * m + j + 1);
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1') {
set.add(uf.find(i * m + j));
}
}
}
return set.size();
}
}
前缀树
前缀树又名字典树，单词查找树，Trie树，是一种多路树形结构，是哈希树的变种，和hash效率有一拼，是一种用于快速检索的多叉树结构。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
前缀树
前缀树的基本思想：
- 每个节点记录金国当前节点的字符串有多少以及由多少字符串以当前节点结尾，路径表示各个字符
- 具有相同前缀的字符串具有 完全一样的前缀节点
前缀树的实现思路： - 首先定义节点类： 包含path属性（记录当前有多少个字符串经过此节点），end属性（表示当前有多少个字符串以此节点结尾），next域，用于记录下一节点（而下一个节点存在next数组的索引位置则可以代表插入的字符）
- 定义前缀树的类Trie： 包含头点root，任何字符串的插入都是从root节点开始插入。
- 插入方法： 遍历字符串依次加入字符，经过的path加1；结尾的end加1；
- 删除操作： 遍历字符串从root根节点向下搜索，一旦当前的path - 1= 0； 表示当前只有这么一个字符串经过这个位置，直接将此位置置为null即可
- 查询有多少个元素以str为前缀，直接返回以此字符串结尾节点的path即可。
- 查询是否存在某个字符串： 遍历完字符串，检查尾节点的end 是否大于0；
- 查询存在多少个str元素
代码如下：
/**
* 前缀树的节点类
*/
public static class TrieNode{
int path; //用于记录有多少个字符串经过
int end; //用于记录以此节点结尾的字符串有多少个
TrieNode[] next; // 存放下一个节点的数组，节点的位置下标表示当前路径上存放的元素值
public TrieNode(){
path = 0;
end = 0;
next = new TrieNode[26]; // 保存26个英文字母
}
}
/**
* 前缀树的实体类
*/
public static class Trie{
private TrieNode root; //根节点
// 空参构造器
public Trie(){
root = new TrieNode();
}
// 插入元素
public void insert(String str) {
if(str == null) return; // 空字符串则直接返回
char[] chars = str.toCharArray();
TrieNode node = root; // 每次插入都是从根节点开始向下插入
int index = 0; // index存放当前节点的插入位置
for (int i = 0; i < chars.length; i++) {
index = chars[i] - 'a';
// 如果当前节点的插入位置为空，则建一个新的节点
if(node.next[index] == null){
node.next[index] = new TrieNode();
}
node = node.next[index]; // 将当前节点跳到指定索引位置
node.path++; //每经过一次节点，则将节点的path自增
}
node.end++; //遍历结束之后，用end指针表示添加多少了相同类型的字符串
}
// 删除元素
public void delete(String str) {
if(str == null) return;
char[] chars = str.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chars.length; i++) {
index = chars[i] - 'a';
if(--node.next[index].path == 0){
// 如果某一个位置的path只用过一次，那么直接将此索引位置的节点对象直接置为null，那么后面所有的字符都回被删除
node.next[index] = null; //直接将这里置为空，那么后面的元素都不会继续用到，所以从这里直接给截断
return;
}
node = node.next[index];
}
node.end--;
}
// 查找待查找元素在前缀树中出现的次数
public int search(String str) {
if(str == null) return 0;
char[] chars = str.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chars.length; i++) {
index = chars[i] - 'a';
if(node.next[index] == null){
return 0; // 查找的字符串在前缀树中不存在
}
node = node.next[index];
}
return node.end;
}
// 查看有多少字符串以此字符串为前缀
public int prefixNumber(String str) {
if(str == null) return 0;
char[] chars = str.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chars.length; i++) {
index = chars[i] - 'a';
if(node.next[index] == null) {
return 0;
}
node = node.next[index];
}
return node.path;
}
前缀树的应用案例
问题描述：
给定一个数组，求子数组的最大异或和。一个数组的异或和为，数组中所有的数异或起来的结果。
基本思路：
- 路线一：将数组中0-i位置元素的亦或和按照二进制数值放入前缀树中，前缀树每个节点只有两条路径，0或者1
- 路线二：掌握亦或的性质，如果
a = b ^ c，那么肯定有c = a ^ b。 - 所以如果0-i位置（
i= 0 - i）上得所有亦或和都直到，全放入前缀树中，那么当计算i+1长度数组得最大亦或和时，只要从前缀树种找出一个与当前0-i+1亦或值最大得元素即可。 - 再搜索最大亦或值时，因为最高位我们不希望为负，所以最高位符号位优先选0，其他位置优先选1。如果当前期望得路径不存在，那么只能默认选择另外一条路径。
代码如下：
//-------------方法三： 前缀树求解---------------
// 节点类，存储int值得二进制元素
public static class Node {
// 书中只有一个属性，长度为2的Node数组,分别表示0,1
public Node[] nexts = new Node[2]; //0 , 1
}
// 前缀树结构
public static class NumTrie {
public Node head = new Node();
// 将每个int型数据加入前缀树
public void add(int num) {
Node cur = head;
for (int move = 31; move >= 0; move--) {
int path = ((num >> move) & 1); // 按位找出当前位置上面得元素（0或1）（0&1为0， 1&1为1）
cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path]; // 当前位置上得path如果为空，那么就建出来，否则，直接转移到下一层
cur = cur.nexts[path];
}
}
// num.从0-i的亦或结果中选出最优的亦或和结果返回
public int maxXor(int num) {
Node cur = head; // 从头节点开始
int res = 0;
for (int move = 31; move >= 0; move--) {
int path = (num >> move) & 1; // 首先还是确定出当前位置是0或者1
int best = move == 31 ? path : (path ^ 1); // 如果是最高位符号位，我们希望可以和path保持同号，因为这样才可以保证符号位为0
best = cur.nexts[best] != null ? best : (best ^ 1); // 如果当前节点的best没有被开发过，那么不走这条路，转而走另外一条路
res |= (path ^ best) << move; // 计算亦或结果，当前位置亦或之后，左移32位，然后再与之前的计算的res相或，计算结果。
cur = cur.nexts[best]; // cur节点移往下一位
}
return res;
}
}
public static int maxXorSubarray(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int eor = 0;
NumTrie numTrie = new NumTrie(); // 创建前缀树
numTrie.add(0); // 将初始值0扔进去
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
// 这部是关键，假设现在eor是数组元素0-7位置的疑惑和，纳闷当前数组的最大亦或和为从前缀树种挑选一个树与当前eor亦或结果最大的值即为最终的max
// 因为亦或满足交换律和结合率（ a = b ^ c）, 那么（c = a ^ b = b ^ a）
max = Math.max(max, numTrie.maxXor(eor));
numTrie.add(eor);
}
return max;
}
随时可以获取中位数的流
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
思路： 考虑使用优先级队列，创建两个队列，一个大顶堆，一个小顶堆，不停的调成两个优先级队列的长度则可以动态的保证获取中位数
- 大顶堆，元素逆序排列，队列头为最大值，小顶堆，元素升序排列，队列头为最小值。
所以这个时候就要想办法使得大顶堆放前半部分数据，小顶堆放后半部分数据。 - 添加元素： 如果大顶堆为null，优先添加大顶堆，如果大顶堆堆顶元素>= 当前的元素，则放入大顶堆，否则放入小顶堆，添加完成之后，检查两个对的size差值是否大于1，如果大于1，进行均衡操作。
- 获取中位数操作： 如果大小堆的size和为偶数，则y回a自堆元素的均值，否则，返回较长堆的堆顶。
- 代码如下：
class MedianFinder {
class MyMaxComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
class MyMinComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
private PriorityQueue<Integer> maxHeap;
private PriorityQueue<Integer> minHeap;
/** initialize your data structure here. */
public MedianFinder() {
maxHeap = new PriorityQueue<Integer>(new MyMaxComparator()); // 创建大顶堆
minHeap = new PriorityQueue<Integer>(new MyMinComparator()); // 创建小顶堆
}
public void addNum(int num) {
// 如果大顶堆为null，直接加入即可，只会进行依次
if(maxHeap.isEmpty()) {
maxHeap.add(num);
return;
}
// 如果大顶堆元素>=当前元素，则放在大顶堆下面
if(maxHeap.peek() >= num){
maxHeap.add(num);
}else{
// 如果小顶堆为null，直接加入
if(minHeap.isEmpty()){
minHeap.add(num);
return;
}else{
// 如果小顶堆元素<=当前元素，则放在小顶堆下面
if(minHeap.peek() <= num){
minHeap.add(num);
}else{
// 否则，可能介于大顶堆头和小顶堆头之间的元素，优先入大顶堆
maxHeap.add(num);
}
}
}
// 添加结束之后进行均衡操作
balanceHeap(maxHeap,minHeap);
}
public double findMedian() {
int maxSize = maxHeap.size();
int minSize = minHeap.size();
if(maxSize == 0 && minSize == 0) throw new RuntimeException("queue is empty");
if(maxSize == 0) return minHeap.peek();
if(minSize == 0) return maxHeap.peek();
if(minSize == maxSize) return (minHeap.peek() + maxHeap.peek()) / 2.0;
return maxSize > minSize ? maxHeap.peek() : minHeap.peek();
}
private void balanceHeap(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
if(maxHeap.size() == minHeap.size() + 2){
minHeap.add(maxHeap.poll());
}
if(minHeap.size() == maxHeap.size() + 2){
maxHeap.add(minHeap.poll());
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
