算法六

四十一、用栈实现队列

原题链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485449&idx=1&sn=91d22371d76fdb58508b596798288430&chksm=fd9ca316caeb2a005aac5e79d9e8fde74e3294ef117160233881ab32d915c8ec4bc255ec7e24&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「232. 用栈实现队列」**，难度为 Easy。

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

进阶：

• 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

提示：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

（1）O(n)解法

做这道题需要了解栈和队列的特点，栈是末尾进，末尾出；队列末尾进，开头出。

用栈模拟队列实际就是 将栈底的元素弹出。在日常生活可知，想要拿箱底的东西，必须要将东西上面的东西全部拿出来，才能拿到箱底的东西。

例如下面所示，依次放入 1、2、3、4、5

栈底				栈顶
1	2	3	4	5

此时需要将 1 取出，则需要将 2 3 4 5 全部取出

• 临时栈：

栈底				栈顶
5	4	3	2

• 主栈：

栈底				栈顶

如果这时要放入元素 6，这再次需要将临时栈的元素放入到主栈中，然后再放入

• 主栈：

栈底				栈顶
2	3	4	5	6

由上可知，无论是取出还是放入都需要将在两个栈之间倒腾元素。

下面为完整代码：

• in 栈（主栈）用作处理输入操作 push()，使用 in 时需确保 out 为空
• out 栈（临时栈）用作处理输出操作 pop() 和 peek()，使用 out 时需确保 in 为空

class MyQueue {
  Deque<Integer> out, in;
  public MyQueue() {
    in = new ArrayDeque<>();
    out = new ArrayDeque<>();
  }

  public void push(int x) {
    // 将out栈元素全部清空
    while (!out.isEmpty()) in.addLast(out.pollLast());
    in.addLast(x);
  }

  public int pop() {
    // 将in栈元素全部清空
    while (!in.isEmpty()) out.addLast(in.pollLast());
    return out.pollLast();
  }

  public int peek() {
    // 将in栈元素全部清空
    while (!in.isEmpty()) out.addLast(in.pollLast());
    return out.peekLast();
  }

  public boolean empty() {
    return out.isEmpty() && in.isEmpty();
  }
}

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

（2）均摊O(1)解法

在将主栈的元素放入到临时栈后，会发现临时栈的已经排列成需要的形状了。

例如下面所示：

• 原先的栈：

栈底				栈顶
1	2	3	4	5

• 临时栈：由原先的栈可知，当 1 取出后下一个要取出 2，而临时栈中正好能够取出 2

栈底				栈顶
5	4	3	2

而当放入元素时，因为处于模拟队列的队尾，所以在临时栈为空之前，都取不到新元素。所以当临时栈为空时，再将主栈的元素放到临时栈里。

下面为全部代码：

class MyQueue {
  Deque<Integer> out, in;
  
  public MyQueue() {
    in = new ArrayDeque<>();
    out = new ArrayDeque<>();
  }

  public void push(int x) {
    // 直接放入，不用倒腾
    in.addLast(x);
  }

  public int pop() {
    // 如果临时栈为空，则将主栈倒腾放入到临时栈里
    if (out.isEmpty()) {
      while (!in.isEmpty()) out.addLast(in.pollLast());
    }
    return out.pollLast();
  }

  public int peek() {
    if (out.isEmpty()) {
      while (!in.isEmpty()) out.addLast(in.pollLast());
    }
    return out.peekLast();
  }

  public boolean empty() {
    return out.isEmpty() && in.isEmpty();
  }
}

• 时间复杂度：pop() 和 peek() 操作都是均摊 $O( 1 )$
• 空间复杂度：$O( n )$

（3）均摊复杂度

我们先用另外一个例子来理解「均摊复杂度」，大家都知道「哈希表」底层是通过数组实现的。

正常情况下，计算元素在哈希桶的位置，然后放入哈希桶，复杂度为 $O( 1 )$，假定是通过简单的 “ 拉链法 ” 搭配「头插法」方式来解决哈希冲突。

但当某次元素插入后，「哈希表」达到扩容阈值，则需要对底层所使用的数组进行扩容，这个复杂度是 $O( n )$

显然「扩容」操作不会发生在每一次的元素插入中，因此扩容的 $O( n )$ 都会伴随着 n 次的 $O( 1 )$，换句话就是你插入了 n 个元素，就会触发一次 $O( n )$ 的扩容，这样 $O( n )$ 的复杂度会被均摊到每一次插入当中，因此哈希表插入仍然是 $O( 1 )$ 的。

「同理，我们的「倒腾」不是发生在每一次的「输出操作」中，而是集中发生在一次「输出栈为空」的时候，因此 pop 和 peek 都是均摊复杂度为 的操作。」

我们需要对操作进行复杂度分析进行判断，而不是看时间来判断自己是不是均摊 O(1) 哦 ~

四十二、用队列实现栈

原题链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485519&idx=1&sn=cd984987eb9e03493b1e775794b79971&chksm=fd9ca350caeb2a4623f2d8d71bc0f12a1f7ae38ca5e0301f97a01742782cbca3f1ed21da801c&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「225. 用队列实现栈」**，难度为 Easy。

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

提示：

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

进阶：你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。

（1）双队列解法

和上一道题思路一致，需要额外一个队列，作为临时存放数据的地方。例如下面所示：

• 主队列：

队头				队尾
1	2	3	4	5

现在需要弹出 5，但只能将前面的 1 - 4 先存放到临时队列中

