1、上台阶

1.1、题目介绍

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

  • 函数声明
1
2
3
4
5
6
/**
 * 跳台阶问题
 * @param target 台阶阶数
 * @return 跳法
 */
public int jumpFloor(int target);

1.2、解题思路

  • 递归

使用递归解决这个问题，对于青蛙来说，它到达最后一个台阶时只能由 f(n - 1) + 1 或者 f(n - 2) + 2 得来，类似一个斐波那契数列。

引入一个备忘录来简化这个问题，将已经计算过的数据存入其中，减少计算

image-20210911135701313

  • 动态规划
  1. 明确 base case ，当 target == 1 时，此时青蛙只有一种跳法，即跳一步到达，当 target == 2 时，青蛙有两种跳法到达终点，第一种是跳二次，一次一步，第二种是一步到位，直接跳两步到达终点（target == 0 时，也有一种跳法）
  2. 明确状态，在青蛙跳台阶的过程中，距离终点的台阶数就是状态
  3. 明确状态转移方程， f(n) = f(n - 1) + f(n -2)
  4. 使用一个一维数组 dp 来表示以第 i 步为终点的台阶有 dp[i] 种跳法

1.3、解题代码

  • 递归 + 备忘录
1
2
3
4
5
6
7
8
9
10
11
12
private Map<Integer,Integer> memo = new HashMap<>();
public int jumpFloor(int target) {
    if (target == 0 || target == 1) {
        return 1;
    }
    if (memo.containsKey(target)) {
        return memo.get(target);
    }
    int res = jumpFloor(target - 1) + jumpFloor(target - 2);
    memo.put(target, res);
    return res;
}
  • 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int jumpFloor(int target) {
    // base case
    if (target == 0 || target == 1) {
        return 1;
    }
    // 初始化一个数组，长度为 target + 1，因为我们需要记录 target = 0 时的情况
    int[] dp = new int[target + 1];
    // 这里还需要初始化数组的第一个元素和第二个元素
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= target; i++) {
        // 进行状态转移
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    // 数组中的第 target 个元素就是以 target 为终点时，青蛙有几种跳法
    return dp[target];
}

2、带环链表中链表环的入口结点

2.1、题目介绍

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

2.2、解题思路

  • 对于一个链表，先判断它是否有环，如果没有环，那么直接返回 null

  • 使用快慢指针来判断是否有环，在一个带环链表中，我们设快慢指针相遇的结点为 meet ，在确定完 meet 后，我们让一个结点从链表头结点开始，一个结点从 meet 开始，每次走一步，它们相遇的结点就是链表的环入口结点。

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
public ListNode entryNodeOfLoop(ListNode pHead) {
    if (pHead == null || pHead.next == null) {
        return null;
    }
    ListNode slow = pHead;
    ListNode fast = pHead;
    // 指定保存相遇结点的 meet 结点
    ListNode meet = null;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (slow == fast) {
            meet = fast;
            break;
        }
    }
    // 如果退出循环时 meet 为空，那么证明没有环
    if (meet == null) {
        return null;
    }
    // 让一个结点从头开始
    ListNode search = pHead;
    while (search != meet) {
        meet = meet.next;
        search = search.next;
    }
    return meet;
}

3、LRU 缓存结构设计

3.1、题目介绍

LRU 即 Least Recently Used，最近最久未使用的意思，是一种缓存淘汰策略。

实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

3.2、解题思路

使用哈希表 + 双向链表解决这个问题，题目的难点在于维护键的访问和插入顺序，题目要求每次 get 或者 put 数据后，需要将该数据设置为最新访问的数据

  • 需要能进行随机访问（哈希表查询数据的时间复杂度为 O (1) ）
  • 需要将数据移动到头部或者尾部（使用链表）

下面举一个例子来说明情况

  • 创建一个容量大小为 2 的 LRUCache 缓存对象

这里通过一个哈希表 + 一个双向链表来模拟 LRUCache，其中双向链表中 head 指向最新访问的数据 entry

1
LRUCache cache = new LRUCache(2);
  • 往缓存中放入一个键值对 1-1 ，此时需要将 1-1 设置为最新访问的数据

在 put 数据时，如果缓存未满，那么直接将结点放在双向链表的头节点的后面即可。

