算法五-8月28

hahg大约 28 分钟

算法五-8月28

三十七、统计所有可行路径

原题链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485297&idx=1&sn=5ee4ce31c42d368af0653f60aa263c82&chksm=fd9cac6ecaeb25787e6da90423c5467e1679da0a8aaf1a3445475199a8f148d8629e851fea57&cur_album_id=1715134171561410565&scene=189#wechat_redirect

给你一个互不相同的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量
每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|
请你返回从 start 到 finish 所有可能路径的数目。
由于答案可能很大，请将它对 10⁹ + 7 取余后返回
示例 1：
输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
输出：4
解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
1 -> 3 （3 -> 8）
1 -> 2 -> 3 （3 -> 6 -> 8 ）
1 -> 4 -> 3 （3 -> 4 -> 8 ）
1 -> 4 -> 2 -> 3 （3 -> 4 -> 6 -> 8 ）
提示：
2 <= locations.length <= 100
1 <= locations[i] <= 10⁹
所有 locations 中的整数互不相同
0 <= start, finish < locations.length
1 <= fuel <= 200

（1）思路

首先理解题意：给出起始城市和终点城市，然后给出一定的油量，计算出有几条路径。

前面几天的题目，本质上对应的模型其实是：特定「起点」，明确且有限的「移动方向」（转移状态），求解所有状态中的最优值。

但本题只是告诉了我们移动规则，没有告诉我们具体该如何移动。一定程度上，你可以将此类问题理解成另外一种【路径问题】。

这道题的数据范围也只有 10²，很多同学会想到 DFS。但是之前讲过，单纯的 DFS 由于是指数级别的复杂度，通常数据范围不出超过 30。不过，「记忆化搜索」可以符合题目的时间复杂度。

（2）找递归出口

我们知道，如果要实现 DFS 的话，通常有以下几个步骤：

设计好递归函数的「入参」和「出参」
设置好递归函数的出口（Base Case）
编写「最小单元」处理逻辑

【对于大多数的 DFS 来说，第 1 步和第 3 步都很好实现，而找 Base Case 通常是三部曲中最难的。】

以本题为例，我们来剖析一下「该如何找 Base Case」。

首先要明确，所谓的找 Base Case，其实是在确定什么样的情况下，算一次有效/无效。
- 对于本题，找 Base Case 其实就是在确定：什么样的情况下，算是 0 条路径；什么样的情况下，算是 1 条路径。
然后再在 DFS 过程中，不断的累加有效情况（算作路径数量为 1）的个数作为答案。
- 这是 DFS 的本质，也是找 Base Case 的思考过程。
- 回到本题，对于 有效情况 的确立，十分简单直接，如果我们当前所在的位置就是目的位置 且不能到任何一个地方 的话，那就算成是一条有效路径，我们可以对路径数量进行 +1。
那么如何确立 无效情况 呢？
- 一个直观的感觉是 当油量消耗完，所在位置又不在最终位置，那么就算走到头了，算是一次「无效情况」，可以终止递归。

逻辑上这没有错，但是存在油量始终无法为零的情况。

考虑以下样例数据：

locations = [0,2,2,2], start = 0, finish = 3, fuel = 1
我们当前位置在 0，想要到达 3，但是油量为 1，无法移动到任何位置。

因此还要增加一个限制条件：油量不为 0，但无法再移动到任何位置，且不在目的位置，也算是一次「无效情况」，可以终止递归。

（3）记忆化搜索

我们将使用缓存来记忆之前搜索过的路径。

缓存器的设计也十分简单，使用二维数组 cache[n][fuel+1] 进行记录即可。（fuel + 1 的长度是为了能取到 cache[x][fuel] ）
我们用 cache[i][fuel] 代表从位置 i 出发，当前剩余的油量为 fuel 的前提下，到达目标位置 的「路径数量」。
之所以能采取「缓存中间结果」这样的做法，是因为 在 i 和 fuel 确定的情况下，其到达目的地的路径数量是唯一确定的。因为目的位置不会动，当 i 和 fuel 也不动的话，那么所有条件都固定了，到达目的位置的路径数量也不会动
每次都使用到之前计算过的数据，就有点像之前几题的动态规划的思路了。

（4）代码分段实现

首先实现递归退出条件，退出条件也涉及到递归的最后一层，也就是条件最小范围的一层。只有最后一层设计正确，上面几层才能正确地滚雪球。

根据第（2）点知道了退出递归的条件：

最小逻辑的有效路径：
- 当前所在的位置就是目的地 且不能到任何一个地方
无效路径：
- 当油量消耗完，所在位置又不在最终位置
- 油量不为 0，但不能到任何一个地方，且不在目的位置。

