leetcode数据结构

发表于 | 分类于

单调栈

单调栈主要解决以下几个问题：

  • 比当前元素更大的下一个元素
  • 比当前元素更大的前一个元素
  • 比当前元素更小的下一个元素
  • 比当前元素更小的前一个元素

寻找比当前元素更大的下一个元素或者下一个元素，那么应该使用栈底到栈顶由大到小的单调栈。当某个元素大于栈顶元素，将栈顶元素弹出，而该元素就是栈顶元素的最右侧的第一个大于它的元素。最左侧的最大元素，那么，某个元素在栈中的下一个元素就是大于它的第一个元素。

寻找比当前元素更小的下一个元素或者前一个元素，则使用栈底到栈顶由小到大的单调栈。

496.下一个更大元素

给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
     * 因为nums1是nums2的子集，所以只需要求出nums2中的每一个元素的下一个更大元素即可，存储在map中，使用单调递增来解决
     * 遍历nums2，当栈顶元素比他小的时候，该元素是没有用的，将其踢出栈，并入栈
     * 当栈顶元素大于该元素的时候，保留栈顶元素，入栈
     * */
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    HashMap<Integer,Integer> map = new HashMap<>();
    Stack<Integer> stack = new Stack<>();
    for(int i=nums2.length-1;i>=0;i--){
        while(!stack.isEmpty()&&stack.peek()<=nums2[i]){
            stack.pop();
        }
        map.put(nums2[i],stack.isEmpty()?-1:stack.peek());
        stack.push(nums2[i]);
    }
    int[] result = new int[nums1.length];
    for(int i=0;i<nums1.length;i++){
        result[i] = map.get(nums1[i]);
    }
    return result;
}




/**
     * 因为要求更大元素，建立一个从栈底到栈顶由大到小的栈.
     * 当某个元素大于栈顶元素，将栈顶元素弹出，而该元素就是栈顶元素的最右侧的第一个大于它的元素。
     * 而要是求最左侧的最大元素，那么，某个元素在栈中的下一个元素就是大于它的第一个元素。
     * */
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer,Integer> map = new HashMap<>();
    Stack<Integer> statck = new Stack<>();
    for(int i=0;i<nums2.length;i++){
        while(!statck.isEmpty()&&nums2[statck.peek()]<nums2[i]){
            int index = statck.pop();
            map.put(nums2[index],nums2[i]);
        }
        statck.push(i);
    }
    while(!statck.isEmpty()){
        map.put(nums2[statck.pop()],-1);
    }
    int[] res = new int[nums1.length];
    for(int i=0;i<nums1.length;i++){
        res[i] = map.get(nums1[i]);
    }
    return res;
}

503.下一个更大元素2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），
     * 输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，
     * 这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。
     * 如果不存在，则输出 -1。
     *
     * 关于环型数组的问题，构建一个环型数组可以通过取余运算来解决
     * 例如，[1,3,4,2]，我们将其当作[1,3,4,2,1,3,4,2]来看待，遍历这个2n长度的数组
     * 其他的，与之前的求下一个最大元素类似，使用单调栈来解决
     * */
public int[] nextGreaterElements(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    int[] result = new int[nums.length];
    int length = nums.length;
    for(int i = 2*nums.length-1;i>=0;i--){
        while(!stack.isEmpty()&&stack.peek()<=nums[i%length]){
            stack.pop();
        }
        result[i%length] = stack.isEmpty()?-1:stack.peek();
        stack.push(nums[i%length]);
    }
    return result;
}

 public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i<nums.length*2;i++){
            while(!stack.isEmpty()&&nums[i%n]>nums[stack.peek()%n]){
                int index = stack.pop()%n;
                res[index%n] = nums[i%n];
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int index = stack.pop();
            if(index<nums.length){
                res[index] = -1;
            }
        }
        return res;
    }

556.下一个更大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 /**
     * 给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，
     * 并且其值大于n。如果不存在这样的32位整数，则返回-1。
     *1.寻找第一个不是单调减的元素i，假如没有，返回-1
     * 2.寻找大于i的最小元素
     * 3.交换两个元素
     * 4.将i之后的元素反置
     * */
