[数据结构与算法]LeetCode精选TOP面试题（中等2）

787. K 站中转内最便宜的航班

（bellman-ford最短路）

本题是一个用限制条件的最短路径问题，我们可以使用bellman-ford算法直接计算即可。

本质上bellman-ford算法就是一个dp。

dp[k][i]表示从起点出发最多经过k条边走到i中所有路径中长度的最小值。

所以f[k][i] = min{f[k - 1][j] + dist[j]}。

class Solution {
    static int INF = 0x3f3f3f3f;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[][] f = new int[k + 2][n];
        for (int i = 0; i < k + 2; i ++)
            Arrays.fill(f[i], INF);
        f[0][src] = 0;
        int ans = INF;
        for (int t = 1; t <= k + 1; t ++) {
            for (int[] flight : flights) {
                int from = flight[0], to = flight[1], w = flight[2];
                f[t][to] = Math.min(f[t][to], f[t - 1][from] + w);
            }
        } 
        for (int t = 1; t <= k + 1; t ++)
            ans = Math.min(ans, f[t][dst]);
        return ans == INF ? -1 : ans;
    }
}

（bellman-ford最短路-空间优化）

因为每一次只用到二维数组中的上一层中的数字，所以我们可以使用两个一维数组滚动的使用。

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int INF = 0x3f3f3f3f;
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        // k个中间点,k+1条边,k+1次循环
        for (int i = 0; i <= k; i ++) {
            // 用cur表示临时数组
            int[] cur = new int[n];
            cur = Arrays.copyOf(dist, n);
            // 上面两句可以使用int[] cur = dist.clone();替代
            for (int[] f : flights) {
                int from = f[0], to = f[1], w = f[2];
                cur[to] = Math.min(cur[to], dist[from] + w);
            }
            dist = cur;
        }
        if (dist[dst] == INF) return -1;
        else return dist[dst];
    }
}

Java的完整写法

class Solution {
    class Edge {
        int x, y, w;
        Edge(int _x, int _y, int _w) {
            x = _x; y = _y; w = _w;
        }
    }

    int N = 110, INF = 0x3f3f3f3f;
    // n个点，m条边，k步之内，从src到dst
    int n, m, k, src, dst;
    List<Edge> list = new ArrayList<>();
    int[] dist = new int[N];

    public int findCheapestPrice(int _n, int[][] flights, int _src, int _dst, int _k) {
        n = _n; src = _src; dst = _dst; k = _k + 1;
        for (int[] f : flights) {
            list.add(new Edge(f[0], f[1], f[2]));
        }
        m = list.size();
        int ans = bellman_ford();
        return ans > INF / 2 ? -1 : ans;
    }

    public int bellman_ford() {
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int i = 0; i < k; i ++) {
            int[] cur = dist.clone();
            for (Edge e : list) {
                int x = e.x, y = e.y, w = e.w;
                dist[y] = Math.min(dist[y], cur[x] + w);
            }
        }
        return dist[dst];
    }
}

319. 灯泡开关

（数学+脑筋急转弯）

如果一个灯泡最后是亮的，说明它被摁了偶数次。如果灯泡最后是灭的，说明它被摁了奇数次。而一个灯泡被摁的次数和n的约数个数有关。如果一个数字是完全平方数说明它的约数个数为奇数。如果一个数字不是完全平方数，说明它的约数个数一定是偶数。所以我们只要看1~n中有多少的完全平方数即可。即sqrt(n)。

class Solution {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }
}

743. 网络延迟时间

我们要知道多久才可以使得所有的点都可以接收到信号。其实就是在求从k出发到达所有点的最短路中，哪一个最短路需要的时间最多。（因为如果最大的最短路所用的时间一定可以到达其他所有的点）。

所以本题主要考察我们最短路的图论模板怎么写，有5种方式的图论最短路朴素版Dijkstra，堆优化版Dijkstra，bellman-ford，spfa和floyd最短路。

（朴素版Dijkstra最短路）

每一次确定一个离源点最近的点，然后用这个点去优化从这个出发的路径。

class Solution {
    final int INF = 0x3f3f3f3f;
    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] g = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i ++)
            Arrays.fill(g[i], INF);
        for (int[] time : times) {
            int a = time[0], b = time[1], w = time[2];
            g[a][b] = w;
        }
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[k] = 0;
        
        boolean[] vis = new boolean[n + 1];
        for (int i = 1; i <= n; i ++) {
            int x = -1;
            for (int y = 1; y <= n; y ++) 
                if (!vis[y] && (x == -1 || dist[x] > dist[y]))
                    x = y;
            vis[x] = true;
            for (int j = 1; j <= n; j ++)
                dist[j] = Math.min(dist[j], dist[x] + g[x][j]);
        }
        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
}

（堆优化版Dijkstra最短路）

我们可以使用堆的结构优化上面使用循环找到离源点最近的一个点的位置。使用priority_queue，并且存放{从该点到源点的距离, 该点的编号}，就可以在O(1)的时间内找到距离源点最近的点。

class Solution {
    final int N = 110, M = 6010;
    int INF = 0x3f3f3f3f;
    int[] he = new int[N], e = new int[M], w = new int[M], ne = new int[M];
    int idx = 0;
    void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = he[a];
        he[a] = idx;
        idx ++;
    }
    boolean[] vis = new boolean[N];
    int[] dist = new int[N];
    int n, k;
    public int networkDelayTime(int[][] times, int _n, int _k) {
        n = _n; k = _k;
        Arrays.fill(he, -1);
        Arrays.fill(dist, INF);
        for (int[] time : times) {
            int a = time[0], b = time[1], c = time[2];
            add(a, b, c);
        }
        dijkstra();
        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void dijkstra() {
        dist[k] = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0]-b[0]);
        q.add(new int[]{0, k});
        while (!q.isEmpty()) {
            int[] top = q.poll();
            int ver = top[1], distance = top[0];
            if (vis[ver]) continue;
            vis[ver] = true;
            for (int i = he[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > distance + w[i]) {
                    dist[j] = distance + w[i];
                    q.add(new int[]{dist[j], j});
                }
            }
        } 
    }
}

（bellman-ford最短路）

