LeetCode-Weekly Contest 150

1160. 拼写单词

https://leetcode-cn.com/classic/problems/find-words-that-can-be-formed-by-characters/description/

给你一份『词汇表』（字符串数组） 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。

提示：
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
所有字符串中都仅包含小写英文字母

先遍历一次chars记录各字母数量num，然后分别遍历各word记录其各字母数量vis，然后比较就行了

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) 
    {
        int N=chars.length();
        int count=0;
        vector<int> num(26,0);
        for(int i=0;i<N;i++) num[chars[i]-'a']++;
        for(int i=0;i<words.size();i++)
        {
            vector<int> vis(26,0);
            int M=words[i].size();
            for(int j=0;j<M;j++) vis[words[i][j]-'a']++;
            for(int j=0;j<26;j++)
            {
                if(vis[j]>num[j]) break;
                else if(j==25) count+=M;
            }
        }
        return count;
    }
};

1161. 最大层内元素和

https://leetcode-cn.com/classic/problems/maximum-level-sum-of-a-binary-tree/description/

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
请你找出层内元素之和最大的那几层（可能只有一层）的层号，并返回其中最小的那个。

示例：

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

提示：
树中的节点数介于 1 和 10^4 之间
-10^5 <= node.val <= 10^5

用deep记录深度，先序遍历二叉树，每次更新deep深度，同深度求和num[deep]，最后求最大值的deep就行了

/**
 * 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 deep=1;
    // vector<int> num(20,0);
    int num[50];
    void findtree(TreeNode* root)
    {
        num[deep]+=root->val;
        if(root->left!=NULL) 
        {
            deep++;
            findtree(root->left);
            deep--;
        }
        if(root->right!=NULL) 
        {
            deep++;
            findtree(root->right);
            deep--;
        }
    }
    int maxLevelSum(TreeNode* root) 
    {
        findtree(root);
        int maxx=0,ans=0;
        for(int i=0;i<50;i++) if(num[i]>maxx)
        {
            maxx = num[i];
            ans=i;
        }
        return ans;
    }
};

1162. 地图分析

你现在手里有一份大小为 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。

示例 2：

输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4

解释：
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。

提示：
1 <= grid.length == grid[0].length <= 100
grid[i][j] 不是 0 就是 1

用bfs遍历所有陆地即grid为1的点，用vis记录是否为未被探索的海洋

每一层遍历前先用size()求出当前层节点的数量，以此为依据遍历，每遍历一层距离即ans加一。
要注意第一层是原陆地节点，ans应该为0，最后返回ans即可。

class Solution {
public:
    queue<pair<int, int>> q;
    int N,M;
    int ans = 0;
    int dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
    void bfs(vector<vector<int>> vis)
    {
        while (!q.empty())
        {
            int times = q.size();
            ans++;
            // cout<<"\ntimes:"<<ans<<" \n";
            for (int i = 0; i < times; ++i)
            {
                pair<int, int> p = q.front();
                q.pop();
                for (int j = 0; j < 4; ++j)
                {
                    int x = p.first + dir[j][0], y = p.second + dir[j][1];
                    if (x >= N || x < 0 || y >= N || y < 0) continue;
                    if (vis[x][y]) continue;
                    vis[x][y]=1;
                    // printf("x=%d y=%d \n",x,y);
                    q.push(make_pair(x, y));
                }
            }
        }
        ans--;
    }
    int maxDistance(vector<vector<int>>& grid)
    {
        N = grid.size();
        M = grid[0].size();
        vector<vector<int>> vis(N,vector<int>(M,0));
        for (int i=0;i<N;++i) for (int j=0;j<M;++j) if (grid[i][j] == 1) 
        {
            q.push(make_pair(i,j));
            vis[i][j]=1;
        }
        if (q.size() == N * M || q.size() == 0) return -1;
        bfs(vis);
        return ans;
    }
};

1163. 按字典序排在最后的子串

https://leetcode-cn.com/classic/problems/last-substring-in-lexicographical-order/description/

给你一个字符串 s，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

示例 1：
输入："abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。

示例 2：
输入："leetcode"
输出："tcode"

提示：
1 <= s.length <= 10^5
s 仅含有小写英文字符。

这题有个隐含条件，即返回的字符串必然一直到串s末尾。

用cnt保存各个字母在串s中的索引，ch记录当前遍历阶段的最大字母，

第一次对串s遍历后，判断是否只有一种字母或者最大字母只有一个，并分别返回不同字符串。

ans作为所求字符串，每次遍历目的为求下一位字母，遍历过程是对当前最大字母的所有索引做判断，把其下一位字母最大的那些索引记录下来作为下次判断的依据

虽然能过，但感觉其实有点问题，对于特别长的连续相同字母会做大量的无用for操作，最坏的情况下应该肯定是会时间超限的，应该单独做个对连续相同字符的处理

class Solution {
public:
    map<char, vector<int>> cnt;
    vector<int> cur;
    char ch = 'a';
    string findans(string s)
    {
        string ans = "";
        ans += ch;
        cur = cnt[ch];
        int len = s.length();
        while (cur.size() > 1)
        {
            map<char, vector<int>> tmp;
            ch='a';
            for (int i = 0; i < cur.size(); i++)
            {
                if(cur[i] == len - 1) continue;
                tmp[s[cur[i] + 1]].push_back(cur[i] + 1);
                ch = max(ch, s[cur[i] + 1]);
            }
            ans += ch;
            cur = tmp[ch];
        }
        if (cur.size() == 1) ans += s.substr(cur[0] + 1);
        return ans;
    }
    
    string lastSubstring(string s) 
    {
        if(s.length() == 0) return "";
        for (int i = 0; i < s.length(); i++)
        {
            if(s[i] > ch) ch = s[i];
             cnt[s[i]].push_back(i);
        }
        if(cnt.size() == 1) return s;
        if(cnt[ch].size() == 1) return s.substr(cnt[ch][0]);
        return findans(s);
    }
};