public int nextGreaterElement(int n) {
    char[] a = (""+n).toCharArray();
    if(a.length<2){
        return -1;
    }
    //从尾部寻找第一个不是递减的元素
    int index = a.length-2;
    while(index>=0&&a[index+1]<=a[index]){
        index--;
    }
    if(index<0){
        return -1;
    }
    int j = a.length-1;
    //寻找大于a[index]的
    while(j>index&&a[index]>=a[j]){
        j--;
    }
    swap(a,index,j);
    reverse(a,index+1,a.length-1);
    //注意处理异常，可能会溢出int范围
    try {
        return Integer.parseInt(new String(a));
    }catch(Exception e){
        return -1;
    }
}
public void swap(char[] a,int i,int j){
    char tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

public void reverse(char[] a,int i,int j){
    while(i<j){
        swap(a,i,j);
        i++;
        j--;
    }
}

739.每日温度

下一个更大元素问题，单调递增栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
     * 每日温度
     * 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。
     * 如果之后都不会升高，请在该位置用 0 来代替。
     *
     *单调递增栈来解决
     * */
public int[] dailyTemperatures(int[] T) {
    Stack<Integer> stack = new Stack<>();
    int[] res = new int[T.length];
    for(int i=0;i<T.length;i++){
        while(!stack.isEmpty()&&T[i]>T[stack.peek()]){
            int index = stack.pop();
            res[index] = i-index;
        }
        stack.push(i);
    }
    while(!stack.isEmpty()){
        int index = stack.pop();
        res[index] = 0;
    }
    return res;
}

901.股票价格跨度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
 * 其实就是求最近的大于他的元素
 * */
public class StockSpanner {
    Stack<Integer> prices = new Stack<>();
    Stack<Integer> weights = new Stack<>();
    public StockSpanner() {

    }

    public int next(int price) {
        int weight = 1;
        while(!prices.isEmpty()&&prices.peek()<=price){
            prices.pop();
            weight+=weights.pop();
        }
        prices.push(price);
        weights.push(weight);
        return weight;
    }
}

题解

84. 柱状图中最大的矩形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//本质就是找到某个元素左侧第一个小于它的元素，以及右侧小于它的第一个元素
public int largestRectangleArea(int[] nums) {
    if(nums.length==0){
        return 0;
    }
    Stack<Integer> stack = new Stack<>();
    int max = 0;
    for(int i =0;i<nums.length;i++){
        while(!stack.isEmpty()&&nums[i]<nums[stack.peek()]){
            int ele = stack.pop();
            int after_index = i;
            int before_index = stack.isEmpty()?-1:stack.peek();
            max = Math.max(max,(after_index-before_index-1)*nums[ele]);
        }
        stack.push(i);
    }

    while(!stack.isEmpty()){
        int after_index = nums.length;
        int ele = stack.pop();
        int before_index =  stack.isEmpty()?-1:stack.peek();
        max = Math.max(max,(after_index-before_index-1)*nums[ele]);
    }
    return max;
}

85. 最大矩形

本题与上一题类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
     * 单调栈的应用
     * 对于某一个数组[3,2,4,2],求他形成的最大的最大矩形面积
     * 例如，对3，求其两侧的第一个小于它的元素，这两者之间的距离即是可以形成的矩形
     * */
public int maximalRectangle(char[][] matrix) {
    int max = 0;
    if(matrix.length==0||matrix[0].length==0){
        return max;
    }
    int[] helper = new int[matrix[0].length];
    for(int i=0;i<matrix.length;i++){
        for(int j =0;j<matrix[0].length;j++){
            if(String.valueOf(matrix[i][j]).equals("0")){
                helper[j] = 0;
            }else{
                helper[j]++;
            }
        }
        max = Math.max(max,generateMatrixArea(helper));
    }
    return max;
}
//本质就是找到某个元素左侧第一个小于它的元素，以及右侧小于它的第一个元素
public int generateMatrixArea(int[] nums){
    Stack<Integer> stack = new Stack<>();
    int max = Integer.MIN_VALUE;
    for(int i =0;i<nums.length;i++){
        while(!stack.isEmpty()&&nums[i]<nums[stack.peek()]){
            int ele = stack.pop();
            int after_index = i;
            int before_index = stack.isEmpty()?-1:stack.peek();
            max = Math.max(max,(after_index-before_index-1)*nums[ele]);
        }
        stack.push(i);
    }

    while(!stack.isEmpty()){
        int after_index = nums.length;
        int ele = stack.pop();
        int before_index =  stack.isEmpty()?-1:stack.peek();
        max = Math.max(max,(after_index-before_index-1)*nums[ele]);
    }
    return max;
}

42. 接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//使用单调递减栈，假如某个元素大于栈顶元素，因为元素栈底到栈顶是由大到小的，所以必定可以形成雨水区域
public int trap(int[] height) {
    if(height.length<3){
        return 0;
    }
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    for(int i=0;i<height.length;i++){
        while(!stack.isEmpty()&&height[stack.peek()]<height[i]){
            int top = stack.pop();
            if(stack.isEmpty()){
                break;
            }
            //计算雨水区域大小,注意是i-stack.peek()-1，不是i-top
            res+=(i-stack.peek()-1)*(Math.min(height[i],height[stack.peek()])-height[top]);
        }
        stack.push(i);
    }
    return res;
}

题解

单调队列

滑动窗口最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 /**
     * 双端队列
     * 队头永远存储最大值，双端队列是单调递减的。
     * 入队的时候，假如<队尾元素,直接入队,假如>=队尾元素，那么将队尾元素挤掉，直到<队尾元素
     * 还需要注意的是，需要对队头元素是否过期进行判断：i-w==queue.peekFirst()
     * */
public int[] maxSlidingWindow(int[] nums, int k) {
    if(nums.length<k||nums.length<1){
        return new int[0]; 
    }
    //队列中存储的是下标
    LinkedList<Integer> queue = new LinkedList<>();
    int[] res = new int[nums.length-k+1];
    int index = 0;
    for(int i=0;i<nums.length;i++){
        //假如>=队尾元素，那么将队尾元素挤掉，直到<队尾元素
        while(!queue.isEmpty()&&nums[i]>=nums[queue.peekLast()]){
            queue.pollLast();
        }
        //元素入队
        queue.addLast(i);
        //过期判定
        if(i-k==queue.peekFirst()){
            queue.pollFirst();
        }
        //窗口中至少有k个元素，求取最值
        if(i>=k-1){
            res[index++] = nums[queue.peekFirst()];
        }
    }
    return res;
}

滑动窗口变形

这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
     * 准备两个单调队列，一个单调递减，存储的是最大值，一个单调递增，存储的是最小值
     * 假如[L,R]区间内满足max-min<=target，那么[L,L..R]中也必定满足；假如[L,R]区间内不满足max-min<=target，那么[L,R.R+1...arr.length]中也必定不满足；
     * */
public int SubArray(int[] nums,int target){
    //单调减队列，队头存储的是最大值
    LinkedList<Integer> qmax = new LinkedList<>();
    //单调增队列，队头存储的是最小值
    LinkedList<Integer> qmin = new LinkedList<>();
    int left = 0;
    int right = 0;
    int res = 0;
    while(left<nums.length){
        //构建单调队列，假如nums[qmax.peekFirst()]-nums[qmin.peekFirst()]>target，表明以left开始，只有[left,left.....right)这些个子数组是符合条件的
        while(right<nums.length){
            while(qmax.size()>0&&nums[qmax.peekLast()]<=nums[right]){
                qmax.pollLast();
            }
            qmax.push(right);
            while(qmin.size()>0&&nums[qmin.peekLast()]>=nums[right]){
                qmin.pollLast();
            }
            qmin.push(right);
            if(nums[qmax.peekFirst()]-nums[qmin.peekFirst()]>target){
                break;
            }
            right++;
        }

        //过期条件，因为需要将left右移，所以，下标为left的队列元素应该删除
        if(qmax.peekFirst()==left){
            qmax.pollFirst();
        }
        if(qmin.peekFirst()==left){
            qmin.pollFirst();
        }
        res+=right-left;
        left++;
    }
    return res;
}

滑动窗口处理子串的问题

关于处理最小字串，最长字串等问题，可以使用滑动窗口来解决。

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string s, t;
// 在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
    window.add(s[right++]);
    // 如果符合要求，移动 left 缩小窗口
    while (window 符合要求) {
        // 如果这个窗口的子串更短，则更新 res
        res = minLen(res, window);
        window.remove(s[left++]);
    }
}
return res;