bellman-ford算法可以算出在k步之内从起点到终点的最短路。而我们只需要将k设置成本题中n代表的点的数量即可。

class Solution {
    class Edge {
        int a, b, w;
        Edge(int _a, int _b, int _w) {
            a = _a; b = _b; w = _w;
        }
    }
    int n, k;
    int[] dist = new int[110];
    int INF = 0x3f3f3f3f;
    List<Edge> list = new ArrayList<>();
    public int networkDelayTime(int[][] times, int _n, int _k) {
        n = _n; k = _k;
        for (int[] time : times) {
            int a = time[0], b = time[1], w = time[2];
            list.add(new Edge(a, b, w));
        }
        bellman_ford();
        int ans = 0;
        for (int i = 1; i <= n; i ++)
            ans = Math.max(ans, dist[i]);
        return ans > INF / 2 ? -1 : ans;
    }
    void bellman_ford() {
        Arrays.fill(dist, INF);
        dist[k] = 0;
        for (int i = 1; i <= n; i ++) {
            int[] prev = dist.clone();
            for (Edge e : list) {
                int a = e.a, b = e.b, w = e.w;
                dist[b] = Math.min(dist[b], prev[a] + w);
            }
        }
    }
}

（spfa最短路）

spfa最短路就是在bellman-ford算法的基础上做一些优化。即每一次不像bellman-ford算法一样：每一次都将在所有的点的出边都进行更新。因为dist[b] = min(dist[b], prev[a] + w)，只有prev[a]更新变小了，dist[b]才会更新变小，所以我们可以只使用被更新过了点去更新其他的点。

class Solution {
    final int N = 110, M = 6010;
    int INF = 0x3f3f3f3f;
    int[] he = new int[N], e = new int[M], w = new int[M], ne = new int[M];
    int idx = 0;
    void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = he[a];
        he[a] = idx;
        idx ++;
    }
    boolean[] vis = new boolean[N];
    int[] dist = new int[N];
    int n, k;
    public int networkDelayTime(int[][] times, int _n, int _k) {
        n = _n; k = _k;
        Arrays.fill(he, -1);
        Arrays.fill(dist, INF);
        for (int[] time : times) {
            int a = time[0], b = time[1], c = time[2];
            add(a, b, c);
        }
        spfa();
        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void spfa() {
        dist[k] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(k);
        while (!q.isEmpty()) {
            int top = q.poll();
            vis[top] = false;
            for (int i = he[top]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[top] + w[i]) {
                    dist[j] = dist[top] + w[i];
                    if (!vis[j]) {
                        q.add(j);
                        vis[j] = true;
                    }
                }
            }
        }
    }
}

（floyd最短路）

本题是一个单源最短路问题，但是也可以使用多源最短路floyd算法来完成，floyd算法是基于动态规划的一个算法。所以只需要3重循环就可以算出任意两个之间的最短距离。

class Solution {
    final int INF = 0x3f3f3f3f;
    public int networkDelayTime(int[][] times, int n, int t) {
        int[][] dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                dist[i][j] = i == j ? 0 : INF;

        for (int[] time : times) {
            int a = time[0], b = time[1], w = time[2];
            dist[a][b] = w;
        }

        for (int k = 1; k <= n; k ++) 
            for (int i = 1; i <= n; i ++)
                for (int j = 1; j <= n; j ++)
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        
        int ans = 0;
        for (int i = 1; i <= n; i ++)
            ans = Math.max(ans, dist[t][i]);
        return ans > INF / 2 ? -1 : ans;
    }
}

397. 整数替换

（递归模拟）

如果本题直接模拟暴力递归的话，是可以过的。

class Solution {
    public int integerReplacement(int n) {
        return dfs(n);
    }
    public int dfs(long n) {
        if (n == 1) return 0;
        else if (n % 2 == 0) return 1 + dfs(n / 2);
        else return 1 + Math.min(dfs(n + 1), dfs(n - 1));
    }
}

（记忆化搜索）

我们也可以将中间过程使用哈希表HashMap保留下来，以空间换时间变成记忆化搜索。

class Solution {
    Map<Long, Integer> hash = new HashMap<>();
    public int integerReplacement(int n) {
        return dfs(n);
    }
    public int dfs(long n) {
        if (n == 1) return 0;
        if (hash.containsKey(n)) return hash.get(n);
        int ans = 0;
        if (n % 2 == 0) {
            ans = 1 + dfs(n / 2);
        } else {
            ans = 1 + Math.min(dfs(n + 1), dfs(n - 1));
        }
        hash.put(n, ans);
        return ans;
    }
}

（位运算+贪心）

奇数和偶数体现在为运算上其实就是看一个数字的二进制中的最后一位是否为1即可，为1就是奇数，为0就是偶数。

如果是偶数的话，我们就直接/2，也就是将n >> 1。

如果是奇数的话，我们可以+1或者-1。如果最后一位是1，并且倒数第二位是0，我们就可以直接-1，这样就是的数字的二进制中减少一个1。

如果倒数第二位也是1的话，此时+1由于两个1的进位使得数字的二进制可以减少两个1，这样可以更快。但是如果n==3的话，此时-1可以变成2比+1变成4减少的更快，这是一个特例。

class Solution {
    public int integerReplacement(int _n) {
        long n = _n;
        int ans = 0;
        while (n != 1) {
            if (n % 2 == 0) {
                n >>= 1;
            } else {
                // 3是特例
                if ((n != 3) && ((n >> 1) & 1) == 1) n ++;
                else n --;
            }
            ans ++;
        }
        return ans;
    }
}

204. 计数质数

（埃式筛法）

埃式筛法就是利用了一个质数的倍数一定都是合数，所以每一次找到一个质数的时候，就需要将这个质数的所有倍数都标记成为合数，剩下的数字就是质数了。

class Solution {
    public int countPrimes(int n) {
        int ans = 0;
        boolean[] vis = new boolean[n + 1];
        for (int i = 2; i < n; i ++) {
            if (!vis[i]) {
                ans ++;
                for (int j = i; j <= n; j += i) vis[j] = true;
            }
        }
        return ans;
    }
}

• 时间复杂度O(nlognlogn)

（线性筛法）

