面试经典 150 题-队列

LeetCode 面试经典 150 题-队列

环形链表

快慢指针

定义快慢指针，若两指针最后相遇则有环，否则快指针会指向空。

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // 处理边界
        if (head == null || head.next == null) {
            return false;
        }
        // 快慢指针
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            slow = slow.next;
            if (fast == null || fast.next == null) {
                return false;
            }
            fast = fast.next.next;
        }
        return true;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

环形链表II

快慢指针

找到环形入口点。假设入环点距链表头为a，相遇点距入环点为b，相遇点到最后是c，则有快指针走了a + n(b+c) + b，慢指针走了a + b，快指针走的是慢指针的两倍，即a + n(n+c) + b = 2(a + b)，即a = c + (n-1)(b+c)。即从链表头到入环点的距离等于从相遇点出发走了n-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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 边界处理
        if (head == null || head.next == null) {
            return null;
        }
        // 快慢指针
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 走到相遇点
            if (slow == fast) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }

        return null;
    }
}
  • 时间复杂度：O(n)，在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。
  • 空间复杂度：O(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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addTwo(l1, l2, 0);
    }

    private ListNode addTwo(ListNode l1, ListNode l2, int carry) {
        // 递归结束
        if (l1 == null && l2 == null) {
            return carry != 0 ? new ListNode(carry) : null;
        }
        // 保证l1是更长的那个
        if (l1 == null) {
            l1 = l2;
            l2 = null;
        }
        // 计算
        int sum = carry + l1.val + (l2 != null ? l2.val : 0);
        l1.val = sum % 10;
        carry = sum / 10;
        l1.next = addTwo(l1.next, (l2 != null ? l2.next : null), carry);
        return l1;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

迭代

初始化答案为一个「空链表」，每次循环，向该链表末尾添加一个节点（保存一个数位）。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 定义哑节点
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        // 计算
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            if (l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }
            ListNode node = new ListNode(carry % 10);
            cur.next = node;
            cur = cur.next;
            carry /= 10;
        }
        return dummy.next;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        // 链接剩余部分
        cur.next = list1 != null ? list1 : list2;
        return dummy.next;
    }
}
  • 时间复杂度：O(m + n)
  • 空间复杂度：O(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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 递归结束
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        // 比较
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}
  • 时间复杂度：O(m + n)
  • 空间复杂度：O(m + n)

随机链表的复制

回溯+哈希表

定义一个哈希表，用于存储节点的副本，如果这个节点已经存在，就直接返回，如果不存在，就复制一份，然后递归复制它的next和random。

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
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    Map<Node, Node> hash = new HashMap<>();

    public Node copyRandomList(Node head) {
        // 递归结束
        if (head == null) {
            return head;
        }
        // 如果不存在，就创建
        if (!hash.containsKey(head)) {
            Node newNode = new Node(head.val);
            hash.put(head, newNode);
            // 递归创建指针副本
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);
        }

        return hash.get(head);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

迭代

  1. 将所有节点都复制一份，链接到原节点后面。
  2. 复制节点的random就是原节点的random的next。
  3. 分离链表。
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
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        // 处理边界
        if (head == null) {
            return head;
        }

        // 复制链表节点
        for (Node cur = head; cur != null; cur = cur.next.next) {
            cur.next = new Node(cur.val, cur.next, null);
        }

        // 链接random
        for (Node cur = head; cur != null; cur = cur.next.next) {
            // 注意cur->random需要不为空才能这样操作
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
        }

        // 分离链表
        Node newHead = head.next;
        for (Node cur = head; cur != null; cur = cur.next) {
            Node copy = cur.next;
            cur.next = cur.next.next;
            copy.next = copy.next != null ? copy.next.next : null;
        }

        return newHead;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)，返回值不计入。

反转链表II

一次遍历

定义指针：

  1. cur：当前待反转节点；
  2. next：待反转节点的下一个节点；
  3. pre：待反转区域的前一个节点；

