leetcode困难题目刷题集

发表于 更新于

leetcode困难难度题目的题解。

Number of Ways to Reorder Array to Get Same BST

题解

算法：DP
时间复杂度：O(n2)O(n^2)

显然需要使用递归的思想解决这道题。不妨称生成一棵BST对应的序列为生成序列。

对于一棵BST树，考虑已知左右子树生成序列的数量，将这两棵树与根节点组成新的一棵BST。显然，新树生成序列的第一个元素一定是根节点本身，接下来是随后左右子树生成序列的组合。

不难发现，对于一个生成序列，先插入左子树的节点还是先插入右子树的节点不影响结果。只需要子树内部节点插入的相对顺序不变，都能保证子树保持不变。

由乘法原理可以推测，这棵树的生成序列数量为三部分的乘积：左子树生成序列的数量，右子树生成序列的数量，两个生成序列的组合方法数量。前两者可以递归得到，如何计算两个序列的组合数量？

我们想象把右子树的节点插入到左子树的生成序列元素之间的空格中，保证节点在右子树生成序列中的顺序不变。以左子树为 {2,1,3}\{2,1,3\}，右子树为 {4,5}\{4, 5\} 举例，可以看到，左子树有 44 个空格可以供右子树插入： 22 之前、22 和 11 之间、11 和 33 之间、33 之后。这样就是把 {4,5}\{4,5\} 在保证两者顺序不变的情况下插到 44 个空格之中。

假定把 ii 个数保持顺序不变，插到 jj 个空格中的方法数量为 f(i,j)f(i,j)。

分类讨论序列第一个数的位置。假设第一个数放在第一个空格中，剩下 i−1i-1 个数仍然可以放在所有的 jj 个空格中，这种情况下方案数为 f(i−1,j)f(i-1,j)；假设第一个数不放在第一个空格中，为保证相对顺序不变，所有数都不会放在第一个空格中，这种情况方案数为 f(i,j−1)f(i, j-1)，得到状态转移方程：

f(i,j)=f(i−1,j)+f(i,j−1)f(i,j)=f(i-1,j)+f(i,j-1)

考虑边界条件。当所有数字插入到一个空格中时或数字为 00 个时，都只有一种摆放方案。

f(x,1)=f(0,x)=1f(x,1)=f(0,x)=1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    static const int N = 1010, MOD = 1e9 + 7;
    int f[N][N];

    Solution() {
        memset(f, -1, sizeof(f));
    }
    
    int get(int a, int b)
    {
        if (f[a][b] != -1)
            return f[a][b];
        if (a == 0)
            return f[0][b] = 1;
        if (b == 1)
            return f[a][1] = 1;
        return f[a][b] = (get(a - 1, b) + get(a, b - 1)) % MOD;
    }

    int solve(vector<int> &nums)
    {
        if (nums.size() == 0)
            return 1;
        if (nums.size() == 1)
            return 1;
        vector<int> left, right;
        int mid = nums[0];
        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] < mid)
                left.push_back(nums[i]);
            else
                right.push_back(nums[i]);
        }
        int res = (long long)solve(left) * solve(right) % MOD;
        res = (long long)res * get(left.size(), right.size() + 1) % MOD;
        return res;
    }
    
    int numOfWays(vector<int> &nums) {
        return (solve(nums) - 1 + MOD) % MOD;
    }
};
1
2
Runtime: 215 ms, faster than 71.36% of C++ online submissions for Number of Ways to Reorder Array to Get Same BST.
Memory Usage: 45.7 MB, less than 66.02% of C++ online submissions for Number of Ways to Reorder Array to Get Same BST.

Minimum Possible Integer After at Most K Adjacent Swaps On Digits

题解

算法：树状数组
时间复杂度：O(nlog(n))O(nlog(n))

不难看出，高位数字变化带来的贡献是必定大于低位数字的。所以我们从高到低考虑是否通过交换来更新高位数字。

对于第 ii 位上的数字，我们从小到大枚举能否修改为 0∼90\sim 9。如果 当前的 kk 大于修改为 xx 所需要的交换次数，则必定需要修改（特别的，当 xx 等于位置上的值时，交换次数为零，此时必定符合条件）。找到最小 xx 后即考虑下一位数字。交换次数要怎么计算呢？

首先，我们维护数字 0∼90\sim 9 在最前面的位置，一旦交换，一定是交换最前的数字。考虑从后往前将位置 jj 的数交换到位置 ii ，此时交换次数为 j−ij-i。假设在交换时， jj 之后已经有 mm 个数字交换到了前面，则实际上 jj 便移到了位置 j+mj+m 上，实际需要交换次数为 j+m−ij+m-i。