• 临时队列

队头				队尾
1	2	3	4

• 主队列：

队头				队尾
5

和上一题一样，不用每次都倒腾，放入可以直接放入到临时队列或者主队列中，弹出元素再倒腾到另一个队列中。或者放入时倒腾，弹出时直接弹出。

• 全部代码如下：下面代码为弹出时倒腾。
  • data 为主队列
  • help 为临时队列
  • 但这两个队列其实不用分得太清楚，因为都可以互相转换

class MyStack {
  // 主队列
  Deque<Integer> data = new ArrayDeque<>();
  // 临时队列
  Deque<Integer> help = new ArrayDeque<>();

  public void push(int x) {
    // 直接放入数据即可
    data.addLast(x);
  }

  public int pop() {
    // 将主队列的数据放入到临时队列
    while (data.size() > 1) {
      help.addLast(data.pollFirst());
    }
    int u = data.pollFirst();
    // 将主队列和临时队列调换
    swap();
    return u;
  }

  public int top() {
    while (data.size() > 1) {
      help.addLast(data.pollFirst());
    }
    int u = data.peekFirst();
    help.addLast(data.pollFirst());
    swap();
    return u;
  }

  public boolean empty() {
    return data.isEmpty() && help.isEmpty();
  }

  void swap() {
    Deque<Integer> tmp = data;
    data = help;
    help = tmp;
  }
}

• 时间复杂度： push() 和 empty() 方法的复杂度为 $O( 1 )$ ；而 pop() 和 top() 的复杂度为 $O( n )$ 。
• 空间复杂度：$O( n )$

（2）单队列解法

由第 （1） 点可知：经过倒腾后的队列，里面的排序没有变化，就如同弹栈，栈底的排序不会变化，例如下面所示

• 主队列：

队头				队尾
1	2	3	4	5

现在需要弹出 5，但只能将前面的 1 - 4 先存放到临时队列中

• 临时队列：1 - 4 的排序没有变化

队头				队尾
1	2	3	4

我们可以使用这个特效来简化成只使用一个队列。就像体育课同学先按高到低排好队，然后老师让同学从低到高排队，这时只需要第一个同学走到最后一个，然后后面的同学就依次跟着前面的同学，直到最后一个同学位置。

全部代码如下：

class MyStack {
  Deque<Integer> data = new ArrayDeque<>();

  public void push(int x) {
    data.addLast(x);
  }

  public int pop() {
    int size = data.size();
    // 将最前面的元素依次放到最后面
    while (size-- > 1) {
      data.addLast(data.pollFirst());
    }
    // 去掉目标元素
    return data.pollFirst();
  }

  public int top() {
    int size = data.size();
    while (size-- > 1) {
      data.addLast(data.pollFirst());
    }
    // 取目标元素的值
    int u = data.peekFirst();
    // 将目标元素也添加到最后面，还原成之前的样子
    data.addLast(data.pollFirst());
    return u;
  }

  public boolean empty() {
    return data.isEmpty();
  }
}

• 时间复杂度： push() 和 empty() 方法的复杂度为 $O( 1 )$ ；而 pop() 和 top() 的复杂度为 $O( n )$ 。
• 空间复杂度：$O( n )$

（3）总结

第四十一题和第四十二题，都是用队列或者栈其中一个，来模拟另一个，但实现思路完全不同。

其实就是队列和栈的特性导致的：

• 队列添加元素和删除元素的位置 不是同一个位置。这就可以让队列删除的同时添加元素，所以就可以缩减成一个队列。这个特性在其他领域也很常见，例如消息队列，你发送消息，我就放到队尾，而我在队头处理消息，一点都不受影响。
• 栈添加元素和删除元素的位置 是同一个位置。这个特性就让在操作栈的时候，必须明确是添加元素还是删除元素。在操作系统保存现场信息的时候使用，可以明确还原现场的顺序。

四十三、最小栈

原题链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485547&idx=1&sn=22a592f1c62b69af177845ef85a686fd&chksm=fd9ca374caeb2a628610fa4fbdd951f209b5989e2d4de900ab0c302e19a143ea3cdcc6bcf773&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「155. 最小栈」**，难度为 Easy。

设计一个支持 push ，pop ，top 操作，并能在「常数时间」内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。
• 提示：
  • pop、top 和 getMin 操作总是在「非空栈」上调用。

（1）思路

这题的难点是在常数时间检索到最小元素。通常会拿一个变量来存放最小值。每次弹栈需要判断弹栈的元素是否为最小值。

但又有一个问题，如果弹的是最后一个最小值，则需要获取到次小值，这个要求需要将每个元素排列好。

还有一个问题，如何知道这是最后一个最小值，所以需要记录最小值的数量。

这三个要求，其实多用一个栈就可以全部解决。这个栈的要求：

• 当放入的元素比第一个元素大，则在栈顶多复制第一个元素
• 当放入的元素比第一个元素小，则直接放入到栈里
• 弹栈的时候和主栈同步

（2）解法详情

下面假设输入 [2, 6, 2, 8, 4, 6, 5]

辅助栈的结构如下：

• 首先入 2。然后入 6，6 大于 2，则改成入 2

下标	数据
0
1
2
3
4
5	2
6	2

• 然后入 2。入 8 ，8 大于 2 则改成入 2。后面的数都大于 2，所以也都是入 2

下标	数据
0	2
1	2
2	2
3	2
4	2
5	2
6	2

