Leetcode 第140场周赛解题报告

字数统计: 2.3k阅读时长: 9 min

 2019/04/21 

今天的题目难度适中。第二道题计算排列数，实际上是有优化方法的，但是题目的测试数据比较宽松，暴力就可以过掉。

今天比赛的主题可以归纳为「暴力」，都用最直白，最直接的方法，都可以过掉题目。

在实际编程工作中，大多数是把一个模型实现为程序，用所谓「直白」的方法。

有一种方法论，叫做先实现，再优化。先想办法实现，保证正确性，然后再逐渐优化，让性能越来越好。性能优化到什么样才停止呢？满足当前要求就可以停止。因为性能优化也是要付出代价和成本的，「够用」最好。当然要有技术储备，当需要进一步优化的时候能够立刻去做。

做比赛也是一样，能够在有限的时间内，在题目的要求下，过掉题目是最好的。至于最优算法，可以比赛结束后慢慢研究。

上面的方法论第一步有时也叫做原型。做原型类似于做个demo，用现有工具快速实现。在语言侧python有很大优势，库很全。既有类似shell的语法简洁功能强大，又有类似C的语法约束，不至于看不懂。缺点当然是性能了。但是能够让人专注于实现逻辑，本身已经很强大了。

例如许多字符串操作，像把文本按空格分成单词，在python中只要一句话，这些在C++中就只能干捉急了，没个三五行，再加上些检查和约束，根本写不出来。

语言都是工具，没有高低贵贱之分，要看应用场景。

下面是详细的题解和思考。

比赛的地址 Weekly Contest 140

https://leetcode-cn.com/contest/weekly-contest-140

1. Bigram 分词

题目：

Bigram 分词(Occurrences After Bigram)

地址：

https://leetcode-cn.com/contest/weekly-contest-140/problems/occurrences-after-bigram/

题意：

给出第一个词 first 和第二个词 second，考虑在某些文本 text 中可能以 “first second third“ 形式出现的情况，其中 second 紧随 first 出现，third 紧随 second 出现。

对于每种这样的情况，将第三个词 “third“ 添加到答案中，并返回答案。

思路：

题目比较直白，就是给出两个单词，和一段文本，让返回所有的出现在这两个单词组成的短语后挨着的第三个单词。

例如：

1 2	输入：text = "alice is a good girl she is a good student", first = "a", second = "good" 输出：["girl","student"]

把两个单词先拼成一个短语，然后在文本中查找该短语。找到后，输出短语后的下一个单词。然后从上次查找到的短语的尾部继续上面的操作，直至找到文本结尾。

class Solution {
public:
    vector<string> findOcurrences(string text, string first, string second) {
        string str = first + " " + second + " ";
        vector<string> res;
        string::size_type start = 0;
        string::size_type pos = 0;
        while((pos = text.find(str, start))!=text.npos)
        {
            string::size_type spacepos = text.find(" ", pos + str.length());
            string tmp = text.substr(pos + str.length(), spacepos - (pos + str.length()));
            if(tmp != "")
                res.push_back(tmp);
            start = pos + str.length();
        }
        return res;
    }
};

2. 活字印刷

题目：

活字印刷(Letter Tile Possibilities)

地址：

https://leetcode-cn.com/contest/weekly-contest-140/problems/letter-tile-possibilities/

题意：

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
1
2
3
输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

思路：

给定一个字母集合，然后求用这些字母，可以组成的字母排列的个数。

这是一道数学题，如果用手算，最好的方法是计算出全排列的数量，然后再除以每个重复的排列个数。例如”AAABBC”组成的6个字母的排列数为A（6，6）/[A(3,3)*A(2,2)]。

但是做这个题目用这个方法有点难写，最简单的方法，就是枚举所有的排列，然后汇总结果。

代码：

class Solution {
public:
    map<char, int> mp;
    int dfs(int width, int pos)
    {
        if(pos > width)
        {
            return 1;
        }
        int sum = 0;
        for(auto iter = mp.begin(); iter!=mp.end(); ++iter)
        {
            char key = iter->first;
            int value = iter->second;
            if(value == 0)
                continue;
            iter->second--;
            sum += dfs(width, pos+1);
            iter->second++;
        }
        return sum;
    }
    int numTilePossibilities(string tiles) {
        int res = 0;
        for(char ch : tiles)
        {
            mp[ch]++;
        }
        for(int i = 1; i <= tiles.size(); ++i)
        {
            int cnt = dfs(i, 1);
            res += cnt;
        }
        return res;
    }
};

3. 根到叶路径上的不足节点

题目：

根到叶路径上的不足节点(Insufficient Nodes in Root to Leaf Paths)

地址：

https://leetcode-cn.com/contest/weekly-contest-140/problems/insufficient-nodes-in-root-to-leaf-paths/

