LeetCode——第 213 场周赛

2020-11-27

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

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

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

示例 1:

输入:arr = [85], pieces = [[85]]
输出:true
示例 2:

输入:arr = [15,88], pieces = [[88],[15]]
输出:true
解释:依次连接 [15] 和 [88]
示例 3:

输入:arr = [49,18,16], pieces = [[16,18,49]]
输出:false
解释:即便数字相符,也不能重新排列 pieces[0]
示例 4:

输入:arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
输出:true
解释:依次连接 [91]、[4,64] 和 [78]
示例 5:

输入:arr = [1,3,5,7], pieces = [[2,4,6,8]]
输出:false

提示:

1 <= pieces.length <= arr.length <= 100
sum(pieces[i].length) == arr.length
1 <= pieces[i].length <= arr.length
1 <= $arr[i], pieces[i][j]$ <= 100
arr 中的整数 互不相同
pieces 中的整数 互不相同(也就是说,如果将 pieces 扁平化成一维数组,数组中的所有整数互不相同)

**思路直接暴力即可,因为每个数均不相同,只需记录第一个vector内的每个vector的开头元素及其对应的下标即可,然后扫一遍第二个vector判断:

  1. 如果当前数没有对应的下标则返回false
  2. 如果当前数有对应的下标,那么两个vector同时向后遍历,如果遇到中间有元素不相同则返回false
  3. 其余情况返回true

代码

const int N=1e5+10;
class Solution {

int vis2[N];
int idx[N];
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        int len=pieces.size();
        for(int i=0;i<len;i++) {
            int x=pieces[i][0];
            idx[x]=i;
            vis2[x]=1;
        }
        int len3=arr.size();
        bool flag=true;
        int len2=0;
        for(int i=0;i<len3;i++) {
            int x=idx[arr[i]];
            if(vis2[arr[i]]==0) {
                flag=false;
                break;
            }
            len2=pieces[x].size();
            int j=0;
            while((j<len2&&i<len3)&&arr[i]==pieces[x][j]) i++,j++;
            if(j<len2) {
                flag=false;
                break;
            }
            if(i>=len3) break;
            i--;
        }
        return flag;
    }
};

一个坑点是:c++为class分配的是堆内存,所以对应的数组或者变量应该开在类里面,相当于全局变量

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

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

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

示例 1:

输入:n = 1
输出:5
解释:仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]
示例 2:

输入:n = 2
输出:15
解释:仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意,"ea" 不是符合题意的字符串,因为 'e' 在字母表中的位置比 'a' 靠后
示例 3:

输入:n = 33
输出:66045

思路:
两个思路:第一个直接dfs,第二个找规律递推

思路一:dfs

class Solution {
    int cnt = 0;
    public void dfs(int i, int cur, int n){
        if (cur == n - 1){
            cnt += 1;
            return ;
        }
        for (int j = i ; j < 5; j++){
            dfs(j, cur + 1, n);
        }
    }
    
    public int countVowelStrings(int n) {
        for (int i = 0; i < 5; i++){
            dfs(i, 0, n);
        }
        return cnt;
    }
}

思路二:线性DP递推
容易发现每一个a向后可以延伸5中情况,e对应四种情况.....

class Solution {
public:
    int countVowelStrings(int n) {
        int num[10]={0,1,0,0,0,0};
        int sum=0;
        for(int i=1;i<n;i++) {
            for(int j=1;j<=5;j++) {
                num[j]+=num[j-1];
            }
        }
        int res=num[1]*5+num[2]*4+num[3]*3+num[4]*2+num[5];
        return res;
    }
};

网上找到了一个可以展现清晰思路的代码

int countVowelStrings(int n) {
        int a=5;
        int e=4;
        int i=3;
        int o=2;
        int u=1;
        if(n==1) return a;

        for(int j=3;j<=n;j++){
            a=(a+e+i+o+u);
            e=(e+i+o+u);
            i=(i+o+u);
            o=(o+u);
            u=u;
        }
        return a+e+i+o+u;
}

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

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

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

当从建筑物 i 移动到建筑物 i+1(下标 从 0 开始 )时:

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