看上面的辅助栈，全部是 2，是因为 2 在栈底，只要入栈的元素大于 2，则栈中的最小值还是 2。

上面的例子是全部入栈后再全部弹栈，如果在弹栈入栈的过程中，涉及到最小值的变化，会不会有问题呢？

例如先入栈 [6, 5, 3, 6] ，然后再弹栈两个，再入栈 [4, 7]

• 入栈 [6, 5, 3, 6] ，这时最小值为 3

下标	数据
0	3
1	3
2	5
3	6

• 弹栈两个，这时最小值为 5

下标	数据
0
1
2	5
3	6

• 再入栈 [4, 7] ，最小值为 4

下标	数据
0	4
1	4
2	5
3	6

很明显，没有任何问题。辅助栈的使用解决了第（1）点提出的问题：

• 栈顶存放了最小值，最小值的数值问题解决
• 记录了最后一个最小值的下标，可以知道最后一个最小值是否被弹出
• 因为入栈元素等于最小值，也会直接入栈，栈里就会有多个最小值，所以记录了最小值的数量

其实这个栈的核心就是：

• 在最小值还没弹出之前，最小值上面的元素怎么操作，都不会影响到最小值和次小值，除非加入了比最小值小的数，但之前的最小值和次小值的 顺序还是保持不变

（3）全部代码

class MinStack {
  Deque<Integer> data = new ArrayDeque<>();
  Deque<Integer> help = new ArrayDeque<>();

  public void push(int val) {
    data.addLast(val);
    // 如果栈为空或者比最小值小，则直接入栈
    if (help.isEmpty() || help.peekLast() >= val) {
      help.addLast(val);
    } else {	// 否则复制最小值
      help.addLast(help.peekLast());
    }
  }

  public void pop() {
    // 两个栈同时弹出
    data.pollLast();
    help.pollLast();
  }

  public int top() {
    return data.peekLast();
  }

  public int getMin() {
    // 取出辅助栈的第1个元素
    return help.peekLast();
  }
}

• 时间复杂度：所有的操作均为 $ O( 1 ) $
• 空间复杂度：$ O( 1 ) $

四十四、最大得分的路径数目

原题链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485565&idx=1&sn=9d307e3ef239d9ba509624736408fc3c&chksm=fd9ca362caeb2a7400a621755acffc51c9eabbade8bd2e0dec07ef4c8c7ffae4a98b84b9243e&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「1301. 最大得分的路径数目」**，难度为 Hard。

给你一个 正方形 字符数组 board ，你从数组最右下方的字符 'S' 出发。

你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1,2,...,9 或者障碍 'X'。

在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。

一条路径的 「得分」 定义为：路径上所有数字的和。

请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。

如果没有任何路径可以到达终点，请返回 [0, 0]

示例 1：

• 输入：board = ["E23","2X2","12S"]
• 输出：[7,1]
• 解释：上 -> 上 -> 左 -> 左，2 + 3 + 2 = 7，1 条路径

E  2  3
2  X  2
1  2  S

示例 3：

• 输入：board = ["E11","XXX","11S"]
• 输出：[0,0]
• 解释：路全部被封死，走不到终点

E  1  1
X  X  X
1  1  S

提示：

• 2 <= board.length == board[i].length <= 100

（1）动态规划

这道题之前也做过类似的，也是有障碍的，但这道题要求得出方案数，所以在执行动态规划时，需要记录两种值，即需要两个二维数组来存放数据

• f[m][n] ：存放最大数值
  • 转移条件：取右、下和右下中最大，加上当前格
• g[m][n] ：存放最大数值的方案数
  • 转移条件：将等于最大数值的方案数全部相加起来

class Solution {
  public int[] pathsWithMaxScore(List<String> board) {
    // 获取一行的长度
    int n = board.get(0).length();

    final int MOD = 1000000007;

    // 每行是一个字符串，所以将字符串转为字符数组更方便
    char[][] cs = new char[n][n];
    for (int i = 0; i < n; i++) {
      cs[i] = board.get(i).toCharArray();
    }

    // 将开头和结尾都初始化为 0，因为经过开头和结尾都不会增加数值
    cs[0][0] = '0';
    cs[n - 1][n - 1] = '0';

    // 计算全部元素数量
    int total = n * n;
    // 使用一维数组存放方案数
    int[] g = new int[total];
		// 初始化方案数的开头
    g[total - 1] = 1;
		// 新建存放最大数值的数组
    int[][] f = new int[n][n];

    // 双层循环，分别遍历行和列
    for (int i = n - 1; i >= 0; i--) {
      for (int j = n - 1; j >= 0; j--) {

        // 如果在开头则直接跳过
        if (i == n - 1 && j == n - 1)
          continue;

        // 如果当前格为障碍，当前格的最大数组为0，方案数也为0
        // 正常情况就会避免通过障碍
        if (cs[i][j] == 'X') {
          f[i][j] = 0;
          g[getIndex(i, j, n)] = 0;
          continue;
        }

        int bottom = 0;
        int bottomRight = 0;
        int right = 0;
        // 不是最后一行就取下边的数字
        if (i != n - 1) {
          bottom = f[i + 1][j];
        }
        // 不是最后一列就取右边的数字
        if (j != n - 1) {
          right = f[i][j + 1];
        }
        // 既不是最后一行也不是最后一列就取右下边
        if (i != n - 1 && j != n - 1) {
          bottomRight = f[i + 1][j + 1];
        }

        // 找出三个中的最大值
        int maxNum = findMax(bottom, bottomRight, right);
				// 将结果记录到f[][]数组中
        f[i][j] = (cs[i][j] - 48 + maxNum) % MOD;

        // 处理路径数量
        // 分别判断三个方向是否等于最大值，
        // 等于最大值就将g[]数组里的值累加到当前格
        if (maxNum == bottom && i != n - 1) {
          g[getIndex(i, j, n)] += g[getIndex(i + 1, j, n)];
          g[getIndex(i, j, n)] %= MOD;
        }
        if (maxNum == bottomRight && j != n - 1 && i != n - 1) {
          g[getIndex(i, j, n)] += g[getIndex(i + 1, j + 1, n)];
          g[getIndex(i, j, n)] %= MOD;
        }
        if (maxNum == right && j != n - 1) {
          g[getIndex(i, j, n)] += g[getIndex(i, j + 1, n)];
          g[getIndex(i, j, n)] %= MOD;
        }
      }
    }

    // 当路全部被障碍挡住时，f[][]数组的终点依然会有值，
    // 这时需要看g[]数组的值，对f[][]数组的值进行矫正
    // 因为g[]数组的0值会传播，当前格的三个方向的方案数都为0时，当前格也为0
    int[] res = new int[2];
    res[0] = f[0][0];
    res[1] = g[0];
    if (res[1] == 0) {
      res[0] = 0;
    }
    return res;
  }