有效和无效的第 2 点都需要遍历每一个地方，来确定不能到任何一个地方，所以将这两个情况写在一起。

start ：代表当前递归的起始位置
fuel ：当前递归所拥有的油量

boolean hasNext = false;
for (int i = 0; i < locations.length; i++) {
  // 排除掉当前格到当前格的情况
  if (i != start) {
    int need = Math.abs(locations[i] - locations[start]);	
    // 油量大于移动所需的量，则证明可以到达其他位置
    if (fuel >= need) {
      hasNext = true;
      break;
    }
  }
}

// 有效情况
if (!hasNext && start == end) {
  cache[start][fuel] = 1;
  return 1;
} else if (!hasNext && start != end) {
  // 无效情况
  return 0;
}
// 第15~20行可以简写成下面
// if (fuel != 0 && !hasNext) {
//  int a= cache[u][fuel] = u==end?1:0;
//  return a;
// }

无效的第 1 点很好写，直接判断即可。

if (fuel == 0 && start != end) {
  cache[start][fuel] = 0;
	return 0;
}

接着就需要写出 「最小单元」处理逻辑 ，也就是 如何处理最小单元的返回值。每次把路线加起来就行。

但代码注意几个地方：

sum 代表当前递归的路线总和。初始化的时候不单单只赋值 0，有时要赋值 1，例如当前为目的位置。如第 1 行所示。
sum 要对指定数字取余。如第 7 行所示。
- 为什么要对 10⁹ + 7 取余？（整型的取值范围为 -2147483648～2147483647 —— -2 * 10⁹～ 2 * 10⁹ ）
- 似乎是可以将较大的数变成较小的数。原理好像涉及到一些模运算的性质。待研究。
- 参考链接：
  - https://www.geeksforgeeks.org/modulo-1097-1000000007/
  - https://www.quora.com/What-exactly-is-print-it-modulo-10-9-+-7-in-competitive-programming-web-sites
在循环每个起始位置时，判断当前有的油量能不能到达指定位置，不能到达则可以不进入下一个递归。如第 5 行所示。
- 因为进入递归后返回的是 0，sum += 0 和不进入递归一样。
- 如果不想判断的话，需要改动无效的第 1 点，返回 0 的条件改为 fuel < 0 || (fuel == 0 && start != end)
最后需要将当前结果记录到缓存中。如第 12 行所示。

int sum = u == end ? 1 : 0;
for (int i = 0; i < locations.length; i++) {
	if (i != start) {
    int need = Math.abs(locations[i] - locations[start]); 
    if (fuel >= need) {
      sum += dfs(locations, i, end, fuel - need);
    	sum %= MOD;
    }
  }
}

cache[start][fuel] = sum;
return sum;

在上面的全部内容都是说明如何填充缓冲，现在需要使用缓冲。使用缓冲的条件是当前条件已经计算过了。

if (cache[start][fuel] != -1) {
	return cache[start][fuel];
}

这个可能有点抽象，在哪个地方会使用到缓冲，所以第（6）点运行一遍代码。

（5）全部代码

class Solution {
    int mod = 1000000007;
    
    // 缓存器：用于记录「特定状态」下的结果
    // cache[i][fuel] 代表从位置 i 出发，当前剩余的油量为 fuel 的前提下，到达目标位置的「路径数量」
    int[][] cache;
    
    public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
        
        // 初始化缓存器
        // 之所以要全部初始化为 -1
        // 是为了区分「某个状态下路径数量为 0」和「某个状态尚未没计算过」两种情况
        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        
        return dfs(ls, start, end, fuel);
    }
    
    /**
     * 计算「路径数量」
     * @param ls 入参 locations
     * @param u 当前所在位置（ls 的下标）
     * @param end 目标哦位置（ls 的下标）
     * @param fuel 剩余油量
     * @return 在位置 u 出发，油量为 fuel 的前提下，到达 end 的「路径数量」
     */
    int dfs(int[] ls, int u, int end, int fuel) {
        // 如果缓存器中已经有答案，直接返回
        if (cache[u][fuel] != -1) {
            return cache[u][fuel];
        }
        
        int n = ls.length;
        // base case 1：如果油量为 0，且不在目标位置
        // 将结果 0 写入缓存器并返回
        if (fuel == 0 && u != end) {
            cache[u][fuel] = 0;
            return 0;
        } 
        
        // base case 2：油量不为 0，且无法到达任何位置
        // 将结果 0 写入缓存器并返回
        boolean hasNext = false;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                int need = Math.abs(ls[u] - ls[i]);    
                if (fuel >= need) {
                    hasNext = true;
                    break;
                }
            }
        }
        if (fuel != 0 && !hasNext) {
            int a = cache[u][fuel] = u == end ? 1 : 0;
            return a;
        }
        
        // 计算油量为 fuel，从位置 u 到 end 的路径数量
        // 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
        int sum = u == end ? 1 : 0;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                int need = Math.abs(ls[i] - ls[u]);
                if (fuel >= need) {
                    sum += dfs(ls, i, end, fuel - need);
                    sum %= mod;
                }
            }
        }
        cache[u][fuel] = sum;
        return sum;
    }
}