题意：

给定二叉树的根 root，考虑所有从根到叶的路径：从根到任何叶的路径。（叶节点是没有子节点的节点。）

如果交于节点 node 的每个根到叶路径的总和严格小于限制 limit，则该节点为不足节点。

同时删除所有不足节点，并返回生成的二叉树的根。

思路：

题目的意思是，从根节点到每个叶子节点所经过的路径的节点和，如果大于等于limit，则这条路径上所有的节点都留下来。最终没留下来的节点删掉。

如果这样理解题意，做起来会简单些。

方法一：

最简单的方法，进行深度优先搜索，例如先序遍历。到达叶节点，统计从根到叶子所经过的路径和。如果大于limit则把路径经过的节点都染色「保留」，否则染色「删除」。

最后保存所有「保留」的节点，就是答案。

方法一最好想，也容易实现，但是要辅助存储和经过两次遍历。对于这道题是可以过掉的。

在方法一的基础上可以优化下，达到一次遍历就能够得到最终结果。

对于一个节点，最终是否要删掉，满足的条件是：所有经过该节点的路径和都是小于limit的。

虽然有多个子节点，有多条路径，但是我们只要考虑和最大的哪条路径是否小于limit就可以了。因为只要有一条路径大于等于limit的值，就可以保留该节点。

方法二：

采用后序遍历，父节点到该节点的路径和，获取左右两个儿子节点路径和的最大值。求出经过该节点的路径和的最大值，如果最大值小于limit，则让父节点删掉当前节点，否则让父节点保留当前节点。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    pair<TreeNode* , int> dfs(TreeNode* root, int limit, int sum)
    {
        if(root == nullptr)
            return {nullptr, 0};
        
        pair<TreeNode* , int> l, r;
        l = dfs(root->left, limit, sum+root->val);
        r = dfs(root->right,limit, sum+root->val);
        root->left = l.first;
        root->right = r.first;
        
        int maxsum = max(l.second, r.second);
        
        if(maxsum + sum + root->val < limit)
            return {nullptr, maxsum + root->val};
        
        return {root, maxsum + root->val};
    }
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        pair<TreeNode* , int> ans;
        ans = dfs(root, limit, 0);
        return ans.first;
    }
};

4. 不同字符的最小子序列

题目：

不同字符的最小子序列(Smallest Subsequence of Distinct Characters)

地址：

https://leetcode-cn.com/contest/weekly-contest-140/problems/smallest-subsequence-of-distinct-characters/

题意：

返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
1
2
输入："cdadabcc"
输出："adbc"

思路：

用贪心的方法。

对于每个text中的字符，如果该字符已经出现在最终的结果中，则不必再处理。

对于还没出现在最终结果中的字符text[i]。如果该字符只剩下一个，那么该字符要马上加入到结果中。如果该字符还有多个，那么查看在该字符右侧出现的字符中，是否有小于该字符的字符text [ j ] (j > i) 出现。如果选择text[j]作为本轮输出的字符，还要满足在i到j-1中所有未出现在结果的字符的数量，都要是大于1的。否则不能满足相对顺序和text中的一致。因为如果小于等于1，在j的右侧，就不会再有该字符出现了，那么最终结果也不会包含该字符了。

代码：

class Solution {
public:
    map<char, int> mp;
    string dfs(string text, int startpos, int n, string cur)
    {
        char ch='z' + 1;
        int pos;
        int i;
        for(i = startpos; i < n; ++i)
        {
            if(mp[text[i]] == -1)
                continue;
            if(text[i]<ch)
            {
                ch = text[i];
                pos = i;
            }
            mp[text[i]]--;
            if(mp[text[i]]==0)
            {
                for(int j = pos + 1; j <=i; ++j)
                    if(mp[text[j]]!=-1)
                        mp[text[j]]++;
                break;
            }
        }
        if(i==n)
            return cur;
        mp[ch] = -1;
        return dfs(text, pos+1, n, cur+ch);
    }
    string smallestSubsequence(string text) {
        for(char ch : text)
            mp[ch]++;
        string res;
        res = dfs(text, 0, text.size(), "");
        return res;        
    }
};

原文作者：owenzhang

原文链接：https://yunpengzhang.github.io/2019-Leetcode-%E7%AC%AC140%E5%9C%BA%E5%91%A8%E8%B5%9B%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A/

发表日期：April 21st 2019, 10:00:03 am

更新日期：April 21st 2019, 10:00:03 am

Next Post

Leetcode 第139场周赛解题报告
Previous Post

Leetcode 第157场周赛解题报告

CATALOG

1. 1. Bigram 分词
2. 2. 活字印刷
3. 3. 根到叶路径上的不足节点
4. 4. 不同字符的最小子序列