  private int findMax(int bottom, int bottomRight, int right) {
    int temp = Math.max(bottom, bottomRight);
    temp = Math.max(temp, right);
    return temp;
  }

  int getIndex(int row, int col, int n) {
    return row * n + col;
  }
}

当然也可以处理存到 f[][] 数组的数据，存三个方向数据时判断是否和当前值一致，一致的话 g[][] 的值加 1；三个方向有比当前值大的时候，更新 f[][] 的值并重置 g[][] 的值为 1。

这样如果三个方向都被障碍拦住时，当前的值依然是非法值，而不是上面的 cs[i][j] - 48

• 时间复杂度：所有的操作均为 $ O( n^{2} ) $
• 空间复杂度：$ O( n^{2} ) $

四十五、在系统中查找重复文件

原题链接：

https://leetcode.cn/problems/find-duplicate-file-in-system/

这是力扣上的 【609. 在系统中查找重复文件】，难度为 普通

给你一个目录信息列表 paths ，包括目录路径，以及该目录中的所有文件及其内容，请你按路径返回文件系统中的所有重复文件。答案可按 任意顺序 返回。

一组重复的文件至少包括 两个 具有完全相同内容的文件。

输入 列表中的单个目录信息字符串的格式如下：

• "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

这意味着，在目录 root/d1/d2/.../dm 下，有 n 个文件 ( f1.txt, f2.txt ... fn.txt ) 的内容分别是 ( f1_content, f2_content ... fn_content ) 。

注意：n >= 1 且 m >= 0 。如果 m = 0 ，则表示该目录是根目录。

输出 是由 重复文件路径组 构成的列表。其中每个组由所有具有相同内容文件的文件路径组成。文件路径是具有下列格式的字符串：

• "directory_path/file_name.txt"

示例 1：