76. 最小覆盖子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
     *需要准备两个指针，left以及right，将right不断右移，直到[left...right]包含了t，那么这是一个满足条件的子数组
     * 但是，还有可能更短，将left右移动，直到[left...right]依旧包含t，当[left...right]不包含t的时候left移动停止
     * 再将right右移，重复以上过程
     * */
public String minWindow(String s, String t) {
    if(s==null||t==null||s.length()<t.length()){
        return "";
    }
    //存储欠的字符的个数,例如t="abc"，那么初始应该前a:1,b:1,c:1
    int[] map = new int[256];
    for(int i=0;i<t.length();i++){
        map[t.charAt(i)]++;
    }
    //还差多少个字符串才能包含t，初始为t的长度，当match==0时，表明已经包含了t
    int match = t.length();
    int left = 0;
    int right = 0;
    int min = Integer.MAX_VALUE;
    String res="";
    while(right<s.length()){
        map[s.charAt(right)]--;
        //假如某个字符的map>=0，match--
        if(map[s.charAt(right)]>=0){
            match--;
        }
        //假如match==0，表明找到了一个子数组;但有可能该子数组并不是最短的，因此，应该将left左移，假如移动过程中有一个字符欠元素了，left停止移动
        if(match==0){
            while(map[s.charAt(left)]<0){
                map[s.charAt(left++)]++;
            }
            if(min>right-left+1){
                min = right-left+1;
                //beginIndex - 开始处的索引（包括）endindex 结尾处索引（不包括）
                res = s.substring(left,right+1);
            }
            match++;
            map[s.charAt(left++)]++;
        }
        right++;
    }
    return res;
}