时间复杂度：最坏情况下共有 n * fuel 个状态需要计算（填满整个 cache 数组）。每计算一个状态需要遍历一次 locations 数组，例如上面代码中的第 63 ~ 73 行，复杂度为 $O ( n )$ 。整体复杂度为 $O ( n^{2} fuel )$
空间复杂度： $O ( n^{2} fuel )$

（6）初步运行代码

以题目中的示例为例子，locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5，位置表示使用数组中的值

起始位置为 3，最终位置为 8。
首先遍历将每一个作为开始位置。
- 【3 -> 2】：剩余油量 4
- 【3 -> 6】：剩余油量 2
- 【3 -> 8】：剩余油量 0
- 【3 -> 4】：剩余油量 4
然后再深度遍历第 1 条路径【3 -> 2】，起点为 2，拥有油量 4
- 【2 -> 3】：剩余油量 3
  - 【3 -> 2】：剩余油量 2，在油耗尽之前无法到达，所以路径为 0
    - 【2 -> 3】：剩余油量 1，在油耗尽之前无法到达，所以路径为 0
      - 【3 -> 2】：剩余油量 0
      - 【3 -> 6】：油量不足
      - 【3 -> 8】：油量不足
      - 【3 -> 4】：剩余油量 0
    - 【2 -> 6】：油量不足
    - 【2 -> 8】：油量不足
    - 【2 -> 4】：剩余油量 0
  - 【3 -> 6】：剩余油量 0
  - 【3 -> 8】：油量不足
  - 【3 -> 4】：剩余油量 2，在油耗尽之前无法到达，所以路径为 0
    - 【4 -> 2】：剩余油量 0
    - 【4 -> 3】：剩余油量 1，由上面可知，从 3 开始，油量为 1，路径为 0
    - 【4 -> 6】：剩余油量 0
    - 【4 -> 8】：油量不足
- 【2 -> 6】：剩余油量 0
- 【2 -> 8】：油量不足
- 【2 -> 4】：剩余油量 2，路径为 0
  - 由上面可知，从 4 开始，油量为 2，路径为 0
由上可知，该递归了大半天，最后只能得出【3 -> 2】是不能走的路。那能不能进行剪枝，不用递归那么深就能知道结果呢？
- 答案是可以的，当走一步不能从起点到终点，那么走多步也不能到达终点。从日常生活可知，直线走多步和走一步，所走路程一致，如果不直线走，则走的路程会更多。
- 回到上面例子中，从 3 到达 2 的时候，油量剩余 4，而【2 -> 8】需要油量 6，就可知直接返回 0 了，不用再递归下去了。
那么代码该怎么写呢？放到代码中的哪个部分
- 前面代码部分是判断是否是有效还是无效条件，用于结束递归。
- 无效条件包括 油为 0 且不目的位置、油不为 0 且不能到任何位置
- 可以发现判断 一步是否能走到目的位置，也包括了两个无效条件：
  - 油为 0，当然无法一步到达目的位置
  - 不能到任何位置，当前也无法一步到达目的位置
- 所以直接将这两个无效条件删除替换成一步判断代码，如下所示第 10 ~ 14 行。

注：代码中 start 变量使用了 u 变量代替

int dfs(int[] ls, int u, int end, int fuel) {
  // 如果缓存中已经有答案，直接返回
  if (cache[u][fuel] != -1) {
    return cache[u][fuel];
  }

  // 如果一步到达不了，说明从位置 u 不能到达 end 位置
  // 将结果 0 写入缓存器并返回
  // 同时包含了两个无效条件
  int need = Math.abs(ls[u] - ls[end]);
  if (need > fuel) {
    cache[u][fuel] = 0;
    return 0;
  }

  int n = ls.length;
  // 计算油量为 fuel，从位置 u 到 end 的路径数量
  // 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
  int sum = u == end ? 1 : 0;
  for (int i = 0; i < n; i++) {
    if (i != u) {
      need = Math.abs(ls[i] - ls[u]);
      if (fuel >= need) {
        sum += dfs(ls, i, end, fuel - need);
        sum %= mod;
      }
    }
  }
  cache[u][fuel] = sum;
  return sum;
}

