网站排名易下拉刷词,账号注册免费,WordPress加载语言包,电子商务网站建设实训目的文章目录1. 比赛结果2. 题目1. LeetCode 5396. 连续字符 easy2. LeetCode 5397. 最简分数 medium3. LeetCode 5398. 统计二叉树中好节点的数目 medium4. LeetCode 5399. 数位成本和为目标值的最大数字 hard1. 比赛结果
做出来了 1、2、3 题#xff0c;19分钟做出来3题#x…
文章目录1. 比赛结果2. 题目1. LeetCode 5396. 连续字符 easy2. LeetCode 5397. 最简分数 medium3. LeetCode 5398. 统计二叉树中好节点的数目 medium4. LeetCode 5399. 数位成本和为目标值的最大数字 hard1. 比赛结果
做出来了 1、2、3 题19分钟做出来3题拼手速第4题回溯超时1把然后想到了是背包DP没写出来继续加油冲啊
全国排名363 / 197118.4%全球排名1291 / 779516.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;elsecount 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:vectorstring simplifiedFractions(int n) {unordered_setstring 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 vectorstring(ans.begin(),ans.end());}
};下面解法无需去重找最大公约数为1的情况
class Solution {
public:vectorstring simplifiedFractions(int n) {vectorstring ans;int i, k;for(i 1; i n; i)//分子for(k i1; 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 - 42 - 33 - 24 - 55 - 66 - 77 - 28 - 59 - 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] // 超时例子
10class Solution {vectorvectorint v;string path, ans0;int sum 0;int t;bool found false;
public:string largestNumber(vectorint cost, int target) {t target;for(int i 0; i 9; i)v.push_back({cost[i],i1});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();}}
};
