文章目录
- 1. 比赛结果
- 2. 题目
- 1. LeetCode 5396. 连续字符 easy
- 2. LeetCode 5397. 最简分数 medium
- 3. LeetCode 5398. 统计二叉树中好节点的数目 medium
- 4. LeetCode 5399. 数位成本和为目标值的最大数字 hard
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();
}
}
};