线性筛法的核心法则就是：每一个合数都会被并且只会被这个数字的最小质因子筛一次。

假设p是num的最小质因子，那么num/p=i，因为i是num的约数，所以p也一定是i的最小质因子。因此N可以被p这个最小质因子筛掉，直到p已经不再是i的最小质因子了，即i % p == 0。

class Solution {
    public int countPrimes(int n) {
        int ans = 0;
        int[] primes = new int[n];
        boolean[] vis = new boolean[n + 1];
        for (int i = 2; i < n; i ++) {
            if (!vis[i]) primes[ans ++] = i;
            for (int j = 0; i * primes[j] < n; j ++) {
                vis[i * primes[j]] = true;
                if (i % primes[j] == 0) break;
            } 
        }
        return ans;
    }
}

• 时间复杂度O(n)

241. 为运算表达式设计优先级

（二叉搜索树+递归）

对运算符的设计优先级可以两个思路：第一个是保留这个优先级原来的思路，第二个是将这个运算符的优先级设置为最高。

因此我们就可以让每一个运算符都将当做是左右两个表达式的分隔符。也就是将当前这个运算符的优先级设置为最低。而其他的在表达式中的运算符的优先级不变。最后就可以得到左右两边表达式中可以得到的不同的结果，然后让左右两边集合中的数字两两运算即可。

class Solution {
    boolean isNum(String s) {
        char[] arr = s.toCharArray();
        int i = 0, n = arr.length;
        while (i < n && arr[i] <= '9' && arr[i] >= '0') i ++;
        return i == n;
    }    
    int cal(int n1, int n2, char expr) {
        if (expr == '+') return n1 + n2;
        else if (expr == '-') return n1 - n2;
        else return n1 * n2;
    }
    public List<Integer> diffWaysToCompute(String s) {
        if (isNum(s)) {
            List<Integer> arr = new ArrayList<>();
            arr.add(Integer.valueOf(s));
            return arr;
        }
        int n = s.length();
        char[] arr = s.toCharArray();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i ++) {
            if (Character.isDigit(arr[i])) continue;
            List<Integer> left = diffWaysToCompute(s.substring(0, i));
            List<Integer> right = diffWaysToCompute(s.substring(i + 1, n));
            for (int l : left) {
                for (int r : right) {
                    ans.add(cal(l, r, arr[i]));
                }
            } 
        }
        return ans;
    }
}

423. 从英文中重建数字

（哈希表 + 找规律）

我们需要每一次在10个数字中找出拥有可以代表数字的字母。按照{0, 8, 3, 2, 6, 4, 5, 1, 7, 9}。按照这个顺序每一次都可以有一个独特的字母可以代表自己表示的数字。

关键就是：找到可以代表自己数字的字母。

注意：因为s字符串中可能存在多个相同的数字，所以我们需要找出所有的相同的数字，我们可以使用while循环，循环地找出所有的数字。或者我们也可以找出每一次我们需要找出的数字中那个独特的字母的最小值。比如说：所有的数字中只有zero才有字母z，那么我们就在所有的z e r o四个字母中找出出现次数最少的字母，即z。而其他字母因为是其他的数字构成的，所以出现的次数一定大于z出现的次数。

class Solution {
public:
    string originalDigits(string s) {
        string name[] = {
            "zero", "one", "two", "three", "four", "five",
            "six", "seven", "eight", "nine"
        };
        int ord[] = {0, 8, 6, 3, 2, 7, 5, 9, 4, 1};
        unordered_map<char, int> cnt;
        for (char ch : s) cnt[ch] ++;
        string ans;
        for (int x : ord) {
            int t = INT_MAX;
            for (char ch : name[x]) t = min(t, cnt[ch]);
            for (char ch : name[x]) {
                cnt[ch] -= t;
            }
            while (t -- ) ans += to_string(x);
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

413. 等差数列划分

（差分 + 数学）

本题我们需要知道一个子数组是否为一个满足等差数列性质的数组。也就是知道是否相邻的两个数的差值是否相等。

因此我们就可以使用差分数组来表示两个数字的差值。差分数组minux[i]表示nums[i] - nums[i - 1]也就是i位置上的数字和前面i-1数字上的差值。所以如果想要看一个数组是否为一个等差数列我们只需看差分数组中的值是否相等即可。

如果一个数组的长度为t的话，那么其中的自区间的个数（等差数列的个数）就位t*(t-1)/2。

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return 0;
        vector<int> minus(n);
        minus[0] = nums[0];
        for (int i = 1; i < n; i ++) {
            minus[i] = nums[i] - nums[i - 1];
        }
        int ans = 0;
        for (int i = 1; i < n; i ++) {
            int j = i;
            while (j < n && minus[j] == minus[i]) j ++;
            int t = j - i;
            ans += (t - 1) * t / 2;
            i = j - 1;
        }
        return ans;
    }
};

我们也可以将原数组nums直接改造成差分数组，但是需要从往前的递推，因为差分数组中的值是从一个数组减前一个数字，所以我们不能改变前面一个数字，而从后往前就可以先改变后面一个数字。

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        for (int i = n - 1; i > 0; i --) nums[i] -= nums[i - 1]; 
        int ans = 0;
        for (int i = 1; i < n; i ++) {
            int j = i;
            while (j < n && nums[j] == nums[i]) j ++;
            int t = j - i;
            ans += (t - 1) * t / 2;
            i = j - 1;
        }
        return ans;
    }
};

524. 通过删除字母匹配到字典里最长单词

（排序 + 双指针 + 贪心）

因为我们需要找到长度最长的字符串，所以我们可以将dictionary中的单词按单词的长度排一个降序。然后再利用双指针将dictionary中的单词和s字符串进行比对，这样找到的第一个可以匹配的单词就是长度最长并且字母序最小的字符串。

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        sort(dictionary.begin(), dictionary.end(), [](string& a, string& b){
            if (a.size() != b.size()) return a.size() > b.size();
            return a < b;
        });
        for (string& word : dictionary) {
            int i = 0;
            for (char ch : s) {
                if (ch == word[i]) i ++;
            }
            if (i == word.size()) return word;
        }
        return "";
    }
};

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        // Collections.sort(dictionary, new Comparator<String>() {
        //     public int compare(String a, String b) {
        //         if (a.length() != b.length()) return b.length() - a.length();
        //         return a.compareTo(b);
        //     }
        // });
        Collections.sort(dictionary, (a, b)-> {
            if (a.length() != b.length()) return b.length() - a.length();
            return a.compareTo(b);
        });
        int n = s.length();
        for (String word : dictionary) {
            int m = word.length();
            int i = 0, j = 0;
            while (i < m && j < n) {
                if (word.charAt(i) == s.charAt(j)) i ++;
                j ++;
            }
            if (i == m) return word;
        }
        return "";
    }
}

