172. 阶乘后的零

题目　　

给定一个整数 $n$ ，返回 $n!$ 结果中尾随零的数量。

提示：$0 \leq n \leq 10^4$

思路

阶乘运算的运算量非常大且非常容易溢出，这里 $n$ 最大值可以取到 $10^4$，说明需要用数学的方法来解决这个问题。
要求 $n!$ 尾零的数量，就要求 $n!$ 中因子 $10$ 的个数，而 $10 = 2\times 5$，因此转换成求 $n!$ 中质因子 $2$ 的个数和质因子 $5$ 的个数的较小值。
由于质因子 $5$ 的个数不会大于质因子 $2$ 的个数，所以只要乘数贡献出一个 $5$，尾部就会多一个 $0$，所以就需要求出 $n$ 及小于它的所有正整数能够贡献的质因子 $5$ 的数量。
那么对于 $n$，只需要求出：

对于这个值，我们可以用一个递归方法完成，即可得到最终的答案。

class Solution {
    public int trailingZeroes(int n) {
        return f(n);
    }
    private int f(int n){
        if(n==0) return 0;
        return n/5 + f(n/5);
    }
}

793. 阶乘函数后 K 个零

题目

$f(x)$ 是 $x!$ 末尾是 $0$ 的数量。
例如， $f(3) = 0$，因为 $3! = 6$ 的末尾没有 $0$ ；而 $f(11) = 2$ ，因为 $11!= 39916800$ 末端有 $2$ 个 $0$ 。 给定 $k$，找出返回能满足 $f(x) = k$ 的非负整数 $x$ 的数量。

提示：$0 \leq k \leq 10^9$

思路

与上一题相似，不过这次我们需要求出结尾为 $k$ 个 $0$ 的所有数字的数量。

方法一

记 $n_{x}$ 表示 $x!$ 末尾零的个数不小于 $x$ 的最小数，那么题目等价于求解 $n_{k + 1} - n_k$。
接下来就可以通过二分查找找到 $n_{k + 1}$ 和 $n_k$。左边界设为 $0$，由于我们需要的 $x!$ 末尾 $0$ 的个数即 $\Sigma_{k=1}^{\infty} \lfloor \frac{x}{5^{k}} \rfloor \geq \lfloor \frac{x}{5} \rfloor$，所以 $\Sigma_{k=1}^{\infty} \lfloor \frac{5x}{5^{k}} \rfloor \geq x$，则可以将右边界设为 $5x$，另外这里由于 $k$ 的最大值取到了 $10^9$，$5x$ 若为 int 类型则会越界，需要我们转为 long 类型。

class Solution {
    private int nx(int x){
        long l = 0, r = 5*x;
        while(l<=r){
            long mid = (l+r)/2;
            if(f(mid)<x) l = mid+1;
            else r = mid-1;
        }
        return (int) l;
    }
    public int preimageSizeFZF(int k) {
        return nx(k+1) - nx(k);
    }
    private long f(long x){
        if(x==0) return 0;
        return x/5 + f(x/5);
    }
}

方法二

可以很容易的得到，$x$ 的值不是 $0$ 就是 $5$，所以我们只需要在二分阶段找到了 $k$ 即可返回 $5$，否则返回 $0$。

class Solution {
    private boolean exists(long x){
        long l = 0, r = 5*x;
        
        while(l<=r){
            long mid = (l+r)/2;
            if(f(mid)<x) l = mid+1;
            else if(f(mid)>x) r=mid-1;
            else return true;
        }
        return false;
    }
    public int preimageSizeFZF(int k) {
        return exists(k)?5:0;
    }
    private long f(long x){
        if(x==0) return 0;
        return x/5 + f(x/5);
    }
}

300. 最长递增子序列

题目　　

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

思路

方法一：动态规划

$dp[i]$ 记录到第 $i$ 个为止（包括第 $i$ 个在内）的最长递增子序列的长度，可以得到转换方程：

最后返回 dp 中的最大值即可。

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

方法二：贪心 + 二分查找

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组 $d[i]$，表示长度为 $i$ 的最长上升子序列的末尾元素的最小值，用 $len$ 记录目前最长上升子序列的长度，起始时 $len$ 为 $1$，$d[1] = \textit{nums}[0]$。

$d[i]$ 是关于 $i$ 单调递增的。我们依次遍历数组 $\textit{nums}$ 中的每个元素，并更新数组 $d$ 和 $len$ 的值。如果 $\textit{nums}[i] > d[\textit{len}]$ 则更新 $len = len + 1$，否则在 $d[1 \ldots len]$ 中找满足 $d[i - 1] < \textit{nums}[j] < d[i]$ 的下标 $i$，并更新 $d[i] = \textit{nums}[j]$。