3. 无重复字符的最长子串？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int lengthOfLongestSubstring(String s) {
    int left = 0;
    int right = 0;
    int max = 0;
    //记录字符出现的次数
    int[] map = new int[256];
    while(right<s.length()){
        char c1 = s.charAt(right);
        map[s.charAt(right++)]++;
        while(map[c1]>1){
            map[s.charAt(left++)]--;
        }
        max = Math.max(max,right-left);
    }
    return max;
}

跳表

多级索引+链表。空间复杂度O(n)，查找以及插入时间复杂度O(logn)。

对于链表的查找，常见的形式是O(n)的复杂度，需要遍历链表。

img

因此，可以抽取索引来解决。这样的话，时间复杂度就可以缩短一半。

img

skiplist正是受这种多层链表的想法的启发而设计出来的。

他会为每一个节点随机生成一个层数。

img

  • 跳表实际上是通过多级索引来达到一个链表的二分查找的目的。
  • 每个元素level是随机生成的。
  • 最底层包含所有元素。
  • 跳表查询、插入、删除的时间复杂度为O(log n)
  • 每个元素内部是一个list，例如，7就是一个由4个元素组成的list。

查找数据

查找时间复杂度是O(logn)。

从最高层开始，一层层遍历直到原始链表。

img

最高层索引：从head开始，head下一个元素未7，所以后移。7下一个未null，所以位于7，null之间，下沉。

二层索引：从7开始，7下一个元素是37，23位于7，37之间。下沉。

一级索引：从7开始，7下一个元素19，23不位于，向右移动，19下一个元素37，23位于。下沉。

原始链表：从19开始，19下一个元素是22，23不位于，向右移动，22下一个元素26，找到23位置。

插入数据

当插入数据的时候，根据该点生成的层数level，从level层开始，逐层开始插入。跟查找整个过程相似，只不过添加了一个插入元素的过程。

插入数据6，level=3。

插入数据且维护跳表图示1.jpeg

三级索引，1<6<13，所以往下移动。

插入数据且维护跳表图示2.jpeg

二级索引，6位于1，7之间，所以，直接在1，7之间插入7。

插入数据且维护跳表图示3.jpeg

一级索引，6不在1，4之间，所以向后移动，6位于4，7之间，所以插入。

插入数据且维护跳表图示4.jpeg

原始链表，6不位于4，5之间，向后移动，6位于5，7之间，直接插入。

删除数据

与查找，插入数据类似。时间复杂度也是O(logn)。

删除数据.jpeg

跳表

LRU和LFU

LRU：当容量满的时候，删除最久未使用的元素。

LFU：当容量满的时候，删除使用次数最少的，假如使用次数最少有多个元素，那么删除最久未使用的元素。

LRU

