查询企业信息的官方网站,网站开发公司名单,ps素材网,网站怎么销售文章目录1. 比赛结果2. 题目LeetCode 5336. 上升下降字符串 easyLeetCode 5337. 每个元音包含偶数次的最长子字符串 mediumLeetCode 5338. 二叉树中的最长交错路径 mediumLeetCode 5339. 二叉搜索子树的最大键值和 hard1. 比赛结果
只做出来了第1题#xff0c;第3题有一个例子…
文章目录1. 比赛结果2. 题目LeetCode 5336. 上升下降字符串 easyLeetCode 5337. 每个元音包含偶数次的最长子字符串 mediumLeetCode 5338. 二叉树中的最长交错路径 mediumLeetCode 5339. 二叉搜索子树的最大键值和 hard1. 比赛结果
只做出来了第1题第3题有一个例子超时没解决
全国排名779 / 191340.7%全球排名2027 / 472942.8%
2. 题目
LeetCode 5336. 上升下降字符串 easy
题目链接
给你一个字符串 s 请你根据下面的算法重新构造字符串
从 s 中选出 最小 的字符将它 接在 结果字符串的后面。从 s 剩余字符中选出 最小 的字符且该字符比上一个添加的字符大将它 接在 结果字符串后面。重复步骤 2 直到你没法从 s 中选择字符。从 s 中选出 最大 的字符将它 接在 结果字符串的后面。从 s 剩余字符中选出 最大 的字符且该字符比上一个添加的字符小将它 接在 结果字符串后面。重复步骤 5 直到你没法从 s 中选择字符。重复步骤 1 到 6 直到 s 中所有字符都已经被选过。
在任何一步中如果最小或者最大字符不止一个 你可以选择其中任意一个并将其添加到结果字符串。
请你返回将 s 中字符重新排序后的 结果字符串 。
示例 1
输入s aaaabbbbcccc
输出abccbaabccba
解释第一轮的步骤 123 后结果字符串为 result abc
第一轮的步骤 456 后结果字符串为 result abccba
第一轮结束现在 s aabbcc 我们再次回到步骤 1
第二轮的步骤 123 后结果字符串为 result abccbaabc
第二轮的步骤 456 后结果字符串为 result abccbaabccba示例 2
输入s rat
输出art
解释单词 rat 在上述算法重排序以后变成 art示例 3
输入s leetcode
输出cdelotee示例 4
输入s ggggggg
输出ggggggg示例 5
输入s spo
输出ops提示
1 s.length 500
s 只包含小写英文字母。解答
一次遍历对字符进行计数正反遍历计数数组直到计数全部为0
class Solution {
public:string sortString(string s) {int m[26] {0}, sum 0, i;for(auto ch : s){m[ch-a];sum;}string ans;while(sum){for(i 0; i 26; i){if(m[i]){ans.push_back(ia);sum--;m[i]--;} }for(i 25; i 0; i--){if(m[i]){ans.push_back(ia);sum--;m[i]--;} }}return ans;}
};执行用时12 ms 内存消耗9.9 MB
LeetCode 5337. 每个元音包含偶数次的最长子字符串 medium
题目链接
给你一个字符串 s 请你返回满足以下条件的最长子字符串的长度每个元音字母即 ‘a’‘e’‘i’‘o’‘u’ 在子字符串中都恰好出现了偶数次。
示例 1
输入s eleetminicoworoep
输出13
解释最长子字符串是 leetminicowor 它包含 eio 各 2 个以及 0 个 au 。示例 2
输入s leetcodeisgreat
输出5
解释最长子字符串是 leetc 其中包含 2 个 e 。示例 3
输入s bcbcbc
输出6
解释这个示例中字符串 bcbcbc 本身就是最长的因为所有的元音 aeiou 都出现了 0 次。提示
1 s.length 5 x 10^5
s 只包含小写英文字母。解题
哈希map 记录所有元音字符的前缀异或值及当前位置当哈希表中可以查到该异或值时说明当前位置与查到的位置之间的子串是满足题意的
举个例子
qacaba初始没有元音前缀异或值0位置记为 -1m[0] -1 i 0没有元音前缀异或值00 存在maplen 0-(-1) 1最长“q” i 1出现元音a前缀异或值a位置 1m[a] 1 i 2没有元音前缀异或值alen 2-m[a] 1 i 3出现元音a前缀异或值a^a0len 3-m[0] 3-(-1) 4最长“qaca” i 4没有元音前缀异或值0len 4-m[0] 4-(-1)5最长“qacab” i 5出现元音a前缀异或值0^aalen 5-m[a] 5-1 4最长“caba”
所以最长的是5个字符qacab
class Solution {
public:int findTheLongestSubstring(string s) {unordered_mapint,int m; // 前缀异或值对应的位置int XOR 0, i, maxlen 0;m[0] -1; //没有元音位置为-1方便计算个数for(i 0; i s.size(); i) {if(s[i]!a s[i]!e s[i]!i s[i]!o s[i]!u){if(m.count(XOR))maxlen max(maxlen, i-m[XOR]);}else //s[i] 是元音{XOR ^ s[i];//元音异或值if(m.count(XOR))maxlen max(maxlen, i-m[XOR]);elsem[XOR] i;}}return maxlen;}
};or
class Solution {
public:int findTheLongestSubstring(string s) {unordered_mapint,int m; // 前缀异或值对应的位置int XOR 0, i, maxlen 0;m[0] -1; //没有元音位置为-1方便计算个数for(i 0; i s.size(); i) {if(s[i]a || s[i]e || s[i]i || s[i]o || s[i]u)XOR ^ s[i];//元音异或值 if(m.count(XOR))maxlen max(maxlen, i-m[XOR]);elsem[XOR] i;}return maxlen;}
};执行用时184 ms 内存消耗18.7 MB
LeetCode 5338. 二叉树中的最长交错路径 medium
题目链接
给你一棵以 root 为根的二叉树二叉树中的交错路径定义如下
选择二叉树中 任意 节点和一个方向左或者右。如果前进方向为右那么移动到当前节点的的右子节点否则移动到它的左子节点。改变前进方向左变右或者右变左。重复第二步和第三步直到你在树中无法继续移动。
交错路径的长度定义为访问过的节点数目 - 1单个节点的路径长度为 0 。
请你返回给定树中最长 交错路径 的长度。 来源力扣LeetCode 链接https://leetcode-cn.com/problems/longest-zigzag-path-in-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 解题
52 / 58 个通过测试用例 超时例子代码如下
class Solution {int ans 0;
public:int longestZigZag(TreeNode* root) {if(!root)return 0;dfs(root-left,0,0);dfs(root-right,0,1);longestZigZag(root-left);longestZigZag(root-right);return ans;}void dfs(TreeNode* root, int count, bool dir){if(!root){ans max(ans,count);return;}if(dirtrue)dfs(root-left,count1,!dir);elsedfs(root-right,count1,!dir);}
};原因主函数遍历了每个点重复走了很多次改在调用的时候遇到没变方向的直接count计数置为 0 继续向下走。
class Solution {int ans 0;
public:int longestZigZag(TreeNode* root) {if(!root)return 0;dfs(root-left,0,0);dfs(root-right,0,1);return ans;}void dfs(TreeNode* root, int count, bool dir){if(!root) {ans max(ans,count);return;}if(dir)//前一个是右节点{dfs(root-left,count1,0);dfs(root-right,0,1);}else//前一个是左节点{dfs(root-left,0,0);dfs(root-right,count1,1);}}
};LeetCode 5339. 二叉搜索子树的最大键值和 hard
题目链接
给你一棵以 root 为根的 二叉树 请你返回 任意 二叉搜索子树的最大键值和。
二叉搜索树的定义如下
任意节点的左子树中的键值都 小于 此节点的键值。任意节点的右子树中的键值都 大于 此节点的键值。任意节点的左子树和右子树都是二叉搜索树。 解题
参考大佬的解法
自底向上返回4个变量的 vector【0】是不是搜索树【1】左子树最小值【2】右子树最大值【3】子树val 的 sum空节点 返回 {true,INT_MAX,INT_MIN,0}获得左右子树的状态后开始判断都必须是搜索树左子树最大值小于 root右子树最小值 大于 root全部满足才是搜索树
class Solution {int maxSum 0;
public:int maxSumBST(TreeNode* root) {dfs(root);return maxSum;}vectorint dfs(TreeNode* root) {if(!root)return {true,INT_MAX,INT_MIN,0};//子树是不是二叉搜索树 vec[0]//子树的最小值 vec[1]//子树的最大值 vec[2]//子树的sum值 vec[3]auto Lstate dfs(root-left);auto Rstate dfs(root-right);if(!Lstate[0] || !Rstate[0] || Lstate[2] root-val || Rstate[1] root-val)return {false,INT_MAX,INT_MIN,0};//后三个参数随意//是二叉搜索树int Lmin root-left ? Lstate[1] : root-val;int Rmax root-right ? Rstate[2] : root-val;int cursum root-valLstate[3]Rstate[3];maxSum max(maxSum, cursum);return {true,Lmin,Rmax,cursum};}
};