以输入序列 [0, 8, 4, 12, 2, 3] 为例：

• 第一步插入 0， d = [0]；
• 第二步插入 8， d = [0, 8]；
• 第三步插入 4， d = [0, 4]；
• 第四步插入 12，d = [0, 4, 12]；
• 第五步插入 2， d = [0, 2, 12]。
• 第六步插入 3， d = [0, 2, 3]。

因为我们只需要获取最后的长度，所以可以采用这种方法。每次如果是插入能够使长度变长的数，一定在最后面新增，否则维护前面潜在的更长子序列。注意这里 $d$ 存放的并不是最后的最长子序列，而是走到当前遍历的数字式，长度为 $i$ 所存放的最小数是多少，同样遍历到这个数字，子序列长度同样为 $i$，我们希望最后一个数字越小越好。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = 1, n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] d = new int[n + 1];
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
}

435. 无重叠区间

题目　　

给定一个区间的集合 intervals ，其中 $intervals[i] = [start_i, end_i]$ 。返回需要移除区间的最小数量，使剩余区间互不重叠。

提示:

• $1 \leq intervals.length \leq 10^5$
• $intervals[i].length == 2$
• $-5 * 10^4 \leq starti < endi \leq 5 * 10^4$

思路

方法一：动态规划

这个题目等价于「选出最多数量的区间，使得它们互不重叠」。首先将数组排序，则可以利用到之前的结果。我们按数字对的第一个数字从小到大排序，到第 $i$ 个数字对能够选出最多的区间数量记为 $f_i$，数字对第一个数记为 $l_i$，第二个数字记为 $r_i$，则 $f_i$ 就等于排好序的数组中，在第 $i$ 个前面且数字对第二个数字小于等于第 $i$ 个数字对第一个数字的最大值加一，即可得到转换方程：

最后我们取 $l_i$ 最大中的 $r_i$ 最大的 $f_i$ 即可。我们可以在排序中，分别按照两个数字递增的条件排序，也可以最后取所有 $f_i$ 的最大值。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0] == 0? o1[1]-o2[1]:o1[0] - o2[0];
            }
        });

        int len = intervals.length;
        int[] f= new int[len];
        Arrays.fill(f,1);
        for(int i = 1;i<len;i++){
            for(int j = 0;j<i;j++){
                if(intervals[j][1]<=intervals[i][0]) f[i] = Math.max(f[j]+1, f[i]);
            }
        }

        return len - f[len-1];
    }
}

这么做的问题是在最后几个用例会超时。

方法二： 贪心

我们不妨想一想应该选择哪一个区间作为首个区间。

假设在某一种最优的选择方法中，$[l_k, r_k]$ 是首个（即最左侧的）区间，那么它的左侧没有其它区间，右侧有若干个不重叠的区间。设想一下，如果此时存在一个区间 $[l_j, r_j]$，使得 $r_j < r_k$，即区间 $j$ 的右端点在区间 $k$ 的左侧，那么我们将区间 $k$ 替换为区间 $j$，其与剩余右侧被选择的区间仍然是不重叠的。而当我们将区间 $k$ 替换为区间 $j$ 后，就得到了另一种 最优的 选择方法。

我们可以不断地寻找右端点在首个区间右端点左侧的新区间，将首个区间替换成该区间。那么当我们无法替换时，首个区间就是所有可以选择的区间中右端点最小的那个区间。因此我们将所有区间按照右端点从小到大进行排序，那么排完序之后的首个区间，就是我们选择的首个区间。

如果有多个区间的右端点都同样最小怎么办？由于我们选择的是首个区间，因此在左侧不会有其它的区间，那么左端点在处是不重要的，我们只要任意选择一个右端点最小的区间即可。

当确定了首个区间之后，所有与首个区间不重合的区间就组成了一个规模更小的子问题。由于我们已经在初始时将所有区间按照右端点排好序了，因此对于这个子问题，我们无需再次进行排序，只要找出其中与首个区间不重合并且右端点最小的区间即可。用相同的方法，我们可以依次确定后续的所有区间。

在实际的代码编写中，我们对按照右端点排好序的区间进行遍历，并且实时维护上一个选择区间的右端点 $\textit{right}$。如果当前遍历到的区间 $[l_i, r_i]$ 与上一个区间不重合，即 $l_i \geq \textit{right}$，那么我们就可以贪心地选择这个区间，并将 $\textit{right}$ 更新为 $r_i$。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];
            }
        });

        int n = intervals.length;
        int right = intervals[0][1];
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] >= right) {
                ++ans;
                right = intervals[i][1];
            }
        }
        return n - ans;
    }
}