146.设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/**
 * 需要准备一个map，一个双向链表，双向链表来解决访问记录的问题 .hashMap来存储数据。
 * 双向链表来存储数据访问的先后顺序，头节点代表的就是最久未访问的数据
 * 双向链表中存储的节点包含key以及value
 * 添加元素时，需要将node插入到双向链表以及map中，而且，假如插入的key以及包含了，那么代表该点被访问了，需要将其移动到双向链表尾部；当添加元素大于容量，需要将双向链表头部元素以及map中相应元素删除
 * 当访问某一个元素时，需要将该元素移动到链表尾部
 * */
public class LRUCache {
    //双链表中的数据节点，存储的是key
    public class Node{
        public int key;
        public int value;
        public Node pre;
        public Node next;
        Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
    //定义双链表
    public class DoubleList{
        private Node head;
        private Node tail;
        public DoubleList(){
            this.head=null;
            this.tail=null;
        }
        public void addNode(Node node){
            if(node==null){
                return ;
            }
            if(this.head==null){
                head = node;
                tail = node;
            }else{
                tail.next = node;
                node.pre = tail;
                tail = node;
            }
        }

        //将某个节点移动到尾部，即将访问过的节点移动到尾部
        public void moveToTail(Node node){
            if(tail==node){
                return;
            }
            if(head==node) {
                head.next.pre = null;
                head = head.next;
            }else{
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            tail.next = node;
            node.pre = tail;
            tail = node;
            node.next = null;
        }
        //删除头节点
        public Node removeHead(){
            if(head==null){
                return null;
            }
            Node tmp = head;
            if(head==tail){
                head=null;
                tail=null;
            }else {
                head.next.pre = null;
                head = head.next;
                tmp.next = null;
            }
            return tmp;
        }
    }
    Map<Integer,Node> map = new HashMap<>();
    DoubleList list = new DoubleList();
    private int capicity;
    public LRUCache(int capacity) {
        this.capicity = capacity;
    }

    public int get(int key) {
        //map中含有该元素，直接获取value，并将节点移动至尾部
        if(map.containsKey(key)){
            list.moveToTail(map.get(key));
            return map.get(key).value;
        }else{
            return -1;
        }
    }

    public void put(int key, int value) {
        //map中包含该元素，那么更新value，并将list中节点移动到队尾
        if(map.containsKey(key)){
            map.get(key).value = value;
            list.moveToTail(map.get(key));
        }else{
            //map中没有该元素，新建节点直接插入map，并且插入到list尾部,假如超过了容量，需要list头部元素删除，并且删除map中相应元素
            Node node = new Node(key,value);
            map.put(key,node);
            list.addNode(node);
            if(map.size()==size+1){
                removeHead();
            }
        }
    }