（7）动态规划思路

原文链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485319&idx=1&sn=95a3dc9c97ca57185de792ca70924afe&chksm=fd9cac98caeb258ebea466f59378670a90af1cb3015ae70922e1d04ac711a5b8d8d853ac5e7d&cur_album_id=1715134171561410565&scene=189#wechat_redirect

上面使用了递归算法，在上面的思路中，已经有了动态规划的模型，我们可以将其提取出来，使用之前的解法来实现。

cache 数组是我们要求的数据，最终答案为 cache[start][fuel]
递归的退出条件 就是作为动态规划的最小单元。
- 退出条件是油量最小的时候，所以动态规划就将油量从 0 开始遍历
向下递归的动作 就是动态规划的状态转移
- 向下递归的动作是把一个位置作为终点，然后再减取相应的油量
- 状态转移就是遍历当前所有能去的位置。用方程来写就是 cache[start][fuel] += cache[k][fuel - need] ，k 代表下一个位置。注意因为是取数组中的值，所以 fuel - need 不能为负数，如递归代码一样。

然后代码如下：

class Solution {
  int mod = 1000000007;
  public int countRoutes(int[] ls, int start, int end, int fuel) {
    int n = ls.length;

    // f[i][j] 代表从位置 i 出发，当前油量为 j 时，到达目的地的路径数
    int[][] f = new int[n][fuel + 1];

    // 对于本身位置就在目的地的状态，路径数为 1
    // 这里处理本身位置在目的地的情况，
    // 因为在下面遍历的时候需要排除起始位置是目的位置的情况
    for (int i = 0; i <= fuel; i++) f[end][i] = 1;
    
    // 从小到大枚举油量
    for (int cur = 0; cur <= fuel; cur++) {
      // 遍历起始位置
      for (int i = 0; i < n; i++) {
        // 遍历下一个的位置
        for (int k = 0; k < n; k++) {
          if (i != k) {
            int need = Math.abs(ls[i] - ls[k]);
            if (cur >= need) {
              f[i][cur] += f[k][cur-need];
              f[i][cur] %= mod;
            }
          }
        }
      }
    }
    return f[start][fuel];
  }
}

时间复杂度：在代码中，很明显有三层循环，复杂度分别为 n、n、fuel，所以整体复杂度为 $O ( n^{2} fuel )$
空间复杂度： $O ( n^{2} fuel )$

（8）总结

至此，我们只利用 DFS 的方法签名与主逻辑，就写出了「动态规划」解法。

我再帮你来总结一下这个过程：

从 DFS 方法签名出发。分析哪些入参是可变的，将其作为 DP 数组的维度，这道题 fuel 和起始位置可变，就作为了数组的两个维度。将返回值作为 DP 数组的存储值，这道题就是将每个递归的路径数量存储在数组里
**从 DFS 的主逻辑可以抽象中单个状态的计算方法。**这道题是以将 其余点作为终点 的思路提取出来

其中第一点对应了「动态规划」的「状态定义」，第二点对应了「动态规划」的「状态方程转移」。

三十八、设计哈希集合

原题链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485333&idx=1&sn=717ccedd7ad0c838e775332ef864cc27&chksm=fd9cac8acaeb259c04deedb940f73167aabb112efddd27a2b5c4f3b9646f0fcd3166e0d8f7ae&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「705. 设计哈希集合」**，难度为 Easy。
不使用任何内建的哈希表库设计一个哈希集合（HashSet）。
实现 MyHashSet 类：
void add(key) 向哈希集合中插入值 key
bool contains(key) 返回哈希集合中是否存在这个值 key
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做
提示：
0 <= key <= 10⁶
最多调用 104 次 add、remove 和 contains 。
进阶：你可以不使用内建的哈希集合库解决此问题吗？

（1）数组解法

因为 key 限制了是 int 类型，并且范围不超过 10⁶ ，再加上运行时间的限制，使用数组解法是比较容易通过的。

思路：开辟一个足够大的数组，然后将传来的数直接取下标，看是否存在。

class MyHashSet {
    boolean[] nodes = new boolean[1000009];
    
    public void add(int key) {
        nodes[key] = true;
    }
    
    public void remove(int key) {
        nodes[key] = false;
    }
    
    public boolean contains(int key) {
        return nodes[key];
    }
}

时间复杂度： $O ( 1 )$
空间复杂度： $O ( 1 )$

（2）链表数组解法

如果用普通的链表的话，时间复杂度会很高，所以就将链表和哈希结合，可以优化时间复杂度。