（双指针）

或者我们就可以直接使用双指针的算法，直接判断一个字符串是否为另一个字符串的子序列即可。

判断一个字符串中是否存在另一个字符串其实只需要要遍历原字符串，在遍历的同时遍历我们需要检查的word，其中两个字符串中相同的字符就可以继续向下比较，否则就让原串中的指针向下即可。

注意：判断一个字符串中是否存在另一个字符串是一个常用的双指针模板。

class Solution {
public:
    bool check(string& a, string& b) {
        int i = 0, j = 0;
        int n = a.size(), m = b.size();
        while (i < n && j < m) {
            if (a[i] == b[j]) i ++;
            j ++;
        }
        return i == n;
    }

    string findLongestWord(string s, vector<string>& dictionary) {
        string ans;
        for (string& word : dictionary) {
            if (check(word, s)) {
                if (word.size() > ans.size() || (word.size() == ans.size() && word < ans)) 
                    ans = word;
            }
        }
        return ans;
    }
};

109. 有序链表转换二叉搜索树

（递归）

因为需要将链表中的数值构造成二叉搜索树，而需要满足二叉搜索树最大的性质就是要使得构造成的树的中序遍历是一个有序的，在本题中因此链表是升序的，所以二叉搜索树的中序遍历还必须是升序的。

根据这一点有一种构造的方法就是：每一次将链表中间的数值作为二叉搜索树的树根，然后将链表分成左右两个分别有序的链表即可。

因此链表中不能支持随机访问，所以我们可以将链表中的数组放在数组中这样就可以快速地找到数组中的数值了。

class Solution {
public:
    TreeNode* dfs(vector<int>& nodes, int l, int r) {
        if (l > r) return nullptr;
        int mid = (l + r) / 2;
        TreeNode* left = dfs(nodes, l, mid - 1);
        TreeNode* right = dfs(nodes, mid + 1, r);
        TreeNode* root = new TreeNode(nodes[mid]);
        root->left = left, root->right = right;
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> nodes;
        for (ListNode* cur = head; cur; cur = cur->next) {
            nodes.push_back(cur->val);
        }
        return dfs(nodes, 0, nodes.size() - 1);
    }
};

?

（递归2）

如果不将链表保存为数组也是可以的，但是我们每一次都需要去找链表的中间节点。

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        int n = 0;
        for (ListNode* cur = head; cur; cur = cur->next) n ++;
        // 因为后面需要使用到head->next->val,所以必须要保证head->next!=nullptr
        // 所以如果链表中只有head这一个节点的话，我们就需要提前判断return节点
        if (n == 1) return new TreeNode(head->val);
        
        ListNode* cur = head;
        for (int i = 0; i < n / 2 - 1; i ++) cur = cur->next;
        TreeNode* root = new TreeNode(cur->next->val);
        root->right = sortedListToBST(cur->next->next);
        cur->next = nullptr;
        root->left = sortedListToBST(head);
        return root;
    }
};

406. 根据身高重建队列

（排序）

本题是一个排序题，而且是一个有两个维度的排序题。所以我们就需要考虑两个维度之间排序的优先级问题。因为题目中限定了第二维度，即第i个人前面只能由people[i][1]个人升高的高度比第i个人大。因此我们在排序的过程中是不能影响第二维度的。

所以如果我们想要将第一维升序排的话，那么我们就要考虑当前第i个人前面需要有people[i][1]个空位置（如果被别人占了的位置就不算空位置）加上自己需要占的位置，就是需要将people[i]放在ans中第people[i][1] + 1的空位置上。

如果出现了两个相同的身高的时候，我们需要按第二维度排降序。因此两个身高一样高，所以需要增加第二维度上的人数。为了不影响第二维的话，我们就可以降序排序，这样相同升高之间的人就不会相互影响了。

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b){
            if (a[0] != b[0]) return a[0] < b[0];
            return a[1] > b[1];
        });
        int n = people.size();
        vector<vector<int>> ans(n);
        for (vector<int>& p : people) {
            int k = p[1] + 1;
            for (int i = 0; i < n; i ++) {
                if (ans[i].empty()) {
                    k --;
                    if (k == 0) {
                        ans[i] = p;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

（排序 + 贪心）

如果第一维降序排序的话，那么就在people[i][1]的位置上插入people[i]即可，因此people[i][1]表示的就是前面的人数，而因为第一维已经是降序排序了，所以ans中的人就是已经排好队而且比待插入的人的升高要高。

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b){
            if (a[0] != b[0]) return a[0] > b[0];
            return a[1] < b[1];
        });
        vector<vector<int>> ans;
        for (vector<int>& p : people) {
            ans.insert(ans.begin() + p[1], p);
        }
        return ans;
    }
};

总结：在本题这种有两维需要排序的题目中，我们通常都是抓住其中的一维，固定下来之后在再第一维已经有序的情况下继续考虑第二维上的数字。

如第一种方法中：固定了第一维是升序的，所以我们需要看的是其中的空位置。

在第二种方法中：固定了第二维是降序的，所以我们需要看的数组中的人数。

375. 猜数字大小 II

（记忆化搜索 + 博弈论）

本题不能使用二分来解决，而是要使用递归来爆搜。

因为本题不是要求出能找到某一个数字的最少次数，而是找到任意一个数字的最小代价。因此我们需要考虑每一个数字作为第一个被猜到的数字。

使用递归（爆搜）或者动态规划枚举所有的情况。