Alt text

  1. 将cur.next指向next.next；
  2. 将next.next指向pre.next；
  3. 将pre.next指向next。
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 定义哑节点
        ListNode dummy = new ListNode(0, head);
        // 找到反转起点
        int i = 1;
        ListNode pre= dummy;
        while (i < left) {
            pre = pre.next;
            i++;
        }
        // 开始反转
        ListNode cur = pre.next;
        while (i < right) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
            i++;
        }

        return dummy.next;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

灵神做法

Alt text

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 定义哑节点
        ListNode dummy = new ListNode(0, head);
        // 找到反转起点
        int i = 1;
        ListNode p0= dummy;
        while (i < left) {
            p0 = p0.next;
            i++;
        }
        // 开始反转
        ListNode pre = null;
        ListNode cur = p0.next;
        while (i < right) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
            i++;
        }
        // 链接
        p0.next.next = cur;
        p0.next = pre;

        return dummy.next;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

k个一组翻转链表

分析

  1. 先得到链表的长度n，即需要翻转n/k组。
  2. p0指向待反转组的前一个节点。
    Alt text
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 统计节点个数
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            n++;
        }

        // 定义哑节点
        ListNode dummy = new ListNode(0, head);
        ListNode p0 = dummy;
        ListNode pre = null;
        ListNode cur = head;

        // k个一组处理
        for (; n >= k; n -= k) {
            for (int i = 0; i < k; i++) {
                ListNode nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }
            // p0指向下一个待反转区域的前一个节点
            ListNode nxt = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = nxt;
        }
        
        return dummy.next;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

删除链表的倒数第N个结点

双指针

快指针先走n步，然后慢指针从哑节点开始和快指针一起走到末尾，此时慢指针指向的就是第len-n个结点。但是要删除倒数第n个节点，需要让slow指向待删除结点的前一个结点。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 定义哑节点，便于处理删除头结点的情况
        ListNode dummy = new ListNode(0, head);

        // 快指针先走n步
        ListNode fast = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 快慢指针同时走
        ListNode slow = dummy;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 此时slow指向待删除结点的前一个结点
        slow.next = slow.next.next;

        return dummy.next;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

删除链表中的重复元素II

分析

  1. 定义哑节点；
  2. 遍历，初始化cur = dummy：
    • cur.next.val == cur.next.next.val：开启循环，删除所有重复的节点；
    • 否则指向下一个即可。
  3. 返回dummy.next。
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;

        while (cur.next != null && cur.next.next != null) {
            // 如果相等就删除所有重复的
            if (cur.next.val == cur.next.next.val){
                int val = cur.next.val;
                while (cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

旋转链表

双指针

可以利用求倒数第n个结点的思想，找到倒数第k个结点，断开链表，将后端链表链接到开头。

  1. 求出链表长度n，然后找倒数第k%n个结点。
  2. 断开链接；
  3. 后段链表的最后一个节点指向链表头。
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 边界处理
        if (head == null) {
            return head;
        }
        // 求链表长度
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            n++;
        }
        // 找倒数第k%n个结点
        k = k % n;
        if (k == 0) {
            return head;
        }
        ListNode fast = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        ListNode slow = head;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 断开链接
        ListNode back = slow.next;
        slow.next = null;
        // 链到表头
        fast.next = head;

        return back;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

分隔链表

模拟

  1. 使用两个链表small和large，并定义哑节点指向它们；
  2. 遍历链表，小于x的链接到small，大于等于x的链接到large；
  3. small链接到largeHead.next。
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // 定义两个链表
        ListNode smallHead = new ListNode();
        ListNode largeHead = new ListNode();
        ListNode small = smallHead;
        ListNode large = largeHead;

        // 遍历链表
        for (ListNode cur = head; cur != null; cur = cur.next) {
            if (cur.val < x) {
                small.next = cur;
                small = small.next;
            } else {
                large.next = cur;
                large = large.next;
            }
        }

        // 链接起来
        large.next = null;
        small.next = largeHead.next;
        return smallHead.next;
    }
}

注意最后要让large.next置空，否则会让链表出现环路。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

LRU缓存