    //删除list头部元素以及map中相应元素
    public void removeHead(){
        Node node = list.deleteHeadNode();
        map.remove(node.key);
    }
}

LFU

当容量满的时候，删除的是访问次数最少的，假如有多个访问次数最少的节点，删除最久未访问的。

多个桶组成，每个桶代表的是访问次数的数值，桶内存储的是相同访问次数的所有节点，采用头插法，所以尾节点是该桶内最久未访问的节点。

各个桶之间也是使用双向链表来进行存储。

因此，需要定义一个Node：key，value，times(访问次数),pre,next.

两个map，一个存储key与Node，一个存储Node属于哪一个桶。

插入数据：假如map中包含该元素，那么更新value，访问次数++，并将该元素移动到访问次数+1桶。假如没有该元素，直接将该元素插入到访问次数为1的桶。假如超过了size，那么删除第一个桶的尾节点。

get数据：访问次数++，移动到访问次数+1的桶。

并查集

检查两个元素是否属于一个集合。

合并两个元素各自所在的所有集合。

并查集需要一次性将所有的数据传给他.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class UnionFind<K> {
    //需要两个map，一个来存储元素的代表节点，一个来存储代表节点:集合大小
    Map<K,K> fatherMap ;
    Map<K,Integer> sizeMap;
    //初始化并查集，并查集需要一次性将所有的数据传给他，初始化每一个元素代表一个集合，代表节点是他本身，size = 1
    public UnionFind(List<K> nodes){
        fatherMap = new HashMap<>();
        sizeMap = new HashMap<>();
        for(K node:nodes){
            fatherMap.put(node,node);
            sizeMap.put(node,1);
        }
    }

    //寻找代表节点，通过不断的迭代寻找自己的上层节点，知道找到最顶层,需要注意的是，有一个路径压缩的问题，在node寻找代表节点的过程中
    //他经过的所有父节点都需要将自己的父节点更新为代表节点
    public K findHead(K node){
        //stack中存储寻找代表节点过程中经历的所有父节点
        Stack<K> stack = new Stack<>();
        //寻找父节点
        while(node!=fatherMap.get(node)){
            stack.push(node);
            node = fatherMap.get(node);
        }
        //路径压缩
        while(!stack.isEmpty()){
            fatherMap.put(stack.pop(),node);
        }
        return node;
    }

    /**
     * 合并两个集合
     * 两个节点各自寻找到自己的代表节点，
     *      两个代表节点一致，不用合并
     *      将小集合的元素合并到大集合元素中
     * */

    public void union(K a,K b){
        K aHead = findHead(a);
        K bHead = findHead(b);
        if(aHead!=bHead) {
            int aRank = sizeMap.get(aHead);
            int bRank = sizeMap.get(bHead);
            //a集合大，直接将bHead设置为aHead的子节点,将a集合size+bRank，并将b集合的size抹除
            if(aRank>bRank){
                fatherMap.put(bHead,aHead);
                sizeMap.put(aHead,aRank+bRank);
                sizeMap.remove(bHead);
            }else{
                fatherMap.put(aHead,bHead);
                sizeMap.put(bHead,aRank+bRank);
                sizeMap.remove(aHead);
            }
        }
    }
}

前缀树

经常用于统计和排序大量的字符串（但不仅限于字符串）。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

前缀匹配

trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能

字符串检索

给定一组字符串，查找某个字符串是否出现过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
public class Trie {
        public class TrieNode{
            //该节点被经过了几次，可以用来求以其为前缀的字符串有多少
            int path;
            //该点为终止节点次数,可以用于求解某个字符串的个数
            int end;
            //字符串a-z一共有26个分支
            TrieNode[] nexts ;
            public TrieNode(){
                this.path = 0;
                this.end = 0;
                nexts = new TrieNode[26];
            }
        }
        //根节点，根节点是不存数值的
        private TrieNode root;
        /** Initialize your data structure here. */
        public Trie() {
            root = new TrieNode();
        }

        /**
         * 插入元素。
         * "XXXX"转化成字符数组，遍历整个数组，假如nexts[i]不存在，说明第一次遇到该字符，新建一个TrieNode，另next[i]=TrieNode,并path++，
         * 当遍历完成整个数组，在最后一个TrieNode的end++,代表"XXXX"出现了几次
         * */
        public void insert(String word) {
            if(word==null){
                return ;
            }
            char[] values = word.toCharArray();
            TrieNode node = this.root;
            node.path++;
            for(int i=0;i<values.length;i++){
                int index = values[i]-'a';
                if(node.nexts[index]==null){
                    node.nexts[index] = new TrieNode();
                }
                node = node.nexts[index];
                node.path++;
            }
            node.end++;
        }

        /** 查找元素,与插入元素类似，需要注意的是最后一个节点的end值必须>1*/
        public boolean search(String word) {
            if(word==null){
                return false;
            }
            TrieNode node = root;
            char[] vals = word.toCharArray();
            for(int i=0;i<vals.length;i++){
                int index = vals[i]-'a';
                if(node.nexts[index]==null){
                    return false;
                }
                node = node.nexts[index];
            }
            return node.end!=0;
        }

        /** 查询是否存在以某字符串为前缀 */
        public boolean startsWith(String prefix) {
            if(prefix==null){
                return false;
            }
            TrieNode node = root;
            char[] vals = prefix.toCharArray();
            for(int i=0;i<vals.length;i++){
                int index = vals[i]-'a';
                if(node.nexts[index]==null){
                    return false;
                }
                node = node.nexts[index];
            }
            return true;
        }
         /**
         * 删除元素
         * 首先寻找是否在前缀树中，假如在，在前缀树中依次寻找节点，将path--，并将最后一个字符end--
         * 需要注意的是，假如某个节点path--==0，那么后续的节点可以直接不用判断，直接全部删除
         * */
        public void delete(String word){
            if(search(word)){
                TrieNode node = root;
                char[] vals = word.toCharArray();
                for(int i=0;i<vals.length;i++){
                    int index = vals[i]-'a';
                    if(node.nexts[index].path--==1){
                        node.nexts[index]=null;
                        return ;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }
        }
}