注：力扣运行普通链表耗时 242 ms，链表哈希结合 11 ms

链表和数组结合
- 储存方式：数组存放链表头节点。数组可以直接获取指定位置，链表用于解决哈希冲突，在同一格的话，就插入到链表里
- 计算哈希码的方式：数组长度可以不用太大，但一定要把 key 均匀地放到每个格上。详细代码如第 87 ~ 94 行。
- 增加：先根据 key 获取到数组的指定位置，再判断是否存在链表，如果不存在则新建链表，存在则添加到链表里。删除和判断是否存在也一样思路。

class MyHashSet {
  // 由于使用的是「链表」，这个值可以取得很小
  Node[] nodes = new Node[10009];

  public void add(int key) {
    // 根据 key 获取哈希桶的位置
    int idx = getIndex(key);
    
    Node loc = nodes[idx], tmp = loc;
    
		// 判断链表中是否已经存在
    if (loc != null) {
      Node prev = null;
      
      while (tmp != null) {
        // 如果存在则直接结束添加
        if (tmp.key == key) { 
          return;
        }
        // 不断地移动指针
        prev = tmp;
        tmp = tmp.next;
      }
      tmp = prev;
    }
    
    // 利用key新建一个节点
    Node node = new Node(key);

    // 头插法
    // 插入到头部
    // node.next = loc;
    // 更新数组
    // nodes[idx] = node;

    // 尾插法 
    // 如果tmp为null代表链表为空，则需要更新数组
    if (tmp != null) {
      tmp.next = node;
    } else {
      nodes[idx] = node;
    }
  }

  public void remove(int key) {
    int idx = getIndex(key);
    Node loc = nodes[idx];
    if (loc != null) {
      Node prev = null;
      while (loc != null) {
        if (loc.key == key) {
          if (prev != null) {
            prev.next = loc.next;
          } else {
            nodes[idx] = loc.next;
          }
          return;
        }
        prev = loc;
        loc = loc.next;
      }
    }
  }

  public boolean contains(int key) {
    int idx = getIndex(key);
    Node loc = nodes[idx];
    if (loc != null) {
      while (loc != null) {
        if (loc.key == key) {
          return true;
        }
        loc = loc.next;
      }
    }
    return false;
  }

  static class Node {
    private int key;
    private Node next;
    private Node(int key) {
      this.key = key;
    }
  }

  int getIndex(int key) {
    // 因为 nodes 的长度只有 10009，对应的十进制的 10011100011001（总长度为 32 位，其余高位都是 0）
    // 为了让 key 对应的 hash 高位也参与运算，这里对 hashCode 进行右移异或
    // 使得 hashCode 的高位随机性和低位随机性都能体现在低 16 位中
    int hash = Integer.hashCode(key);
    hash ^= (hash >>> 16);
    return hash % nodes.length;
  }
}

（3）分桶数组解法

分桶数组解法：

做法：将数组中的每个数字的每一位代表一个 key 值
原理：这样数组中的每个元素就代表了 32 个数，题目中 key 的范围为 10⁶ ，10⁶ / 32 = 31250，所以定义一个大于 31250 长度的数组就可以包含全部的数了。
- 在力扣中，三千多长度的数组的内存（48.8 MB）大于四千长度（46.6 MB），可能是虚拟机优化问题
好处：用数组找出大概位置，用位运算找出具体位置。数组取数和位运算取数都是很省时的操作。
- 增加运算：(1 << loc) —— 得到一个只有指定位为 1 其他位为 0 的数；bs[bucket] | (1 << loc) —— 使用或运算，不改变其他的位置的情况下，将指定位置的数改为 1
- 删除运算：~(1 << loc) ——得到一个只有指定位置为 0 其他位为 1 的数；bs[bucket] | (1 << loc) —— 使用与运算，不改变其他的位置的情况下，将指定位置的数改为 0
- 得到具体位置：(bs[bucket] >> loc) & 1 将最后一位变为指定位置，然后与运算 1 ，就可以得到指定位置的数字

class MyHashSet {
  int[] bs = new int[40000];
  
  public void add(int key) {
    // 获取桶下标
    int bucketIdx = key / 32;
    // 获取具体位数
    int bitIdx = key % 32;
    setVal(bucketIdx, bitIdx, true);
  }

  public void remove(int key) {
    int bucketIdx = key / 32;
    int bitIdx = key % 32;
    setVal(bucketIdx, bitIdx, false);
  }

  public boolean contains(int key) {
    int bucketIdx = key / 32;
    int bitIdx = key % 32;
    return getVal(bucketIdx, bitIdx);
  }