856. 括号的分数

题目

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。

思路

方法一：分治

根据题意，一个平衡括号字符串 s 可以被分解为 A+B 或 (A) 的形式，因此我们可以对 s 进行分解，分而治之。

如何判断 s 应该分解为 A+B 或 (A) 的哪一种呢？我们将左括号记为 1，右括号记为 −1，如果 s 的某个非空前缀对应的和 bal=0，那么这个前缀就是一个平衡括号字符串。如果该前缀长度等于 s 的长度，那么 s 可以分解为 (A) 的形式；否则 s 可以分解为 A + B 的形式，其中 A 为该前缀。将 s 分解之后，我们递归地求解子问题，并且 s 的长度为 2 时，分数为 $1$。

public int scoreOfParentheses(String s) {
    if(s.length() == 2) return 1; // ()
    int bal = 0;
    char[] chars = s.toCharArray();
    int i = 0;
    for(; i < chars.length; i++){
        char c = chars[i];
        bal += (c == '(' ? 1: -1);
        if(bal == 0) break;
    }
    if(i == s.length() - 1){
        return 2 * scoreOfParentheses(s.substring(1, s.length() - 1));
    }else{
        return scoreOfParentheses(s.substring(0, i + 1)) + scoreOfParentheses(s.substring(i + 1));
    }
}

方法二：栈

我们可以将 (A) 视为一个 $0$ 和 (A) 相连的得分，那么同一深度下多个项相连时，我们每次将前两项的得分压缩，作为后一项的前项，便可以利用栈解决问题。

遇到 ( 时，压入 0，并计算该括号内部得分；
遇到 ) 时，说明内部得分计算完毕，从栈顶取得内部得分，与前项得分压缩后重新放入栈中。

当字符串扫描完成后，取栈顶元素即可。

class Solution {
    public int scoreOfParentheses(String s) {
        Deque<Integer> st = new ArrayDeque<Integer>();
        st.push(0);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.push(0);
            } else {
                int v = st.pop();
                int top = st.pop() + Math.max(2 * v, 1);
                st.push(top);
            }
        }
        return st.peek();
    }
}

886. 可能的二分法

题目　　

给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。

给定整数 n 和数组 dislikes，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi 的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

提示： $1 \leq n \leq 2000$
$0 \leq dislikes.length \leq 104$
$dislikes[i].length == 2$
$1 \leq dislikes[i][j] \leq n$
$ai < bi$
$dislikes$ 中每一组都 不同

思路

这是一道经典的 二分图染色 模板题，以下放出 dfs 模板。

class Solution {
    int NODE_NUM = 2010;            // todo 点数
    int EDGE_NUM = 10010 * 2;       // todo 边数
    int index;
    int[] end = new int[EDGE_NUM];
    int[] lastEdgeFinder = new int[EDGE_NUM];
    int[] finder4Node = new int[NODE_NUM];
    int[] color = new int[NODE_NUM];// 0 未染色    1 色一    2 色2    3-color 另一种颜色

    private void addEdge(int s, int e){
        end[index] = e;                         // 记录这一次的终点             e 记录对应以 a 为起点的边的终点
        lastEdgeFinder[index] = finder4Node[s]; // 记录上一次的 index    通过上一条以 a 为起点的边的索引，可以找到以 a 为起点的另一条边的索引（直至 -1 ）
        finder4Node[s] = index++;               // 记录这一次的index       通过起点 a 能够拿到最后一个以 a 为起点的边的索引
    }

    private boolean dfs(int curr, int color2Paint){
        color[curr] = color2Paint;
        int i = finder4Node[curr];
        while(i != -1){
            int e = end[i];
            if(color[e] == color2Paint){    // 同色，肯定不行，返回false
                return false;
            }
            if(color[e] == 0 && !dfs(e, 3 - color2Paint)){  // 未被染色，尝试染不同的颜色
                return false;
            }
            i = lastEdgeFinder[i];
        }
        return true;
    }


    public boolean possibleBipartition(int n, int[][] dislikes) {
        // init
        Arrays.fill(finder4Node, -1);
        for(int[] dislike: dislikes){
            int a = dislike[0], b = dislike[1];
            addEdge(a, b); addEdge(b, a);
        }
        // todo 编号从 1 开始
        for(int i = 1; i <= n; i++){
            if(color[i] != 0){          // 已被染色，判定过没有冲突
                continue;
            }
            if(!dfs(i, 1)){   // 第一个染成色一，只要和 1 以及 以 1 为起点的边的终点及其所有有关的点都会在深搜中完成染色
                return false;
            }
        }
        return true;
    }
}

