LeetCode 213周赛题解-蒲公英云

LeetCode 213周赛题解

A-1640. 能否连接形成数组

题意：

给你一个整数数组 arr ，数组中的每个整数互不相同。另有一个由整数数组构成的数组 pieces，其中的整数也互不相同。请你以任意顺序连接 pieces 中的数组以形成 arr 。但是，不允许对每个数组 pieces[i] 中的整数重新排序。

如果可以连接 pieces 中的数组形成 arr ，返回 true ；否则，返回 false 。

思路：

由于每个数字都不相同，所以我们只要看每个子数组在arr中是否连续出现即可。

Code：

class Solution { 
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) { 
        for(auto v :pieces)
        { 
            int len = 0;
            for(int i = 0; i < arr.size(); ++i)
            { 
                int cnt = 0;
                for(int j = 0; j < v.size() && i + j < arr.size(); ++j)
                { 
                    if(v[j] == arr[i + j])
                        ++cnt;
                }
                len = max(len, cnt);
            }
            if(len != v.size())
                    return false;
        }
        return true;
    }
};

B-1641. 统计字典序元音字符串的数目

题意：

给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按字典序排列的字符串数量。

字符串 s 按字典序排列需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

思路：

用DP或者DFS其实都可以，我就说说我场上的写法，找到4的答案查了一波oeis发现就是n * (n - 1) * (n - 2) * (n - 3) / 24

Code：

class Solution { 
public:
    int countVowelStrings(int n) { 
        n = n + 4;
        return n*(n-1)*(n-2)*(n-3)/24;
    }
};

C-1642. 可以到达的最远建筑

题意：

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1（下标从 0 开始）时：

如果当前建筑物的高度大于或等于下一建筑物的高度，则不需要梯子或砖块
如果当前建筑的高度小于下一个建筑的高度，您可以使用一架梯子或 (h[i+1] - h[i]) 个砖块
如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标从 0 开始）。

思路：

贪心来讲，需要砖头较多的用梯子比较划算，所以我们用堆来维护ladders个最大的砖头数，看最远能延伸多远。

Code：

class Solution { 
public:
    priority_queue<int, vector<int>, greater<int> > q;
    long long sum = 0, now = 0;
    int furthestBuilding(vector<int>& heights, int bricks, int ladders)
    { 
        while(!q.empty()) q.pop();
        int ans = 0;
        for(int i = 1; i < heights.size(); ++i)
        { 
            int d = heights[i] - heights[i - 1];
            if(d > 0)
                q.push(d);
            if(q.size() > ladders)
                sum += q.top(), q.pop();
            if(sum <= bricks)
                ans = i;
        }
        return ans;
    }
};

D-5600. 第 K 条最小指令

题意：

Bob 站在单元格 (0, 0) ，想要前往目的地 destination ：(row, column) 。他只能向右或向下走。你可以为 Bob 提供导航指令来帮助他到达目的地 destination 。

指令用字符串表示，其中每个字符：

‘H’ ，意味着水平向右移动
‘V’ ，意味着竖直向下移动
能够为 Bob 导航到目的地 destination 的指令可以有多种，例如，如果目的地 destination 是 (2, 3)，“HHHVV” 和 “HVHVH” 都是有效指令。

然而，Bob 很挑剔。因为他的幸运数字是 k，他想要遵循按字典序排列后的第 k 条最小指令的导航前往目的地 destination 。k 的编号从 1 开始。

给你一个整数数组 destination 和一个整数 k ，请你返回可以为 Bob 提供前往目的地 destination 导航的按字典序排列后的第 k 条最小指令。

思路：

也就是给你n个‘V’和m个‘H’，让你找到字典序第k大的序列。

首先我们有C(n + m, m)种方案数，因为相当于在n+m中选择哪一次向下走。

那么我们就看第一次是用H还是用V，可以通过判断是否大于k来决定。然后就把剩下的子问题同样的步骤处理即可

Code：

typedef long long ll;
const int maxn = 30 + 10;
class Solution { 
public:
    ll C[maxn][maxn];
    string kthSmallestPath(vector<int>& destination, int k) 
    { 
        C[0][0] = 1; //组合数打表
        for(int i = 1; i < maxn; ++i)
        { 
            C[i][0] = C[i][i] = 1;
            for(int j = 1; j < i; ++j)
                C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
        int n = destination[1], m = destination[0], lim = n + m;
        string res;
        for(int i = 1; i <= lim; ++i)
        { 
            if(n >= 1 && C[n + m - 1][m] >= k) //看当前位是‘H’还是‘V’
            { 
                res.push_back('H');
                --n; //用过一个‘H’
            }
            else
            { 
                res.push_back('V');
                k -= C[n + m - 1][m];
                --m;
            }
        }
        return res;
    }
};