A.能否连接形成数组

解题思路：
暴力。从第一位开始枚举，如果piece[i] 可以满足，则加上piece[i] 的长度继续枚举。
代码展示：

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
class Solution {
public:
    vector<int> arr,vis;
    vector<vector<int>> pieces;
    int n,m;
    bool tmp;
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        this->arr = arr;
        this->pieces = pieces;
        n = arr.size();
        tmp = false;
        m = pieces.size();
        vis.resize(m,false);
        dfs(0);
        return tmp;
    }
    bool isok(int k,int t){
        for(int i = 0;i < pieces[t].size();i++)
            if(pieces[t][i] != arr[k + i])  return false;
        return true;
    }
    void dfs(int k){
        if(k >= n){
            tmp = true; return ;
        }
        for(int i = 0;i < m;i++){
            if(!vis[i] && isok(k,i)){
                vis[i] = true;
                dfs(k + pieces[i].size());
                vis[i] = false;
            }
        }
    }
};

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

解题思路：
动态规划。dp[i] [0], dp[i] [1] ……dp[i] [4]，记为长度为 i 的字符串为a,e,i,o,u开头的合法字符串个数。所以递推公式为：
$$
dp[i][j] = \sum\limits_{k=j}^4dp[i-1][k]
$$
代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countVowelStrings(int n) {
        int dp[55][5];
        memset(dp,0,sizeof(dp));
        for(int i = 0;i < 5;i++)    dp[1][i] = 1;
        for(int i = 2;i <= n;i++){
            for(int j = 0;j < 5;j++){
                for(int k = j;k < 5;k++)
                    dp[i][j] += dp[i-1][k];
            }
        }
        int ans = 0;
        for(int i = 0;i < 5;i++)    ans += dp[n][i];
        return ans;
    }
};

C.可以到达的最远建筑

解题思路：
贪心，优先队列。从左往右的移动，优先使用砖头，当砖头不够用时，如果无梯子，则当前位置即为能到达最远位置，如果有梯子，将到下一个位置所需要的砖头数与之前每一次使用的砖头数的大值替换成梯子，用优先队列存放每次使用的砖头数。
代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue <int,vector<int>,less<int> > q;
        int n = heights.size();
        for(int i = 0;i < n - 1;i++){
            if(heights[i] >= heights[i + 1])    continue;
            int x = heights[i + 1] - heights[i];
            if(x <= bricks){
                q.push(x);
                bricks -= x;
            }else{
                bricks -= x;
                if(ladders--){
                    q.push(x);
                    bricks += q.top();
                    q.pop();
                }else
                    return i;
            }
        }
        return n - 1;
    }
};

D.第 K 条最小指令

解题思路：
组合数学。优先确定高位，用组合数算出以H为高位接下来有t种方案，如果t>=k，则确定高位为H，否则为V，如果为V则减去以H为高位的所有方案。

代码展示：

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
typedef long long ll;
class Solution {
public:
    int k,cnt;
    string res;
    ll dp[50][50];
    string kthSmallestPath(vector<int>& destination, int k) {
        dp[1][0]=dp[1][1]=1;
        for(int i=2;i<=30;++i){
            dp[i][0]=dp[i][i]=1;
            for(int j=1;j<i;++j){
                dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            }
        }
        int r = destination[0], c = destination[1]; //r个V c个H
        int n = r + c; 
        res = "";
        for(int i = 0;i < n;i++){
            if(!c)  {
                res += 'V';continue;
            }
            if(!r)  {
                res += 'H';continue;
            }
            ll t = dp[r+c-1][c-1];
            if(t >= k){
                res += 'H';
                c--;
            }else{
                k -= t;
                res += 'V';
                r--;
            }
        }
        return res;
        
    }
};

做题情况：
AC 三题
排名：351 / 3826

总结反思：
第三题忘记把当前的使用砖头数减去，导致wa了一发。第四题一开始想到的是递归回溯的方法，写了半天T了。