输入:heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
输出:4
解释:从建筑物 0 出发,你可以按此方案完成旅程:

  • 不使用砖块或梯子到达建筑物 1 ,因为 4 >= 2
  • 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子,因为 2 < 7
  • 不使用砖块或梯子到达建筑物 3 ,因为 7 >= 6
  • 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子,因为 6 < 9
    无法越过建筑物 4 ,因为没有更多砖块或梯子。
    示例 2:

输入:heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
输出:7
示例 3:

输入:heights = [14,3,19,3], bricks = 17, ladders = 0
输出:3

提示:

1 <= heights.length <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= heights.length

思路:
可以有两种贪心思路:1、让所有的砖头先填,如果填完了就拿梯子替换掉前面出现的最大的砖头,并维护这样一个由砖头组成的大根堆即可,如果梯子和砖头都用完了,则结束掉循环即可,时间复杂度$O(Nlog_2N)$

2、先拿梯子填,并维护一个小根堆,放需要补充的砖块数量,等梯子填完了,再用砖块去替代里面最小的砖块数量,等砖块没了就继续拿梯子填,总体都是一个维护的过程

代码:

class Solution {
    priority_queue<int,vector<int>,less<int> >q;
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        
        int len=heights.size();
        int i;
        for(i=0;i<len-1;i++) {
            if(heights[i]<heights[i+1]) {
                //还有砖头
                int cz=heights[i+1]-heights[i];
                q.push(cz);
                if(bricks>=cz) {
                   // cout<<cz<<'\n';
                    bricks-=cz;
                }
                else {
                    //没有砖头但有梯子
                    if(ladders>0) {
                        if(q.size()) {
                            int top=q.top();
                            q.pop();
                            bricks+=top;
                            bricks-=cz;
                        }
                        ladders--;
                    //    puts("yes");
                    }
                    //既没有砖头也没有梯子
                    else {
                        break;
                    }
                }
            }
        }
        return i;
    }
};

D、1643. 第 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 条最小指令 。

示例 1:
image.png