• 输入：paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
• 输出：[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

（1）Java代码

这道题一长串，其实就是 考验处理字符串。麻烦的是 Java 处理字符串没有很多方法。就只能一个个处理。

思路：题目要求找到文本内容相同的文件，文件内容（1）-> 文件（n），一对多关系，很明显使用哈希表 + 列表就比较简单。

这道题的难点：

1. 使用正则表达式处理字符串
2. 看明白题目要求。例如，只返回重复了的文件名，不是返回曾经出现过的文件名。

完整代码如下：

class Solution {
  public List<List<String>> findDuplicate(String[] paths) {
    // 新建存放结果的哈希表
    Map<String, List<String>> map = new HashMap<>();
    
    // 遍历数组的每一个元素，每个元素是一长串字符串
    for (int i = 0; i < paths.length; i++) {
      // 取出字符串
      String string = paths[i];
      // 取出文件名和文件内容
      String suffix = string.replaceFirst("^([^\\s]+ )", "");
      // 计算出文件路径的长度
      int prefixLength = string.length() - suffix.length();
      // 取出文件路径
      String prefix = string.substring(0, prefixLength);
      // 将一长串字符串分割成数组
      String[] fileNameArray = suffix.split(" ");
      
      // 遍历结果数组
      for (int j = 0; j < fileNameArray.length; j++) {
        // 取出数组中的每一个元素，元素内容包括每一个文件名和文件内容
        String index = fileNameArray[j];
        // 取出文件名
        String fileName = index.replaceFirst("\\(.*?\\)", "");
        // 取出文件内容
        String content = index.substring(fileName.length() + 1, index.length() - 1);
        // 如果第一次放入到哈希表，则新建一个列表
        if (!map.containsKey(content)) {
          map.put(content, new ArrayList<String>());
        }
        // 将拼接后的字符串加入到哈希表中的列表中
        map.get(content).add(prefix.substring(0, prefixLength - 1) + "/" + fileName);
      }
    }
    
    List<List<String>> res = new ArrayList<>();
    // 遍历哈希表中的内容 
    for (Map.Entry<String, List<String>> entry : map.entrySet()) {
      // 取出 key
      String key = entry.getKey();
      // 取出 value
      List<String> val = entry.getValue();
      // 只有列表的长度大于2，才是要的结果
      if (val.size() >= 2) {
        res.add(val);
      }
    }
    return res;
  }
}

（2）JS代码

在 Javascript 中，有很多操作字符串的方法，所以 Javascript 代码会比较简洁。

代码来自力扣题解：

https://leetcode.cn/problems/find-duplicate-file-in-system/solution/js-qing-jiao-wo-jsde-gong-ju-han-shu-xia-73gj/

var findDuplicate = function (paths) {
  // ans Array 存放最终结果 每一个元素是拥有相同内容的多个文件
  // map Object 存放文本的内容 [key-文本内容, value-map的下标]
  const map = {}, ans = [];
  
  for (const path of paths) {
    // ES6新语法
    // 将字符串以空格分开然后依次赋值到 root 和 files 变量
    // root为字符串，files为数组
    const [root, ...files] = path.split(' ');
    
    // 然后遍历files数组
    for (const file of files) {
      // 将字符串再以"("分隔
      // 例如，4.txt(efgh) 分割成 4.txt efgh)
      const [filename, content] = file.split('(');
      if (content in map) {	// 如果文本内容在map里，则直接往map放入数据
    		// 在map取出下标后，再去ans里取对应的数组
        ans[map[content]].push(`${root}/${filename}`);
      } else {	// 如果不在，则要将数据放入map里，用作之后的判断
        // push()方法会返回数组的长度
        // 长度-1 作为ans的下标
        map[content] = ans.push([`${root}/${filename}`]) - 1;
      }
    }
  }
  // 最后将长度大于2的数组返回
  return ans.filter(arr => arr.length > 1);
};

四十六、贴纸拼词

原题链接：

https://leetcode.cn/problems/stickers-to-spell-word/

这是 LeetCode 上的**【691. 贴纸拼词】**，难度为 Hard。

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。

注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。

示例 1：

• 输入： stickers = ["with","example","science"], target = "thehat"
• 输出：3
• 解释：我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。 把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。 此外，这是形成目标字符串所需的最小贴纸数量。

提示:

• n == stickers.length
• 1 <= n <= 50
• 1 <= stickers[i].length <= 10
• 1 <= target.length <= 15
• stickers[i] 和 target 由小写英文单词组成

（1）暴力解法

下面是暴力解法，使用递归，遍历每一个元素，但这是困难题，所以不可能使用暴力解法就能通过。提交结果为超时，所以需要进一步优化思路

class Solution {
  String[] s;

  int res = -1;

  public int minStickers(String[] stickers, String target) {
    int m = stickers.length;
    int n = target.length();
    s = stickers;

    dfs(0, target, 0);

    return res;

  }

  /**
     * 不断递归的方法
     * 先取第1个字符串，然后再继续取第1个字符串，
     * 如果这时剩余字符串没有改变，则改为取第2个字符串
     * @param count 当前的贴片数量
     * @param target 目标字符串
     * @param depth 记录当前遍历到元素的下标
     */
  private void dfs(int count, String target, int depth) {
		// 如果目标字符串为空，代表已经取完了
    if (target.equals("")) {
      if (res == -1) {	// 如果是第1次，则直接赋值
        res = count;
      } else {	// 否则就和之前值比较，取其中最小
				res = res < count ? res : count;
      }
      return;
    }
    
    // 如果遍历完全部字符串都不能凑出目标字符串，则直接退出
    if (depth >= s.length) {
      return;
    }

    // 存放变化的字符串
    String newString = target;
    // 存放上一次的字符串
    String temp = "";
    // int useCount = count;
    do {
      // 第1次先不选择当前索引的字符串，即不选择s[depth]
      dfs(count, newString, depth + 1);
      
      // 将目标字符串减取当前索引的字符
      temp = newString;
      newString = deleteChar(s[depth], newString);
      count++;
    } while (!newString.equals(temp));	
    // 如果新的字符串没有变化，则证明当前索引的字符串已经没有用了，
    // 需要开始使用下一个字符串了
  }

  /**
     * 将原字符串去掉另一个字符串所出现的所有字符，
     * 使用的是 replaceFirst() 方法
     * @param sub 需要在原字符串去掉的字符串
     * @param oldString 原字符串
     */
  public String deleteChar(String sub, String oldString) {
    String newString = oldString;
    for (int i = 0; i < sub.length(); i++) {
      String item = sub.charAt(i) + "";
      newString = newString.replaceFirst(item, "");
    }
    return newString;
  }
}

（2）动态规划-深度优先

深度遍历的优化思路，就是记忆化搜索，使用过之前遍历过的结果。

哪些结果可以被之后的计算所使用？

• 字符种数和字符类型
• 单字符种数不可重用。例如当前目标字符串剩余两种字符，但无法得知剩的是哪两种字符

下面思路来自评论区：https://leetcode.cn/problems/stickers-to-spell-word/solution/by-ac_oier-5vv3/1563033/

• 字符类型：使用目标字符串长度的二进制——state，来记录每一位的使用情况。
  • 初始化为 0 ，因为每一位都没有取到，每一位都为 0。
  • 最终状态为每一位为 1，即 2^target.lenth - 1
• 循环遍历：每一层递归的循环都会循环 stickers 的每一个字符串
  • 取出 stickers 的每一个字符串
    • 取出字符串的每一个字符
      • 取出 target 目标字符串的每一个字符
        • if (s[i] == t[j] && state & (1 << j) == 0) ：字符相等且当前位为 0，说明此时 t[j] 还未被凑出，并且 s[i] 能凑出 t[j]，那么 state 第 j 个位置变为1
        • 然后 break; ，因为每个字符只能取一次
    • 取出完当前字符串的每一个字符后，需要检查是否对目标字符串有贡献，如果有贡献，则进入下一层递归。没有则继续循环
  • 备忘录：当前循环结束的时候，记录当前的状态，实现目标字符串的最小使用字符串数。
    • 例如目标字符串是 “ a ”，如果有字符串有 “ a ” 字符，则存到备忘录的数据是 1，没有的话就直接退出方法。
    • 当目标字符串是 “ ?a”，遍历字符串中，如果只有字符 “ ? ” 被取到了，目标字符串只剩下字符 “ a ”，则需要看 “ a ” 的最小字符串，而这个已经存到备忘录里，则可以省去再遍历一次全部的字符串。

int n;

int[] memo;

/**
     * 方法一：dfs
     * 需要考虑的是，对于任意一张贴纸，使用当前贴纸后(假设每个字符都做出最大贡献)，能够得到什么样的字符串
     * 我们最终要得到target，所以我们可以 用 0 或 1 表示 target 每一位置上的字符是否已经凑出，因为 target 长度在 1-15 之间，
     * 所以我们可以用1个int变量state完成这件事，
     * 初始时：state = 0，每个字符都没凑出来
     * 如果能凑出 target，最终 state就是 2^(target.length)-1，也就是 target.length()个1，表示每个位置都被凑到了
     * 为了避免某些状态重复搜索，我们还需要一个memo数组来做备忘录，因为一共有 2^(target.length) 个状态（state取值为0-1<<len-1），所以数组大小为 1<< len
     *
     * 那么，假设当前状态为state，选择 某个 贴纸 sticker时，能得到什么样的新状态
     *
     * 遍历 sticker 的每个字符 s[i]
     *      遍历 target 的每个字符 t[j]
     *          if (s[i] == t[j] && state & (1 << j) == 0) 说明此时t[j]还未被凑出，并且s[i] 能凑出 t[j]，那么state第j个位置变为1
     *          break；s[i]对当前字符做出贡献后，就该考虑s[i+1]为哪个位置做贡献了，并且因为state已经更新，所以不会出现s[i+1]仍然为t[j]贡献的情况
     *                  这里不要先统计s每个字符出现次数，再统计t每个字符出现次数，又逐一比较，更新，这样是做不到明确target每个位置是否被凑出的，也就是得不到新的state
     * 因为每次可以选择任意一个贴纸，所以 遍历s前要准备一个 state的备份nstate，在遍历过程中使用的也是nstate
     * 并且，如果遍历完成后，nstate==state，说明当前贴纸对当前状态已再无贡献，直接换下一个贴纸
     * 否则·从当前状态 到 target 所需要的贴纸数 就是 1(使用当前贴纸) + dfs(nstate)
     *
     * 然后从多个选择的结果中选择结果最小的（所以，先给一个不可能的结果）
     *
     * 并且，当 state == 1<<n-1时，返回0
     *
     */
public int minStickers(String[] stickers, String target) {
  // 记录target长度
  n = target.length();
  // 备忘录，注意初始化大小
  memo = new int[1 << n];
  // 标记备忘录
  Arrays.fill(memo, -1);
  // 如果凑不出来target，返回的是个不可能的值，这里用 n + 1代替
  int ans = dfs(stickers, target, 0);
  return ans > n ? - 1: ans;
}

/**
     * dfs，当前状态是 state（二进制第j位为1代表target[j]已经凑出）
     * 返回从当前状态凑出target需要的最少贴纸数
     * @param stickers 可以使用的贴纸数组
     * @param target 目标字符串
     * @param state 当前状态
     * @return int 当前状态到达目标字符串的最小贴纸数
     */
private int dfs(String[] stickers, String target, int state) {
  // target每个字符全部凑出
  if (state == (1 << n) - 1) {
    return 0;
  }
  // 已计算过
  if (memo[state] != -1) {
    return memo[state];
  }
  // 可以选择任意一张贴纸，选择结果最小的选择，先给个不可能的值
  int ans = n + 1;
  // 任意选一张贴纸
  for (String sticker : stickers) {
    // 先做state的备份
    int nstate = state;
    // 考虑贴纸s每个字符能做出的贡献
    for (char c: sticker.toCharArray()) {
      for (int j = 0; j < n; ++j) {
        // 如果s[i]恰好能凑上t[j]（前提是t[j]还未被凑出，注意这里用的是nstate）
        if (c == target.charAt(j) && ((nstate >> j) & 1) == 0) {
          // 标记t[j]被凑出
          nstate |= (1 << j);
          // 考虑是[i+1]做贡献
          break;
        }
      }
    }
    // 的确做出了贡献
    if (nstate != state) {
      // 选择当前贴纸，完成整个过程所需要的最小贴纸数
      // 多个选择中选最优
      ans = Math.min(ans, 1 + dfs(stickers, target, nstate));
    }
  }
  // 更新备忘录并返回
  memo[state] = ans;
  return ans;
}

（3）动态规划-广度优先

这个思路是广度优先，每次都记录选择的贴纸。因为状态可能会重复，所以需要去重，则使用 Set 集合。

因为 Set 集合充当了备忘录的功能，记录每层的状态，所以不用再设置备忘录。

• queue ：队列
  • poll ：删除队列头的元素
  • offer ：将元素添加到队列位
• Set 的作用是在变化状态时，防止重复，因为上一层的状态是三种，但这层的状态不一定是三种，三种状态都可能同时转换为同一个状态
• 当凑出答案时，就可以直接返回函数，因为广度优先，最先催出的答案的层数（贴纸数）一定是最小的

/**
     * 思路不变，使用 bfs, 每次可以 选择任意一张贴纸。选择不同贴纸就会得到不同邻接状态
     * 按照 bfs 【齐头并进】特点，最先 达到 终极状态 (1<<n-1)时，返回 step(看作多叉树数层序遍历的话，对应最小的叶子节点层数)即可
     * @param stickers
     * @param target
     * @return
     */
public int minStickers2(String[] stickers, String target) {
  n = target.length();
  return bfs(stickers, target);
}

/**
     * bfs，当前状态是 state（二进制第j位为1代表target[j]已经凑出）
     * 
     * 每个节点 有 stickers.length 种邻接选项，选择不同贴纸，得到不同邻接状态
     *
     * @param stickers 可以使用的贴纸数组
     * @param target 目标字符串
     */
private int bfs(String[] stickers, String target) {
  int step = 0;
  Deque<Integer> queue = new ArrayDeque<>();
  // bfs不需要备忘录，但要避免节点重复访问
  Set<Integer> set = new HashSet<>();
  // 初始状态
  queue.offer(0);
  set.add(0);
  
  while (!queue.isEmpty()) {
    // 当前层 节点个数
    int sz = queue.size();
    // 逐个取出当前层节点，找到他们的邻接点，加入下一层队列
    // 每一轮都可以删除完当前层的状态
    for (int i = 0; i < sz; ++i) {
      Integer state = queue.poll();
      // 发现目标状态，返回 step
      if (state == (1 << n) - 1) {
        return step;
      }
      // 找寻全部邻接点
      // 任意选一张贴纸
      for (String sticker : stickers) {
        // 先做state的备份
        int nstate = state;
        
        // 考虑贴纸s每个字符能做出的贡献
        for (char c: sticker.toCharArray()) {
          for (int j = 0; j < n; ++j) {
            // 如果s[i]恰好能凑上t[j]（前提是t[j]还未被凑出，注意这里用的是nstate）
            if (c == target.charAt(j) && ((nstate >> j) & 1) == 0) {
              // 标记t[j]被凑出
              nstate |= (1 << j);
              // 考虑是[i+1]做贡献
              break;
            }
          }
        }
        
        // 的确做出了贡献 并且 邻接状态没访问过
        if (nstate != state && !set.contains(nstate)) {
          // 邻接状态入队列
          queue.offer(nstate);
          // 标记邻接状态已访问
          set.add(nstate);
        }
      }
    }
    // 齐头并进
    step++;
  }
  // 不在bfs过程中返回，就是无法凑出target
  return -1;
}

四十七、水果成篮

力扣链接：https://leetcode.cn/problems/fruit-into-baskets/

这是 LeetCode 上的**【904. 水果成篮】**，难度为 Normal。

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

• 输入：fruits = [1,2,1]
• 输出：3
• 解释：可以采摘全部 3 棵树。

示例 2：

• 输入：fruits = [0,1,2,2]
• 输出：3
• 解释：可以采摘 [1,2,2] 这三棵树。如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

提示：

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

（1）双指针滑动窗口

题目简意：求不超过两种字符类型的最大字符串长度

思路：当遇到第三种字符类型时，去除全部第一种类型的字符

去除第一种类型的字符，可以从右指针向左移动，一旦遇到第一种类型的字符，就停止移动

class Solution {
  public int totalFruit(int[] fruits) {
    // 初始化篮子，全部置为-1
    int[] basket = new int[2];
    Arrays.fill(basket, -1);
    
    int maxSize = 0;
    int n = fruits.length;

    // 左右指针
    int left = 0;
    int right = 0;

    // 将第1个水果装进篮子
    basket[0] = fruits[right];

    // 如何知道替换的是哪个
    // 不用知道更新哪个，直接全部更新
    while (right < n) {
      if (isInBasket(basket, fruits[right])) { // 如果在篮子里，只移动右指针
        maxSize = Math.max(right - left + 1, maxSize);
        right++;
      } else {	// 不在篮子里，移动右指针后移动左指针
        left = right - 1;
        basket[0] = fruits[left];
        
        // 左指针从右指针向左移动更方便
        while (left >= 1 && fruits[left - 1] == basket[0]) {
          left--;
        }

        // 更新最大值再移动指针
        maxSize = Math.max(right - left + 1, maxSize);
        basket[1] = fruits[right];
        right++;
      }
    }
    return maxSize;
  }

  public boolean isInBasket(int[] basket, int fruit) {
    for (int i = 0; i < basket.length; i++) {
      if (basket[i] == fruit) {
        return true;
      }
    }
    return false;
  }
}

四十八、1696. 跳跃游戏 VI

力扣链接：https://leetcode.cn/problems/jump-game-vi/

这是 LeetCode 上的**【1696. 跳跃游戏 VI】**，难度为 Normal。

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。

请你返回你能得到的 最大得分 。

示例 1：

• 输入：nums = [1, -1, -2, 4, -7, 3], k = 2
• 输出：7
• 解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。

示例 2：

• 输入：nums = [10, -5, -2, 4, 0, 3], k = 3
• 输出：17
• 解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。

提示：

• 1 <= nums.length, k <= 10⁵
• -10⁴ <= nums[i] <= 10⁴

（1）简单的动态规划

如果直接使用动态规划，记录每个格的得分，即从当前格出发 所得到的最大得分。然后在计算后面的格子时，先比较前面 k 个格子，然后找到 其中的最大值，表示要从这格跳到当前格，才会得到最大得分。

时间复杂度是 $k * (n-k)$

• 当 k 很小，n 很大，时间复杂度可以看成 $n$

• 当 k 中等，n 很大，可以看成 $k * {n/2}$ ，忽略常数可以看出 $k^2$ 。如果将 k 和 n 看成 10⁵ ，时间复杂度为 $10^5 * 10^4 = 10^9 $ 所以一定会超时

• 当 k 很大，n 很大，可以看出 $k$

class Solution {
  public int maxResult(int[] nums, int k) {
    int[] res = new int[nums.length];
    int n = nums.length;
    res[0] = nums[0];
    
		// 从第二格开始遍历
    for (int i = 1; i < n; i++) {
      int j = i - 1;
      int temp = res[j];
      // 往前找最大值
      while (j >= 0 && j >= i - k) {
        temp = Math.max(temp, res[j]);
        j--;
      }
      // 将结果记录到数组里
      res[i] = temp + nums[i];
    }
    return res[n - 1];
  }
}

（2）初步优化

在往前找最大值时，会发现我们大部分数字已经取到过，变动的数字只有开头和结尾——开头添加数字，结尾删除数字。所以中间的数就可以不用每次都去判断。

• 用最大值和添加的数字判断，如果比最大值大，则更新最大值
• 用最大值的 下标 和删除数字的 下标 判断，如果一致，就说明删除的是最大值，则需要再遍历窗口里的每个数字，来找到最大值

但其实总体上思路没有变，还是通过遍历找到最大值，只是优化了找最大值的时机。

（3）特性优化

我可以根据滑动窗口的机制来优化。下标和时机的关系

现在构造一个队列，队列里存放当前格的前 k 个数字，并要求按从大到小排序，但下标从小到大排序，和向右移动指针类似。

假设现在队列里有 [x, y, z] ，即 x > y > z，xIndex < yIndex < zIndex

现在加入了一个数 a，可知 aIndex > z，这时候需要将 a 插入到队列里。

• 假设 z > a，则直接放到 z 后面即可，因为这样队列还能满足之前的要求，然后移除第 1 个数
• 假设 z <= a，那要肯定要放到 z 的前面，这时 z 就 没有必要存到队列里了。因为在窗口向右移动的过程中，找的是其中的最大值，也就是队列里的第 1 个数。现在有一个 a，比 z 大，且下标比 zIndex 大，那么就说明 在 a 移除之前，z 不可能是最大值。这个是一个优化点。

拿着示例2做例子：

输入：nums = [10, -5, -2, 4, 0, 3], k = 3

k 的队列为 3，即队列长度最大为 3

• 添加 10，队列 [10]
• 添加 -5，队列 [10, -5]
• 添加 -2，队列 [10, -5, -2]
• 添加 4，队列满了移除 10，队列 [4]，跳到 4
• 添加 0，队列 [4, 0]
• 添加 3，队列 [4, 3] ，已到尽头，结束

下面为全部代码。需要注意几个点

1. 队列存放的是下标，因为存放数字无法和数组一一对应
2. 因为找 a 的位置时，移除了多个队列里的数字，所以需要 将队列里填满数字后，才开始移除第 1 个数字。换句话说就是，在右指针移到指定位置时，左指针才移动。

class Solution {
  public int maxResult(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n];

		// 初始化队列
    Deque<Integer> deque = new ArrayDeque<>();
    deque.addLast(0); 
    res[0] = nums[0];

    // 队列存放下标较简单，存放数值无法和数组对应上
    for (int i = 1; i < n; i++) {

      // 判断当前数字前面的最大值
      while (!deque.isEmpty() && res[deque.peekLast()] <= res[i - 1]) {
        deque.pollLast();
      }

      deque.addLast(i - 1);

      // 移除不是在范围里的数
      // 执行的时机：栈满的时候移除第1个
      // 且栈不满的时候不移除
      while (deque.peekFirst() < i - k) {
        deque.pollFirst();
      }

      // 记录当前结果
      res[i] = res[deque.peekFirst()] + nums[i];
    }
    return res[n - 1];
  }
}

（4）贪心优化

上面的思路都是固定 nums[] 数组里的一个数，然后向前找 res[] 里的最大值。

我们也可以固定 res[] 数组的一个数，然后向后面找 nums[] 数组里的最大值。

但依然需要剪枝，因为数字有大有小，只要找到比向后找

class Solution {
    public int maxResult(int[] nums, int k) {
        int length = nums.length;
        int[] dp = new int[length];
        dp[0] = nums[0];
        for (int i = 1; i < length; i++) {
            dp[i] = Integer.MIN_VALUE;
        }

        // i 左指针 j 右指针
        for (int i = 0; i < nums.length; i++) {

            // 更新dp[j]?
            for (int j = i + 1; j < length && j <= i + k; j++) {
                int nextNum = dp[i] + nums[j];
                if (nextNum > dp[j]) {
                    dp[j] = nextNum;
                }
                // 在外层循坏再操作
                // 后面也有大的？
                if (dp[j] >= dp[i]) {
                    break;
                }
            }
        }
        return dp[length - 1];
    }
}