双向循环链表

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
class LRUCache {
    // 双向链表结构
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {
            key = _key;
            value = _value;
        }
    }

    //数据结构
    private int capacity;
    private DLinkedNode dummy;
    private Map<Integer, DLinkedNode> cache = new HashMap<>();

    public LRUCache(int capacity) {
        // 初始化哑节点
        dummy = new DLinkedNode();
        dummy.prev = dummy;
        dummy.next = dummy;
        // 初始化缓存容量
        this.capacity = capacity;
    }
    
    public int get(int key) {
        DLinkedNode node = getNode(key);
        return node == null ? -1 : node.value;
    }
    
    public void put(int key, int value) {
        DLinkedNode node = getNode(key);
        // 如果已经存在，就更新value
        if (node != null) {
            node.value = value;
        } else {
            // 否则new一个新节点加入哈希表
            node = new DLinkedNode(key, value);
            pushFront(node);
            cache.put(key, node);
            // 如果超出容量，需要删除结点
            if (cache.size() > capacity) {
                cache.remove(dummy.prev.key);
                remove(dummy.prev);
            }
        }
    }

    // 辅助函数
    private DLinkedNode getNode(int key) {
        if (cache.containsKey(key)) {
            // 取出并放在最前面
            DLinkedNode node = cache.get(key);
            remove(node);
            pushFront(node);
            return cache.get(key);
        } else {
            return null;
        }
    }

    // 删除结点
    private void remove(DLinkedNode x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }

    // 放在头部
    private void pushFront(DLinkedNode x) {
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
  • 时间复杂度：O(1)
  • 空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。

LFU缓存

双向链表

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
class LFUCache {
    // 双向链表结构
    class DLinkedNode {
        int key;
        int value;
        int freq = 1;

        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {
            key = _key;
            value = _value;
        }
    }

    //数据结构
    private int capacity;
    private Map<Integer, DLinkedNode> keyToNode = new HashMap<>();
    private Map<Integer, DLinkedNode> freqToDummy = new HashMap<>();
    private int minFreq;

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        DLinkedNode node = getNode(key);
        return node == null ? -1 : node.value;
    }
    
    public void put(int key, int value) {
        // 有就更新
        DLinkedNode node = getNode(key);
        if (node != null) {
            node.value = value;
            return;
        }

        // 否则判断容量
        if (keyToNode.size() == capacity) {
            // 移出频率最小的那个
            DLinkedNode dummy = freqToDummy.get(minFreq);
            DLinkedNode back = dummy.prev;
            keyToNode.remove(back.key);
            remove(back);
            // 移除空链表
            if (dummy.prev == dummy) {
                freqToDummy.remove(minFreq);
            }
        }
        // 加入
        node = new DLinkedNode(key, value);
        keyToNode.put(key, node);
        pushFront(1, node);
        minFreq = 1;
    }

    // 辅助函数
    private void remove(DLinkedNode x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }

    // 创建新的双向链表
    private DLinkedNode newList() {
        DLinkedNode dummy = new DLinkedNode(0, 0);
        dummy.prev = dummy;
        dummy.next = dummy;
        return dummy;
    }

    // 放在最前面
    private void pushFront(int freq, DLinkedNode x) {
        DLinkedNode dummy = freqToDummy.computeIfAbsent(freq, k -> newList());
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }

    private DLinkedNode getNode(int key) {
        // 不存在
        if (!keyToNode.containsKey(key)) {
            return null;
        }
        // 取出
        DLinkedNode node = keyToNode.get(key);
        remove(node);
        DLinkedNode dummy = freqToDummy.get(node.freq);
        // 为空
        if (dummy.prev == dummy) {
            freqToDummy.remove(node.freq);
            // 更新最小频率
            if (minFreq == node.freq) {
                minFreq++;
            }
        }
        pushFront(++node.freq, node);
        return node;
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
  • 时间复杂度：O(1)
  • 空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。

总结

简单链表的题一般与双指针有关，LRU、LFU缓存的设计利用了双向循环链表，需要多加复习。

算法笔记 > 队列
#队列
面试经典 150 题-队列
http://example.com/2025/01/12/posts/hot150-8/
作者
Xuan Yang
发布于
2025年1月12日
许可协议