1.每个元音包含偶数次的最长子字符串
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
示例 1：
输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
示例 2：
输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
示例 3：
输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts
思路：前缀和＋状态压缩
首先题目中要求子字符串中每个元音字母恰好出现偶数次，我们就可以使用 0 和 1 来标识每个字母的状态(偶数次或奇数次)，我们不需要知道每个字母出现的完整次数，只需要知道这个次数的奇偶性
那么我们可以注意到奇数次 + 1 = 偶数次，偶数次 + 1 = 奇数次，所以我们可以使用 异或 来参与运算： 比如 aba
初始时 status = 00000，然后到 a 的时候 00000 ^ 00001 = 00001，1 说明 a 出现奇数次
然后到 b 的时候 00001 ^ 00010 = 00011，两个 1 说明 a、b 都出现奇数次
最后到 a 的时候 00011 ^ 00001 = 00010，说明只有 b 出现奇数次了。
以上也说明我们确实是可以使用状态码去标识每个元音字母出现次数的奇偶性。
那么我们怎么去统计最长子串的长度呢？
首先我们先盘盘哪些子串符合要求，因为现在每个下标对应的状态码其实也就只有 0 和 1
如果坐标 i 对应的状态码是 00011，坐标 j 对应的状态码是 00011，那么他们俩中间的元音字母数一定是偶数，如果某一位不相同，那么绝对不可能是偶数，因为偶数-奇数=奇数，奇数-偶数=奇数
所以我们每次求出一个坐标的状态码的时候就去瞅瞅这个状态码前面是否存在，如果存在，那么就计算一下之间子字符串的长度就 ok 了，那么我们还需要啥？明显需要一个hash表，存储每个状态码对应的下标！当然因为我们状态码最长也就是 11111 = 2^5 - 1 = 31，开一个 32 大小的数组就好了。
class Solution {
public:
int findTheLongestSubstring(string s) {
int len=s.length();
int ans=0;//存储结果
int status=0;//存储状态
vector<int> pos(32,-1);//哈希表，0-31一共32个状态
pos[0]=0;//这个要记录一下，防止没有元音的情况，也指初始状态
for(int i=0;i<len;i++)
{
if(s[i]=='a')
{
status^=1;
}
else if(s[i]=='e')
{
status^=1<<1;
}
else if(s[i]=='i')
{
status^=1<<2;
}
else if(s[i]=='o')
{
status^=1<<3;
}
else if(s[i]=='u')
{
status^=1<<4;
}//每出现一个元音字母，记录状态的改变
if(pos[status]!=-1)
{
ans=max(ans,i+1-pos[status]);//如果不为-1，说明之前有个这个状态，那么就计算长度
}
else
{
pos[status]=i+1;//之前此状态不存在，哈希表记录当前这个位置的下标
}
}
return ans;
}
};2.对称二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
return judge(pRoot,pRoot);
}
bool judge(TreeNode* pRoot1,TreeNode* pRoot2)
{
if(pRoot1==nullptr&&pRoot2==nullptr)
return true;//都遍历完了，说明对称
if(pRoot1==nullptr||pRoot2==nullptr)
return false;//有没遍历完的，不对称
if(pRoot1->val!=pRoot2->val)
return false;//值不相等，不对称
return judge(pRoot1->left,pRoot2->right)&&judge(pRoot1->right,pRoot2->left);//左和右比，右和左比
}
};3.之字形打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > res;
vector<int> v;
if(pRoot==nullptr) return res;
stack<TreeNode*> s[2];//两个堆栈
int cur=0;
int next=1;
s[cur].push(pRoot);//堆栈1放入根节点
while(!s[0].empty()||!s[1].empty())
{
TreeNode* p=s[cur].top();
v.push_back(s[cur].top()->val);
s[cur].pop();
if(cur==0)
{
if(p->left)
s[next].push(p->left);
if(p->right)
s[next].push(p->right);
}//如果cur为0，说明是下一层是偶数层，在next里从左到右放
else
{
if(p->right)
s[next].push(p->right);
if(p->left)
s[next].push(p->left);
}//如果cur为1，说明下一层是奇数层，在next里从右到左放
if(s[cur].empty())
{
res.push_back(v);
v.clear();
cur=1-cur;
next=1-next;
}//打印完一层，互换cur和next
}
return res;
}
};4.把二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> res;
vector<int> v;
if(pRoot==nullptr) return res;
queue<TreeNode* > q;
q.push(pRoot);
int num=1;//记录当前层节点数
int cur=0;//记录下一层节点数
while(!q.empty())
{
for(int i=0;i<num;i++)
{
TreeNode* p=q.front();
v.push_back(p->val);
q.pop();
if(p->left)
{
q.push(p->left);
cur++;
}
if(p->right)
{
q.push(p->right);
cur++;
}
}
res.push_back(v);
v.clear();
num=cur;
cur=0;
}
return res;
}
};
京公网安备 11010502036488号