我们使用dfs(int l, int r)表示在区间[l, r]中的最坏情况下的最小值。意思就是我们第一次猜的数字有n种情况，而每一种情况下需要的次数不同，最终的答案就是这n中情况中的最小值。但是猜每一个数字都需要考虑最坏的情况，即我们需要尽可能地猜错或者是多猜。这就是博弈论，在最聪明的情况下做出最傻的事情。

class Solution {
public:
    int memo[210][210];
    int dfs(int l, int r) {
        if (l >= r) return 0;
        if (memo[l][r]) return memo[l][r];
        int ans = INT_MAX;
        for (int i = l; i <= r; i ++) {
            int left = dfs(l, i - 1);
            int right = dfs(i + 1, r);
            ans = min(ans, max(left, right) + i);
        }
        memo[l][r] = ans;
        return ans;
    }

    int getMoneyAmount(int n) {
        return dfs(1, n);
    }
};

（动规 + 博弈论）

可以将递归的过程写成动规。因此我们枚举的一个一个的区间，所以可以使用区间DP的模板。

注意：因为下标从1开始所以会枚举n，而转移方程中f[i][j] = min(f[i][j], max(f[i][k - 1], f[k - 1][j]) + k)当枚举右边界枚举到n的时候，会用到n+1，所以需要开到f[n+2][n+2]。

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> f(n + 2, vector<int>(n + 2));
        for (int len = 2; len <= n; len ++) {
            for (int i = 1; i + len - 1 <= n; i ++) {
                int j = i + len - 1;
                f[i][j] = INT_MAX;
                for (int k = i; k <= j; k ++) {
                    f[i][j] = min(f[i][j], max(f[i][k - 1], f[k + 1][j]) + k);
                }
            }
        }
        return f[1][n];
    }
};

也可以开到f[n+1][n+1]，但是需要判断一下特殊的情况。

class Solution {
    public int getMoneyAmount(int n) {
        int[][] f = new int[n + 1][n + 1];
        for (int len = 2; len <= n; len ++) {
            for (int i = 1; i + len - 1 <= n; i ++) {
                int j = i + len - 1;
                f[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k <= j - 1; k ++) {
                    f[i][j] = Math.min(f[i][j], Math.max(f[i][k - 1], f[k + 1][j]) + k);
                }
                f[i][j] = Math.min(f[i][j], i + f[i + 1][j]);
                f[i][j] = Math.min(f[i][j], j + f[i][j - 1]);
            }
        }
        return f[1][n];
    }
}

1583. 统计不开心的朋友

（大模拟）

为了实现模拟，我们准备了match数组和close数组，这样就可以快速地找到一个数字的配对数字，也可以通过close数组来表示两个数组的亲密程度。

class Solution {
public:
    int unhappyFriends(int n, vector<vector<int>>& pf, vector<vector<int>>& pairs) {
        vector<vector<int>> close(n, vector<int>(n));
        vector<int> match(n);
        for (auto pair : pairs) {
            match[pair[0]] = pair[1];
            match[pair[1]] = pair[0];
        }
        for (int i = 0; i < n; i ++) {
            int cnt = n;
            for (int j = 0; j < n - 1; j ++) {
                close[i][pf[i][j]] = cnt --;
            }
        }
        int ans = 0;
        for (int x = 0; x < n; x ++) {
            int y = match[x];
            for (int u : pf[x]) {
                if (u == y) break;
                int v = match[u];
                if (close[u][x] > close[u][v]) {
                    ans ++;
                    break;
                }
            }
        }
        return ans;
    }
};

384. 打乱数组

（API）

class Solution {
public:
    vector<int> a;
    Solution(vector<int>& nums) {
        a = nums;
    }
    
    vector<int> reset() {
        return a;
    }
    
    vector<int> shuffle() {
        auto tmp = a;
        random_shuffle(tmp.begin(), tmp.end());
        return tmp;
    }
};

（洗牌算法）

洗牌算法就是在模拟C++中的random_shuffle函数。即对于下标i而言，从[i, n - 1]中随机选出一个数字和i位置上的数字交换。这样就可以得到一个公平的洗牌结果。也就是前i个数字已经被打乱了，我们需要打乱下来的n - i的数字。

class Solution {
    static int[] a;
    Random rand = new Random();
    public Solution(int[] nums) {
        a = nums;
    }
    
    public int[] reset() {
        return a;
    }
    
    public int[] shuffle() {
        int[] b = a.clone();
        int n = a.length;
        for (int i = 0; i < n; i ++) {
            swap(b, i, i + rand.nextInt(n - i));
        }
        return b;
    }

    void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}

863. 二叉树中所有距离为 K 的结点

（深搜 + 哈希表）

因为本题需要顺着树枝往上找节点，所以我们就可以将树转换成无向图（树本就是一个有向图），这样就可以倒着往上找树的节点了。

然后就是从target这个节点开始往外找到第k层的节点即可。

注意：

使用哈希表存储图。

如果使用爆搜的话，需要记得son != parent，这样就不会循环找同一个节点了。

class Solution {
public:
    unordered_map<TreeNode*, vector<TreeNode*>> g;
    vector<int> ans;

    void dfs1(TreeNode* root) {
        if (root == nullptr) return ;
        if (root->left) {
            g[root].push_back(root->left);
            g[root->left].push_back(root);
            dfs1(root->left);
        }
        if (root->right) {
            g[root].push_back(root->right);
            g[root->right].push_back(root);
            dfs1(root->right);
        }
    }

    void dfs2(TreeNode* root, TreeNode* parent, int k) {
        if (k == 0) {
            ans.push_back(root->val);
            return ;
        }
        for (TreeNode* son : g[root]) {
            if (son != parent) {
                dfs2(son, root, k - 1);
            }
        }
        // 配合上面定义了vis[510]
        // for (TreeNode* son : g[root]) {
        //     if (!vis[son->val]) {
        //         vis[son->val] = true;
        //         dfs2(son, k - 1);
        //     }
        // }
    }

    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        dfs1(root);
        dfs2(target, nullptr, k);
        return ans; 
    }
};

（宽搜 + 哈希表）

如果使用宽搜的话，需要使用vis数组来标识节点已经被访问过了。

class Solution {
public:
    unordered_map<TreeNode*, vector<TreeNode*>> g;