864. 获取所有钥匙的最短路径

题目

给定一个二维网格 grid ，其中：

• '.' 代表一个空房间
• '#' 代表一堵
• '@' 是起点
• 小写字母代表钥匙
• 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 $k$ 为 钥匙/锁 的个数，且满足 $1 \leq k \leq 6$，字母表中的前 $k$ 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 30
• grid[i][j] 只含有 '.', '#', '@', 'a'-'f' 以及*  'A'-'F'
• 钥匙的数目范围是 [1, 6] 
• 每个钥匙都对应一个 不同 的字母
• 每个钥匙正好打开一个对应的锁

思路：状态压缩 + 广度优先搜索

这种探路的题，好像很多都是使用 状态压缩 + 广度优先搜索 来解决，利用一个队列广度优先搜索，每一层能到的位置全部判断完再判断下一层，所以找到的一定是最短路径，再确定一个在最短路径上不会出现的状态对 BFS 进行剪枝，就能解决问题。

如果给定一个只包含空房间、墙、起点和终点的二维网格，我们可以使用广度优先搜索的方法求出起点到终点的最短路径。这是因为在最短路径上，我们最多只会经过每个房间一次。因此到访过的房间可以不再访问。
如果加上了钥匙和锁，类似地，在最短路径上也不可能存在如下的情况：我们经过了某个房间两次，并且这两次我们拥有钥匙的情况是完全一致的。 这就是我们要找的状态压缩，利用最短路径上不会重复出现的状态进行剪枝。

所以，在这个题目中，我们需要对持有🔑的状态进行保存，这里有一个非常关键的提示：$k$ 为 钥匙/锁 的个数，且满足 $1 \leq k \leq 6$。这里就很明显的在暗示我们可以使用掩码来记录状态。

class Solution {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int sx = 0, sy = 0;

        // 构建 map 存放钥匙字母和对应的编号
        Map<Character, Integer> keyToIndex = new HashMap<Character, Integer>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i].charAt(j) == '@') {
                    sx = i;
                    sy = j;
                } else if (Character.isLowerCase(grid[i].charAt(j))) {
                    if (!keyToIndex.containsKey(grid[i].charAt(j))) {
                        int idx = keyToIndex.size();
                        keyToIndex.put(grid[i].charAt(j), idx);
                    }
                }
            }
        }

        // BFS
        // dist[m][n][k]存放以状态 k 到位置 (m, n) 时的步数，-1表示未涉足
        Queue<int[]> queue = new ArrayDeque<int[]>();
        int[][][] dist = new int[m][n][1 << keyToIndex.size()];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                Arrays.fill(dist[i][j], -1);
            }
        }
        queue.offer(new int[]{sx, sy, 0});
        dist[sx][sy][0] = 0;
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int x = arr[0], y = arr[1], mask = arr[2];
            for (int i = 0; i < 4; ++i) {   // 三个方向
                int nx = x + dirs[i][0];
                int ny = y + dirs[i][1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx].charAt(ny) != '#') {
                    // 新的位置能走（不是边缘不是墙）
                    if (grid[nx].charAt(ny) == '.' || grid[nx].charAt(ny) == '@') {
                        if (dist[nx][ny][mask] == -1) {
                            // 空白或起点 且没有以这个状态走过
                            dist[nx][ny][mask] = dist[x][y][mask] + 1;
                            queue.offer(new int[]{nx, ny, mask});
                        }
                    } else if (Character.isLowerCase(grid[nx].charAt(ny))) {
                        // 新的位置是钥匙
                        int idx = keyToIndex.get(grid[nx].charAt(ny));
                        if (dist[nx][ny][mask | (1 << idx)] == -1) { // 测试是否以这个状态走过
                            dist[nx][ny][mask | (1 << idx)] = dist[x][y][mask] + 1;
                            if ((mask | (1 << idx)) == (1 << keyToIndex.size()) - 1) {
                                // 如果拿到所有钥匙
                                return dist[nx][ny][mask | (1 << idx)];
                            }
                            queue.offer(new int[]{nx, ny, mask | (1 << idx)});
                        }
                    } else {
                        // 是锁
                        int idx = keyToIndex.get(Character.toLowerCase(grid[nx].charAt(ny)));
                        if ((mask & (1 << idx)) != 0 && dist[nx][ny][mask] == -1) {
                            // 有对应钥匙 且 没有以这个状态走过
                            dist[nx][ny][mask] = dist[x][y][mask] + 1;
                            queue.offer(new int[]{nx, ny, mask});
                        }
                    }
                }
            }
        }
        return -1;
    }