  /*
  * 改变相应位置
  * @param bucket 桶下标
  * @param loc 位下标
  * @param val 判断是增加还是删除
  */
  void setVal(int bucket, int loc, boolean val) {
    if (val) {
 			// 添加操作
      int u = bs[bucket] | (1 << loc);
      bs[bucket] = u;
    } else {
      // 删除操作
      int u = bs[bucket] & ~(1 << loc);
      bs[bucket] = u;
    }
  }

  boolean getVal(int bucket, int loc) {
    // 获取指定位置
    int u = (bs[bucket] >> loc) & 1;
    return u == 1;
  }
}

时间复杂度： $O ( 1 )$
空间复杂度： $O ( 1 )$

三十九、出界的路径数

原题链接：

https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485426&idx=1&sn=071aec0bf5bc2e20c58f4cbb3dcb0fbc&chksm=fd9cacedcaeb25fb895cb99963dcfcde6b10268893a085eed4000b48bf070cecbdf7c81bf991&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「576. 出界的路径数」**，难度为 Medium。
给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你最多可以移动 maxMove 次球。
给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余后的结果。
示例1：
输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出：6
解释：
移动一次：
 ——————————————————————————
|<---	 	↑		  |					   |
 --————————————————————————
|							|					   |
 --————————————————————————
移动两次：
 ————————————————————————
|  |	|     |					   |
 --|——|——————————————————
|	 ↲  ↆ    |					  |
 --——————————————————————
 
 ———————————————————————
|    -------|----↑----> |
 --—————————————————————
|	          |					  |
 --—————————————————————
提示：
1 <= m, n <= 50
0 <= maxMove <= 50
0 <= startRow < m
0 <= startColumn < n

（1）记忆化搜索

这道题和第三十七题思路一致，第三十七题是一维路径，这道题是二维路径。

开始找递归出口：

已经出界的情况则返回 1；
如果无法出界则返回 0，无法出界指剩余可走距离，直线向上下左右都无法出界；
已经计算过的数据直接返回。

递归向下条件：

向上下左右移动，剩余可走距离减一

缓冲数组：

三维数组，第一维和第二维代表位置，第三维代表剩余可走距离

class Solution {
  final int MOD = 1000000007;

  public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {

    // 可走距离在0~maxMove，所以数组要定义多一个位置
    int[][][] cache = new int[m][n][maxMove + 1];

    // 将第三维的数组全部置为-1
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        Arrays.fill(cache[i][j], -1);
      }
    }

    return dfs(cache, startRow, startColumn, maxMove);

  }

  private int dfs(int[][][] cache, int startRow, int startColumn, int maxMove) {
    int m = cache.length;
    int n = cache[0].length;

    // 如果已经出界则代表1个路径
    if (startColumn == -1 || startRow == -1 || startColumn == n || startRow == m) 
      return 1;
    // 如果已经计算过则直接返回
    else if (cache[startRow][startColumn][maxMove] != -1)
      return cache[startRow][startColumn][maxMove];

    // 如果上下左右都无法出界，即到达4条边的距离都大于剩余可走距离
    // 则返回0
    if (startRow >= maxMove && startColumn >= maxMove && m - startRow - 1 >= maxMove
        && n - startColumn - 1 >= maxMove) {
      cache[startRow][startColumn][maxMove] = 0;
      return 0;
    }

    // 下面开始递归计算路径数
    
    int sum = 0;
    // 向上
    sum += dfs(cache, startRow - 1, startColumn, maxMove - 1);
    sum %= MOD;
    // 向下
    sum += dfs(cache, startRow + 1, startColumn, maxMove - 1);
    sum %= MOD;
    // 向左
    sum += dfs(cache, startRow, startColumn - 1, maxMove - 1);
    sum %= MOD;
    // 向右
    sum += dfs(cache, startRow, startColumn + 1, maxMove - 1);
    sum %= MOD;
    // 将结果缓冲起来
    cache[startRow][startColumn][maxMove] = sum;
    return sum;
  }
}

时间复杂度：实际是填充三维数组，就像计算长方体的体积，长宽代表坐标，高代表剩余可走距离，所以总复杂度为： $O ( m \times n \times maxMove )$
空间复杂度： $O ( m \times n \times maxMove )$

（2）动态规划

上面使用了递归 + 记忆化搜索，这小节将其转换成动态规划。

状态转移：当前格的路径等于上下左右的路径相加

$f[(x,y)][step] = f[(x-1,y)][step-1] + f[(x+1,y)][step-1] f[(x,y-1)][step-1]f[(x,y+1)][step-1]$