    void dfs(TreeNode* root) {
        if (root == nullptr) return ;
        if (root->left) {
            g[root].push_back(root->left);
            g[root->left].push_back(root);
            dfs(root->left);
        }
        if (root->right) {
            g[root].push_back(root->right);
            g[root->right].push_back(root);
            dfs(root->right);
        }
    }

    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        dfs(root);
        queue<TreeNode*> q;
        q.push(target);
        vector<bool> vis(510);
        vis[target->val] = true;
        vector<int> ans;
        while (!q.empty() && k >= 0) {
            if (!k) {
                while(!q.empty()) {
                    ans.push_back(q.front()->val);
                    q.pop();
                }
            }
            int size = q.size();
            while (size --) {
                TreeNode* top = q.front();
                q.pop();
                for (TreeNode* son : g[top]) {
                    if (!vis[son->val]) {
                        q.push(son);
                        vis[son->val] = true;
                    }
                }
            }
            k --;
        }
        return ans; 
    }
};

（深搜 + 链式向前星）

也可以通过使用数组的方式（链式向前星）的方法来建图。

class Solution {
    int N = 510, M = 2010;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    int idx = 0;

    void add(int a, int b) {
        e[idx] = b; ne[idx] = he[a]; he[a] = idx ++;
    }

    void dfs(TreeNode root) {
        if (root == null) return ;
        if (root.left != null) {
            add(root.val, root.left.val);
            add(root.left.val, root.val);
            dfs(root.left);
        }
        if (root.right != null) {
            add(root.val, root.right.val);
            add(root.right.val, root.val);
            dfs(root.right);
        }
    }

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Arrays.fill(he, -1);
        dfs(root); 
        Queue<Integer> q = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        boolean[] vis = new boolean[N];
        vis[target.val] = true;
        q.add(target.val);
        while (!q.isEmpty() && k >= 0) {
            int size = q.size();
            while (size -- != 0) {
                int poll = q.poll();
                if (k == 0) {
                    ans.add(poll);
                    continue;
                }
                for (int i = he[poll]; i != -1; i = ne[i]) {
                    int j = e[i];
                    if (!vis[j]) {
                        q.add(j);
                        vis[j] = true;
                    }
                }
            }
            k --;
        }
        return ans;
    }
}

1818. 绝对差值和

（二分 + set）

题目要求需要替换nums1中的一个元素使得|nums1[i] - nums2[i]|之间的绝对值的总和最小，所以需要在nums1中挑出一个nums1[j]使得nums1[j]和nums2[j]之间的绝对值在nums1[j]被替换之后可以替换所得的差值最大。即将nums1[j]替换成t之后，|t - nums2[j]| - |nums1[j] - nums2[j]|的差值最大，这样就可以使得最后的绝对值总和最小。

如果将每一个nums1[i]都遍历一遍，时间复杂度为O(n²)。因为是要在一个数组中找两个和nums2[j]最接近的数字（左右两边），所以我们就可以使用二分。

可以使用set中自带的lower_bound函数，或者将nums1拷贝一份。将拷贝的函数进行排序，然后再拷贝并且排序之后的数组中使用二分。

class Solution {
public:
    const int mod = 1e9 + 7;
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        long long ans = 0;
        set<int> st;
        for (int i = 0; i < n; i ++) {
            st.insert(nums1[i]);
            ans += abs(nums1[i] - nums2[i]);
        }
        int maxv = 0;
        for (int i = 0; i < n; i ++) {
            auto it = st.lower_bound(nums2[i]);
            long long t = abs(nums1[i] - nums2[i]);
            if (it != st.end()) {
                maxv = fmax(maxv, t - (abs(*it - nums2[i])));
            }
            if (it != st.begin()) {
                it --;
                maxv = fmax(maxv, t - (abs(*it - nums2[i])));
            }
        }
        return (ans - maxv) % mod;
    }
};

（二分 + 排序）

class Solution {
public:
    const int mod = 1e9 + 7;
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        vector<int> sorted(nums1);
        sort(sorted.begin(), sorted.end());
        int n = nums1.size();
        long long ans = 0, maxv = 0;
        for (int i = 0; i < n; i ++) {
            int diff = abs(nums1[i] - nums2[i]);
            ans += diff;
            auto it = lower_bound(sorted.begin(), sorted.end(), nums2[i]);
            if (it != sorted.end()) {
                maxv = fmax(maxv, diff - abs(*it - nums2[i]));
            }
            if (it != sorted.begin()) {
                it --;
                maxv = fmax(maxv, diff - abs(*it - nums2[i]));
            }
        }
        return (ans - maxv) % mod;
    }
};

class Solution {
    final int mod = 1_000_000_000 + 7;
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int[] sorted = nums1.clone();
        Arrays.sort(sorted);
        int ans = 0, maxv = 0;
        int n = nums1.length;
        for (int i = 0; i < n; i ++) {
            int diff = Math.abs(nums1[i] - nums2[i]);
            ans += diff;
            ans %= mod;
            int index = binSearch(sorted, nums2[i]);
            if (index < n) {
                maxv = Math.max(maxv, diff - Math.abs(sorted[index] - nums2[i]));
            }
            if (index > 0) {
                maxv = Math.max(maxv, diff - Math.abs(sorted[index - 1] - nums2[i]));
            }
        }
        return (ans - maxv + mod) % mod;
    }
    public int binSearch(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        if (nums[r] < target) return n;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}

1711. 大餐计数

（哈希表 优化）

如果使用暴力方法做本题的话，因为需要枚举每一个数字和其他数字的和然后再判断是否为2的幂，所以这样会超时。

所以本题就是一个使用哈希表去优化时间的典型案例。我们可以将前面的数字使用哈希表记录下数字和这个数字出现的次数。而且我们枚举的是可以配对成2的幂的一对数的后一个数字。然后每一次在2²²中挑选出，所有的2的幂进行判断，是否有2的幂 - 枚举的数字出现在前面枚举的数字中（即哈希表中），然后就可以使用O(1)的时间将算出可以和当前枚举到的数字进行配对的数字的个数了。

注意：因为我们只关心数字出现的次数，而不关心具体哪两个数组，所以可以使用哈希表以空间换时间来优化。其实本题很像「两数之和」都是边计算边存储。

