腾讯音乐笔试ak代码
第一题卡了比较久，其实只要每次变成计数为双数的字母就好，因为aa和aaa都只需要一步就可以变成无重复
int minOperations(string str)
{
int cnt[300]={0};
long long ans=0;
for(auto &c:str)
{
cnt[c]++;
}
while(true)
{
int maxVal=INT_MIN, v=-1;
for(int i='a';i<='z';i++)
{
if(maxVal<cnt[i])
{
maxVal=cnt[i];
v=i;
}
}
if(maxVal<=1)
break;
int u=-1;
for(int i='a';i<='z';i++)
{
if(cnt[i]%2==0)
{
u=i;
break;
}
}
if(u==-1)
u='a';
cnt[v]-=2;
cnt[u]++;
ans++;
}
return ans;
} unordered_map<TreeNode*, int> levs;
const int MOD=1e9+7;
int getLev(TreeNode *root)
{
if(root==nullptr)
return 0;
if(!levs.count(root))
{
levs.insert(make_pair(root, 1+max(getLev(root->left), getLev(root->right))));
}
return levs[root];
}
int DFS(TreeNode *root)
{
if(!root->left && !root->right)
return 1;
int leftLev=levs[root->left], rightLev=levs[root->right];
int maxChildSum=leftLev>rightLev?DFS(root->left):DFS(root->right);
return (2*maxChildSum+1)%MOD;
}
int getTreeSum(TreeNode* tree)
{
getLev(tree);
return DFS(tree);
} 第三题会建树就可以写，枚举所有可能的情况，纯看代码功底了
vector<TreeNode*> createTree(vector<int>& preOrder, vector<int>& inOrder, int pl, int ph, int il, int ih)
{
if(pl>ph)
return vector<TreeNode*>{nullptr};
vector<TreeNode*> res;
for(int idx=il;idx<=ih;idx++)
{
if(preOrder[pl]==inOrder[idx])
{
int leftNum=idx-il;
auto leftChilds=createTree(preOrder, inOrder, pl+1, pl+leftNum,il,idx-1);
auto rightChilds=createTree(preOrder, inOrder, pl+leftNum+1, ph,idx+1,ih);
for(auto &leftChild:leftChilds)
{
for(auto &rightChild:rightChilds)
{
auto p=new TreeNode(preOrder[pl]);
p->left=leftChild;
p->right=rightChild;
res.push_back(p);
}
}
}
}
return res;
}
vector<TreeNode*> getBinaryTrees(vector<int>& preOrder, vector<int>& inOrder)
{
int n=preOrder.size();
return createTree(preOrder, inOrder, 0, n-1, 0, n-1);
} 