存储数组：这里将三维数组变为二维数组，定义位置的二维变成了一维，这样就和第三十七题一致了。
初始化数据：动态规划需要初始数据来滚雪球，初始数据是递归中的 退出递归条件，即在边缘格的时候。
- 因为动态规划是在数组中计算，所以不会像递归一样超出数组范围。既然不能超出数组范围，那就剩余可走距离 从 1 开始遍历，不从 0 开始了。
- 如果剩余可走距离是 1，就可以知道 $f[(x,y)][1]$ 的内容，在角落的路径为 2，在边的路径为 1，中间的路径为 0，例如下面表格

2	1	1	2
1	0	0	1
2	1	1	2

全部代码如下：

class Solution {
  int mod = (int)1e9+7;
  int m, n, N;
  // int m, int n, int maxMove, int startRow, int startColumn
  public int findPaths(int _m, int _n, int _N, int _i, int _j) {
    m = _m; n = _n; N = _N;

    // f[i][j] 代表从 idx 为 i 的位置出发，移动步数不超过 j 的路径数量
    int[][] f = new int[m * n][N + 1];

    // 初始化边缘格子的路径数量
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        // 初始化第1行
        if (i == 0) add(i, j, f);
        // 初始化最后1行
        if (i == m - 1) add(i, j, f);
        // 初始化第1列
        if (j == 0) add(i, j, f);
        // 初始化最后1列
        if (j == n - 1) add(i, j, f);
      }
    }

    // 定义可移动的四个方向
    // 便于使用循环来遍历四个方向
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};

    // 从1开始枚举「可移动步数」
    for (int step = 1; step <= N; step++) {
      // 枚举所有的「位置」
      for (int k = 0; k < m * n; k++) {
        // 将一维位置转为二维位置
        int x = parseIdx(k)[0], y = parseIdx(k)[1];
        // 遍历四个方向
        for (int[] d : dirs) {
          // 计算出四个方向的x和y
          int nx = x + d[0], ny = y + d[1];
          // 如果位置有「相邻格子」，则「相邻格子」参与状态转移
          if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
            f[k][step] += f[getIndex(nx, ny)][step - 1];
            f[k][step] %= mod;
          }
        }
      }
    }

    // 最终结果为从起始点触发，最大移动步数不超 N 的路径数量
    return f[getIndex(_i, _j)][N];
  }

  // 为每个「边缘」格子，添加一条路径
  void add(int x, int y, int[][] f) {
    int idx = getIndex(x, y);
    for (int step = 1; step <= N; step++) {
      f[idx][step]++;
    }
  }

  // 将 (x, y) 转换为 index
  int getIndex(int x, int y) {
    return x * n + y;
  }

  // 将 index 解析回 (x, y)
  int[] parseIdx(int idx) {
    return new int[]{idx / n, idx % n};
  }
}

时间复杂度：两层循环的复杂度分别为 maxMove、m * n，所以总复杂度为： $O ( m \times n \times maxMove )$
空间复杂度： $O ( m \times n \times maxMove )$

四十、设计哈希映射

原题链接：

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

这是 LeetCode 上的**「706. 设计哈希映射」**，难度为 Easy。
不使用任何内建的哈希表库设计一个哈希映射（HashMap）。
实现 MyHashMap 类：
MyHashMap() 用空映射初始化对象
void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。
提示：
0 <= key, value <= 10⁶
最多调用 10⁴ 次 put、get 和 remove 方法
进阶：你能否不使用内置的 HashMap 库解决此问题？

（1）数组解法

和第三十八题一致，因为限制了 key 和 value 的范围，所以可以用数组让 key 直接定位到位置。key 作为下标，value 为数组中的数据，第三十八题数组中的数据是布尔值，没什么价值。

定义没有数据，可以使用整型的最大值或者 -1，下面代码使用的是整型的最大值

class MyHashMap {
  int INF = Integer.MAX_VALUE;
  int N = 1000009;
  int[] map = new int[N];
  
  public MyHashMap() {
    // 初始化数组中的全部格
    Arrays.fill(map, INF);
  }

  public void put(int key, int value) {
    // 因为是覆盖放入，所以不用判断之前是否存在
    map[key] = value;
  }

  public int get(int key) {
    // 如果是最大值则返回-1
    return map[key] == INF ? -1 : map[key];
  }

  public void remove(int key) {
    // 将数据重新赋值整型的最大值
    map[key] = INF;
  }
}

时间复杂度： $O(1)$
空间复杂度： $O(1)$

（2）链表数组法

链表数组法大致的代码与第三十八题的一致，都是计算哈希值，直接定位数组中的内容，然后看是否已经存在链表。

