本文共 4302 字，大约阅读时间需要 14 分钟。

1. 比赛结果

全国排名：363 / 1971，18.4%；全球排名：1291 / 7795，16.6%

2. 题目

1. LeetCode 5396. 连续字符 easy

请你返回字符串的能量。

示例 1：输入：s = "leetcode"输出：2解释：子字符串 "ee" 长度为 2 ，只包含字符 'e' 。示例 2：输入：s = "abbcccddddeeeeedcba"输出：5解释：子字符串 "eeeee" 长度为 5 ，只包含字符 'e' 。示例 3：输入：s = "triplepillooooow"输出：5示例 4：输入：s = "hooraaaaaaaaaaay"输出：11示例 5：输入：s = "tourist"输出：1 提示：1 <= s.length <= 500s 只包含小写英文字母。

解答：

• 跟前一个比较，相等的话，计数+1，不等，计数置1
• 记录最大计数

class Solution {
   public:    int maxPower(string s) {
       	int i, count = 0, maxc = 0;    	char prev = '*';    	for(i = 0; i < s.size(); ++i)    	{
       		if(prev == s[i])    			count++;    		else    			count = 1;    		maxc = max(count, maxc);    		prev = s[i];    	}    	return maxc;    }};

2. LeetCode 5397. 最简分数 medium

示例 1：输入：n = 2输出：["1/2"]解释："1/2" 是唯一一个分母小于等于 2 的最简分数。示例 2：输入：n = 3输出：["1/2","1/3","2/3"]示例 3：输入：n = 4输出：["1/2","1/3","1/4","2/3","3/4"]解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。示例 4：输入：n = 1输出：[] 提示：1 <= n <= 100

解题：

• 求最大公约数，化简分子分母，遍历所有可能，插入set

class Solution {
   public:    vector
   
     simplifiedFractions(int n) {
       	unordered_set
    
      ans;    	int i, k, g, u, d;    	for(k = 2; k <= n; ++k)	    	for(i = 1; i < k; ++i)	    	{
   	    		g = __gcd(i,k);	    		u = i/g;	    		d = k/g;	    		ans.insert(to_string(u)+"/"+to_string(d));	    	}    	return vector
     
      (ans.begin(),ans.end());    }};
     
    
   

下面解法，无需去重，找最大公约数为1的情况

class Solution {
   public:    vector
   
     simplifiedFractions(int n) {
       	vector
    
      ans;    	int i, k;        for(i = 1; i < n; ++i)//分子    	    for(k = i+1; k <= n; ++k)//分母 > 分子	    	{
   	    		if(__gcd(i,k)==1)	    		    ans.push_back(to_string(i)+"/"+to_string(k));	    	}    	return ans;    }};
    
   

3. LeetCode 5398. 统计二叉树中好节点的数目 medium

「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。

示例 1：

输入：root = [3,1,4,3,null,1,5]输出：4解释：图中蓝色节点为好节点。根节点 (3) 永远是个好节点。节点 4 -> (3,4) 是路径中的最大值。节点 5 -> (3,4,5) 是路径中的最大值。节点 3 -> (3,1,3) 是路径中的最大值。

示例 2：

输入：root = [3,3,null,4,2]输出：3解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。示例 3：输入：root = [1]输出：1解释：根节点是好节点。 提示：二叉树中节点数目范围是 [1, 10^5] 。每个节点权值的范围是 [-10^4, 10^4] 。

解答：

• 简单的二叉树遍历，带一个最大值递归更新

class Solution {
   	int count = 0;public:    int goodNodes(TreeNode* root) {
           dfs(root, root->val);        return count;    }    void dfs(TreeNode* root, int maxv)    {
       	if(!root) return;    	if(root->val >= maxv)    		count++;    	maxv = max(maxv, root->val);//更新最大值    	dfs(root->left, maxv);    	dfs(root->right,maxv);    }};

4. LeetCode 5399. 数位成本和为目标值的最大数字 hard

• 给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
• 总成本必须恰好等于 target 。
• 添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 “0” 。

示例 1：输入：cost = [4,3,2,5,6,7,2,5,5], target = 9输出："7772"解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "997" 也是满足要求的数字，但 "7772" 是较大的数字。 数字     成本  1  ->   4  2  ->   3  3  ->   2  4  ->   5  5  ->   6  6  ->   7  7  ->   2  8  ->   5  9  ->   5  示例 2：输入：cost = [7,6,5,5,5,6,8,7,8], target = 12输出："85"解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。示例 3：输入：cost = [2,4,6,2,4,6,4,4,4], target = 5输出："0"解释：总成本是 target 的条件下，无法生成任何整数。示例 4：输入：cost = [6,10,15,40,40,40,40,40,40], target = 47输出："32211" 提示：cost.length == 91 <= cost[i] <= 50001 <= target <= 5000

解题：

[1,1,1,1,1,1,1,3,2] // 超时例子10

class Solution {
   	vector
   
    
     > v;	string path, ans="0";	int sum = 0;	int t;	bool found = false;public:    string largestNumber(vector
     
      & cost, int target) {
       	t = target;    	for(int i = 0; i < 9; ++i)    		v.push_back({
   cost[i],i+1});    	sort(v.begin(),v.end(),[](auto a, auto b){
       		if(a[0]==b[0]) return a[1] > b[1];    		return a[0] < b[0];    	});    	dfs();    	sort(ans.begin(),ans.end(),[](auto a, auto b){
       		return a > b;    	});    	return ans;    }    void dfs()    {
       	if(sum > t)    		return;    	if(sum == t)    	{
       		if(path.size() > ans.size() ||     			(path.size() == ans.size() && path > ans))    			ans = path;    		return;    	}    	for(int i = 0; i < 9; ++i)    	{
       		sum += v[i][0];    		path += v[i][1]+'0';    		dfs();    		sum -= v[i][0];    		path.pop_back();    	}    }};
     
    
   

转载地址：https://michael.blog.csdn.net/article/details/106167968 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！