1
cache.put(1,1);
  • 继续往缓存中放入数据，此时将新放置的数据的 next 指向 tail
1
cache.put(2,2);
  • 从 LRUCache 缓存对象中 get 数据，这里 get(1) ，我们需要将缓存 1-1 置为最新访问的数据，然后返回 1

在 get 数据时，我们将双向链表中该 Node 的前后断开，然后令其前后结点连接结，最后将该 entry 放在头节点之后即可。

image-20210911154609376

  1. entry(1 - 1) 与前后结点的连接断开，然后将前后结点相互连接

image-20210911154724359

  1. 将entry(1 -1) 放到头节点的后面即可

image-20210911154840336

1
2
// 此时返回 1 ，同时将这个键值对 1 - 1 设置为最新访问的数据
cache.get(1);
  • 往已满的缓存中放入数据，此时由于缓存已满，所以我们需要先删除最近最久没有使用的数据，即 2-2 ，然后将 3-3 放入缓存中，并设置为最新访问
1
2
// 此时由于缓存容量达到上限，所以需要先剔除掉最近没有使用的缓存键值对 2 - 2。然后插入 3-3，同时将 3-3 设置为最新
cache.put(3,3);
  1. 删除 2-2 数据

删除时，我们只需要删除双向链表的倒数第二个结点，即 tail 的前驱结点即可

  1. 放入 3 -3 然后将其置为最新访问数据

3.3、解题代码

  • 双向链表的设计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 定义一个双向链表结点类
 */
class LinkedListNode {
    int key;
    int value;
    /**
     * 双向链表的前驱结点和后置结点
     */
    LinkedListNode front;
    LinkedListNode next;

    public LinkedListNode (int key, int value) {
        this.key = key;
        this.value = value;
    }
}
  • LRUCache 中的成员变量声明
  1. capacity：用于指定该 LRUCache 对象中缓存的大小
  2. map：用于存储 entry
  3. head / tail：双向链表中的头尾结点，这个双向链表用于维护缓存中 entry 的优先级与淘汰
1
private final int capacity;    // 创建一个 HashMap    private final Map<Integer, LinkedListNode> map;    private final LinkedListNode head;    private final LinkedListNode tail;
  • 构造方法

在构造方法中，我们需要初始化 LRUCache 缓存的大小、同时初始化双向链表的头尾结点与哈希表

