🌽第150周的题解

第一题

5048. 拼写单词

要求:
给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。
示例1：

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例2：

输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

思路：
直接把字符串问题转化成为一个大小为26的数组，对给定的「字母表」进行遍历，将数组的对应位置记录下每个字母出现了多少次，再循环一遍给出的「词汇表」，只要词汇表每个都比给定的字母表的数组元素小，那么就说明可以表示。

solution in cpp:

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int s[26],t[26],i,result = 0;
        memset(s,0,sizeof(s));
        for(auto c:chars)s[c-'a']++;
        for(auto d:words){
            memset(t,0,sizeof(t));
            for(auto e:d)t[e-'a']++;
            for(i=0;i<26;i++) if(s[i]<t[i]) break;
            if(i==26) result+=d.size();
        }
        return result;
    }
};

第二题

5052.最大层内元素和

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

请你找出层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
给定一个二叉树 大概长下面这样
实例：

输入：[1,7,0,7,-8,null,null]
输出：2
解释：
第 1 层各元素之和为 1，
第 2 层各元素之和为 7 + 0 = 7，
第 3 层各元素之和为 7 + -8 = -1，
所以我们返回第 2 层的层号，它的层内元素之和最大。

思路：
使用一个dict用来存储每一层的元素的值，每一对键值对都是层数和相对应的值的和，使用dfs遍历所有树的节点，同时将节点所在的层数传进去，传进去的同时直接访问对应的dict对应的元素,直接加起来，最后遍历一遍输出最大的值

• solution in cpp:

/**
 * 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:
    int s[10005], n;
    void dfs(TreeNode* root, int level){
        if(!root) return;
        n = max(n,level);
        s[level]+=root->val;
        dfs(root->left,level+1);
        dfs(root->right,level+1);
    }
    int maxLevelSum(TreeNode* root) {
        memset(s,0,sizeof(s));
        n = 0;
        dfs(root,1);
        int j = 1;
        for(int i = 1;i<=n;i++){
            if(s[i] > s[j])
                j = i;
        }
        return j;
    }
};

• solution in python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    
    def maxLevelSum(self, root: TreeNode) -> int:
        m,res,level = {},0,0
        def dfs(root,level):
            if root == None:
                return
            if level not in m:
                m[level] = 0
            m[level]+=root.val
            dfs(root.left,level+1)
            dfs(root.right,level+1)
        dfs(root, 1)
        min_ = -sys.maxsize
        for key in m.keys():
            if m[key] > min_:
                min_, res = m[key], key
        return res

第三题

5053.地图分析

你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。

我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。

如果我们的地图上只有陆地或者海洋，请返回 -1。

实例1：

输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。

太菜了 没做出来