LeetCode 213周赛题解

淡淡的烟草味﹌ 2022-11-21 15:08 172阅读 0赞

## A-[1640. 能否连接形成数组][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. 统计字典序元音字符串的数目][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. 可以到达的最远建筑][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 条最小指令][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;
    	}
    };

[1640.]: https://leetcode-cn.com/problems/check-array-formation-through-concatenation/
[1641.]: https://leetcode-cn.com/problems/count-sorted-vowel-strings/
[1642.]: https://leetcode-cn.com/problems/furthest-building-you-can-reach/
[5600. _ K]: https://leetcode-cn.com/problems/kth-smallest-instructions/