class Solution {
public:
    const int mod = 1e9 + 7;
    int countPairs(vector<int>& nums) {
        unordered_map<int, int> hash;
        int maxv = 0;
        for (int num : nums) maxv = max(maxv, num);
        int ans = 0;
        for (int num : nums) {
            for (int i = 1; i <= maxv * 2; i <<= 1) {
                int cnt = hash[i - num];
                ans += cnt;
                ans %= mod;
            }
            hash[num] ++;
        }
        return ans;
    }
};

981. 基于时间的键值存储

（二分 + 哈希表）

本题还是一个键值对的问题，所以可以使用哈希表来完成。

但是key对应的value需要同时存放timestamp和value两个值，所以可以使用vector来保存。而且因为放入的值的timestamp是递增的，所以vector中是按timestamp排的升序。

因此当得到一个key的时候，我们就可以在hash[key]这个数组中使用二分找到<= timestamp的最大的时间对应的值了。

class TimeMap {
public:
    unordered_map<string, vector<pair<int, string>>> hash;
    TimeMap() {
    }
    
    void set(string key, string value, int timestamp) {
        hash[key].push_back({timestamp, value});
    }
    
    string get(string key, int timestamp) {
        if (!hash.count(key)) return "";
        auto& nums = hash[key];
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid].first <= timestamp) l = mid;
            else r = mid - 1;
        }
        if (nums[l].first <= timestamp) return nums[l].second;
        return "";
    }
};

（套娃哈希表）

也可以使用哈希表中套一个map，这样就可以使用upper_bound函数了。（这是使用upper_bound函数来模拟找到<= target的最大值）。

注意：upper_bound函数是求出> target的最小的数字，lower_bound函数是求出>= target最小的数字。但是本题需要求出<= target最大的数字，其实可以使用upper_bound找到> target最小的数字，然后-1就是<= target最小的数字了。

class TimeMap {
public:
    unordered_map<string, map<int, string>> mp;
    TimeMap() {
    }
    
    void set(string key, string value, int timestamp) {
        mp[key].insert({timestamp, value});
    }
    
    string get(string key, int timestamp) {
        auto it = mp[key].upper_bound(timestamp);
        if (it == mp[key].begin()) return "";
        --it;
        return it->second;
    }
};

313. 超级丑数

（优先队列 + 哈希表）TLE

因为超级丑数有由另一个超级丑数和primes数组中的质数的乘积，所以我们可以通过不断的从超级丑数中选取一个数字和primes中的质数相乘就可以得到一个超级丑数，如果想要得到第n个超级丑数的话，我们可以将求得的超级丑数放入小根堆中，这样每一次堆顶的元素就是最小的超级丑数，在使用这个超级丑数去和primes中的质数相乘得到新的超级丑数。

注意：一个超级丑数可能是多个超级丑数和pirmes中乘积的结果，所以如果遇到相同的超级丑数需要跳过。

class Solution {
public:
    typedef long long LL;
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        unordered_set<LL> vis;
        priority_queue<LL, vector<LL>, greater<LL>> q;
        q.push(1);
        vis.insert(1);
        for (int i = 1; i <= n; i ++) {
            LL top = q.top();
            q.pop();
            if (i == n) return top;
            for (int prime : primes) {
                LL x = prime * top;
                if (!vis.count(x)) {
                    vis.insert(x);
                    q.push(x);
                }
            }
        }
        return -1;
    }
};

（多路归并）TLE

一列超级丑数一定是由另一列超级丑数和primes中的乘积构成的。所以primes中的每一个质数都可以构成一列新的超级丑数。

我们可以使用index数组表示primes中第i个质数在超级丑数的序列中已经排序到第几个位置了。例如：如果primes[i]已经加入到超级丑数的行列中之后，那么就将ans[index[i]] * primes[i]放入超级丑数的行列中，并将index[i] ++，这样下一次primes[i]就会与primes[i]这个超级丑数这个行列中的超级丑数相乘。

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> ans;
        int len = primes.size();
        vector<int> index(len);
        ans.push_back(1);
        int idx = 1;
        while (idx < n) {
            int minVal = INT_MAX;
            int minIdx = -1;
            for (int i = 0; i < len; i ++) {
                if (primes[i] * ans[index[i]] < minVal) {
                    minVal = primes[i] * ans[index[i]];
                    minIdx = i;
                }
            }
            index[minIdx] ++;
            if (minVal == ans.back()) continue;
            ans.push_back(minVal);
            idx ++;
        }
        return ans.back();
    }
};

（多路归并 + 优先队列）

如果小根堆就可以快速地找到剩余超级丑数中最小的超级丑数了。并且将当前这个超级丑数所在的primes[i]对应的超级丑数的列的位置记录下来。

如果val = top.first, ptr = top.second，那么val代表上面的minVal，ptr代表index[minIdx]，而val / ans[ptr]就等于primes数组中对应的质数。

class Solution {
public:
    typedef long long LL;
    typedef pair<LL, LL> PII;
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<LL> ans(n);
        ans[0] = 1;
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        for (int prime : primes) heap.push({ans[0] * prime, 0});
        int idx = 1;
        while (idx < n) {
            auto top = heap.top(); heap.pop();
            // val是当前的超级丑数
            // ptr是在val这一列丑数中,val处在ans中的位置,ans[ptr]是val在ans中丑数
            // prime是val对应的质数
            int val = top.first, ptr = top.second, prime = val / ans[ptr];
            if (val != ans[idx - 1]) ans[idx ++] = val;
            heap.push({ans[ptr + 1] * prime, ptr + 1});
        }
        return ans.back();
    }
};

395. 至少有 K 个重复字符的最长子串

（枚举 + 哈希表 + 双指针）

一般看到了「最长字符串/区间」这种题目，我们都会想到使用双指针和滑动窗口的解法。但是如果本题使用双指针的话，却是不可以，因为这题不满足使用双指针的性质，即满足「单调性」。假设s串的一段区间[i, j]，如果右指针j向右滑动的话，如果加入的字符是一个i左侧出现过的字符的话，那么此时i指针向左滑动就有可能满足区间中的字符个数也是>k的，所以这就不符合单调性的要求了。