1
public LRUCache(int capacity) {        this.capacity = capacity;        // 初始化哈希表        map = new HashMap<>(capacity);        // 为 head 和 tail 赋予一个无意义的值        head = new LinkedListNode(Integer.MIN_VALUE, Integer.MIN_VALUE);        tail = new LinkedListNode(Integer.MIN_VALUE, Integer.MIN_VALUE);        // 构建双向链表        head.next = tail;        tail.front = head;    }
  • put 方法

这个方法接收 key - value，先判断此时 map 中是否已经存在该 key ，如果不存在，那么判断缓存是否已满

  1. 如果缓存已满，那么我们需要淘汰掉最近最久没有使用过的缓存 entry，删除双向链表的最后一个结点即可，同时将该 entry 对应的 node 插入到双向链表的头结点后，然后将 entry 放到哈希表中
  2. 如果缓存未满，那么将 entry 对应的 node 插入到头结点后即可，同时需要将 entry 放到哈希表中

如果缓存中已经存在该 key，那么我们需要先将该 key 对应的 node 取出来，然后将该 node 的value 置为传入的 value ，然后将该结点放到双向链表的头结点后即可。

1
/** * 往 LRUCache 对象中放入 entry * @param key * @param value */public void put(int key, int value) {    //1 先判断 map 中存不存在这个 key    if (!map.containsKey(key)) {        // 如果当前缓存已满，那么我们需要淘汰最近最久没有使用过的数据        if (map.size() == capacity) {            deleteLastNode();        }        LinkedListNode node = new LinkedListNode(key, value);        // 将 node 对象插入到 head 和 head 的下一个结点之间        insertFirstNode(node);        map.put(key, node);        return;    }    //2 如果 map 中存在该 key，那么我们需要先将该 Node 获取出来    LinkedListNode target = map.get(key);    //2.1 将获取到的 target 结点的 value 置为传入的 value    target.value = value;    //2.2 断开 target 结点与前后结点的联系，然后将 target 的前后结点连在一起    removeTargetNode(target);    //2.3 将 target 结点放在头节点后的第一个结点    insertFirstNode(target);}
  • get 方法

这个方法接收一个 key，判断 map 中是否存在该 key ，如果不存在，那么直接返回-1，如果存在，那么将 map 中对应的 Node 对象提出来放在双向链表头结点后，然后返回 Node 对象的 value 即可

1
2
3
4
5
6
7
8
9
10
11
public int get(int key) {
    if (!map.containsKey(key)) {
        return -1;
    }
    // 获得数据
    LinkedListNode target = map.get(key);
    // 将对应得 entry 提到最前面
    removeTargetNode(target);
    insertFirstNode(target);
    return target.value;
}
  • 删除双向链表中最后一个结点的方法
1
2
3
4
5
6
7
8
9
10
/**
 * 用于删除双向链表最后一个结点的方法
 */
private void deleteLastNode() {
    LinkedListNode lastNode = tail.front;
    lastNode.front.next = tail;
    tail.front = lastNode.front;
    // 在链表中删除结点后，还需要在 map 中移除该 entry
    map.remove(lastNode.key);
}
  • 将结点插入到 头结点后的方法
1
2
3
4
5
6
private void insertFirstNode(LinkedListNode node) {
    node.next = head.next;
    node.front = head;
    head.next.front = node;
    head.next = node;
}
  • 将 target 结点从链表中分离出来的方法
1
2
3
4
private void removeTargetNode(LinkedListNode target) {
    target.next.front = target.front;
    target.front.next = target.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
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 LRUCache {
    private final int capacity;
    // 创建一个 HashMap
    private final Map<Integer, LinkedListNode> map;
    private final LinkedListNode head;
    private final LinkedListNode tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 初始化哈希表
        map = new HashMap<>(capacity);
        // 为 head 和 tail 赋予一个无意义的值
        head = new LinkedListNode(Integer.MIN_VALUE, Integer.MIN_VALUE);
        tail = new LinkedListNode(Integer.MIN_VALUE, Integer.MIN_VALUE);
        // 构建双向链表
        head.next = tail;
        tail.front = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // 获得数据
        LinkedListNode target = map.get(key);
        // 将对应得 entry 提到最前面
        removeTargetNode(target);
        insertFirstNode(target);
        return target.value;
    }

    /**
     * 往 LRUCache 对象中放入 entry
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        //1 先判断 map 中存不存在这个 key
        if (!map.containsKey(key)) {
            // 如果当前缓存已满，那么我们需要淘汰最近最久没有使用过的数据
            if (map.size() == capacity) {
                deleteLastNode();
            }
            LinkedListNode node = new LinkedListNode(key, value);
            // 将 node 对象插入到 head 和 head 的下一个结点之间
            insertFirstNode(node);
            map.put(key, node);
            return;
        }
        //2 如果 map 中存在该 key，那么我们需要先将该 Node 获取出来
        LinkedListNode target = map.get(key);
        //2.1 将获取到的 target 结点的 value 置为传入的 value
        target.value = value;
        //2.2 断开 target 结点与前后结点的联系，然后将 target 的前后结点连在一起
        removeTargetNode(target);
        //2.3 将 target 结点放在头节点后的第一个结点
        insertFirstNode(target);
    }

    private void removeTargetNode(LinkedListNode target) {
        target.next.front = target.front;
        target.front.next = target.next;
    }

    private void insertFirstNode(LinkedListNode node) {
        node.next = head.next;
        node.front = head;
        head.next.front = node;
        head.next = node;
    }

    /**
     * 用于删除双向链表最后一个结点的方法
     */
    private void deleteLastNode() {
        LinkedListNode lastNode = tail.front;
        lastNode.front.next = tail;
        tail.front = lastNode.front;
        // 在链表中删除结点后，还需要在 map 中移除该 entry
        map.remove(lastNode.key);
    }
}
/**
 * 定义一个双向链表结点类
 */
class LinkedListNode {
    int key;
    int value;
    /**
     * 双向链表的前驱结点和后置结点
     */
    LinkedListNode front;
    LinkedListNode next;

    public LinkedListNode (int key, int value) {
        this.key = key;
        this.value = value;
    }
}

4、单向环形链表和约瑟夫问题

4.1、环形链表

  • 单向环形链表的构建思路
  1. 先创建第一个结点，让 head 指向该结点，并自己成环
  2. 后面每当我们添加新结点时，就将该结点加入到已有的环中
  • 单向环形链表的遍历思路
  1. 让一个辅助指针指向当前环形链表的 head 结点
  2. 使用一个 while 循环进行遍历，遍历在辅助指针的 next 域 == head 时停止
  • 创建一个类，用于表示结点类
1
class LinkedListNode {    int val;    LinkedListNode next;    public LinkedListNode (int val) {        this.val = val;    }}
  • 创建一个环形链表类
1
class CircleLinkedList {    LinkedListNode head;    public void addNodes(int nums) {        // 当传入的 nums 小于 1 时，直接返回        if (nums < 1) {            return;        }        // current 指针用于指向单向链表中的 “最后” 一个结点，它的 next 始终指向 head        LinkedListNode current = null;        // 循环进行添加链表结点        for (int i = 1; i <= nums; i++) {            // 根据编号创建结点对象            LinkedListNode node = new LinkedListNode(i);            if (i == 1) {                head = node;                head.next = head;                current = head;            } else {                current.next = node;                node.next = head;                // 让辅助指针后移                current = node;            }        }    }}

4.2、约瑟夫问题

  • 问题描述

设编号为 1,2,3…n 的 n 个人围坐在一起，约定一个编号 k (1 <= k <= n) 的人从 1 开始报数，数到 m 的人出列，出列的人的下一个人又从 1 开始报数，数到 m 的人又出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列。

  • 约瑟夫问题的函数如下

其中 n 为一个大于 0 的整数，表示有编号为 1,2,3…n 的 n 个人，而 m 表示游戏中数到 m 的人即出列。

1
public int ysf (int n, int m);
  • 解题思路
  1. 创建一个辅助指针 help ，这个指针指向环形链表的最后一个结点，即 help.next 为 first （初始化）

help 指针用于帮助结点出圈，这个结点必须跟在待删除结点的后面，即 help.next = 出圈结点

  1. 在进行报数时，令 help 与 first 同时移动 m - 1 次

  2. 这时将 head 指向的结点出圈

先令 first = first.next ，然后令 help.next = first

  • 解题代码
1
2
3
4
5
6
7
8
9
10
11
12
public int lastRemaining(int n, int m) {
    List<Integer> list = new ArrayList();
    for(int i = 0;i < n;i++) {
        list.add(i);
    }
    int index = 0;
    while (list.size() > 1) {
        index = (index + m - 1) % list.size();
        list.remove(index);
    }
    return list.get(0);
}

5、最小的 K 个数

5.1、题目描述

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

  • 0 <= k <= input.length <= 10000
  • 0 <= input[i] <= 10000

5.2、解题思路

  • 思路一：先排序后取前 k 个数

  • 思路二：建立一个长度为 k 的数组

以上面的数组为例，先将这个长度为 k 的数组填满，如下所示

image-20210912154928314

让指针从下标 k 开始，遍历剩下原数组中的元素，每遍历到一个元素，就将其与下面数组的最大值进行比较，如果

  1. 当前遍历的元素大于数组中的最大值，那么此时什么都不做
  2. 当前遍历的元素小于数组中的最大值，那么用当前遍历的元素替代数组中的最大值

由于我们每次都需要替代数组中的最大值，那么我们可以将下面长度为 k 的数组换为一个大顶堆，在大顶堆中，根元素总是大于其他元素，我们可以使用 PriorityQueue 来模拟大顶堆。

5.3、解题代码

  • 思路一解题代码

这里使用 Java 中自带的排序方法来进行排序

1
2
3
4
5
6
7
8
9
10
11
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    if (input == null || input.length == 0 || k < 0 || k > input.length) {
        return new ArrayList<>();
    }
    Arrays.sort(input);
    ArrayList<Integer> result = new ArrayList<>();
    for (int i = 0; i < k; i++) {
        result.add(input[i]);
    }
    return result;
}
  • 思路二解题代码
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
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (input == null || input.length == 0 || k <= 0 || k > input.length) {
            return new ArrayList<>();
        }
        //1 构建一个大顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        //2 将 input 数组前 k 个数放入大顶堆中
//        for (int i = 0; i < k; i++) {
//            queue.add(input[i]);
//        }
//        for (int i = k; i < input.length; i++) {
//            //3 如果当前遍历的数大于大顶堆中的最大值，那么跳过
//            //4 如果当前遍历的数小于大顶堆中的最大值，那么使用当前遍历的数替换大顶堆中的最大值
//            if (input[i] < queue.peek()) {
//                queue.poll();
//                queue.add(input[i]);
//            }
//        }
        for (int i = 0; i < input.length; i++) {
            // 当大顶堆中的元素小于 k 时，此时往大顶堆中放入元素
            if (queue.size() < k) {
                queue.add(input[i]);
            } else {
                if (queue.peek() > input[i]) {
                    queue.poll();
                    queue.add(input[i]);
                }
            }
        }
        return new ArrayList<>(queue);
    }

6、合并两个有序数组、

6.1、题目描述

给出一个整数数组 A 和有序的整数数组 B，请将数组 B合并到数组 A中，变成一个有序的升序数组
注意：
1.可以假设 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n ，A 的数组空间大小为 m + n

2.不要返回合并的数组，返回是空的，将数组 B 的数据合并到 A 里面就好了

3.A 数组在[0,m-1]的范围也是有序的

6.2、解题思路

  • 思路一

创建一个辅助数组，合并的思路与归并排序的多组合并大致相似，第一个指针 leftPoint 从 0 指向 A 数组的第一个元素，第二个指针 rightPoint 指向 B 数组的第一个元素，第三个指针 assistPoint 指向辅助数组的第一个元素。

开始循环，如果 leftPoint 指向的元素大于 rightPoint 指向的元素，那么就将 rightPoint 指向的元素放入辅助数组中，同时让 rightPoint 和 assistPoint 后移，反之将 leftPoint 指向的元素放入 assist 数组中，同时移动指针

  • 思路二

不需要开辟新的 assist 数组，同样使用三个指针，此时进行反向遍历，让辅助指针指向数组的最后一个元素 (m + n - 1)，让 leftPoint 指向 A 数组的最后一个有效元素（m - 1），让 rightPoint 指向 B 数组的最后一个元素 （n - 1）

开始循环，当 leftPoint >=0 && rightPoint >= 0 的条件下进行循环，如果此时 leftPoint 指向的元素大于 rightPoint 指向的元素，那么将 leftPoint 指向的元素放到辅助指针的位置中，同时让 leftPoint 和 辅助指针往前移动，反之将 rightPoint 指向的元素放到辅助指针的位置，同时让 rightPoint 和 辅助指针前移。

6.3、解题代码

  • 思路一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void merge(int A[], int m, int B[], int n) {
    // 初始化一个辅助数组，这个数组的大小为 m + n
    int[] assist = new int[m + n];
    int assistPoint =  0;
    int aPoint = 0;
    int bPoint = 0;
    while (aPoint < m && bPoint < n) {
        if (A[aPoint] < B[bPoint]) {
            assist[assistPoint++] = A[aPoint++];
        } else {
            assist[assistPoint++] = B[bPoint++];
        }
    }
    while (aPoint < m) {
        assist[assistPoint++] = A[aPoint++];
    }
    while (bPoint < n) {
        assist[assistPoint++] = B[bPoint++];
    }
    for (int index = 0; index < m + n; index++) {
        A[index] = assist[index];
    }
}
  • 思路二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void merge(int A[], int m, int B[], int n) {
    int aPoint = m - 1;
    int bPoint = n - 1;
    int assistPoint = m + n - 1;
    while (aPoint >= 0 && bPoint >= 0) {
        if (A[aPoint] > B[bPoint]) {
            A[assistPoint--] = A[aPoint--];
        } else {
            A[assistPoint--] = B[bPoint--];
        }
    }
    while (aPoint >= 0) {
        A[assistPoint--] = A[aPoint--];
    }
    while (bPoint >= 0) {
        A[assistPoint--] = B[bPoint--];
    }
}

7、随机链表的复制

7.1、题目描述

一种特殊的单链表结点类描述如下：

1
2
3
4
5
6
class Node {
    int value;
    Node next;
    Node rand;
    Node(int value) {this.value = value;}
}

rand 指针是单链表结构中新增的指针，rand 可能指向链表中任意一个结点，也可以指向 null ，给定一个由 Node 结点类型组成的无环单链表的头结点 head ，请实现一个函数完成对这个链表的复制，并返回新链表的头结点

无环 指单独凭借 next 无法构造成环

  • 要求时间复杂度为 O(N)，额外空间复杂度为 O(1)

7.2、解题思路

  • 思路一：使用哈希表

使用一个 Map，其中 key 为被克隆的结点，即原来的结点，而 value 为克隆品结点，假设 1 的克隆品为 1^ ，2 的克隆品为 2^ ，那么我们以 1 为键， 1^ 为value，将这条记录存入 map 中。

  1. 遍历一遍原链表，以原品地址为 key ，克隆品地址为 value ，将记录存入 map 中

  2. 根据 map 中原品的 rand 指针指向的结点和 next 指针指向的结点就可以还原出克隆品中 rand 和 next 应该指向的值

我们需要进行两次遍历，第一次遍历是为了获取所有原品的克隆品，并将其放入到一个哈希表中，第二次遍历是为了根据原品的 next 和 rand 指针确定克隆品之间的关系。

在循环中，使用的 cur 结点是原品结点，而通过 cur 从哈希表中获取的结点是克隆品

  • 思路二：不使用哈希表

遍历链表，在遍历到一个结点时，克隆一个结点放在原品结点与下一个原品结点之间，然后不设置克隆结点的 rand 指针，假设有链表 1 - 2 - 3（rand忽视），那么遍历一次链表后链表变为 1 - 1^ - 2 - 2^ - 3 - 3^ ，这个时候我们不一个个从链表中取出数据，而是两个为一组（1 - 1^） 拿出数据，这样我们就可以根据原品的 rand 指针为克隆品的 rand 指针赋值（克隆品.rand = 原品.rand.next）。

然后分离链表

7.3、解题代码

  • 使用哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public Node copyRandomList(Node head) {
    //1 创建一个哈希表，这个哈希表以原品为键，克隆品为值
    Map<Node, Node> nodeMap = new HashMap<>();
    //2 循环遍历链表，将原品与克隆品放入哈希表中
    Node cur = head;
    while (cur != null) {
        nodeMap.put(cur, new Node(cur.val));
        cur = cur.next;
    }
    //3 再次遍历链表，每找到一个结点，就根据这个原品的 rand 和 next 指定复制品的 next 和 rand
    cur = head;
    while (cur != null) {
        // cur.next 原品，我们使用这个值可以取出它在 map 中的复制品，然后让克隆品的 next 指针指向 cur.next 的克隆品
        nodeMap.get(cur).next = nodeMap.get(cur.next);
        // 同理可以取到随机值
        nodeMap.get(cur).random = nodeMap.get(cur.random);
        cur = cur.next;
    }
    return nodeMap.get(head);
}

完整代码如下

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
import java.util.HashMap;
import java.util.Map;
public class TestExam {
    public Node copyRandomList(Node head) {
        //1 创建一个哈希表，这个哈希表以原品为键，克隆品为值
        Map<Node, Node> nodeMap = new HashMap<>();
        //2 循环遍历链表，将原品与克隆品放入哈希表中
        Node cur = head;
        while (cur != null) {
            nodeMap.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        //3 再次遍历链表，每找到一个结点，就根据这个原品的 rand 和 next 指定复制品的 next 和 rand
        cur = head;
        while (cur != null) {
            // cur.next 原品，我们使用这个值可以取出它在 map 中的复制品，然后让克隆品的 next 指针指向 cur.next 的克隆品
            nodeMap.get(cur).next = nodeMap.get(cur.next);
            // 同理可以取到随机值
            nodeMap.get(cur).random = nodeMap.get(cur.random);
            cur = cur.next;
        }
        return nodeMap.get(head);
    }
}
class Node {
    int val;
    Node next;
    Node random;

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

8、动态规划

8.1、动态规划特点

  • 重叠子问题。
  • 状态转移方程。
  • 最优子结构。

题型：求最值。

核心：穷举。

8.2、动态规划解题道路

  • 明确 【状态】
  • 明确 【选择】
  • 明确 【dp函数/数组的定义】
  • 明确 【base case】

8.3、解题框架

image-20210415221718051

9、01背包问题

9.1、题目介绍

给你一个可装载容量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。

其中第 i 个物品重量为 wt[i] ，价值为 val[i] ，现在让你用这个背包装物品，问最多能装的价值为多少？

  • 函数的定义如下
1
int knapsack(int number, int capacity, int[] wt, int[] val);
  • 例子
1
2
3
capacity = 3,number = 3
wt[] = {2,1,3}
val[] = {4,2,3}

结果返回 6

9.2、明确状态与选择

  • 状态：会变化的量就是状态
  1. 背包的空余容量剩多少
  2. 可选择的物品还有哪些？
  • 选择：能使状态发生变化的动作就是选择
  1. 将这件物品装入背包
  2. 不将这个物品放入背包

9.3、dp 数组的意义

  • dp[i] [w] 数组的意义为

对于前 i 个物品，当背包的容量为 w 时，可以装的最大价值为 dp[i] [w]

比如说：dp[3] [5] = 6 的意义为，如果只对前三个物品进行选择，那么当背包的容量为 5 时，可以装的物品的最大价值为 6

  • 由上面的定义可以得到：dp [0] […] = dp […] [0] = 0，我们需要计算的结果为 dp [N] [W]

9.4、状态转移方程

  • 在背包容量为 w 时，如果我们选择把第 i 件物品装入背包，那么此时得到的价值为多少？

应为这件物品的价值 val[i] + x

x 为当只有前 i 件物品可供选择，且背包容量为 (w - wt[i]) 时背包能装的最大价值

1
dp[i] [w] = dp[i - 1] [w - wt[i]] + val[i]
  • 在背包容量为 w 时，如果我们选择不把第 i 件物品装入背包（或者第 i 件物品重量大于背包容量），那么此时得到的价值为多少？

应为 dp[i - 1] [w]，如果不选择第 i 件物品，那么只能在前 i - 1 件物品中选择，此时背包容量依然为 w

1
dp[i] [w] = dp[i - 1] [w]
  • 01 背包问题的状态转移方程如下
1
2
3
4
5
if (背包容量大于第 i 件物品容量) {
    dp[i][j] = Math.max (dp[i - 1][j - wt[i]] + val[i],dp[i - 1][j]);
} else {
    dp[i][j] = dp[i - 1][j];
}

9.5、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int knapsack (int number, int capacity, int[] wt, int[] val) {
    //1 base case：dp[0][...] = dp[...][0] = 0，这里需要预留多一个空间，因为需要考虑 dp[0][...] 和 dp[...][0] 的情况
    // 同时有需要考虑 number 件物品以及 capacity 容量，所以需要 + 1
    int[][] dp = new int[number + 1][capacity + 1];
    for (int i = 1; i <= number; i++) {
        for (int j = 1; j <= capacity; j++) {
            // 如果第 i - 1 件物品的重量大于背包当前容量 j
            // 为什么是 i - 1 件？这是因为循环中的 i 从 1 开始，而数组中的物品下标从 0 开始
            // 第一次进入循环时，我们需要考虑数组中的第一件物品，下标为 0
            if (wt[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(
                        dp[i - 1][j],
                        dp[i - 1][j - wt[i - 1]] + val[i - 1]
                );
            }
        }
    }
    return dp[number][capacity];
}

10、斐波那契数列

  • 如果按照原有思路，那么代码如下：
1
2
3
4
5
6
class Solution {
	public int fib(int n) {
        if(n == 0 || n == 1) return n;
    	return fib(n - 1) + fib(n - 2);
    }
}

这样代码虽然可以通过，但执行效率非常低，这是由于以上代码会产生递归树，例如我们要计算 fib(20)，那么计算过程如下

image-20210415222640658

上面存在多次冗余计算，可以使用 数组 或 HashMap 进行优化。

  1. 使用数组优化

在每次进行计算之前先判断备忘录中存不存在该数据，如果存在直接返回，否则计算该

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int fib(int n) {
    // 这里必须创建 n + 1 个空间大小的数组
    // 这是由于数组下标从 0 开始
    int[] memory = new int[n + 1];
    return helper(memory,n);
}

private int helper(int[] memory, int n) {
    if(n == 0 || n == 1) {
        return n;
    }
    if(memory[n] != 0) {
        return memory[n];
    }
    memory[n] = helper(memory,n - 1) + helper(memory,n - 2);
    return memory[n];
}
  1. 使用 HashMap 进行优化
1
2
3
4
5
6
7
8
9
10
11
12
private static Map<Integer, Integer> map = new HashMap<>();
public static int fib(int n) {
    if(n == 0 || n == 1) {
        return n;
    }
    if(map.get(n) != null) {
        return map.get(n);
    }
    int count = fib(n - 1) + fib(n - 2);
    map.put(n,count);
    return count;
}
  1. 使用迭代法进行自下而上递推，直到 fib(0)，fib(1)，就可以退出 fib(2)，以此类推

先确定 base case，即 fib(0) = 0，fib(1) = 1。

使用循环进行迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int fib(int N) {
    if(N == 0) {
        return 0;
    }
    // 这里同样需要 new N + 1 个空间
    int[] dp = new int[N + 1];
    // base case
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= N ; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[N];
}
  1. 继续进行优化，优化空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int fib(int n) {
    if(n == 0) {
        return 0;
    }
    // base case
    int prev = 0;
    int curr = 1;
    for (int i = 2; i <= n; i++) {
        // 状态转移，先计算出当前和 sum
        int sum = prev + curr;
        // 进行变量更新。
        prev = curr;
        curr = sum;
    }
    return curr;
}
  • 递归算法的时间复杂度

递归函数调用次数 * 递归函数本身的时间复杂度

11、零钱兑换问题

11.1、题目介绍

给定不同面额的硬币 coins 和一个总金额 amount，编写一个函数来计算可以凑成总金额 amount 所需的最少的硬币个数。

如果没有任何一种硬币组合能够组成总金额，那么返回 - 1 （我们可以认为给定的每种硬币数是无限的）

  • 函数定义
1
public int coinChange(int[] coins, int amount);

11.2、base case 、状态和选择

  • base case

当输入的金额为 0 时，此时只需要 0 个硬币就能得出答案，所以返回 0

当输入的金额小于 0 时，此时没有结果，返回 -1

  • 状态：总金额 amount
  • 选择：coins 数组中列出的所有硬币面额，当我们选择 coins 数组中的某个硬币时，amount 会随之变化。

11.3、解题思路

  • 给定 coins = {1,2,5}, amount = 11

可以这样想，如果我们知道凑出 10 （11 - 1） 的最少硬币的个数，然后加上一个 1 元硬币，那么就凑出了 11

同理，如果我们知道凑出 9 （11 - 2）的最少硬币的个数，然后加上一个 2 元硬币，那么也凑出了 11

同理，如果我们知道凑出 6 （11 - 5）的最少硬币的个数，然后加上一个 5 元硬币，那么也凑出了 11

  • 从上面的分析中我们可以得到下面这张图

image-20210416084908224

我们需要对上面的三种结果取一个最小值

11.4、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int coinsChange(int[] coins, int amount) {
    // base case：如果输入的 amount 小于 0 ，那么直接返回 - 1
    if (coins == null || coins.length == 0 || amount < 0) {
        return -1;
    }
    // base case：如果输入的 amount 等于 0 ，那么直接返回 0
    if (amount == 0) {
        return 0;
    }
    // 初始化 res 为 Integer.MAX_VALUE
    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 求解子问题的解
        int subResult = coinsChange(coins, amount - coin);
        // 如果子问题的解为 -1 ，证明该子问题无解，那么直接跳过
        if (subResult == -1) {
            continue;
        }
        // 这里需要进行 + 1，因为原问题 = 子问题 + 当前循环的这一块硬币
        res = Math.min(res, subResult + 1);
    }
    return res == Integer.MAX_VALUE ? -1 : res;
}

以上面的例子来说，我们要求解的 amount = 11 的问题可以分解为三个子问题，即

1
coinsChange(coins,11) = min{coinsChange(coins,10),coinsChange(coins,9),coinsChange(coins,6)} + 1

然后 amount = 10、amount = 9、amount = 6 又可以分解为其他的子问题，当子问题的解不合法时，我们需要进行跳过。