码神之路知识体系

开启刷题之旅

目标300道题，能覆盖95%的面试

1. 反转链表

高频面试排行第一，没有谁能撼动，最容易的算法之一

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

1
2

package com.mszlu.alg.one;

public class ReverseNode {
     static class ListNode {
        int value;
        ListNode next;

        public ListNode(int value,ListNode next){
            this.value = value;
            this.next = next;
        }
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null){
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(5,null);
        ListNode listNode4 = new ListNode(4,listNode5);
        ListNode listNode3 = new ListNode(3,listNode4);
        ListNode listNode2 = new ListNode(2,listNode3);
        ListNode listNode1 = new ListNode(1,listNode2);

        ListNode newHead = new ReverseNode().reverseList(listNode1);
        while (newHead != null){
            System.out.println(newHead.value);
            newHead = newHead.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
36
37
38
39

时间复杂度：O(n)，其中 n是链表的长度。需要遍历链表一次。
空间复杂度：O(1)。

2. LRU缓存

最为频繁出现的算法题，难度中等，定输赢的题目

题目：请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

package com.mszlu.alg.one;

import org.w3c.dom.Node;

import java.util.HashMap;
import java.util.Map;

/**
 * @author B站：码神之路
 */
public class LRUCache {
    //双向链表 + map解决
    //定义容量
    private int capacity;
    //定义链表
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
    }
    //链表的头节点和尾部节点
    private Node head;
    private Node tail;

    //key和Node节点的映射
    private Map<Integer, Node> map;

    public LRUCache(int capacity){
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);
    }

    public int get(int key){
        //先从map获取
        Node node = map.get(key);
        if (node == null){
            return -1;
        }
        //将其移动到链表头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value){
        Node node = map.get(key);
        if (node == null){
            node = new Node();
            node.key = key;
            node.value = value;
            if (map.size() == capacity){
                removeTail();
            }
            //加入头部
            addToHead(node);
            map.put(node.key,node);
        }else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void removeTail() {
        map.remove(tail.key);
        Node prev = tail.prev;
        if (prev != null) {
            prev.next = null;
            tail.prev = null;
            tail = prev;
        }
    }

    private void addToHead(Node node) {
        if (map.isEmpty()){
            head = node;
            tail = node;
        }else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    private void moveToHead(Node node) {
        if (node == head){
            return;
        } else if (node == tail){
           node.prev.next = null;
           tail = node.prev;
        }else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        node.next = head;
        node.prev = null;
        head.prev = node;
        head = node;
    }

    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1));    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
        System.out.println(lRUCache.get(3));    // 返回 3
        System.out.println(lRUCache.get(4));    // 返回 4
    }
}

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

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

难度中等，出现频次高

题目：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例：

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

1
2
3

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

1
2
3

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

1
2
3
4
5

输入: s = ""
输出: 0

1
2

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

package com.mszlu.alg.one;

/**
 * @author B站：码神之路
 */
public class NoRepeatString {

    public int lengthOfLongestSubstring(String s){
        int length = s.length();
        //存放上一次出现此字符的位置
        int[] last = new int[128];
        for (int i=0;i<128;i++){
            last[i] = -1;
        }
        int res = 0;
        //重复字串开始位置
        int start = 0;
        for (int i=0;i<length;i++){
            int index = s.charAt(i);
            start = Math.max(start,last[index] + 1);
            res = Math.max(res,i-start+1);
            last[index] = i;
        }
        return res;
    }

    public static void main(String[] args) {
        int i = new NoRepeatString().lengthOfLongestSubstring("abcabcbb");
        System.out.println(i);
    }
}

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

4. 数组中的第K个最大元素

难度中等，出现频次高

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

5. K 个一组翻转链表

难度困难出现频次高

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

6. 手撕快速排序

难度中等出现频次高

https://leetcode-cn.com/problems/sort-an-array/

7. 三数之和

难度中等出现频次高

https://leetcode-cn.com/problems/3sum/

8. 最大子序和

难度容易出现频次高

https://leetcode-cn.com/problems/maximum-subarray/

9. 两数之和

难度容易出现频次高

https://leetcode-cn.com/problems/two-sum/

10. 合并两个有序链表

难度容易出现频次高

https://leetcode-cn.com/problems/merge-two-sorted-lists/

11. 环形链表

难度容易出现频次高

https://leetcode-cn.com/problems/linked-list-cycle/

12. 二叉树的层序遍历

难度中等出现频次高

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

13. 买卖股票的最佳时机

难度容易出现频次高

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

14. 相交链表

难度容易出现频次高

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

15. 合并两个有序数组

难度容易出现频次高

https://leetcode-cn.com/problems/merge-sorted-array/

16. 二叉树的锯齿形层次遍历

难度中等出现频次高

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

17. 二叉树的最近公共祖先

难度中等出现频次高

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

18. 有效的括号

难度容易出现频次高

https://leetcode-cn.com/problems/valid-parentheses/

19. 最长回文子串

难度中等出现频次高

https://leetcode-cn.com/problems/longest-palindromic-substring/

20. 搜索旋转排序数组

难度中等出现频次高

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

# 开启刷题之旅

# 1. 反转链表

# 2. LRU缓存

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

# 4. 数组中的第K个最大元素

# 5. K 个一组翻转链表

# 6. 手撕快速排序

# 7. 三数之和

# 8. 最大子序和

# 9. 两数之和

# 10. 合并两个有序链表

# 11. 环形链表

# 12. 二叉树的层序遍历

# 13. 买卖股票的最佳时机

# 14. 相交链表

# 15. 合并两个有序数组

# 16. 二叉树的锯齿形层次遍历

# 17. 二叉树的最近公共祖先

# 18. 有效的括号

# 19. 最长回文子串

# 20. 搜索旋转排序数组

开启刷题之旅

1. 反转链表

2. LRU缓存

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

4. 数组中的第K个最大元素

5. K 个一组翻转链表

6. 手撕快速排序

7. 三数之和

8. 最大子序和

9. 两数之和

10. 合并两个有序链表

11. 环形链表

12. 二叉树的层序遍历

13. 买卖股票的最佳时机

14. 相交链表

15. 合并两个有序数组

16. 二叉树的锯齿形层次遍历

17. 二叉树的最近公共祖先

18. 有效的括号

19. 最长回文子串

20. 搜索旋转排序数组