此时我们可以枚举区间中字符的个数，来限制滑动窗口的中的字符种类的个数。「当限制了窗口内的字符个数的时候，区间重新获得了单调性」。因为多了字符种类个数的限制，所以当右指针向右移动的时候，左指针只会不移动或者因为字符种类超出限制而也向右移动。这样区间就又获得了单调性。

注意：可以想到使用枚举的方法是因为题目提示中说明了s仅由小写字符组成，因为数量比较少，所以可以使用枚举的方法。

class Solution {
public:
    int longestSubstring(string s, int k) {
        unordered_map<char, int> hash;
        int n = s.size();
        int ans = 0;
        for (int cnt = 1; cnt <= 26; cnt ++) {
            hash.clear();
            int tot = 0, vaild = 0;
            for (int i = 0, j = 0; i < n; i ++) {
                if (hash[s[i]] == 0) tot ++;
                hash[s[i]] ++;
                if (hash[s[i]] == k) vaild ++;
                while (tot > cnt) {
                    if (hash[s[j]] == k) vaild --;
                    hash[s[j]] --;
                    if (hash[s[j]] == 0) tot --;
                    j ++;
                }
                if (tot == vaild) ans = max(ans, i - j + 1);
            }
        }
        return ans;
    }
};

400. 第 N 位数字

（数学模拟）

先按位数分类，1~9, 10~99, 100~999….。k表示数字的位数，t表示数字的个数，d表示10的k次数方。因为数字小于2³¹ - 1，所以最多只有10次计算。然后就可以计算在k位数下的第几个数字，最后转换成字符串计算在一个数字下的第几位上。

class Solution {
public:
    int findNthDigit(int n) {
        // k表示数字的位数，t表示数字的个数，d表示10的k次数方
        long long k = 1, t = 9, d = 1;
        while (n > t * k) {
            n -= t * k;
            k ++, t *= 10, d *= 10;
        }
        int x = (n + k - 1) / k, y = n % k;
        d += x - 1;
        if (y == 0) return to_string(d).back() - '0';
        return to_string(d)[y - 1] - '0';
    }
};

670. 最大交换

（贪心 + 数学）

和「31. 下一个排列」的思考方法类似。如果贪心的想法就是尽量的将大的数字放在高位。

将数字的每一位数字都看成柱状图，那么降序表示高位上已经放着大的数字。而第一个升序表示可以有调整的空间。如果转折点为index的话，为了使得数字的交换一次之后可以变得最大，那么就需要取最后面一位最大的数字（因为最大的数字可能有多个）。将这个最大的数字和前面第一个比这个数字小的数字进行交换即可。

注意：本题不可以直接找到这个数字中最大的一个数字，然后和前的数字交换，因为最大的数字可能会有相同的多个，所以不能确定交换哪一个。

class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        int n = s.size();
        for (int i = 0; i < n - 1; i ++) {
            if (s[i] < s[i + 1]) {
                int k = i;
                for (int j = i; j < n; j ++) 
                    if (s[k] <= s[j])
                        k = j;
                for (int j = 0; j <= i; j ++)
                    if (s[k] > s[j]) {
                        swap(s[k], s[j]);
                        return stoi(s);
                    }
            }
        }
        return num;
    }
};

1418. 点菜展示表

（哈希表 + 排序）

本题就是要模拟这个第一行是title（即食物的名称），第一列是桌号的二维表格。

1.第一行：Table + 去重的并且升序的食物

2.中间内容：升序的桌号 + 食物的数量

我们可以哈希表去重，然后排序来解决第一行的问题。中间的内容需要使用不同的桌号对应相同的食物名称。所以也可以使用哈希表做对应的报表格。并且因为每一个桌号都要对应相同的食物名，所以哈希表中还需要一个哈希表，被嵌套的哈希表需要维护在同一个桌号下不同的食物的数量。

class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        unordered_set<string> flist;
        unordered_map<int, unordered_map<string, int>> rows;
        for (auto& order : orders) {
            string id = order[1], food = order[2];
            flist.insert(food);
            int index = stoi(id);
            rows[index][food] ++;
        }
        vector<vector<string>> ans(1);
        // 第一行
        vector<string> title(flist.begin(), flist.end());
        sort(title.begin(), title.end());
        ans[0].push_back("Table");
        for (auto t : title) ans[0].push_back(t);
        // 第一列
        vector<int> table;
        for (auto& [k, v] : rows) table.push_back(k);
        sort(table.begin(), table.end());
        // 中间food的计数
        for (int index : table) {
            vector<string> cur;
            cur.push_back(to_string(index));
            for (auto& food : title) {
                cur.push_back(to_string(rows[index][food]));
            }
            ans.push_back(cur);
        }
        return ans;
    }
};

class Solution {
    public List<List<String>> displayTable(List<List<String>> orders) {
        Set<String> flist = new HashSet<>();
        Map<Integer, Map<String, Integer>> rows = new HashMap<>();
        List<List<String>> ans = new ArrayList<>();
        for (List<String> order : orders) {
            String id = order.get(1), food = order.get(2);
            flist.add(food);
            int index = Integer.parseInt(id);
            // 如果有index的话，就使用之前的哈希表
            // 否则的话，就需要创建一个新的哈细胞
            Map<String, Integer> map = rows.getOrDefault(index, new HashMap<>()); 
            map.put(food, map.getOrDefault(food, 0) + 1);
            rows.put(index, map);
        }
        // 第一行
        List<String> foods = new ArrayList<>(flist);
        Collections.sort(foods);
        List<String> title = new ArrayList<>();
        title.add("Table");
        title.addAll(foods);
        ans.add(title);
        // 中间内容
        List<Integer> table = new ArrayList<>(rows.keySet());
        Collections.sort(table);
        for (int index : table) {
            List<String> cur = new ArrayList<>();
            cur.add(index + "");
            // java中不能像c++可以直接使用[]引出
            // 所以所有的哈希表最好都在范围中存放一个备份
            // 然后使用这个备份的哈希表
            Map<String, Integer> map = rows.get(index);
            for (String food : foods) {
                cur.add(map.getOrDefault(food, 0) + ""); //
            }
            ans.add(cur);
        }
        return ans;
    }
}