LeetCode 周赛题解 213

ACM算法日常

发布于 2020-11-10 14:03:33

5550

发布于 2020-11-10 14:03:33

文章被收录于专栏：ACM算法日常

5554. 能否连接形成数组

「知识点：暴力」

因为 arr 和 pieces 中都不包含重复的数字，所以直接在pieces中暴力寻找 arr[i] 即可，然后连续的元素是否相同即可。

class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        for (int i = 0; i < arr.size();) {
            int cur = i;
            for (int j = 0; j < pieces.size(); j++) {
                // 在 pieces 中寻找 arr[i]
                if (pieces[j][0] == arr[i]) {
                    bool flag = true;
                    // 检查连续的元素是否都相等
                    for (int k = 0; k < pieces[j].size() && flag; k++) {
                        if (pieces[j][k] != arr[i+k]) {
                            flag = false;
                        }
                    }
                    if (flag == false) {
                        return false;
                    }
                    i += pieces[j].size();
                    break;
                }
            }
            if (cur == i) {
                return false;
            }
        }
        return true;
    }
};

5555. 统计字典序元音字符串的数目

「知识点：排列组合，递推」

解法一，递推。

设 f(i,j) 表示长度为 i，以字符 j 结尾的字符串数量。根据题目要求，可以得出如下式子：

f(i,j) = \left\{ \begin{array}{c} 1, i = 0 \\ \sum_{k=0}^{j} f(i-1, k), i >0 \\ \end{array}\right.

class Solution {
public:
    int dp[51][5] = {0};
    int countVowelStrings(int n) {
        dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1;
        for (int i = 2; i <= n; i++) {
            for(int j = 0; j <= 4; j++) {
                for(int k = 0; k <= j; k++) {
                    dp[i][j] += dp[i-1][k]; 
                }
            }
        }
        return dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4];
    }
};

解法二，排列组合。

可以用高中时的隔板法来考虑这个问题。现在有 n 个小球排成一排，要用四块隔板将其分成五份，每一份均可为空，从前向后分别对应着a,e,i,o,u。

n 个小球，一共有 n+1 个缝隙可以放入隔板，设这 n+1 个位置对应 [1, n+1] 中的数字，四个隔板放置的位置为

p_1, p_2, p_3, p_4

，并满足如下关系：

1 <= p_1 <= p_2 <= p_3 <= p_4 <= n+1

。

令

{p_i}\prime = p_i + i

，则每一种放置方案

(p_1, p_2, p_3, p_4)

都有

(p_1\prime, p_2\prime, p_3\prime, p_4\prime)

与之一一对应，且满足如下关系：

1 <= p_1\prime < p_2\prime < p_3\prime < p_4\prime <= n+1+3

也就是在 n+4 个数字中选取 4 个不同的数字，即

C_{n+4}^4

。


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

5556. 可以到达的最远建筑

「知识点：贪心，排序」

假设移动到下一个建筑时，需要消耗一架梯子或者若干块砖，那么该如何抉择呢？

可以使用贪心的思维来考虑：梯子相当于不可拆分的无限块砖，应该用在高度差最大的地方。换言之，如果有 k 个梯子，应该优先用在高度差最大的k次移动，剩下的地方用砖补齐。

从前向后遍历 heights，遍历过程中使用优先队列维护最大的 k 个高度差，当其他高度差的累加和超过砖数时，就到达了可以最远建筑。

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

5600. 第 K 条最小指令

「知识点：组合数」

一共要发送row 次 'H' 指令，cloumn 次 'V' 指令，

因此有

C_{row+column}^{column}

种不同的指令集。

因为 'H' < 'V'，所以有：

当第一个指令为 'H' 时，只能构造出前

C_{row+column-1}^{column}

个指令集。

当第一个指令为 'V' 时，只能构造出后

C_{row+column-1}^{column-1}

个指令集。

所以可以比较

C_{row+column-1}^{column}

和 k 的大小关系，来决定应该选取哪个指令。

依此类推，我们得到了一个递归的解法，设 f(row, column, k) 为第 k 个字符串，则有：

f(row, column, k) = \left\{ \begin{array}{c} std::string(column, 'V'), row = 0 \\ std::string(row, 'H'), column = 0 \\ 'H' + f(row-1, column, k), k <= C_{row+column-1}^{column}\\ 'V' + f(row, column-1, k-C_{row+column-1}^{column}), k >C_{row+column-1}^{column} \\ \end{array}\right.

组合数的计算也可以借助下述递归公式来完成~

C_n^m = \left\{ \begin{array}{c} 1, m == 0 || n == m \\ C_{n-1}^m + C_{n-1}^{m-1}, n >m > 0 \\ \end{array}\right.

class Solution {
public:
    
    int mat[100][100];
 
    int calc(int n, int m) {
        if (m == 0 || m == n) {
            return 1;
        }
        if (mat[n][m] != -1) {
            return mat[n][m];
        }
        mat[n][m] = calc(n-1, m) + calc(n-1, m-1);
        return mat[n][m];
    }
    int combine(int H, int V) {
        int n = H+V;
        int m = V;
        return calc(n, m);
    }
    std::string dfs(int H, int V, int k) {
        if (H == 0 && V == 0) {
            return "";
        }
        if (H == 0) {
            return std::string(V, 'V');
        }
        if (V == 0) {
            return std::string(H, 'H');
        }
        int cnt = combine(H-1, V);
        if (k <= cnt) {
            return "H" + dfs(H-1, V, k);
        }
        return "V" + dfs(H, V-1, k - cnt);
    }
    string kthSmallestPath(vector<int>& destination, int k) {
        memset(mat, -1, sizeof(mat));
        return dfs(destination[1], destination[0], k);
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-11-02，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度