我们想方设法维护发生一些交换后，数字的实际位置。通过上面的分析，我们在乎的是需要 j+1∼nj+1\sim n 范围内交换到前面的数字的个数，这是一个区间查询。我们可以维护一个数据结构，每当位置 ii 的数字往前交换了，就将该处的值加一。这样的操作可以通过树状数组维护。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution
{
public:
    static const int N = 3e4 + 10;

    int n;
    int tr[N];

    void add(int x, int v) // 位置 x 加 v
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }

    int sum(int x) // 1~x 前缀和
    {
        int sum = 0;
        for (; x >= 1; x -= x & -x)
            sum += tr[x];
        return sum;
    }

    string minInteger(string num, int k)
    {
        n = num.length();
        num = " " + num;
        list<int> li[10]; // 保存了0~9的所有出现位置
        for (int i = 1; i <= n; i++)
            li[num[i] - '0'].push_back(i);
        string res = "";
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= 9; j++)
            {
                if (li[j].size() && li[j].front() + (sum(n) - sum(li[j].front())) - i <= k)
                {
                    k -= (li[j].front() + (sum(n) - sum(li[j].front())) - i);
                    add(li[j].front(), 1);
                    li[j].pop_front();
                    res.push_back(j + '0');
                    break;
                }
            }
        }
        return res;
    }
};
1
2
Runtime: 128 ms, faster than 61.90% of C++ online submissions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits.
Memory Usage: 17.8 MB, less than 26.19% of C++ online submissions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits.

Count the Number of Ideal Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution
{
public:
    static const int N = 1e4 + 10, MOD = 1e9 + 7;
    int fact[N];
    int infact[N];
    int f[20][N];

    int qmi(int x, int n)
    {
        int res = 1;
        while (n)
        {
            if (n & 1)
                res = (long long)res * x % MOD;
            x = (long long)x * x % MOD;
            n >>= 1;
        }
        return res;
    }

    int Cab(int a, int b)
    {
        return (long long)fact[a] * infact[a - b] % MOD * infact[b] % MOD;
    }

    int idealArrays(int n, int maxValue)
    {
        fact[0] = infact[0] = fact[1] = infact[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            fact[i] = (long long)fact[i - 1] * i % MOD;
            infact[i] = (long long)infact[i - 1] * qmi(i, MOD - 2) % MOD;
        }
        int res = 0;
        for (int i = 1; i <= maxValue; i++)
            f[1][i] = 1;

        for (int i = 1; i < 18; i++)
        {
            for (int j = 1; j <= maxValue; j++)
            {
                for (int k = 2 * j; k <= maxValue; k += j)
                    f[i + 1][k] = (f[i + 1][k] + f[i][j]) % MOD;
                if (i <= n)
                    res = (res + (long long)f[i][j] * Cab(n - 1, i - 1)) % MOD;
            }
        }
        return res;
    }
};
1
2
Runtime: 151 ms, faster than 84.07% of C++ online submissions for Count the Number of Ideal Arrays.
Memory Usage: 6.9 MB, less than 92.04% of C++ online submissions for Count the Number of Ideal Arrays.

Process Restricted Friend Requests

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
impl Solution {
    fn find(x: usize, p:&mut Vec<usize>) -> usize {
        return if p[x] == x {
            x
        } else {
            p[x] = Self::find(p[x], p);
            p[x]
        }
    }

    pub fn friend_requests(n: i32, restrictions: Vec<Vec<i32>>, requests: Vec<Vec<i32>>) -> Vec<bool> {
        let mut p = vec![0; (n + 1) as usize];
        for i  in 1..=n {
            p[i as usize] = i as usize;
        }
        let mut ans = vec![false; requests.len()];
        for i in 0..requests.len() {
            let (a, b) = (requests[i][0] as usize, requests[i][1] as usize);
            // 如果已经是朋友
            let pa = Self::find(a, &mut p);
            let pb = Self::find(b, &mut p);
            if pa == pb {
                ans[i] = true;
            } else {
                // pc 作为备份，如果失败则回退
                let pc = p.clone();
                // flag 表示是否可行
                let mut flag = true;
                p[pa] = pb;
                for j in 0..restrictions.len() {
                    let (x, y) = (restrictions[j][0] as usize, restrictions[j][1] as usize);
                    let px = Self::find(x, &mut p);
                    let py = Self::find(y, &mut p);
                    if px == py {
                        flag = false;
                        break;
                    }
                }
                if flag {
                    ans[i] = true;
                } else {
                    p = pc;
                }
            }
        }
        ans
    }
}

Number of Good Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size();
        vector<int> cnt(n, 1);
        vector<int> p(n);
        for (int i = 0; i < n; i++)
            p[i] = i;
        function<int(int)> find;
        find = [&](int x) -> int { return p[x] == x ? x : p[x] = find(p[x]); };
        sort(edges.begin(), edges.end(), [&](const vector<int> &a, const vector<int> &b) -> bool
            { return max(vals[a[0]], vals[a[1]]) < max(vals[b[0]], vals[b[1]]); });
        int ans = n;
        for_each(edges.begin(), edges.end(), [&](const auto &edge)
        {
            int a = find(edge[0]), b = find(edge[1]);
            if (vals[a] == vals[b])
            {
                ans += cnt[a] * cnt[b];
                p[a] = b;
                cnt[b] += cnt[a];
            } else if (vals[a] < vals[b])
                p[a] = b;
            else
                p[b] = a;
        });
        return ans;
    }
};·

Number of Visible People in a Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        stack<int> stk;
        vector<int> ans(heights.size());
        for (int i = heights.size() - 1; i >= 0; i--)
        {
            while (stk.size() && stk.top() <= heights[i]) 
            {
                ans[i]++; // 单调栈本身递减，故此前弹出的元素必定满足小于min(stk.top(), heights[i]);
                stk.pop();
            }
            if (stk.size()) // stk.top()比heights[i]高，所以仍能看到stk.top()，但不可能看到stk.top()之后的任何元素
                ans[i]++;
            stk.push(heights[i]);
        }
        return ans;
    }
};