leetcode 6.22-6.28

2020-06-28

1302 层数最深叶子节点的和
面试题16.02 单词频率

1302. 层数最深叶子节点的和

给你一棵二叉树，请你返回层数最深的叶子节点的和。

示例：

输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
输出：15

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/deepest-leaves-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

深度优先或广度优先搜索均可，通用方法是记录maxdepth，dep >= maxdepth时，记录和。

用修改过的分层层序遍历方法，返回最后一层的和即可。

AC代码：

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        std::queue<TreeNode*> q;
        if(root != NULL) q.push(root);
        int ret = 0;
        while(!q.empty()) {
            ret = 0;
            size_t cur_size = q.size();
            for(size_t i = 0; i < cur_size; i++) {
                auto p = q.front();
                q.pop();
                ret += p->val;
                if(p->left)  q.push(p->left);
                if(p->right) q.push(p->right);
            }
        }
        return ret;
    }
};

面试题16.02. 单词频率

设计一个方法，找出任意指定单词在一本书中的出现频率。

你的实现应该支持如下操作：

WordsFrequency(book)构造函数，参数为字符串数组构成的一本书
get(word)查询指定单词在书中出现的频率
示例：

WordsFrequency wordsFrequency = new WordsFrequency({“i”, “have”, “an”, “apple”, “he”, “have”, “a”, “pen”});
wordsFrequency.get(“you”); //返回0，”you”没有出现过
wordsFrequency.get(“have”); //返回2，”have”出现2次
wordsFrequency.get(“an”); //返回1
wordsFrequency.get(“apple”); //返回1
wordsFrequency.get(“pen”); //返回1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/words-frequency-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

有点疑惑，因为这个类只有get方法，所以在初始化的时候就用字典存，贼方便。

python类https://www.runoob.com/python/python-object.html

AC代码：

class WordsFrequency(object):

    def __init__(self, book):
        """
        :type book: List[str]
        """
        self.dic = {}
        for word in book:
            self.dic[word] = self.dic.get(word, 0) + 1


    def get(self, word):
        """
        :type word: str
        :rtype: int
        """
        return self.dic.get(word, 0)