class MyHashMap {
  static class Node {
    int key, value;
    Node next;
    Node(int _key, int _value) {
      key = _key;
      value = _value;
    }
  }

  // 由于使用的是「链表」，这个值可以取得很小
  Node[] nodes = new Node[10009];

  public void put(int key, int value) {
    // 根据 key 获取哈希桶的位置
    int idx = getIndex(key);
    // 判断链表中是否已经存在
    Node loc = nodes[idx], tmp = loc;
    if (loc != null) {
      Node prev = null;
      while (tmp != null) {
        if (tmp.key == key) { 
          tmp.value = value;
          return;
        }
        prev = tmp;
        tmp = tmp.next;
      }
      tmp = prev;
    }
    Node node = new Node(key, value);

    // 头插法
    // node.next = loc;
    // nodes[idx] = node;

    // 尾插法 
    if (tmp != null) {
      tmp.next = node;
    } else {
      nodes[idx] = node;
    }
  }

  public void remove(int key) {
    int idx = getIndex(key);
    Node loc = nodes[idx];
    if (loc != null) {
      Node prev = null;
      while (loc != null) {
        if (loc.key == key) {
          if (prev != null) {
            prev.next = loc.next;
          } else {
            nodes[idx] = loc.next;
          }
          return;
        }
        prev = loc;
        loc = loc.next;
      }
    }
  }

  public int get(int key) {
    int idx = getIndex(key);
    Node loc = nodes[idx];
    if (loc != null) {
      while (loc != null) {
        if (loc.key == key) {
          return loc.value;
        }
        loc = loc.next;
      }
    }
    return -1;
  }

  int getIndex(int key) {
    // 因为 nodes 的长度只有 10009，对应的十进制的 10011100011001（总长度为 32 位，其余高位都是 0）
    // 为了让 key 对应的 hash 高位也参与运算，这里对 hashCode 进行右移异或
    // 使得 hashCode 的高位随机性和低位随机性都能体现在低 16 位中
    int hash = Integer.hashCode(key);
    hash ^= (hash >>> 16);
    return hash % nodes.length;
  }
}

时间复杂度：由于没有扩容的逻辑，最坏情况下复杂度为 $O( n )$ ，因为如果一直定位到数组的同一个位置就退出成单纯的链表。一般情况下复杂度为 $O( 1 )$
空间复杂度： $O( 1 )$

（3）开放寻址解法

解决哈希冲突除了建立链表之外，还可以偏移哈希值。如果当前下标已经存在数据，则向右偏移一格，再继续判断是否存在数据。因为最多操作 10⁴ 次，所以 Node 数组大于 10⁴ 即可。

class MyHashMap {
  static class Node {
    int key, value;
    Node next;
    boolean isDeleted;
    Node(int _key, int _value) {
      key = _key;
      value = _value;
    }
  }

  // 冲突时的偏移量
  int OFFSET = 1;
  Node[] nodes = new Node[10009];

  public void put(int key, int value) {
    // 获取到存储的下标
    int idx = getIndex(key);
    Node node = nodes[idx];
    
    // 如果不为空，则直接覆盖
    if (node != null) {
      node.value = value;
      node.isDeleted = false;
    } else {
      // 为空则新建个Node对象
      node = new Node(key, value);
      nodes[idx] = node;
    }
  }

  public void remove(int key) {
    Node node = nodes[getIndex(key)];
    // 将删除的标志位置为true，这样就不会频繁地新建对象和回收对象
    if (node != null) node.isDeleted = true;
  }

  public int get(int key) {
    Node node = nodes[getIndex(key)];
    if (node == null) return -1;
    return node.isDeleted ? -1 : node.value;
  }

  // 当 map 中没有 key 的时候，getIndex 总是返回一个空位置
  // 当 map 中包含 key 的时候，getIndex 总是返回 key 所在的位置
  int getIndex(int key) {
    int hash = Integer.hashCode(key);
    hash ^= (hash >>> 16);
    int n = nodes.length;
    int idx = hash % n;
    // 退出的条件：node为空，node的key等于需要找的key
    // 继续循环的条件：在哈希冲突的情况下，继续寻找需要的key
    // 删除操作没有将数据置为null，遍历次数就会增多
    while (nodes[idx] != null && nodes[idx].key != key) {
      // 进行偏移
      hash += OFFSET;
      // 防止数组越界
      idx = hash % n;
    }
    return idx;
  }
}

时间复杂度：一般情况下复杂度为 $O( 1 )$ ，极端情况下为 $O( n )$ ，因为如果哈希冲突严重的话，就需要遍历整个数组才可以找到空位
空间复杂度： $O( 1 )$