leetcode解题思路分析（一百二十九）1079 - 1085 题

1079. 活字印刷
      你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

回溯

class Solution {
public:
    int numTilePossibilities(string tiles) {
        vector<int>count(26,0);
        for(char& ch:tiles){//统计字符频次
            count[ch-'A']++;
        }
        return dfs(count);
    }
    int dfs(vector<int>&count){
        int res=0;
        for(int i=0;i<26;++i){
            if(count[i]==0)continue;
            res++;
            count[i]--;
            res+=dfs(count);
            count[i]++;
        }
        return res;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1080. 根到叶路径上的不足节点
      给定一棵二叉树的根 root，请你考虑它所有 从根到叶的路径：从根到任何叶的路径。（所谓一个叶子节点，就是一个没有子节点的节点）假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为「不足节点」，需要被删除。请你删除所有不足节点，并返回生成的二叉树的根。

递归后续遍历判断即可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//DFS后序遍历
class Solution {
public:
    bool issufficient(TreeNode* root, int presum, int limit){
        //如果为空，也视为不足结点
        if(!root) return true;
        //如果左右孩子都为空
        if (root->left == NULL && root->right == NULL) {
            return presum + root->val < limit; //告诉上一层该结点是否为不足结点
        }
        //如果左右孩子不空
        bool left = issufficient(root->left, presum+root->val, limit); //去判断左孩子是否是不足结点
        bool right = issufficient(root->right, presum+root->val, limit); //判断右孩子是否是不足结点
        
        //如果左边是不足结点，删除左边
        if(left) root->left=NULL;
        //如果右边是不足结点，删除右边
        if(right) root->right=NULL;

        //返回值为当前结点是否为不足结点:如果左右孩子都是不足结点，当前肯定也是不足结点
        return left&&right;

    }
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        TreeNode* dummy = new TreeNode(0); //哑结点
        dummy->left = root;
        bool flag = issufficient(root, 0, limit); //检查以root为根结点的子树
        if(flag) dummy->left=NULL; //如果root自己都不满足，那就删掉
        return dummy->left; //如果root自己都被删了，那就相当于返回空
    }
};


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
39
40
41
42
43
44

1084. 销售分析III
      编写一个SQL查询，报告2019年春季才售出的产品。即仅在2019-01-01至2019-03-31（含）之间出售的商品。以 任意顺序 返回结果表。

# Write your MySQL query statement below
select
    product_id,
    product_name
from product
where product_id in (
    select
        product_id
    from sales
    group by product_id
    having max(sale_date) <= '2019-03-31'
    and min(sale_date) >= '2019-01-01'
)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1089. 复写零
      给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

记录多余的数即可，更好的方法是用双指针，不需要额外内存。

class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int  nSize = arr.size();
        queue<int> changeQueue;

        for (int i = 0; i < nSize; ++i)
        {
            if (changeQueue.size())
            {
                if (changeQueue.front() == 0)
                {
                    changeQueue.push(arr[i]);
                    arr[i] = 0;

                    if (i + 1 == nSize) break;

                    changeQueue.push(arr[i + 1]);
                    arr[i + 1] = 0;

                    changeQueue.pop();
                    i++;
                }
                else
                {
                    changeQueue.push(arr[i]);
                    arr[i] = changeQueue.front();
                    changeQueue.pop();
                }
            }
            else if (arr[i] == 0 && i < nSize - 1)
            {
                changeQueue.push(arr[i + 1]);
                arr[i + 1] = 0;
                i++;
            }
        }

        return;
    }
};
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
39
40
41
42

1090. 受标签影响的最大值
      我们有一个 n 项的集合。给出两个整数数组 values 和 labels ，第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。从 n 个元素中选择一个子集 s :子集 s 的大小 小于或等于 numWanted 。s 中 最多 有相同标签的 useLimit 项。一个子集的 分数 是该子集的值之和。返回子集 s 的最大 分数 。

1 将values[]和labels[]数组中的元素组成pair对
2 将pair对存到priori_queue中进行排序
3 定义一个map统计labels[]中的元素出现的次数
4 遍历priori_queue中的元素 找到符合条件的元素加到res

class Solution {
public:
    struct cmp{
        template<typename T, typename U>
        bool operator()(T const &a, U const &b){
            if(a.first < b.first) return true;
            else return false;
        }
    };
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        priority_queue<pair<int,int>, vector<pair<int,int> >, cmp> q;
        map<int, int> map;
        int count = 0;
        int res = 0;
        int len = values.size();
        for(int i = 0; i < len; i++) q.push({values[i], labels[i]});
        while(!q.empty()){
            auto pairs = q.top();
            if(count < numWanted && map[pairs.second] < useLimit){
                res += pairs.first;
                count++;
                if(map.count(pairs.second) == 0) map[pairs.second] = 1;
                else map[pairs.second] += 1;
            }
            q.pop();
        }
        return res;
    }
};

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

1091. 二进制矩阵中的最短路径
      给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

经典BFS

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid[0][0]==1)return -1;
        int n=grid.size(),ans=1;
        const int dire[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1}};
        queue<pair<int,int> > q;
        q.emplace(0,0);         //从0,0开始
        grid[0][0]=1;           //标记为1代表走过
        while(!q.empty()){      //bfs
            int m=q.size();
            while(m--){
                auto [x,y]=q.front();
                q.pop();
                if(x==n-1&&y==n-1)return ans;
                for(int i=0;i<8;i++){                       //遍历八个方向的
                    int nx=x+dire[i][0];
                    int ny=y+dire[i][1];
                    if(nx<0||ny<0||nx>=n||ny>=n)continue;   //判断是否越界
                    if(grid[nx][ny]==0){        //判断是否能走
                        q.emplace(nx,ny);
                        grid[nx][ny]=1;         //标记
                    }
                }
            }
            ans++;          //记录循环次数
        }
        return -1;
    }
};

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

1092. 最短公共超序列
      给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。

先求最大公共子序列，然后将两个字符串中不在公共序列的拼接上即可（拼接利用动态规划求的dp来判断是否是公共子序列中的元素）

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        string ans;
        int m = str1.size(), n = str2.size();
        //求公共子序列
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                if(str1[i-1] == str2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        int i = m, j = n;
        //从后向前回溯加上字符串
        while(dp[i][j] > 0){
            if(str1[i - 1] == str2[j - 1]){
                //如果只在这里进行push_back这题就变成了求其中一个最长的重复子串的问题了，求超序列就是将不匹配的地方也求进去
                ans.push_back(str1[i - 1]);
                i--;
                j--;
            }
            else{
                if(dp[i-1][j] >= dp[i][j-1]){
                    ans.push_back(str1[i - 1]);
                    i--;
                }
                else{
                    ans.push_back(str2[j - 1]);
                    j--;
                }
            }
        }
        //到这里字符串1的前i和字符串2的前j个字符完全不匹配,将这些字符全部加上即可,顺序随意
        while(i > 0 || j > 0){
            for(int k = i; k > 0; --k){
                ans.push_back(str1[k - 1]);
                i--;
            }
            for(int k = j; k > 0; --k){
                ans.push_back(str2[k - 1]);
                j--;
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};


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
39
40
41
42
43
44
45
46
47
48
49
50
51
52