LeetCode 第 26 场双周赛（363/1971，前18.4%）数据结构与算法Michael是个半路程序员-

1. 比赛结果

做出来了 1、2、3 题，19分钟做出来3题（拼手速），第4题回溯超时1把，然后想到了是背包DP，没写出来，继续加油！冲啊！

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

2. 题目

1. LeetCode 5396. 连续字符 easy

题目链接
给你一个字符串 s ，字符串的「能量」定义为：只包含一种字符的最长非空子字符串的长度。

请你返回字符串的能量。

示例 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 <= 500 s 只包含小写英文字母。 

解答：

• 跟前一个比较，相等的话，计数+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

题目链接
给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。
分数可以以 任意 顺序返回。

示例 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<string> simplifiedFractions(int n) {      unordered_set<string> 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<string>(ans.begin(),ans.end()); } }; 

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

class Solution { public:     vector<string> simplifiedFractions(int n) {      vector<string> 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

题目链接
给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

「好节点」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

题目链接
给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：

• 给当前结果添加一个数位（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 == 9 1 <= cost[i] <= 5000 1 <= target <= 5000 

解题：
比赛回溯超时解：

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

class Solution {  vector<vector<int>> v;  string path, ans="0"; int sum = 0; int t; bool found = false; public:     string largestNumber(vector<int>& 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(); } } };