输入:destination = [2,3], k = 1
输出:"HHHVV"
解释:能前往 (2, 3) 的所有导航指令 按字典序排列后 如下所示:
["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].
示例 2:
image.png

输入:destination = [2,3], k = 2
输出:"HHVHV"
示例 3:
image.png

输入:destination = [2,3], k = 3
输出:"HHVVH"

提示:

destination.length == 2
1 <= row, column <= 15
1 <= k <= nCr(row + column, row),其中 nCr(a, b) 表示组合数,即从 a 个物品中选 b 个物品的不同方案数。

题意转化:容易发现从$(0,0)$走到$(2,3)$,必然要有两个两个V,和3个H,而我们要求的排列之后第k小的字符串:容易发现肯定是先从H开始排,如果将H看成0,而将V看成1,那么转化为2个1和三个0进行排列,第k小是多少?
即00011这是第一小,000101这是第二小.....我发现这样算的话并不能找到什么太好的规律,但是可以从dfs进行搜索。这只是一个思路拓展,那么以后是否遇到只包含0、1的字符串让求其按字典序排列后的第k小的时候便可以转化成走方格问题,我们再根据这个题去分析,很容易发现这其实是数字三角形模型DP的一个变形,具体的可以转移到另外一篇博客学习,需要解决的一个问题是如何满足第k小呢?有以下几个性质:

1. 假设存在第k小那么可以证明前面一定至少有k-1个解决方案,由此我们在这个前提下可以尽可以的选择向'H'即水平向右走,但如果方案数小于这个的话,那么只能增大当前序列,即不能再选择‘H’,而是选择‘V’。
2. dfs对整个路线进行搜索的时候要注意临界情况的取值,即当我们走到最下边的时候只能向右走,当我们走到最右边的时候只能向下走,而假设我们所处位置为$(x,y)$,那么如果向右走的方案数大于等于k即可向右走,反之只能向下走,即满足$dp(x+1,y)>=k$时。

代码:

class Solution {
public:
    vector<vector<int>> dp;
    
    string ans;
    int n,m;
    void dfs2(int x,int y,int k){
        if(x==n-1 && y==m-1) return;
        if(x==n-1){
            //位于右边线,直接一条路走到黑
            ans.push_back('H');
            dfs2(x,y+1,k);
            return;
        }else if(y==m-1){
            //位于下边线,一条路走到黑即可
            ans.push_back('V');
            dfs2(x+1,y,k);
            return;
        }else if(k<=dp[x][y+1]){
            //向右走
            ans.push_back('H');
            dfs2(x,y+1,k);
        }else{
            //向下走
            ans.push_back('V');
            dfs2(x+1,y,k-dp[x][y+1]);
        }
    }
    void dfs(int x,int y,int k)
    {
        if(x==n-1&&y==m-1) return ;
        if(x==n-1) {//到达底边
            ans.push_back('H');
            //ans+='H';
            dfs(x,y+1,k);
            return ;
        }
        else if(y==m-1) {//到达最右边
             ans.push_back('V');
            dfs(x+1,y,k);
            return ;
        }
        else if(dp[x][y+1]>=k){//其他情况 如果想要向右走
             ans.push_back('H');
            dfs(x,y+1,k);
            return ;
        }
        else {//如果选择了向下走,那么就将向右走的方案数减去
            ans.push_back('V');
            dfs(x+1,y,k-dp[x][y+1]);
        }
    }

    string kthSmallestPath(vector<int>& destination, int k) {
        
        n=destination[0]+1,m=destination[1]+1;
        dp.resize(n,vector<int>(m,0));
        for(int i=0;i<m;i++) dp[n-1][i]=1;
        for(int i=0;i<n;i++) dp[i][m-1]=1;
        for(int i=n-2;i>=0;i--){
            for(int j=m-2;j>=0;j--){
                dp[i][j]=dp[i+1][j]+dp[i][j+1];
            }
        }
        dfs(0,0,k);
        return ans;
    }
};

思路2:组合计数
本题的确是组合计数题,而dp状态其实就相当于求组合数,即
杨辉三角,而在我们构建第k小的字符串的时候满足一下性质:

1:"H"和"V"的个数分别为destination[1]和destination[0],记为h,v;
2:以第一个字符是"H"开头的字符串共有C(h+v-1,h-1); #这里C(n,m)表示组合数
3:比较k和C(h+v-1,h-1)的大小:

------如果k大,则说明以"H"开头的所有答案中均小于k,因此第一个字符为"V",则剩余"V"的数量为v--,此时还要更新k的值,让k-C(h+v-1,h-1),而为何要更新k呢?是因为从这时候我们填的数是‘V’,而我们组合数求的是C(h+v-1,h-1)求的是填H的,因此每遇到一次k大证明,填‘H’的方案数不够了,即如果继续填‘H’组不成第k个了,因此要填‘V’,而一旦我们填了‘V’,就相当于重新继续填‘H’,即前面的序列已经确定,接下来重复此过程即可。一定要理解是对‘H’进行的求组合数;
------如果k不大,则说明第一个字符就是"H",剩余"H"的数量为h--;

重复上述2,3过程,直到$h==0||v==0$此时剩余的直接加上就行

代码

class Solution {
public:
    //vector<vector<int>> dp;
    
    string kthSmallestPath(vector<int>& destination, int k) {
        
        int v=destination[0],h=destination[1];
        vector<vector<int>> dp(h + v, vector<int>(h));
        //dp.resize(n+m,vector<int>(m,0));
	//求组合数
        dp[0][0]=1;
        for(int i=1;i<h+v;i++) {
            dp[i][0]=1;
            for(int j=1;j<=i&&j<h;j++) {
                dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            }
        }
        string ans="";
        
        while(h>0&&v>0){
            int zh=dp[h+v-1][h-1];//当前从h+v-1中选h-1个‘H’的方案数
            if(k<=zh) {//若比k大 则继续填‘H’可以构造出第k个
                h--;
                ans+='H';
            }
            else {//反之只能填‘V’,并且接下来构造的也不是k个而是k-zh个解释看上方
                v--;
                ans+='V';
                k-=zh;
            }
        }
        
        if(v==0) {//如果v=0并且h大于则一直填h 相当于dfs中走到了最底边
            while(h>0) {
                ans+='H';
                h--;
            }
        }
        if(h==0) {///相当于走到了最右边
            while(v>0) {
                ans+='V';
                v--;
            }
        }
        
        return ans;
    }
};

标题:LeetCode——第 213 场周赛
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2020/11/27/1606453093390.html